알고리즘11 알고리즘 문제 풀 때 시간,공간복잡도 및 Integer overflow 문제 시간복잡도 공간복잡도입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계예를 들어 크기 N짜리 2차원 배열이 필요하면 O(N²)이고, 따로 배열이 필요 없으면 O(1)이 된다.하지만 코딩테스트에서 대부분의 경우 공간복잡도의 문제보다는 시간복잡도 때문에 문제를 많이 틀린다.그러므로 공간복잡도는 크게 신경쓰지 않아도 된다. But!! 이거 하나만 기억해두자 ☞ 메모리 제한이 512MB일 때 1.2억개의 int를 사용할 수 있다는 것 Integer Overflow Integer Overflow가 발생하는 경우#includeusing namespace std;int main(){ int a = 2000000000 * 2; cout 약 21억정도 까지만 표현할 수 있으므로 40억이라는 값은 a에 저.. 2022. 3. 12. 알고리즘 시간복잡도 구하는 법 ( 반복대치 ) #include factorial(int n){ if(n == 1) return 1; //1 return n * factorial(n-1); //2}시간복잡도 : T(n) = T(n-1) + c ( c는 "1의 수행시간 + 2에서의 곱셈의 수행시간" ) 위의 factorial() 함수의 시간복잡도를 반복대치를 이용해 구해보겠다. 반복대치T(n) = T(n-1) + c = T(n-2) + 2c = T(n-3) + 3c . . . = T(1) + (n-1) * c 이때, n = 1일 때 T(1)은 1의 수행시간 밖에 들지 않으므로 1의 수행시간 + 2의 수행시간의 값을 가지는 c보다 작다. 즉, 빅오의 정의에 의해 .. 2022. 2. 27. 다이나믹 프로그래밍 ( Dynamic Programming ) 다이나믹 프로그래밍 문제는 종류가 굉장히 많으며 컴퓨터적인 사고력을 물어보기에 적합하다는 점에서 자주출제되는 문제이다. 다이나믹 프로그래밍하나의 문제는 단 한 번만 풀도록 하는 알고리즘=> 한 번 푼 것을 여러 번 다시 푸는 비효율적인 알고리즘을 개선시키는 방법dp같은 경우 문제에서 규칙성을 찾아서 점화식을 세우는 게 가장 중요하다. 다이나믹 프로그래밍을 쓰는 이유일반적으로 상당수의 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있다.( 단, 퀵 정렬이나 병합 정렬은 동일한 문제를 다시 푸는 단점이 없다. 그러므로 매우 빠르다. ) 단순 분할 정복으로 풀게 되면 심각한 비효율성을 낳는 대표적인 예시 ' 피보나치 수열 ' 피보나치 수열은 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 .. 2022. 2. 21. 깊이 우선 탐색 ( DFS ) 깊이 우선 탐색 ( DFS )탐색을 함에 있어서 보다 깊은 것을 우선적으로 탐색하는 알고리즘미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해 느리다. 깊이 우선 탐색 특징넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것스택(Stack)을 사용- 사실 스택을 사용하지 않아도 구현이 가능하다. 왜냐하면 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문이다.자기 자신을 호출하는 재귀 알고리즘의 형태이다.탐색 과정이 시작 노드에서 한없이 깊게.. 2022. 2. 20. 너비 우선 탐색 ( BFS ) 너비 우선 탐색 ( Breath First Search )데이터를 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘현재 노드에서 가까운 것을 먼저 탐색하는 방식깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것 너비 우선 탐색 특징재귀적으로 동작 XFIFO 원칙으로 탐색 ( Queue가 필요함 )그래프 탐색 알고리즘은 방문한 노드를 꼭 방문 처리 해줘야 한다. ( 하지 않을 경우 무한 루프에 빠질 수 있음 )너비 우선 탐색 장점과 단점출발노드에서 목표노드까지의 최단 길이 경로 보장경로가 매우 길 경우 탐색 가지가 급격히 증가함에 따라 보다 많은 저장 공간이 필요함해가 존재하지 않는다면 유한 그래프의 경우 모든 그래프를 탐색한 후 실패로 끝남무한 그래프의 경우 해가 없는 경우 해를 찾지.. 2022. 2. 15. 계수 정렬 ( Counting Sort ) 계수 정렬'범위 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘 -> 속도 : O(N)단순하게 '크기를 기준'으로 세는 알고리즘 문제) 주어진 5 이하 자연수 데이터들을 오름차순 정렬하시오. 1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1크기를 기준으로 갯수만 세주면 되기 때문에 다른 정렬들처럼 위치를 바꿀 필요가 없다.모든 데이터에 한 번씩만 접근하면 된다는 점에서 매우 효율적이다. 초기 상태1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1크기 = 1크기 = 2크기 = 3크기 = 4크기 = 500000 1. 첫번째 상태1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 .. 2022. 2. 15. 이전 1 2 다음
