코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 맵리듀스 대규모 데이터셋을 생성하고 처리하기 위한 프로그래밍 모델 및 구현이다. (키, 값) 쌍을 처리해 중간 단계의 (키, 값) 쌍을 생성하는 Map 모든 중간 단계 키에 해당하는 값을 병합하는 Reduce 맵리듀스의 실제 사용 예 하둡(Hadoop) Map 연산의 예 컨테이너의 모든 원소에 f(x)를 적용하는 연산이다. f(x) = x² void map_example(vector S) { auto Fx = [](int& x) { x = pow(x, 2); }; for_each(S.begin(), S.end(), Fx); } Reduce 연산의 예 컨테이너의 모든 원소에 f(acc, x)를 적용하여 하나의 값으로 축약하는 연산이다. f(acc, ..
코딩 테스트를 위한 자료 구조와 알고리즘 with C++ binary_search() 시퀀스(정렬된 상태)에서 이진 검색을 수행한다. #include #include #include using namespace std; void main() { vector v{1, 2, 3, 4, 5, 4, 3, 2, 1}; sort(v.begin(), v.end()); if (binary_search(v.begin(), v.end(), 3)) cout
코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 병합 정렬 분할-정복-결합 과정을 거치는 분할 정복 알고리즘이다. 전체 데이터의 일부를 가져와 정렬한 후 외부에 다시 저장하는 외부 정렬(External Sorting) 알고리즘이다. O(nlog n) 복잡도를 갖는다. 병합 정렬 과정 분할: 부분 집합의 크기가 1이 될 때까지 분할한다. 정복: 나눠진 부분 집합을 오름차순이 되도록 다시 결합한다. 결합: 기존 집합의 크기와 같아질 때까지 2. 정복부터 반복한다. #include #include using namespace std; template vector merge(vector& v1, vector& v2) { vector m; auto it1 = v1.begin(); auto it2 = v2..
코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 이진 검색 분할 정복 알고리즘의 하나이다. 시퀀스(정렬된 상태)에서 검색 범위를 2배씩 줄여나가며 검색한다. O(log n) 복잡도를 갖는다. 재귀를 이용하면 쉽게 구현할 수 있다. 이진 검색 과정 시작 F, 끝 L의 전체 시퀀스를 범위로 잡는다. 가운데 원소 M을 정한다. M이 찾는 원소이면 끝낸다. F와 L이 같은 경우 찾지 못 한 상태로 끝낸다. 찾는 원소가 M보다 작으면 끝 L을 M - 1로 설정하고, M보다 크면 시작 F를 M + 1로 설정한다. 2부터 다시 반복한다. 선형 검색과 이진 검색의 성능 비교 #include #include #include #include #include using namespace std; bool linea..
코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 분할 정복 분할: 문제를 작은 부문제로 나눈다. 정복: 나눠진 각 부문제의 솔루션을 구한다. 결합: 각 부문제의 솔루션을 합쳐 전체 문제의 솔루션을 구한다. 일반적인 경우, 재귀를 사용하면 좀 더 쉽게 나타낼 수 있다. 분할 정복의 예시 이진 검색 병합 정렬 퀵 정렬 행렬 곱셈 ...
코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 알고리즘 정해진 입력을 받아 변환하고 일련의 명령을 수행하여 결과를 출력하는 솔루션 효율적인 알고리즘 연산 횟수를 입력 크기 N에 대한 다항식으로 나타낼 수 있다면 효율적이다. 문제의 종류 Class P (Polynomial Time, 다항 시간): 복잡도를 다항식으로 나타낼 수 있는 문제 Class NP (Non-Deterministic Polynomial Time, 비결정적 다항 시간): 다항 시간 내에 해결할 수는 있지만 정해진 다항식이 존재하지 않는 문제 Class EXPTIME (Exponential Time, 지수 시간): 복잡도를 지수 함수 형태로 나타낼 수 있는 문제 Class PSPACE (Polynomial Space, 다항 공간..