DOTY

HEAP은 최대나 최솟값을 빠르게 찾게 해주는 알고리즘. 완전 이진 트리를 기반으로 만들어진 알고리즘이다. 최대 힙과 최소 힙이 있으며 최대 힙을 구현했다. 1. main int main(void) { fill_n(heap_arr, 100, 0); // 배열 초기화 heap_size = 0; int node; while(node != -1) { cout heap_arr[index*2+1]) { swap(heap_arr[index*2], heap_arr[index], index * 2); index *= 2; } else { swap(heap_arr[index*2 + 1], heap_arr[index], index * 2 + 1); index = index * 2 + 1; } } heap_arr[heap_..

A^2 = A * A 인 것은 알고 있다. A^4 = A * A * A * A 도 알고 있다. A^8 = A * A * A * A * A * A * A * A 인것도 당연하다. 그러나 이런 방법으로 알고리즘을 짠다면 시간이 더욱 걸릴 것이다. 그렇기에 연산을 줄여야 한다. A^4 = (A^2)^2 처럼 표현하여 연산을 3번에서 2번으로 줄일 수 있다. A^8 = ((A^2)^2)^2 또한 연산을 7번에서 3번으로 줄일 수 있다. 이 방법을 사용한다면 시간이 확 줄어들 것이다. 만약 A^6 과 같은 경우에는 어떻게 할까? A^6 = A * (A^2)^2 처럼 쓸 수 있을 것이다. 지수가 홀수가 되버리면 따로 A를 빼주는 방법이다. 기존의 방법은 O(n)의 시간복잡도를 가졌다면 최적화를 한 경우에는 O(lo..

BFS의 응용버전 (BFS와 다이나믹이 합친 느낌이랄까..) 최단 거리를 찾는 알고리즘이다. 하나의 정점에서 모든 점으로 가는 최단 경로로 못 가는 경우에는 무한대로 끝난다. 필기로 정리한 것 또 쓰기가.. ㅎㅎㅎㅎㅎㅎ

어떤 알고리즘인지 모르고 있었지만 이번 기회에 문제를 풀면서 알게 된 알고리즘. 아직은 어떤 타이밍에 이 알고리즘을 써야 하는지 모르지만, 연습하다보면 알게 될것이라 믿는다.....ㅠㅠ 방법은 다음과 같다. 1. 두개의 포인터가 있다. 본인은 front, end로 정한다. 2. 두 포인터중 하나라도 배열의 크기를 넘어가게 되면 그대로 끝! 3-1. 두 포인터의 범위에서 모자라면 end로 범위를 늘려준다. 3-2. 두 포인터의 범위에서 넘치게 되면 front로 범위를 줄여준다. 생각보다 간단한 알고리즘. 그런데 시간복잡도는 O(N)밖에 안된다. 원래대로 하려면 for문을 두개 쓰는 등 해야하는데!!! 빠르자너.....!!! 예시를 들어보자. (초기 : front = 0, end = 0, answer = 9..

오늘 처음 알게 된 DP 에서 중요한거 같은 Memoization!!! 메모이제이션이야 ....? 아니면 메모아이제이션이야....? 쩃든,,,, 코드 두개를 비교 하면서 설명! ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ fibo(int n) { if(n == 1 || n == 2) return 1; return (fibo(n-1) + ribo(n-2)); } fibo(int n) { if(Memoization[n] == 0) Memoization[n] = fibo(n-1) + fibo(n-2); return Memoization[n]; } 처음에는 무슨 차이지... 싶었다. 코드 1은 그냥 한거고, 코드 2는 배열을 사용한것이다. 그런데 잘 생각해보면 ..

소수를 찾는 알고리즘이다. 이렇게 빠를줄은 생각도 안하고 있었는데.... 엄청 빠르다 int prime_Num(int n) { int cnt = 0; vector check(n+1, 1); for(int i = 2; i

이건 BFS 와는 다르게 깊이 우선 탐색이다. BFS라면 1, 2, 3.... 순이겠지만, DFS는 1, 2, 4..... 순이다. 코드는 다음과 같다. void dfs(int num) { if(check[num]) return; check[num] = true; cout

BFS는 너비 우선 탐색이다. 이걸 위해서 직접 만들었다. 역시 대단해 ㅎㅎㅎㅎㅎㅎ 본론으로 BFS는 너비 탐색으로 말 그대로 넓게 퍼져가면서 탐색한다 생각하면 된다. 과정은 간단하다. 큐(Queue)에 하나하나 넣어서 대기 시키는 느낌이랄까... 코드는 다음과 같다. void bfs(int num) { queue q; q.push(num); check[num] = true; int x, y; while(!q.empty()) { x = q.front(); q.pop(); cout