고오급 개발자가 되는길

위상 정렬 (Topological Sort) - 정점들을 위상에 맞춰 정렬 • DAG (Directed Acyclic Graph) Directed = 간선에 방향성이 있다 Acyclic : 싸이클이 없다 Graph = 정점 + 간선 Indegree : 자신(정점) 에 들어오는 개수 (차수) Outdegeree : 자신에서 나가는 간선의 개수(차수) 제일 먼저 올 수 있는 정점은? => 들어오는 간선이 없는 정점 정리 1. 정점들의 Indegree, Indeg[1...N] 계산하기 2. 들어오는 간선이 0개인 (indeg[i] ==0) 정점들을 찾아서 자료구조 D에 넣기 3. D가 빌 떄 까지 1. D에서 원소 X를 꺼내서 정렬 시키기 2. Graph 에서 정점 X 제거하기 3. 새롭게 정렬 가능한 점을 ..

트리 (Tree) - 그래프의 특수한 형태 - V + E + 특성 특성 1. - 모두가 연결되어 있는 그래프 - 어떤 두 점을 골라도 간선을 타고 사이를 이동 가능 특정 2. - 사이클이 존재하지 않음 특성 3. - 정점 개수 v = 간선 개수 e + 1 특성중 2가지를 만족하면 트리로 문제 풀이 Rooted Tree란? 1. Node 2. Root 3. Depth 4. Parent, Child, Ancestor(조상),Sibling(형제, 같은 부모를 갖는 관계) 5. Leaf Node (자식이 없는 노드) - 모든 두 정점 사이에 이들을 잇는 경로가 존재하면서 사이클이 존재하지 않는 경우 - 마을과 마을 사이를 직접 잇는 N-1 개의 길이 있으며, 모든 마을은 연결되어있다 (1,3 만족) 트리는 인접..

그래프와 탐색 그래프란? - 자료구조로써 그래프 = 정점 (Vertex) + 간선 (Edge) • 간선 (Edge) : 무방향 / 방향 을 나타내는 선, 가중치를 가질수도 있다 - degree = 정점 x의 차수, 정점 x에 연결된 간선의 수 모든 정점의 차수의 합 = 간선의 개수의 2배 그래프를 저장하는 대표적인 두 가지 방법 1. 인접 행렬 (Adjacency Matrix) - 그래프를 2차원 배열로 표현하는 방법 => 0이면 두 정점을 연결하지 않는다, 1이면 두 정점이 연결 되어있다 - int[][] adj = int new[V][V]; - O(V^2) 만큼의 공간 필요, 하지만 실제로 1인 대상은 얼마 없으므로 공간 낭비 - A와 B를 잇는 간선 존재 여부 확인 문제에서 사용 2. 인접 리스트 ..

투 포인터 응용 List of Unique Numbers (BOJ 13144) 난이도 4 - 수열에서 연속한 1개 이상의 수를 뽑았을 떄 같은 수가 여러번 등장하지 않는 경우의 수 정답의 최대치 구현 static int N; static int[] A, cnt; static void pro() { long ans = 0; for (int L=1, R=0; L

두 포인터(Two Pointer) - 화살표 두개의 의미를 부여해서 탐색 범위를 압축하는 방법 1. 1차원 배열 위에 2개의 포인터를 만드는 경우 -1) 2개의 포인터가 모두 왼쪽에서 시작해서 같은 방향으로 이동 - 오른쪽 포인터가 먼저 이동하고 왼쪽이 따라감 -2) 2개의 포인터가 양 끝에서 서로를 향해 이동 -1)↓↓ ↓ ↓ ↓ ↓ 0 1 2 3 4 5 67 7 8 9 10 11 18 19 38 58 72 87 92 66 -2) → ← → ← - 1차원 배열에서의 "연속 부분 수열" or "순서를 지키며 차례대로" - 곱의 최소 부분 합 (백준 1806) - 접근 • 가장 쉬운 방법 O(N^2) 1. 왼쪽 시작 L결정 => O(N) 2. 오른쪽 끝을 R을 L로부터 시작해서 이동 => O(N) 3. 총..

이분 탐색 응용편 매개 변수 탐색 (Parametric Search) 1. 정답을 매개변수(Parameter) 로 만들고 Yes/No 문제(결정문제) 로 바꾸기 2. 모든 값에 대해서 Yes/No 를 채웠다고 생각했을 떄, 정렬된 상태인지 확인 3. Yes/No 결정하는 문제를 풀기 => 문제를 거꾸로 푸는것이기 때문에 통찰력을 요구, 많은 훈련이 필요함 자주하는 실수 1. 매개 변수에 대한 결정이 No/Yes 꼴이 아닌데 이분 탐색 하는 경우 2. L, R, M Result 변수의 정의를 헷갈려 부등호 등을 잘못 쓰는 경우 3. L,R 범위를 잘못 설정하거나 Result의 초기값을 잘못 설정하는 경우! 어떠한 경우에 매개변수 탐색을 쓰는것이 좋은가 - ~의 최대값을 구하시오 - ~의 최솟값을 구하시오 ..

이분 탐색(Binary Search) - 정렬이 보장되는 배열에서 기준 x를 가지고 범위를 이분하면서 탐색하는 방법 오름차순이 정렬이된 배열의 특성 - 임의의 M번 인덱스에 있는 배열 A의 A[M]이 기준 X 보다 크다면 A[M...N]은 전부 x 보다 크다. - 임의의 M번 인덱스에 있는 배열 A의 A[M]이 기준 X 보다 작다면 A[1...M]은 전부 x 보다 작다. L : 탐색할 가치가 있는 범위의 왼쪽 끝 인덱스 R : 탐색할 가치가 있는 범위의 오른쪽 끝 인덱스 Result : 탐색한 X의 위치 탐색 목표 : X이하의 원소 중에 가장 오른쪽에 있는 원소 자주하는 실수 1. 입력된 배열에 바로 이분탐색을 하는데, 정렬을 하지 않는 경우 2. L, R, M, Result 변수의 정의를 헷갈려서 부등..

다양한 정렬 응용편(Sort Application) 수열정렬 - N개의원소가P배열에 써있는 값으로 이동하여 B라는 배열을 만듬 static class Elem implements Comparable { public int num, idx; @Override public int compareTo(Elem other) { return num - other.num; } } } static int N; static int[] P; static Elem[] B; static void pro() { Arrays.sort(B); for (int i = 0; i < N; i++) { P[B[i].idx] = i; } for (int i = 0; i < N; i++) { sb.append(P[i]).append(' ')..

다양한 정렬 응용법 정렬이란? - 오름차순이면 크기가 작은것부터 점점 큰 순으로 정렬 - 내림차순이면 크기가 큰것부터 점점 작은 순으로 정렬 1. 정렬 조건이 필요 - 오름차순 이라면 크기가 제일 작은것을 앞으로 이동 시켜야 한다 2. N개의 원소를 정렬하는 것은 O(N logN) 만큼의 시간 복잡도를 가짐 • JAVA의 Arrays.sort(arr) Privitive 원소 정렬 EX) int,double... Object 원소 정렬 Dual-Pivot Quick Sort Tim Sort 최선 시간 복잡도 : O(N) 최선 시간 복잡도 : O(N) 최악 시간 복잡도 : O(N^2) 최악 시간 복잡도 : O(NlogN) 평균 시간 복잡도 : O(N logN) 평균 시간 복잡도 : O(N logN) 3. I..

완전탐색 - 총정리 - 문제를 풀 떄 항상 정답의 최대치를 파악하라! 연산자 끼워넣기 풀이 import java.io.*; import java.util.*; public class Main { static FastReader scan = new FastReader(); static StringBuilder sb = new StringBuilder(); static void input() { N = scan.nextInt(); nums = new int[N + 1]; operators = new int[5]; for (int i = 1; i