본문 바로가기

알고리즘

 (160)
최단경로 알고리즘 노드와 노드를 이어주는 간선의 어떤 값을 부여한 것을 간선의 가중치(weight)라고 한다.최단경로 문제는 어떤 노드부터 노드까지 가는 경로의 가중치의 최솟값을 구하는 문제이다. 위의 경로대로 A부터 B까지 가면 1+1+1+2+9 = 14 가 경로의 가중치를 모두 합한 값이다.하지만 이것은 최단경로가 아니므로 그래프에서 최단경로를 구해보면 12로 다음와 같다. 기초 최단경로 알고리즘은 세가지가 있는데, 특징은 위와 같다.플로이드 알고리즘은 모든 정점에서 모든 정점까지 최단거리를 구하지만, 그만큼 시간이 많이걸린다.다익스트라와 벨만포드 알고리즘의 차이점은 가중치의 음수값이 있느냐 없느냐에 따라 나뉜다. 최단경로 문제를 풀 때 중요한 특징은 2가지가 있는데첫번 째는 X까지 최단거리로 가기 위해서는 그 직전의..
넓이우선탐색 (Breadth First Search) BFS는 DFS와 다르게 Queue를 이용하여 그래프를 순회하는 방법이다. 제일 먼저시작하는 노드를 큐에 push하고 색칠한 후에 시작한다. 그 다음에① pop 하는 노드에서 인접한 노드들을 큐에 넣고 색칠한다.② 더이상 넣을 노드들이 없다면 큐에서 pop을 한다.이런식으로 동작한다. 예를 들어 설명해보자. 위에 그림에서 1에서부터 시작하므로1을 큐에 넣고 방문했다고 색칠한다. 1을 pop하고 나면, 이제 1에 인접한 노드들을 확인 한다. 즉 2와 4를 push 하고 방문했다고 색칠한다.현재 큐 상태는 1이 pop되어 있는 상태이고, 큐에 2와 4가 들어가있다.이제 1에 인접한 모든 노드 2와 4를 큐에 넣었으므로 더이상 넣을 노드가 없다.그러므로 현재 큐에서 pop을 해보면 front에 있는 2가 po..
깊이우선탐색 (Depth First Search) DFS는 자기가 방문했던 자취를 기억하는 스택의 특징을 이용하여 인적한 노드부터 차례대로 그래프를 순회하는 방법이다. 주어진 그래프에서 1부터 DFS를 한다고 예시를 들어보자. 여기에서는 더 작은 숫자가 먼저 탐색한다고 가정하면,2와 6중에서 2를 먼저 방문하게 된다. 2에서 다시 DFS를 시행하는데, 방문할 노드가 3과 6이 있으므로더작은 3을 방문하게 되고, 3에서 DFS를 다시 시행하여 4를 방문하고, 4에서 다시 DFS를 해서 5를 방문한다.이제 5에서 더 방문할 곳이 없기 때문에 그 동안 왔던 순서 대로5 --> 4 --> 3--> 2 로 돌아간다. 2로 다시 돌아와서 DFS를 하면 3과 6을 탐색하려고 하는데,3은 이미 방문한 노드이기 때문에 6을 방문한다. 6까지 방문하고 6에서 DFS를 해..
연속부분최대합L 문제N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다. 입력첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 1,000,000 ) 두 번째 줄에 n개의 정수가 주어진다. 출력연속된 부분을 선택하였을 때의 최댓값을 출력한다. 예제 입력8 2 3 -5 8 -3 4 2 -9 예제 출력11 예제 입력5 -1 -2 3 -2 4 예제 출력5 연속부분최대합을 동적계획법으로 푸는 풀이다. Table(i) 를 i번째 수를 오른쪽 끝으로 하는 연속부분 중 최대합이라고 정의한다. 그러면 Table에 대한 점화식은 Table(i) = max ( Table(i-1) + Data(i) ..
[DP-예제 2] 숫자 만들기 입력 N 과 M 이 주어지면, 1~M 까지 숫자를 더하여 N을 만드는 경우의 수를 구해보자.5와 3 같은 경우는 1~3의 숫자를 임의로 골라 더해서 5를 만드는 경우의 수를 구하는 것이다. 숫자 1~3을 가지고 더해서 5를 만드는 경우의 수를 따지면 위와 같이 13가지가 나온다.이제 문제를 해결하기 위해서 부분 문제를 정의해야 한다.동적 계획법으로 기준을 세우기 위에서 마지막 숫자를 기준으로 3가지로 나눌 수 있다.① 마지막에 숫자 1을 더하는 경우② 마지막에 숫자 2를 더하는 경우③ 마지막에 숫자 3을 더하는 경우 세분류로 나눈 것들이 뜻하는 것은 이렇게 해석 할 수 있다.① 마지막에 숫자 1을 더하는 경우 -> 5에서 1을 뺀 나머지 부분에서 4를 만들어야 한다.② 마지막에 숫자 2를 더하는 경우 -..
[DP-예제 1] 블럭채우기 동적 계획법의 예제인 블록채우기에 대해서 공부하면서 DP를 공부해 보자.세로 길이가 2 이고, 가로 길이가 N 인 블럭에 세로 2, 가로 1의 블럭을 채우는 경우의 수를 구하는 예제이다.쉬운 이해를 위해서 입력 N 이 4일 때(가로 길이가 4) 블럭을 채우는 경우의 수는 5이다. 블럭을 채우는 방법을 보면 이러한 식으로 채울 수 있는 방법이 생각해 보면 5가지가 있다.그런데 이 문제를 코딩으로 어떻게 해결 할 수 있을까? 블럭 채우기 알고리즘을 세울려면 먼저 전체 경우를 어떻게 나눌 것인지 생각해야 한다.이 부분이 동적 계획법에서 가장 생각 해 내기 어려운 부분 문제를 정의하는 과정이다. 모든 경우의 수를 보면 위와 같은데, 어떻게 기준을 세우냐면 가장 마지막에 들어가는 블럭을 본다.그러면 1개가 세로로..
동적 계획법 (Dynamic Programming) 동적 계획법 (Dynamic Programming) 은 각 단계에서 해결해야 할 일련의 문제들이 상호 관련성을 맺고 있을 경우에, 어느 단계에서 하나의 결정이 이루어지면 그 결정은 그 다음 단계의 문제를 결정하는 데 영향을 미치게 되고 그 결과 달성하고자 하는 목표에도 영향을 미치게 되기 때문에 이러한 문제를 해결하기 위해서 필요한 알고리즘이다. 대표적인 예로 [피보나치 수] 가 있다. 피보나치 수는 1 1 2 3 5 8 ... 형식으로 이루어져 있는 수열을 의미하는데,초기값인 첫번째 항과 두번째 항은 1이고, n-2 번째 항과 n-1 번째 항을 더해서 n번째 항을 구한다.n 번째 피보나치 수열을 구하는 코드는 위와 같다. 하지만 피보나치 수를 구하는 알고리즘을 위의 코드 같이 재귀적으로 짜면 문제가 발..
분할정복법 (Divide & conquer) 분할정복법은 문제를 여러 개로 분해하여 해결한 후 풀린 부분 문제들을 거꾸로 조합하여 원래의 문제를 푸는 방식이다.대표적인 예로 합병, 퀵 정렬이 있는데, 합병 정렬에서는 정렬을 반으로 나눠서 숫자를 비교해서 합치는 것이 분할정복법의 원리라고 할 수 있고,퀵정렬도 마찬가지로 pivot 보다 작은 왼쪽부분, pivot 보다 큰 오른쪽 부분을 구해서 pivot 의 자리를 찾아가는 과정이 분할정복법이라 할 수 있 다. 출처 : Algorithm LABS

티스토리툴바