유혁스쿨

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 예산 각 지방에서 신청한 예산안 들이 있는데, 국가의 총 예산을 넘지 않는 선에서 수용 가능한 최대 상한가를 구하라는 문제이다. 예산의 상한가가 정해지면, 요청된 예산이 상한가보다 크거나 같을 경우 상한가 만큼만 지급하고, 상한값보다 작으면 신청된 예산값만 지급한다. 각 지방에서 신청한 예산 액이 있고, 이 예산액의 총 합이 국가에서 지정한 총예산값을 넘기면 안된다. 특정 상한값을 정하고 상한값보다 큰 경우 상한값 만큼만 제공한다. 상한값을 찾아내는것이 문제의 핵심이다. 이진탐색 주어진 데이터에서 내가 원하는 특정 데이터를 찾아내는것을 `탐색` 이라고 한다. 가장 단순한 방법은 모든 경우의 수 0에서부터 최대값 사이..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 정렬 여러개의 정수가 주어지는데, 이 정수들의 숫자를 이어붙혀 만들 수 있는 수중 가장 큰 숫자를 구한다. 6, 10 2 세개의 숫자가 주어졌다고 가정, 이때 가능한 조합은 6가지가 나온다. 그중 가장 큰 수는 6210이 된다. 핵심은 배열의 모든 요소를 사용하는 경우의 수를 모두 구하고 그중 가장 큰 값을 구하는것이며, 이때 함정은 한자릿수 두자리수 한자릿수 합치면 4자리밖에 되지 않지만 만약 배열이 3자리수 10개로 구성된다면 총 30자리의 숫자가 만들어 진다. 이는 integer의 범위가 넘어간다. double을 사용한다고 하더라도 배열이 조금만 길어진다고 하더라도 범위를 넘어가므로 Long을 사용해야 한다. ..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 탐욕법 현재(초기) 위치에서부터 모든 아파트를 순회한다. 현재 위치가 전파범위에 속하는지 확인하고 전파 범위가 아니라면 일단 기지국을 세운다. 이때, 전파 범위의 효과가 최대가 되도록 전파 유효범위 만큼 이동하여 기지국을 설치한다. 전파가 끝나는 지점 이후부터 한칸씩 이동하면서 기지국을 설치한다. 설치 도중, 만약 이미 세워진 기지국의 점파범위 안으로 들어갈 경우 일단 해당 위치에도 설치한다. 다음 위치로 이동했는데, 이미 설치되어있는 기지국의 전파범위에 포함된다면 기지국의 범위 바깥으로 이동한다. 벗어난 뒤 계속해서 마지막 아파트까지 같은 작업을 반복한다. [풀이 1] Queue사용 import java.util...

모든 알고리즘 문제들은 완전탐색을 이용해도 정답 도출이 가능하지만 비효율적인 연산과 시간을 생략하고 답을 효율적으로 도출하기 위해 여러 알고리즘을 사용한다. 동적계획법 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써, 최종적으로 복잡한 문제의 답을 구하는 방법이다. 핵심이론 원리와 구현 방식 큰 문제를 작은(부분) 문제로 나눌 수 있어야 함 작은(부분) 문제들이 반복돼 나타나고 사용되며 그들의 결괏값은 항상 같아야함 모든 작은(부분) 문제들은 한번만 계산해 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) 최단거리 배열 초기화 최단거리 배열 ..