👩🏻‍💻 은진의 로그파일 ✍️

👩🏻‍💻문제설명 [이코테 Ch8-5] 효율적인 화폐 구성 (DP) N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 회폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다. 입력 조건 첫째 줄에 N, M이 주어진다. (1

👩🏻‍💻문제설명 [이코테 Ch7-2] 부품 찾기 (이진 탐색) 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N=5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다. M=3 [5, 7, 9] 이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력..

👩🏻‍💻문제설명 [이코테 Ch6-4] 두 배열의 원소 교체 (정렬) 동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K 번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야한다. N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K 번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하라. 예를 들어 N = 5, K = 3이고, 배열 A와 B가 ..

👩🏻‍💻문제설명 [이코테 Ch5-4] 미로탈출 (BFS) N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력 첫째 줄에 두 정수 N, M(4

👩🏻‍💻문제설명 [이코테 Ch4-1] 상하좌우 (구현) 여행가 A는 N × N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 × 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다. 계획서에는 하나의 줄에 띄어쓰기를 기준으로 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 각 문자의 의미는 다음과 같다. L: 왼쪽으로 한 칸 이동 R: 오른쪽으로 한 칸 이동 U: 위로 한 칸 이동 D: 아래로 한 칸 이동 이때 여행가 A가 N × N 크기의 정사각형 공간..

👩🏻‍💻문제설명 [이코테 Ch3-4] 1이 될 때까지 (그리디) 어떠한 수 N이 1이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. 1. N에서 1을 뺀다. 2. N을 K로 나눈다. (N이 K로 나누어떨어질 때만 선택가능) 예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이경우 전체과정을 실행한 횟수는 3이된다. 이는 N을 1로 만드는 최소 횟수이다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성하시오. 입력조건 첫째줄에 ..

멀티 태스킹 (다중 작업 운영체제) 동시에 2개 이상의 프로그램을 수행하는 다중 작업 운영체제를 말한다. OS 스케줄링과 CPU 시분할을 통해 다수의 프로세스를 전환하는 멀티 프로그래밍을 통해 멀티 태스킹을 구현했다. 멀티 프로그래밍 (다중 프로그래밍 시스템) 프로세서란? 프로세스가 동작하도록 하는 하드웨어(= CPU) 프로그램이란? 어떤 작업을 위해 운영체제 위에서 실행할 수 있는 파일 프로세스란? 운영체제 위에서 실행 중인 프로그램 하나의 CPU가 2개 이상의 프로그램을 전환한다. CPU가 유휴 상태일 때 실행 중인 둘 이상의 프로세스가 CPU를 전환하여 사용할 수 있도록 동작한다. (Context switching) 즉, 여러 프로그램을 메모리에 적재한 후 하나의 프로세스가 CPU를 사용하다가, 입..

Buckets (Hash Table)는 O(1)로 탐색시간이 빠르다 Hash 함수는 입력 값(keys)이 들어오면 언제나 같은 출력 값(Hash 값)을 가짐 buckets의 index 값으로 매핑되어 찾고자 하는 데이터를 얻을 수 있음 미리 저장된 메모리 공간(buckets)에 한 번에 접근을 하기 때문에, 탐색 시간이 O(1)로 빠름 Hash 값이 충돌이 일어나는 등의 최악의 경우, O(N)이 될 수도 있음 탐색시간이 빠른 Hash가 인덱스로 적절하지 않은 이유 단 하나의 데이터를 탐색하는 시간이 O(1)으로 빠른 것이다. Hash Table에 저장되는 값들은 정렬되어 있지 않기 때문에 특정 값보다 크거나 작은 값을 찾을 수 없다. SQL 쿼리문에서 특정 범위의 값을 조회하는 경우, 특정 값보다 크거나..

WEB-WAS-DB의 전형적인 3티어 구조 -> 사용자가 늘어나면 DB에 슬슬 무리가 가기 시작 매 transaction 마다 디스크에 접근해야하기 때문에 부하가 많아지면 상당히 느려짐 사용자가 늘어나면 DB만으로는 부하를 견딜 수 없어 캐시서버 도입 캐시 한 번 읽어온 데이터를 임의의 공간에 저장하여 다음에 읽을 때는 빠르게 결과값을 받을 수 있도록 도와주는 공간 같은 요청이 여러번 들어오는 경우 캐시서버에서 바로 결과값을 반환 DB부하를 줄일 수 있음, 서비스의 개선 cache Hit 클라이언트가 웹서버에 요청 웹서버는 데이터를 DB에서 가져오기 전에 Cache에 데이터가 있는지 확인 Cache서버에 데이터가 있으면, 데이터를 DB에 데이터를 요청하지 않고 바로 클라이언트에 데이터를 반환 cache ..

비정규화(Unnormalized form) : 정규화된 테이블(릴레이션)을 읽기성능 향상을 위해 테이블을 다시 합치는 방법 역정규화(Denormalization) : 정규화된 테이블을 비정규화 상태로 만들기 위한 방법 중 하나 (비정규화가 더 포괄적) 역정규화를 하는 이유 읽기작업이 많이 필요한 테이블의 읽기성능 향상을 위해서 비정규화 상태로 만드는 역정규화 프로세스 데이터베이스의 완벽한 구조설계를 포기하고 데이터의 무결성을 떨어트리는 대신 관계형 데이터베이스의 읽기(Read)성능 향상을 위한 설계 방법 정규화를 통해 분리되었던 릴레이션에서 중복을 허용하고 다시 통합하거나 분할하여 구조를 재조정하는 과정 정규화된 릴레이션의 성능 저하 요인 1. JOIN 연산 정규화된 테이블에서는 3가지 테이블을 같은 키..