똑똑한망치의 성장일기

동적 계획법은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻한다. 동적 계획법의 핵심 이론1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 사용한다. 이를 메모이제이션 기법이라고 한다.4. 동적 계획법은 탑-다운 방식과 바텀-업 방식으로 구현할 수 있다. 동적 계획법의 가장 대표적인 문제인 피보나치 수열의 예D[N] = D[N-1] + D[N-2]  동적 계획법 문제 풀이 과정동적 계획법으로 풀 수 있는지 확인하기점화식 세우기메모이제이션 ..

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

최소 신장 트리(MST) 란?그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다. 특징사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N - 1 개이다. ※ 절대적이지 않지만,간선이 적으면 KRUSKAL, 간선이 많으면 PRIM 알고리즘이 유리 (1) Kruskal MST 알고리즘(간선을 고르는 간선 중심) 핵심 이론1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기데이터를 노드가 아닌 에지 중심으로 저장하므로 에지 리스트의 형태로 저장한다.사이클 처리를 위한 유니온 파인드 배열도 함께 초기화한다. 배열의 인덱스를 해당 자리의 값으로 초기화하면 된다.2. ..

위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 기능특징시간 복잡도(V : 노드 수, E: 엣지 수)노드 간의 순서를 결정사이클이 없어야 함O(V + E)  위상 정렬의 핵심 이론 1. 진입 차수 이해하기진입 차수(in-degree)는 자기 자신을 가리키는 에지의 개수이다.  이 때, 진입 차수 배열 D[N]은 아래와 같다.1234501122  2. 진입 차수 배열 D[N]에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다. 그 후, 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다. 위 그림의 경우 진입 차수가 0인 노드 1을 선택하여 2, 3의 진입 차수를 1씩 빼 D[2], D[3]을 0으로 만든 것이다. 계속해서 다음 노드 2..

유니온 파인드 알고리즘이란?💡 상호 배타적 집합, Disjoin-set(서로소 집합) 이라고도 부른다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어 주고, 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다. 왜 이름이 유니온 파인드 인가?유니온 파인드 알고리즘은 두 가지의 연산을 진행한다. 이 연산 과정을 Union, Find 라고 한다.Union : 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 연산이다, 즉 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산을 말한다. 이 연산은 합집합 연산과 같다.Find : 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산이다.크루스칼 알고리즘과 프림 알고리즘을 알기 위해서는 유니온 파인드 알고리..

최단 경로 알고리즘정점으로부터 정점까지의 모든 경로 중에서 가장 비용이 작은 경로 (1) Dijkstra(정점을 고르는 정점 중심)출발 정점으로부터 다른 모든 정점까지의 거리를 선택된 정점을 지나서 가는 경우와 직접 가는 경우 중 최솟값을 갱신해가면서 가장 가까운 정점을 하나씩 선택된 정점에 편입시켜가며 최단 경로를 갱신음의 가중치를 허용하지 않음기능특징시간 복잡도(노드 수 : V, 에지 수 : E)출발 노드와 모든 노드간의 최단 거리 탐색에지는 모두 양수O(ElogV)public class Dijkstra_Test { static class Edge implements Comparable { int v, weight; public Edge(int v, int weigh..

유클리드 호제법은 두 수의 최대 공약수를 구하는 알고리즘 입니다.  유클리드 호제법의 핵심 이론유클리드 호제법을 수행하려면 먼저 MOD 연산을 이해하고 있어야 한다. MOD 연산이 최대 공약수를 구하는데 사용되는 핵심 연산이기 때문이다.연산기능예제MOD두 값을 나눈 나머지를 구하는 연산10 MOD 4 = 2 // 10 % 4 = 2 MOD 연산으로 구현하는 유클리드 호제법큰 수를 작은 수로 나누는 MOD 연산을 수행한다.앞 단계에서 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행한다.2단계를 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.

오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 오일러 피의 핵심 이론구하고자 하는 오일러 피의 범위만큼 자기 자신의 인덱스값으로 초기화한다.2부터 시작해 현재 배열의 값과 인덱스가 같으면(= 소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열에 끝까지 탐색하며 P[i] = P[i] - P[i] / K 연산을 수행한다. (i는 K의 배수)배열의 끝까지 2번 과정을 반복하여 오일러 피 함수를 완성한다.서로소란?두 수 사이의 관계에서 공통되는 약수가 최대 1이며 1밖에 없는 수를 뜻한다.

너비 우선 탐색 BFS는 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다. 기능특징시간 복잡도 (노드 수 : V, 에지 수: E)그래프 완전 탐색FIFO 탐색Queue 자료구조 이용O(V+E)  너비 우선 탐색의 핵심 이론1. BFS를 시작할 노드를 정한 후 사용할 자료 구조 초기화하기2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기3. 큐 자료구조에 값이 없을 때까지 반복하기

깊이 우선 탐색 (DFS)은 그래프 완전 탐색 기법 중 하나이다.깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 기능특징시간 복잡도(노드 수: V, 엣지 수: E)그래프 완전 탐색재귀 함수로 구현스택 자료구조 이용O(V+E) 깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로(stack overflow)에 유의해야 한다.깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다. 깊이 우선 탐색 DFS의 핵심 이론DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는..