Knowledge Map

알고리즘 푸는 요령 본문

알고리즘

알고리즘 푸는 요령

2018.02.05 21:15

모든 알고리즘 문제는 먼저 전탐색 (brute force)로부터 시작한다.

하지만 그냥 전탐색을 실제로 코딩하기 보다는 전탐색을 전제로 시간 복잡도를 계산해 보는 것이 좋다.


1. 일반적으로 연산 1억번에 1초가 걸린다고 가정하고 문제를 파악한다.

2. 보통 for 하나에 시간복잡도 n, 중첩되면 n의 지수로 증가한다.

3. 시간 복잡도는 n이든, 2n이든 상관없이 보통 n으로 취급하며 상수는 무시한다.


예를 들어 시간제한이 5초인 문제가 있다면 5억번의 연산이 가능하다고 볼수 있다.

만약 전탐색으로 계산을 해보았을 때 시간 복잡도가 n^2라고 해보자.

이때 횟수를 많이 발생시키는 수가 10000이라고 한다면 결과는 10의 8승, 즉 1억이 된다.


이럴 경우 그냥 전탐색으로 문제를 풀면된다.

만약 시간 제한이 0.5초라면 다른 알고리즘을 탐색해봐야 한다.



팁1 : 빠른 속도로 코딩하자. 


1. 알파벳과 숫자를 빠르고 정확하게 타이핑 할 수 있어야 한다.  http://wwwtypingtest.com

2. ( ) { } [ ] < > . , ; : " ' & | ! 등의 특수 문자에 대해서도 빠르게 타이핑 할수 있어야 한다.



팁2 : 문제 유형을 파악하자.


1. 문제 유형

- 애드훅, 완전 탐색(반복적/재귀적), 분할 정복, 탐욕법, 동적 계획법, 자료구조

- 그래프, 수학, 문자열 처리, 계산 기하, 어렵거나 희귀한 유형


위의 유형들을 최대한 A에 많도록 훈련해야 한다.


A. 과거에 풀어본 적이 있는 유형 : 다시 풀 자신이 있음

B. 과거에 접해본 적 있는 유형 : 아직은 풀지 못할 거 같음

C. 과거에 접해본 적 없는 유형



팁3 : 알고리즘 분석을 수행하자


1억번 (10^8) 연산은 몇초 안에 해낸다. 

복잡도와 입력 허용 최대값을 활용하면 걸리는 시간을 어느정도 파악할 수 있고 문제유형도 좀더 파악하기 좋다.


[반복적 알고리즘과 재귀적 알고리즘의 시간 및 공간 복잡도 분석을 위한 기본사항]

- 약 n번씩 반복하는 반복문이 k중으로 중첩된 경우 복잡도는 O(n^k)이다.

- 재귀적 알고리즘이며 깊이가 L이고 매 호출마다 b번씩 재귀호출을 수행한다면 대략적인 복잡도는 O(b^L)이다. 

- DP 알고리즘이 n * n 크기의 2차원 행렬을 다루며 행렬의 각 성분을 다루는데 O(k)만큼의 작업을 수행한다면 그 알고리즘은 수행하는데 O(k * n^2) 시간이 든다.

- 2^10 = 1024(유사값 1000), 2^20 = 1048576 (유사값 1,000,000)

- 부호있는 32비트 정수, 부호있는 64비트정수의 최대값은 각각 2^31-1(대략 9자리 정수까지 안전), 2^63-1(대략 18자리 정수까지 안전)

- n개의 원소가 주어졌을 때 순열은 n!개가 있고, 부분집합은 2^n개가 있다.

- 보통 O(nlogn) 알고리즘 정보면 대부분의 대회 문제를 풀기에 충분하다.

- 2013년 기준으로 대부분의 CPU는 몇 초안에 1억번의 연산을 해낼수 있다. (1초라고 생각하면 됨)


팁4 : 프로그래밍 언어에 능숙해지자


팁5 : 코드를 테스트 하는 기술에 능숙해 지자


팁6 : 연습하고 또 연습하자.


출처 : http://book.naver.com/bookdb/book_detail.nhn?bid=12120061


빅오 : https://github.com/abhbtbb/TIL/blob/master/01.%20algorithm/BigO.md

0 Comments