algorithm/basis (13) 썸네일형 리스트형 다이나믹 프로그래밍[Dynamic Programming] 문제풀이-2 (10문제) 11048 이동하기 https://www.acmicpc.net/problem/11048 문제의 특징 1. 시작-> 도착 2. 이동방향 3가지 3. 양의 정수 이동할수록 문제의 크기가 작아진다. 위나, 왼쪽으로 이동 못하므로 -> 항상 문제가 작아지므로 다이나믹 프로그래밍이라고 알 수 있다. 풀이 1 O(NM) = NxMx1 D[i][j] = (i, j)로 이동할 때 가져올 수 있는 최대 사탕 개수 D[i][j] = Max(D[i-1][j-1], D[i][j-1], D[i-1][j]) + maps[i][j]; for(int y=1; y> w; for (int i = 1; i maps[i][j]; for (int y = 1; y w) return 0; if (dist[y][x] >= 0) return dis.. 알고리즘 문제풀이 메모장 보호되어 있는 글입니다. 트리(Tree) 트리 : 사이클이 없는 그래프, 정점의 개수 : V, 간선의 개수 : V-1 루트가 있는 그래프 : 루트를 1번이라고 하며, 루트부터 아래로 방향을 정할 수 있다. 부모(Parent) 자식(Children) 단말 정점(Leaf Node, Terminal Node) : 자식이 없는 노드 형제(sibling) : 같은 부모를 가지는 노드 깊이(Depth) : 루트에서 부터 거리(루트의 깊이는 0 or 1로 표기가능) 높이(Height) : 깊이중 가장 큰값 조상(Ancestor) : 자기자신을 포함하여 루트와 이어지는 노드 자손(Descendent) : 조상과 반대 트리의 지름(Diamater) : 트리에 존재하는 모든 경로 중에서 가장 긴 것의 길이 - 2번의 탐색으로 구할 수 있다. - 1. 루트에서 모.. 그래프(Graph) 그래프(Graph) : 정의 구성 : 정점(Vertex), 간선(Edge) G = (V, E) 경로(Path) 사이클(Cycle) 단순 경로와 단순 사이클(Simple Path and Simple Cycle) : 경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클(일반적인 경우) 방향 있는 그래프(Directed Graph) 방향 없는 그래프(Undirected Graph,) : 양방향 그래프(Bidirection Graph) 간선 여러개(Multiple Edge) 루프(Loop) 가중치(Weight) 차수(Degree) 연결요소(Connected Component) 이분그래프(Bipartite Graph) : DFS또는 BFS 탐색으로 이분 그래프인지 아닌지 확인가능 플러드 필(Floo.. 정렬(Sorting), Stable_Sorting youtu.be/kPRA0W1kECg 정렬 알고리즘을 소리로 표현한 영상이다. 정렬 방법은 30가지가 넘는 여러가지가 있다., 정렬 알고리즘의 종류로는 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 힙 정렬, 병합 정렬, ...... 등 여러가지가 있지만, 알고리즘 문제풀이에서 주로 사용하는 것들은 정렬시간이 O(NlogN)이 걸리는 정렬을 사용한다. 정렬을 직접 구현하는 것보다는 STL에 있는 sort를 사용하는 것이 좋다. 수학 1. 나머지 연산 2. 최대공약수와 최소공배수 3. 소수 4. 에라토스테네스의 체 5. 골든바흐의 추측 6. 관련문제 수학문제 복습! 1. 나머지 연산(Modular Arithmetic) 컴퓨터의 정수는 저장할 수 있는 범위가 저장되어 있기 때문에, 답을 M으로 나눈 나머지를 출력하라는 문제가 등장한다. 더보기 예를 들어, 다이나믹 문제를 풀때 경우의 수가 너무 큰경우 int값이나 long 값을 넘어서, 값을 처리를 하기 위해서 큰 정수값(big integer)을 구현하기 보다는 몇으로 나눈 나머지를 처리하라는 문제가 많다. (A+B) mod M = ((A mod M) + (B mod M)) mod M (AXB) mod M = ((A mod M) X (B mod M)) mod M 나누기의 경우에는 성립하.. 다이나믹 프로그래밍[Dynamic Programming] 연습하기 좋은 문제 및 풀이 다이나믹 프로그래밍[Dynamic Programming] 연습하기 좋은 문제 및 풀이 알고리즘 문제풀이에서 벡터의 사용은 매우 좋은것 같다. 알고리즘을 간략하고 이해하기 쉽게 표현할 수 있다. 예를들어 d배열에서 최댓값을 찾는 등을 한줄로 표현할 수 있다. cout temp) ret = temp; } if (n % 2 == 0) { temp = go(n / 2) + 1; if (ret > temp) ret = temp; } db[n] = ret; return ret; } int main(void) { int x; int cnt=0; cin >> x; cout > x; for (int i = 2; i n; db[1] = 1; db[2] = 2; for (int i = 3; i n; db[1] = 1; db.. 다이나믹 프로그래밍[Dynamic Programming] 1. 다이나믹 프로그래밍이란? 2. 다이나믹 프로그래밍의 속성 3. 다이나믹 문제 푸는 방법 4. 다이나믹 문제 풀이 전략 5. 다이나믹 프로그래밍 문제 1. 다이나믹 프로그래밍이란? 다이나믹 프로그래밍 :Dynamic Programming 큰 문제를 작은 문제를 나눠서 푸는 알고리즘 1940년대 수학자인 Richard Bellman은 'Dynamic Programming'이란 용어를 사용했다. 그는 프로세스가 다단계로 이루어져 있으며, 시가변적(time-varing)이며, '동적(Dynamic)'이다라는 개념(idea)이 전달되길 원했다. 큰 문제 안에 작은 문제가 중첩되어있는 문제를 해결하는 데 사용하는 계획법(Programming)인것이다. 2. 다이나믹 프로그래밍의 속성 알고리즘 측면에서 다이나믹.. 이전 1 2 다음
