알고리즘 트리 재귀 전위/중위/후위 순회 이진트리를 순회하는 방법에는 전위, 중위, 후위 3가지 방법이 있다. 이진트리에서 보면 전체 트리나 서브 트리나 그 구조는 완전히 동일하다. -> 따라서 전체 트리 순회에 사용된 알고리즘은 똑같이 서브 트리에 적용할 수 있는 것이다. 다만 문제의 크기가 작아진다. 문제의 구조는 같고 크기만 작아지는 경우라면 순환을 적용할 수 있으므로 전체 순회에 사용된 알고리즘을 다시 서브트리에 적용하는 것이 가능해진다. 전위 순회 루트노드 방문 왼쪽 서브트리의 모든 노드 방문 오른쪽 서브트리의 모든 노드 방문 중위 순회 왼쪽 서브트리의 모든 노드 방문 루트노드 방문 오른쪽 서브트리의 모든 노드 방문 후위 순회 왼쪽 서브트리의 모든 노드 방문 오른쪽 서브트리의 모든 노드 방문 루..
알고리즘 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 DFS: 시간 초과 DFS를 이용하여 최단거리를 찾고자 하는 경우 완전 탐색 후 가장 작은 값을 선택하여야 하므로 경로가 많아질 수 있고 이렇게 되면 시간 복잡도가 커진다. #include #include #include using namespace std; int map[101][101], ch[101][101], n, m; int dx[4]={1, 0, -1, 0}; int dy[4]={0, 1, 0, -1}; int cnt=1, minn=2147000000; void DFS(int x, int y){ int xx, yy, i; if(x==n && y == m){ if(cnt
알고리즘 누적 합 1차원 배열의 구간 합 계산 누적합을 이용 5 4 3 2 1이라는 수가 주어지면 1차원 vector v v[1]=5 v [2]=4+v [1]=5+4=9 v [3]=3+v [2]=3+9=12 v [4]=2+v [3]=2+12=14 v [5]=1+v [4]=1+14=15 즉 v[i]는 1번째에서 i번째까지의 수를 더한 값을 나타낸다. v[1] v[2] v[3] v[4] v[5] 5 9 12 14 15 따라서 i번째 수부터 j번째 수까지의 합은 v[i]-v[j-1]을 계산한 값이 된다. v[i] 1~i번째 수의 합 v[j-1] 1~j-1번째 수의 합 틀린 코드: 시간 초과 5 4 3 2 1을 배열에 그대로 저장하여 i번째부터 j번째 수 까지의 합을 구하는 과정을 반복문을 i부터 j까지 돌려 ..
[백준 2750번, 2751번/c++] 수 정렬하기, 수 정렬하기2
2750번, 2751번 문제 차이와 풀이 방법 같은 수 정렬 문제이지만, 두 문제는 정렬할 수의 개수와 수의 크기 면에서 차이가 있다. 2750번에서 선택정렬을 이용하였고 2751번은 우선순위큐의 최소힙을 이용하였다. 2751번을 선택정렬을 이용하여 실행하니 시간 초과가 발생했다. 즉, 많은 수의 정렬에 있어서는 선택정렬 방법이 효율적이지 못했다. 시간복잡도를 통해 살펴보면 선택정렬은 O(n^2)의 시간복잡도를 가지고 우선순위큐 정렬은 삽입과 삭제 시 모두 O(logn)의 시간복잡도를 가지므로 -> 우선순위큐를 이용하여 정렬하는 방법이 시간 면에서 더 효율적이라는 것을 판단할 수 있다. 2750번: 수 정렬하기 #include int main(){ // freopen("input.txt", "rt", s..
아래 정렬은 모두 오름차순 정렬을 기준으로 정리하였다. 선택정렬(Selection Sort) 가장 작은 수를 찾아 앞으로 보내는 과정을 반복 배열의 처음부터 끝까지 반복문을 통해 돌며 가장 작은 수를 찾는다. 가장 작은 수를 배열의 맨 앞으로 보낸다. 그 다음 배열부터 끝까지 또 작은 수를 찾아 맨 앞으로 보낸다. 이 과정을 배열이 끝날때까지 반복하여 정렬을 한다. 시간복잡도는 O(n^2) #include int main() { freopen("input.txt", "rt", stdin); int a[101], n, tmp, idx, i, j; scanf("%d", &n); for(i=0; i
알고리즘 재귀 문제 핵심 원판의 이동 과정 n개의 원판이 start에 쌓여있는 경우, 먼저 위에 쌓여 있는 n-1개의 원판을 mid로 옮긴 다음, 제일 밑에 있는 원판을 C로 옮긴다. 이어서 mid에 있던 n-1개의 원판을 end로 옮긴다. 하노이탑의 최소이동횟수 2^n(하노이 탑의 원판 개수)-1이다. 전체 코드 #include #include using namespace std; void hanoi_tower(int n, int start, int mid, int end){ if(n==1){ printf("%d %d\n", start, end); } else{ hanoi_tower(n-1, start, end, mid); printf("%d %d\n", start, end); hanoi_tower(n..