유혁스쿨

모든 알고리즘 문제들은 완전탐색을 이용해도 정답 도출이 가능하지만 비효율적인 연산과 시간을 생략하고 답을 효율적으로 도출하기 위해 여러 알고리즘을 사용한다. 동적계획법 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써, 최종적으로 복잡한 문제의 답을 구하는 방법이다. 핵심이론 원리와 구현 방식 큰 문제를 작은(부분) 문제로 나눌 수 있어야 함 작은(부분) 문제들이 반복돼 나타나고 사용되며 그들의 결괏값은 항상 같아야함 모든 작은(부분) 문제들은 한번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP테이블을 이용 이를 메모이제이션 이라고 함(시간복잡도 측면에서 유리) DP는 탑-다운, 바텀-업 방식으로 구현가능함 대표문제 피보나치수열 D[N] = D[N-1] + D[N..

조합 Combination ₙCᵣ 로 표현하고, 이는 n개의 숫자에서 r개의를 뽑는 경우의 수를 뜻한다. 조합과 비교되는 순열은 ₙPᵣ 로 표현되고 n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수로 말한다. 순열과 조합의 차이는 순서 고려 유무이다. 즉, 조합에서는 데이터 1, 2, 3과 3, 2,1을 동일한 경우로 판단하고 순열은 다른 경우로 판단한다. 일반적으로 코딩테스트의 핵심 알고리즘은 아래와 같다 그래프 DP (동적계획법) 인덱스트리 조합은 동적계획법(DP)를 이해하는데 기초가되는 알고리즘으로 코딩테스트에 자주 출제된다. 순열과 조합의 핵심이론 순열 순열의 수학적 공식 ₙPᵣ = n! / (n-r)! 예를들어 데이터 5개 중 2개를 순서대로 선택하는 경우의 수를 구한다고 가정한다. ..

① 서로의 깊이를 맞추거나, ②같아지는 노드를 찾을 때, 기존 한단계씩 올려주는 방식에서 2ᵏ씩 올라가 비교하는 방식 → 기존 자신의 부모노드만 저장해 놓던 방식에서 2ᵏ 번째 위치의 부모노드까지 저장해 둬야한다. (미리 배열로 저장해야 탐색이 가능하다.) Step 01) 부모노드 저장 배열 만들기 점화식 활용 부모노드 배열 정의 P[K][N] = N번 노드의 2ᵏ 번째 부모의 노드번호 → P[2][13] = 노드 13의 2² 번째 부모노드 점화식 (동적계획법) P[K][N] = P[K-1][ P[K-1][N] ] → P[2][13] = P[1][ P[1][13] ] 점화식에서 N의 2ᵏ 번째 부모노드는 N의 2ᵏ⁻¹번째 부모노드의 2ᵏ⁻¹번째 라는 의미 즉, k=4라고 가정한다면 K의 16번째 부모노드..

최소공통조상이란? 트리 그래프에서 임의의 두 노드를 선택했을 때, 선택한 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모노드를 탐색할 때 처음 공통으로 만나게되는 부모노드를 말한다. 핵심이론 트리의 높이가 크지 않을 때(시간복잡도 ↓)의 예시 ex) 노드4, 노드5의 LCA → 루트노드에서 탐색을 시작해 각 노드의 부모노드와 깊이를 배열에 저장한다. (여기서 탐색은 DFS 혹은 BFS 알고리즘을 사용) index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 부모노드 0 1 1 2 2 3 3 4 4 6 6 7 7 11 11 깊이 1 2 2 3 3 3 3 4 4 4 4 4 4 5 5 Step 01) 깊이가 다를경우 만약 선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드의 노드를 부..

세그먼트(인덱스)트리 주어진 데이터의 구간 합(합배열)과 데이터 업데이트를 빠르게 수행하기 위해 고안해 낸 자료구조의 형태 더 큰 범위로 '인덱스 트리' 라고 불리며 이는 코딩테스트 영역에서 큰 차이가 없음. 구간합이 있는데 왜 세그먼트 트리를 학습하여 사용하는가? 합배열의 가장 큰 문제점은 특정 데이터 업데이트시 굉장히 느리다. 만약 1번 인덱스 값 5를 10으로 변경한다면 나머지 모든 구간에 5를 더해줘야 한다. 인덱스 0 1 2 3 4 5 6 데이터 3 5 4 2 3 7 4 합배열 S 3 8 12 14 17 24 28 index 4의 구간합인 17은 index 0 ~ 4까지의 데이터의 합이다. 합배열로는 S[4]로 표현하며 S[4] = S[3] + A[4] 라는 공식이 성립된다. 중간 영역인 ind..

이진 트리 각 노드의 자식의 갯수(차수)가 2 이하로 구성된 트리 트리는 기본적으로 그래프의 표현과 일차원 배열 표현으로 나뉜다. 그래프의 표현으로는 인접리스트를 활용한 BFS, DFS탐색 알고리즘 유형이 있으며 1차원 배열 표현으로는 인덱스 트리와 LCA 유형이 있다. 이진트리는 1차원 배열로 표현하는 인덱스 트리, LCA라고 볼 수 있다. 종류 편향 이진 트리 포화 이진 트리 완전 이진 트리 노드들이 한쪽으로 편향 돼 생성됨 트리의 높이 모두 일정, 리프노드가 꽉참 마지막 레벨 제외하고 노드들이 완전하게 채워짐, 마지막 레벨은 왼쪽부터 채워짐 ⓐ ／ ⓑ ／ ⓒ ／ ⓓ ／ ⓔ ⓐ ∧ ⓑ ⓒ ∧ ∧ ⓓ ⓔⓕ ⓖ ⓐ ∧ ⓑ ⓒ ∧ ⓓ ⓔ 편향 이진 트리에 저장시 탐색속도 저하 및 많은 공간이 낭비된다. 따..

트리 (Tree) 노드와 엣지로 연결된 그래프의 특수한 형태 → 그래프의 표현으로도 Tree를 표현할 수 있다. 순환 구조(Cycle)을 지니지 않고, 1개의 루트 노드가 존재한다. 루트노드를 제외한 노드는 단 1개의 부모노드를 가진다. 트리의 부분트리(SubTree) 역시 트리의 모든 특징을 따른다. 연결된 트리에서 임의의 두 노드를 이어주는 경로는 유일하다. Tree 구성요소 전체 트리 서브트리 ⓐ ← 루트 노드 (부모) ∧ ← 엣지 ⓑ ⓒ ←자식 노드 ∧ ⓓ ⓔ ⓑ ←부모 노드 ∧ ⓓ ⓔ ←리프노드 구성요소 설명 노드 데이터의 index와 value를 표현하는 요소 ] 그래프와 유사 엣지 노드와 노드의 연결 관계를 나타내는 선 루트노드 트리에서 가장 상위에 존재하는 노드 ⓐ 부모노드 두 노드 사이의..

최소신장트리(MST) 그래프에서 모든 노드를 연결할 때 사용된 엣지들의 가중치의 합을 최소로 하는 트리 알고리즘 종류 크루스칼 프림 주요 특징 사이클이 포함되면 가주치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다. N개의 노드가 있으면 최소 신장 트리를 구성하는 엣지의 갯수는 항상 N-1개 이다. [그래프] ８ ５ ① ─ ② ─ ⑤ │3 │ 4／2 ③ ─ ④ 13 [엣지리스트] 엣지 ① ② ③ ④ ⑤ ⑥ 노드1 null null null null null null 노드2 null null null null null null 가중치 null null null null null null [유니온파인드리스트] ① ② ③ ④ ⑤ ⑥ null null null null null null Step 01)..

플로이드-워셜 그래프에서 최단거리 구하는 알고리즘 3개(다익스트라, 벨만포드, 플로이드-워셜) 중 1개 기능 특징 시간복잡도(노드수 : V) 모든 노드 간(V³인 이유) 최단경로 탐색 음수 가중치 엣지가 있어도 수행 가능 (단, 음수사이클 x) 동적 계획법 원리를 이용해 알고리즘에 접근 O(V³) (V = 100 / 200 , 1000) (3중 for문으로 코드구성이 간단하기 때문에 쉽게 암기할 수 있음.) A노드에서 B노드 까지 최단 경로를 구했다고 가정했을 때 최단경로 위에 K노드가 존재한다면 그것을 이루는 부분경로 역시 최단경로를 의미한다. 플로이드-워셜 점화식 D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) K는 S부터 E까지 도달하는데 위치한 노드이다. S부터..

벨만포드 그래프에서 최단거리를 구하는 알고리즘 기능 특징 시간복잡도 (노드수:V, 엣지수:E) 특정 노드에서 다른 노드까지의 최단경로를 탐색한다. 음수 가중치 엣지가 있어도 수행 가능 전체 그래프에서 음수 사이클 존재 여부 판단 가능 O(VE) 3단계 `그래프`, `엣지리스트`, `최단거리 리스트` 를 활용하여 최단거리를 구한다. [그래프] ８ ５ ① → ② → ⑤ ↓3 ↑-4↙-2 ③ → ④ ７ [엣지리스트] edge 1 2 3 4 5 6 출발노드 null null null null null null 종료노드 null null null null null null 가중치 null null null null null null [정답(최단거리) 리스트] 1 2 3 4 5 null null null null ..

다익스트라 그래프에서 최단 거리를 구하는 알고리즘 기능 특징 (제약조건) 시간 복잡도 (노드 수: V, 엣지 수:E) 출발 노드와 모든 노드간의 최단 거리 탐색 엣지는 모두 양수 O(ElogV) 핵심이론 5단계로 구현한다 [그래프] ８ 15 ① → ② → ⑤ ↓3 ↓4 ↗2 ③ → ④ 13 Step 01) 인접 리스트로 그래프 구현 ① → [ ②, 8 ] [ ③, 3 ] ② → [ ④, 4 ] [ ⑤, 15 ] ③ → [ ④, 13 ] ④ → [ ⑤, 2 ] ⑤ 그래프 데이터를 자료구조 ArrayList 에 저장한다 다익스트라 알고리즘은 인접 행렬로 구현해도 좋으나 시간복잡도 측면 N의 크기가 클 것을 대비해 인접리스트를 선택하여 구현하는 것이 좋다. Step 02) 최단거리 배열 초기화 최단거리 배열 ..

위상정렬 사이클이 없는 방향에서 노드 순서를 갖는 정렬 기능 특징 시간복잡도 (노드수: V, 엣지수: E) 노드간 순서 결정 사이클이 없어야 함 O(V+E) 항상 유일한 값으로 정렬되지 않음 사이클 존재시 노드간 순서를 명확하게 정의 불가 (위상정렬 적용 불가) 핵심 이론 인접리스트 , 진입차수배열 , 위상정렬배열 세가지를 구현한다. 1. 그래프를 인접리스트로 구현 2. 구현된 인접리스트의 진입차수를 계산하여 진입차수 배열에 저장 3. 진입차수배열에서 진입차수가 0인 노드 선택 4. 선택된 노드 위상정렬 배열에 저장 5. 저장된 노드가 가리키는 노드들의 진입차수를 -1 연산 후 저장(선택) 된 노드의 다음노드를 진입차수 배열에서 다시 선택 6. 3 ~ 5 과정을 반복하며 모든 노드가 정렬될 경우 종료 [..

유니온 파인드 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find연산으로 구성되어 있는 알고리즘 (엄밀히 말하면 그래프 영역이라고 보기에 약간 무리가 있으나 실제로 그래프 문제에서 부분 알고리즘으로 많이 사용됨) find연산이란? 자신의 대표 노드를 찾아주는 연산 핵심이론 union, find 연산을 완벽히 이해하는 것 UNION : 각 노드가 속한 집합을 1개로 합치는 연산 → 노드 a, b가 a ∈ A, b ∈ B일 때 UNION(a,b) 는 A ∪ B를 말함 FIND : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산 → 노드 a가 a ∈ A일 때 find(a)는 A집합의 대표노드를 반환 (대..

그래프의 표현 그래프를 표현할때는 대표적으로 엣지리스트, 인접행렬, 인접리스트 3가지 방법으로 표현한다. 그래프 예 ① → ② → ⑤ ↓ ↓ ↗ ③ → ④ 엣지리스트 엣지를 중심으로 그래프를 표현한다. 배열에 출발,도착 노드를 각각 저장하여 엣지를 표현한다. 가중치가 있는 노드의 경우 배열에 가중치를 추가 행으로 함께 저장한다. 가중치 없는 그래프 표현 출발, 도착 2개의 노드만 2개의 배열행을 구성하여 표현한다. ex) 첫번째 행을 [1, 2]로 표현하며 1에서 2로 뻗어가는 엣지를 뜻한다. ⓢ ⓔ 1 2 1 3 3 4 2 4 2 5 4 5 이처럼 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 표현한다. 노드를 배열에 저장하여 엣지를 표현하므로 엣지리스트 라고 한다. 방향이 없는 그..