코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 배열, 벡터, 리스트, 덱 등의 선형 구조에서는 순방향과 역방향으로 원소를 순회할 수 있다. 하지만 다음과 같은 문제는 선형 구조로 표현할 수 없다. 계층적 문제: 회사의 조직도, 대학의 교과 과정 계층도 순환 종속성 문제: SNS의 친구 관계, 도시의 도로망 트리(Tree) 계층적 문제를 표현할 수 있는 자료 구조이다. 데이터가 저장되는 노드(Node)와 노드 사이를 잇는 간선(Edge)으로 표현된다. 자식(Child) 노드에 대한 참조를 가지며 부모(Parent) 노드에 대한 참조도 가질 수 있다. 그래프(Graph) 순환 종속성 문제를 표현할 수 있는 자료 구조이다. 데이터가 저장되는 정점(Vertex)과 정점 사이를 잇는 간선(Edge)으로..

Level 0. 순서쌍의 개수 n이 제곱근의 제곱인 경우를 처음에 더해준다. 1 ~ n까지 모두 순회할 필요 없이 제곱근보다 작은 수까지만 확인하고 한 번에 2씩 더해주면 된다. #include #include using namespace std; int solution(int n) { float square_root = sqrt(n); int answer = (pow(square_root, 2) == n); for (int i = 1; i < square_root; ++i) answer += !(n % i) * 2; return answer; }

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ std::priority_queue STL에서 제공하는 우선순위 큐 컨테이너 어댑터이다. 기본적으로 std::vector가 컨테이너로 사용된다. 기본 비교자로 std::less가 사용되며, 가장 큰 수가 가장 위에서 높은 우선 순위를 갖는 최대 힙(Max Heap)을 생성한다. std::greater를 사용하면 가장 작은 수가 가장 높은 우선 순위를 갖는 최소 힙(Min Heap)이 생성된다. 순회할 필요가 없으므로 반복자를 제공하지 않는다. Root 이외의 원소는 접근할 수 없다. std::priority_queue의 성능 최대 힙에서 최대 원소, 최소 힙에서 최소 원소에 대한 접근은 O(1)에 수행된다. 원소의 삽입은 상향식 재구성(Bottom..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ std::queue STL에서 제공하는 큐 컨테이너 어댑터이다. 기본적으로 std::deque가 컨테이너로 사용된다. 선입선출(FIFO) 구조를 갖는다. 순회할 필요가 없으므로 반복자를 제공하지 않는다. Front와 Rear에서 원소에 접근할 수 있다. std::queue의 성능 모든 연산은 O(1) 시간에 수행된다. #include #include using namespace std; void main() { queue que; // 1, 2, 3 Push que.emplace(1); que.emplace(2); que.emplace(3); // Pop que.pop(); cout

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ std::stack STL에서 제공하는 스택 컨테이너 어댑터이다. 기본적으로 std::deque가 컨테이너로 사용된다. 후입선출(LIFO) 구조를 갖는다. 순회할 필요가 없으므로 반복자를 제공하지 않는다. Top 이외의 원소는 접근할 수 없다. std::stack의 성능 모든 연산은 O(1) 시간에 수행된다. #include #include using namespace std; void main() { stack stck; // 1, 2, 3 Push stck.emplace(1); stck.emplace(2); stck.emplace(3); // Pop stck.pop(); cout

Level 0. 삼각형의 완성조건 (2) 길이의 최솟값부터 최댓값까지의 개수이다. 자 2개를 맞대어 돌린다고 생각하면 쉽다. #include #include using namespace std; int solution(vector sides) { return (sides[0] + sides[1]) - abs(sides[0] - sides[1]) - 1; }