할머니의 콤퓨타 도전기

분할 정복 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산, 각 부분 문제의 답으로 부터 전체 문제의 답을 계산 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나눔 일반 재귀 호출은 항상 문제를 한 조각과 나머지로 쪼개는 방식 분할 정복법은 항상 문제를 절반씩 나누는 분할 정복 알고리즘 구성 요소 문제를 더 작은 문제로 분할 (Divide) 각 문제에 대한 구한 답을 원래 문제에 대한 답으로 병합 (Merge) 더 이상 답을 분할하지 않고 바로 풀 수 있는 매우 작은 문제 (Base Case) 특성 문제를 둘 이상의 부분으로 나누는 자연스러운 방법이 있어야 함..

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아감 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 가는 것 (가지치기) 일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요하므로 처리가 불가능할 수 있음. 따라서 가지치기를 얼마나 잘하느냐에 따라 효율성 결정 즉 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것 주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에..

그리디(Greedy) 알고리즘은 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘 대표적으로 거스름돈 문제가 있는데, 단순하게 큰 경우 부터 찾는 알고리즘과 같이 간단하게 탐욕적으로 문제를 해결하는 기법 기본적으로 무조건 큰 경우대로, 무조건 작은 경우대로, 무조건 긴 경우대로, 무조건 짧은 경우대로 등으로 극단적으로 문제를 접근한다는 점에서 정렬 기법이 함께 사용되는 경우가 많음. 최적해에 가까운 값을 구하기 위해 사용 그리디를 통해 구한 결과값이 항상 최적해인게 아님 여러 경우 중 하나를 결정할 때마다, 매순간 최적이라 생각하는 경우를 선택하여 최종 결과값을 구함 반드시 최적해가 보장되는 것이 아니기 때문에 근사치 추정에 활용

큐 한쪽 끝(rear)에서는 삽입 연산만 이루어지며 다른 한쪽 끝(front)에서는 삭제 연산만 이루어지는 유한 순서 리스트 먼저 삽입된 item이 먼저 삭제가 이루어짐 (FIFO, First In First Out) 큐의 표현 순차 표현 1차원 배열 이용 front, rear를 -1로 초기화 하여 큐가 empty임을 표시 (front == rear일 때 큐는 공백) rear에서 삽입되므로 rear가 점차 증가하여 rear == n-1인 경우 큐는 full front에서 삭제가 일어났다면 그 만큼 공간이 비어있음. 따라서 큐에 원소가 꽉차있지 않아도 full 따라서 full이 되었을 때는 첫 원소 위치를 큐의 0번 인덱스부터 위치되게 하고 rear의 위치도 다시 계산 큐 원소 이동에 따른 지연시간 발생 ..

스택 가장 늦게 들어간 자료가 가장 먼저 나가는 구조 (LIFO, Last In First Out) 한 쪽 끝에서만 자료를 넣고 뺄 수 있다 스택의 가장 위를 top, 삽입과 삭제가 top에서 일어남 스택 연산 push(): 스택에 새로운 원소를 삽입 pop(): 스택의 top 원소를 제거하고 반환 empty() : 스택이 비어있는지 검사 size() : 스택의 크기

std::map은 key와 value를 갖는 데이터 구조 std::map은 key 값에 따라서 정렬되지만, std::unordered_map은 hash_map과 동일하게 내부적으로 key 값에 의해 정렬되지 않는다. std::unordered_map의 장점은 빠른 탐색속도 n개의 데이터 쌍을 갖는 std::map의 경우 O(logN)의 탐색 속도를 갖는 반면, std::unordered_map은 O(1)의 탐색 속도 map map은 기본적으로 red-black tree 기반 따라서 모든 데이터는 key 값을 기준으로 정렬 map의 경우 입력되는 key 값의 분포가 고르지 못할 경우 balancing에 대한 비용이 계속 들어가기 때문에 성능 저하 탐색 속도 O(logN)은 보장 unordered_map h..