Soongle's Morgorithm

DP(동적계획법)란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 두 가지 방법으로 문제를 해결할 수 있는데, Top-down은 가장 큰 문제를 나누어 작은 문제를 호출해 답을 찾는 방식이고 Bottom-up은 가장 작은 문제들 부터 답을 구해가며 전체 문제의 답을 찾는 방식이다. Top-down 방식은 재귀함수를 이용해 구현한다. 예를 들어, 피보나치 함수를 f(n) = f(n-1) + f(n-2), f(1) = 1, f(2) = 1 위와 같은 점화식으로 세웠을 때 Top-down 방식으로 코드를 구현하면 다음과 같다. int f(int n) { if(n

하노이 탑문제는 N개의 크기가 서로 다른 원판을 다른 기둥으로 옮기는 문제이다. 이 때 다음 두 가지 조건을 만족시키면서 원판을 다른 기둥으로 옮겨야 한다. 한 번에 하나의 원판만 옮길 수 있다. 큰 원판이 작은 원판 위에 있어서는 안된다. 전체 n개의 원판을 옮기는 것은 다음과 같이 재귀적으로 생각해 볼 수 있다. 크기 1 ~ (n-1)인 원판들을 A기둥에서 B기둥으로 옮긴다. 크기 n인 원판을 A기둥에서 C기둥으로 옮긴다. 1 ~ (n-1) 원판들을 B기둥에서 C기둥으로 옮긴다. 소스코드 void hanoi(int n, char from, char tmp, char to) { if(n > 0) { hanoi(n-1, from, to, tmp); cout

Sort 선택 정렬(Selection Sort) 버블 정렬(Bubble Sort) 삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort)을 구현해 보았다. void insertion_sort(int arr[], int n) { int j; for(int i = 1 ; i = 0 ; j--) { if(arr[j] > temp) arr[j+1] = arr[j]; else break; } arr[j+1] = temp; } } 우선, 자신이 삽입되어야 할 자리를 자신의 앞에서 찾기 때문에 아래의 동작을 i = 1에서부터 n-1까지 반복한다. temp 변수에 현재 자신의 값을 저장해둔다. 반복문을 사용해..

Sort 선택 정렬(Selection Sort) 버블 정렬(Bubble Sort) 삽입 정렬(Insertion Sort) 버블 정렬(Bubble Sort)을 구현해 보았다. void bubble_sort(int arr[], int n) { for(int i = n-1 ; i > 0 ; i--) { bool sorted = true; for(int j = 0 ; j arr[j+1]) { swap(arr[j], arr[j+1]); sorted = false; } } if(sorted) break; } } i : 정렬이 끝나는 칸(뒤에서 부터 정렬됨) j : (0 ~ i-1) 앞에서 부터 양 옆의 값을 비교하며 앞의 값이 뒤의 값보다 클 경우 두 값을 교환한다. 아..

Sort 선택 정렬(Selection Sort) 버블 정렬(Bubble Sort) 삽입 정렬(Insertion Sort) 선택 정렬(Selection Sort)을 구현해 보았다. void selection_sort(int arr[], int n) { for(int i = 0 ; i < n-1 ; i++) { int minIndex = i; for(int j = i+1 ; j < n ; j++) { if(arr[j] < arr[minIndex]) minIndex = j; } if(minIndex != i) swap(arr[minIndex], arr[i]); } } 마지막 원소인 n-1번째 원소는 자동 정렬되기 때문에 n-1전까지 반복해 주었다. (i+1) ~ (n-1)번째 원소들 중 가장 작은 값을 찾아 ..

이진 탐색(binary search)알고리즘은 정렬되어있는 데이터에서 특정 값의 위치를 찾는 알고리즘이다. ※정렬되어있지 않은 데이터에 사용할 수 없다※ 재귀로 구현하면 매우 간단해진다. 중간 값(mid)을 잡는다 원하는 값을 찾지 못하였을 때 탈출 조건(first > last)에 의해 -1을 반환한다 : 탐색 실패 원하는 값을 찾았을 때(arr[mid] == key) 해당 위치(mid)를 반환한다 : 탐색 성공 현재 중간 값이 찾고자 하는 값보다 큰 경우, 중간 값의 왼쪽 범위에서 탐색을 시작한다 : 재귀 호출 현재 중간 값이 찾고자 하는 값보다 작은 경우, 중간 값의 오른쪽 범위에서 탐색을 시작한다 : 재귀 호출 소스코드 #include #include using namespace std; int b..