알고리즘

벨만-포드 알고리즘(Bellman-Ford algorithm) 벨만-포드 알고리즘은 시작 노드에서부터 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 이 알고리즘으로 길이가 음수인 사이클을 포함하지 않는 모든 종류의 그래프를 처리할 수 있다. 그래프에 음수 사이클이 있는 경우에는 이를 찾아낼 수도 있다. 이 알고리즘에서는 시작 노드에서 다른 모든 노드까지의 길이를 모두 추적한다. 거리의 초기값은 시작 노드의 경우 0이고 다른 모든 노드의 경우 무한대의 값으로 설정된다. 그리고 이 값을 계속해서 줄여나가는 과정을 더는 줄일 수 있는 값이 없을 때까지 반복한다. 초기 시작 거리가 1인 노드 탐색 거리가 2인 노드 탐색 거리가 3인 노드 탐색 위와 같은 식으로 거리를 줄여나간다. 이후에 거리를 더 줄..

두 수열이 주어졌을 때, 가장 긴 공통 수열을 찾아내는 문제이다. 앞서 풀었던 가장 긴 증가하는 부분 수열과 비슷하다고 생각할 수 있지만 조금 다른 문제이다. for문을 여러 번 돌려 메모제이션을 이용하여 문제를 풀려했었다. 하지만, 문자열을 계속해서 반복하고 어디까지 일치하는지를 기록해야 하고, 건너뛰는 요소가 있을 수 있기 때문에 쉽지 않았다. 해답은 2차원 배열을 이용한 메모제이션이였다. 입력받은 두 문자열 길이보다 1씩 큰 2차원 배열을 생성한 뒤, 0번째 column과 0번째 row을 0으로 초기화 한 뒤, 문제를 풀어나가면 된다. 0으로 채우는 이유는 기저 조건을 설정하는 것이다. 2중 for문을 이용하여 row와 column의 각 요소들을 비교하며 진행한다. 그러다 일치하는 요소가 발견되면,..

증가하는 수열을 만드는 문제이다. 기준을 정해서 그 부분까지의 가장 긴 부분 수열을 구하는 문제로 분할할 수 있다. 즉 i번째까지의 가장 긴 증가하는 수열을 저장해놓고 계속해서 사용하며 마지막까지 수열을 구해 나간다. 다음은 Java로 작성한 코드이다. import java.util.Scanner; public class partSequence { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int x = scan.nextInt(); //수열 저장 int arr[] = new int[x]; //가장 긴 증가하는 수열의 수 int solution[] = new int[x]; //입력을 받는 동시에 soluti..

동적 계획법을 이용하는 문제이다. 이 문제에는 총 세 가지의 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 얼핏 보면, 움직일 수 있는 두개의 계단 중 큰 수를 가진 계단을 이용하는 문제로 볼 수 있다. 하지만, 이것은 탐욕 법을 이용한 문제 풀이이며, 해답이 아니다. 동적 계획법으로 모든 경우의 수를 살펴 보아야 한다. 연속하는 세 개의 계단을 밟을 수 없고, 마지막 계단은 무조건 밟아야 하기 때문에 배열을 이용하여 i번째 계단이 마지막이라 가정하고 하나씩 풀어 나가면..

동적 계획법의 예제이다. 우선, 몇 개의 정수를 처리할지 입력받은 후 입력받은 개수만큼의 입력을 받는다. 그 후, 입력받은 수들을 1, 2, 3의 합으로만 나타내는 방법의 총 개수를 구하는 문제이다. 예를 들어 4는 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1로 총 7개이다. 규칙은 간단하다. 1과 2 그리고 3을 선택한다는 가정을하면 만들려는 수에서 선택한 수를 뺀 수를 만드는 경우의 수를 모두 더하면 되는 것이다. 1을 먼저 선택한 경우 1 + 3을 만드는 경우( 1+1+1, 1+2, 2+1, 3) => 4가지 2를 먼저 선택한 경우 2 + 2를 만드는 경우( 1+1, 2) => 2가지 3을 먼저 선택한 경우 3+ 1을 만드는 경우( 1 ) => 1가지 모두 더하면 ..

그래프(Graph)란? 그래프는 노드(node, 혹은 정점(vertex))와 그들을 잇는 간선(edge)으로 구성되어 있다. 경로(path)는 한 노드에서 그래프의 간선을 지나 다른 노드까지 가는 길을 의미한다. 경로의 길이는 경로에 포함된 간서의 개수이다. 예를 들어 1번 노드에서 5번 노드로 가는 길이가 3인 경로( 1 -> 3 -> 4 -> 5)가 나와 있다. 사이클(Cycle)은 처음 노드와 마지막 노드가 같은 경로를 의미한다. 예를 들어 1 -> 3 -> 4 -> 1로 구성된 사이클이 존재한다. 그래프의 모든 노드 간에 경로가 있는 경우를 연결 그래프(connected graph)라고 한다. 연결 그래프 연결 그래프가 아님 그래프의 연결된 부분을 컴포넌트(component)라고 표현한다. 연결 ..

입력받은 수를 3으로 나누기, 2로 나누기, 1 빼기 이 세 가지 연산을 이용하여 1로 만드는 최소의 연산 횟수를 구하는 문제이다. 얼핏 보면, 3으로 나누는 연산이 가장 수를 많이 줄여주니까 3으로 나누고, 3으로 나누지 못하면 2로 나누고, 그러지 못하면 1을 빼는 식으로 구할 수 있는 간단한 문제인 것 같이 보인다. 하지만 이것은 탐욕 법으로 계산하는 방법이며, 항상 최적해를 구할 수 없다. 예를 들어, 10을 1로 만드는 방법을 탐욕법으로 구한다면 10 -> 5 -> 4 -> 3 -> 1으로 총 4회의 연산이 필요하다. 하지만, 동적 계획법으로 연산을 하면 10 -> 9 -> 3 -> 1 로 총 3회의 연산만으로 1로 만들 수 있다. 따라서, 모든 경우의 수를 살펴 보아야 한다. import ja..

동적 계획법이란? 문제를 풀기 위해서, 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 하위 문제의 해결책이 다른 하위 문제의 해결책과 같은 경우 유용하다. 탐욕 알고리즘과의 비교 탐욕 알고리즘은 문제가 발생하면 그 상황에서의 최적의 해를 선택하는 방식의 알고리즘을 말한다. 순간적으로 볼 때는 최적의 해를 반환하지만 전체적으로 보았을 때 그렇지만은 않은 상황이 존재한다. 예를 들어, 길을 찾는 문제가 주어졌다면 출발지부터 목적지까지 가는 중, 갈림길과 마주했을 때 그 순간 가장 짧은 길로 가는 것이다. 하지만 동적 계획법은 모든 갈림길을 살펴본 후 최적의 길을 탐색하게 된다. 동적 계획법은 모든 경우의 수를 살펴봐야 하기 때문에 시작시 조금의 시간이 걸릴..

퀵 소트란? 퀵 소트는 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 퀵 소트는 정렬 알고리즘 중 가장 빠르다고 하여 붙여진 이름이다. pivot을 선택하여 비교하며 정렬을 수행하는데 pivot으로 선택한 수가 가장 작거나 가장 크다면 최악의 경우로 정렬 수행 시간이 가장 오래 걸린다. 하지만 가장 오래 걸리더라도 O(n^2)의 시간 복잡도를 가지며 이 최악의 경우만 제외한다면 평균적으로 O(nlogn)의 시간 복잡도를 가진다. 퀵 소트은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다. 1. 리스트에서 임의의 수를 pivot으로 정한다. 2. pivot앞에는 pivot보다 값이 작은 모든 원소들이 오고, pivot 뒤에는 pivot보다 값이 큰 모든 원소들이 오도록 ..

버블 소트란? 버블 소트는 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)으로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 위에서와 같이 인접한 원소와 하나하나 비교하며 정렬을 수행한다. 배열의 끝까지 정렬을 완료하면 다시 처음으로 돌아가 같은 작업을 반복하여 수행한다. 다음은 JAVA로 작성된 버블 소트의 코드이다. public class bubbleSort { public static void main(String[] args) { int arr[] = {1,3,6,2,8,2,5,9}; //정렬중 임시 저장 int temp; //출력(정렬전) System.out.print("정렬전..