Search

알고리즘 선택하는 법

대분류
기타
소분류
알쓸신잡
유형
알고리즘
부유형
시간 복잡도
의사 코드
최종 편집 일시
2024/10/27 15:19
생성 일시
2024/10/16 13:02
14 more properties

1. 문제 이해

우선 문제에서 사용하는 데이터와 요구 사항을 확인하여 이해한다.
정의를 잘 읽는다.
예시를 풀어본다. (입력값 포함)
왜 이런 출력값이 나오게 되었는지 생각한다.

2. 문제 분해

a.
내가 풀어본 문제와 유사한 부분은 하나로 묶기
b.
논리(사고)할 수 있는 단위로 문제 쪼개기

2. 시간복잡도 사전 계산

Python 기준 안전하게 1초에 2000만번 이내로 계산되도록 O(N)을 설정하는 알고리즘을 짠다.
예시
시간 제한이 2초면 2×2000만 회=4000만 회=4×1082초 \times \text{2000만 회} = \text{4000만 회} = 4\times10^{8}회까지 가능하다.
1.
최대 입력 데이터 개수(n)가 1000개라면 시간복잡도가 O(n2)O(n^2)알고리즘을 사용하더라도 100만 회 이므로 사용할 수 있다.
2.
최대 입력 데이터 개수(n)가 100000=10510^5개라면 시간복잡도가 O(n2)O(n^2)알고리즘을 사용하였을때 101010^{10}회 이므로 사용할 수 없다.
3.
데이터 개수(n)가 100000=10510^5개라면 시간복잡도가 O(n2)O(n^2)알고리즘을 사용하였을때 101010^{10}회 이므로 사용할 수 없다.

3. 적절한 시간 복잡도의 알고리즘을 떠올린다.

4. 종이에서 먼저 손코딩으로 알고리즘을 선정한다.

5. 의사코드를 작성해본다.

6. 의사코드에 맞춰서 코딩을 시작한다.