kjp0411 님의 블로그

기하 알고리즘은 점, 선, 다각형, 원과 같이 각종 기하학적 도형을 다루는 알고리즘입니다.코딩 테스트에서 기하 알고리즘은 모두 CCW라는 기하학적 성질을 이용해 풀 수 있습니다. 기하의 핵심 이론CCW는 평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘입니다.세 점을 A(X1, Y1), B(X2, Y2), C(X3, Y3)라고 가정했을 때 CCW 공식은 다음과 같습니다. CCW 공식CCW = (X1Y2 + X2Y3 + X3Y1) - (X2Y1 + X3Y2 + X1Y3) CCW 결과 CCW 결과 == 0: 일직선CCW 결과 > 0: 반시계 방향|CCW 결과|: 세 점으로 이루어진 두 백터의 외적값|CCW 결과| / 2: 세 점으로 이루어진 삼각형의 넓이

동적 계획법은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻합니다. 동적 계획법의 핵심 이론동적 계획법으로 풀 수 있는지 확인하기점화식 세우기메모이제이션 원리 이해하기TOP - DOWN 구현 방식 이해하기BOTTOM - UP 구현 방식 이해하기동적 계획법의 원리와 구현 방식큰 문제를 작은 문제로 나눌 수 있어야 한다.작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다.동적 계획법은 TOP - DOWN 방식과 BOTTOM - UP 방식으로 구현할 수 있다.동적 계획법의 가장 대표적인 문제인 피..

최소 공통 조상은 트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드입니다. 최소 공통 조상의 핵심 이론일반적인 최소 공통 조상 구하기1. 먼저 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장합니다.(탐색은 DFS 또는 BFS를 이용해 수행합니다.) 2. 선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드를 부모 노드로 1개씩 올려 주면서 같은 깊이로 맞춥니다.(두 노드가 같으면 해당 노드가 최소 공통 조상이므로 탐색을 종료합니다.) 3. 깊이가 같은 상태에서는 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복합니다.(처음 만나는 노드가 최소 공통 조상이 됩니다.) 위..

주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해 낸 자료구조 형태가 세그먼트 트리입니다. 세그먼트 트리의 핵심 이론세그먼트 트리의 종류는 구간 합, 최대·최소 구하기로 나눌 수 있습니다.구현 단계는 트리 초기화하기, 질의값 구하기(구간 합, 최대·최소 구하기), 데이터 업데이트하기로 나눌 수 있습니다. 1. 트리 초기화하기리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 리스트를 만듭니다.트리 리스트의 크기를 구하는 방법은 2^k >= N을 만족하는 k의 최솟값을 구한 후 2^k * 2를 트리 리스트의 크기로 정의합니다. 2. 질의값 구하기3. 데이터 업데이트하기

이진 트리는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성되어 있는 트리입니다.트리의 영역에서 가장 많이 사용되는 형태입니다. 이진 트리의 핵심 이론이진 트리의 종류이진 트리에는 편향 이진 트리, 포화 이진 트리, 완전 이진 트리가 있습니다.편향 이진 트리: 노드들이 한쪽으로 편향돼 생성된 이진트리포화 이진 트리: 트리의 높이가 모두 일정하며 리프 노드가 꽉 찬 이진 트리완전 이진 트리: 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리데이터를 트리 자료구조에 저장할 때 편향 이진 트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 많이 낭비됩니다.일반적으로 코딩 테스트에서 트리에 담는다고 하면 완전 이진 트리 형태를 떠올리면 됩니다. 이진 트리의 순차 표..

트리는 노드와 엣지로 연결된 그래프의 특수한 형태입니다. 트리의 특징순환 구조(사이클)를 지니지 있지 않고, 1개의 루트 노드가 존재합니다.루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖습니다.트리의 부분 트리 역시 트리의 모든 특징을 따릅니다.구성 요소설명노드데이터의 index와 value를 표현하는 요소엣지노드와 노드의 연결 관계를 나타내는 선루트 노드트리에서 가장 상위에 존재하는 노드부모 노드두 노드 사이의 관계에서 상위 노드에 해당하는 노드자식 노드두 노드 사이의 관계에서 하위 노드에 해당하는 노드리프 노드트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)서브 트리전체 트리에 속한 작은 노드 트라이는 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조입니다. 트라이..

최소 신장 트리는 그래프에서 모든 노드를 연결할 때 사용된 엣지들의 가중치의 합을 최소로 하는 트리입니다. 최소 신장 트리의 특징사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.N개의 노드가 있으면 최소 신장 트리를 구성하는 엣지의 개수는 항상 N - 1개이다.최소 신장 트리의 핵심 이론1. 엣지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화하기(최소 신장 트리는 데이터를 노드가 아닌 엣지 중심으로 저장하므로 인접 리스트가 아닌 엣지 리스트 형태로 저장)(이 리스트는 일반적으로 노드 변수 2개와 가중치 변수로 구성)(사이클 처리를 위한 유니온 파인드 리스트도 함께 초기화)(리스트의 인덱스로 해당 자리의 값을 초기화) 2. 그래프 데이터를 가중치 기준으로 정렬하기(..

벨만 포드 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘입니다.기능특징시간 복잡도(노드 수: V, 엣지 수: E)특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색음수 가중치 엣지가 있어도 수행할 수 있음전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음O(VE) 벨만 포드 알고리즘의 핵심 이론1. 엣지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기(벨만 포드 알고리즘은 엣지를 중심으로 동작하므로 그래프를 엣지 리스트로 구현합니다.)(최단 경로 리스트의 출발 노드는 0, 나머지 노드는 무한대로 초기화)2. 모든 엣지를 확인해 정답 리스트 업데이트하기(최단 거리 리스트에서 업데이트 반복 횟수는 노드 개수 - 1이다.)(노드의 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 ..

다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘입니다.기능특징시간 복잡도(노드 수: V, 엣지 수: E)출발 노드와 모든 노드간의 최단 거리 탐색엣지는 모두 양수O(ElogV) 특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 다익스트라 알고리즘을 사용하면 문제를 해결할 수 있습니다. 다익스트라 알고리즘의 핵심 이론1. 인접리스트로 그래프 구현하기(인접 행렬로 구현해도 좋지만 시간 복잡도 측면과 N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것이 좋습니다.)2. 최단 거리 리스트 초기화하기최단 거리 리스트를 만들고, 출발 노드는 0, 이외에 노드는 무한으로 초기화합니다.(이때 무한은 적당히 큰 값을 사용하면 됩니다.)3. 값이 가장 작은 노드 고르기최단 거리 ..