동적 계획법(Dynamic Programming)은 코딩 테스트를 준비하는 사람이라면 반드시 알고 있어야 할 알고리즘 기법이다. 더 작은 size의 문제를 푼다. 푼 문제의 해답을 저장해두고, 필요할 때마다 가져다 쓴다. 이를 이용해 더 큰 문제의 해답을 도출한다. DP 로 줄여서 부르며, 1차원 배열, 딕셔너리, 트리 등 다양한 형태를 이용하여 기록하지만 가장 많이 쓰는 형태는...
C++ STL의 unordered_set은 중복되지 않는 원소들을 저장하는 해시 기반 컨테이너이다. 다만, 이름 그대로 순서를 보장하지는 않는다. 주요 특징 중복된 원소는 저장되지 않는다. 예를 들어, 같은 값을 두 번 넣으려고 하면 두 번째 삽입은 무시된다. 순서가 없다. 즉, 컨테이너의 원소들은 정렬되지 않는다. 내부적으로 해시 테이블을 사용해 평균 O(1) 시간에 삽입, 삭제,...
C++ STL의 set은 중복되지 않는 원소들을 정렬된 상태로 저장하는 자료구조이다. 주요 특징 중복된 원소는 저장되지 않는다. 예를 들어, 같은 값을 두 번 넣으려고 하면 두 번째 삽입은 무시된다. 원소들은 자동으로 오름차순 정렬된다. (기본 비교 함수: std::less) 내부는 Red-Black Tree로 구현되어 있다. 삽입, 삭제, 탐색 모두 평균 O(logn) 인덱스 접근이 불가능하며...
에라토스테네스의 체는 소수를 효율적으로 찾기 위한 알고리즘이다. 1부터 N까지의 자연수 중에서 소수를 찾고 싶을 때, 다음과 같은 과정을 통해 구한다. 알고리즘 2부터 N까지의 모든 정수를 나열한다. 2는 소수이므로 제외하고, 2의 배수를 모두 지운다. 남아있는 수 중에서 가장 작은 수(3)는 소수이므로 제외하고, 3의 배수를 모두 지운다. 이 과정을 √N까지 반복하면, 남아...
C++ STL의 list는 이중 연결 리스트(doubly linked list)를 구현한 컨테이너이다. 기본 개념 std::list는 이중 연결 리스트를 기반으로 하며, 각 노드는 이전 노드와 다음 노드를 가리키는 포인터를 가지고 있어 리스트 내에서 양방향으로 이동이 가능하다는 특징이 있다. 빠른 삽입/삭제 (O(1)) list의 가장 큰 장점은 임의 위치에서의 삽입과 삭제가 매우 빠르다는 점이다. 예를...