알고리즘 풀이 기초

문제 해결 과정

1. 문제 읽고 이해하기
2. 계획 세우기
   1. 알고리즘 선택
   2. 자료구조 선택
3. 계획 검증하기
   1. 키보드를 잡기 전에 계획을 검증하자
   2. 시간 복잡도, 공간 복잡도 확인
4. 구현하기
5. 회고하기
   1. 어떤 방식으로 접근했는가
   2. 문제의 해답을 찾는 결정적이었던 깨달음은 무엇인가
   3. 틀렸다면 오답 원인 기록하기

---

문제 접근하기

1. 예전에 비슷한 문제를 풀어본 적이 있는가

• 문제의 목적을 보고 적절한 접근 방법을 선택하기 위해서는 어떤 문제가 최적화 문제인지, 경우의 수를 구하는 문제인지, 검색 문제인지 등을 분류하는 방법을 익히고, 각 알고리즘들이 어느 경우에 사용될 수 있는지 체계적으로 공부해야 함.

2. 무식하게 풀 수 있는가

• 단순한 알고리즘을 기반으로 문제를 구성한 뒤, 좀 더 효율적인 자료구조를 사용하거나, 계산 과정에서 같은 정보를 두 번 중복으로 계산하지 않는 등의 최적화를 적용해서 충분히 빨라질 때까지 알고리즘을 개선하는 식으로 문제를 풀 수 있음.

3. 문제를 분해할 수 있을까

• 문제에 주어진 복잡한 조건을 더 단순한 형태를 갖는 조건의 집합으로 분해

4. 뒤에서부터 생각해서 문제를 풀 수 있을까

• 모든 선택지를 위에서 아래로 내려가 보는 대신에, 한 번만 밑에서 위로 올라가서 문제를 해결
• A에서 B로 가는 방법을 찾는 것은 어렵지만 B에서 A로 가는 방법을 찾기 쉬울 때 사용

---

자주 하는 실수

1. 배열 범위 밖 원소에 접근
2. 일관되지 않은 범위 표현 방식 사용
3. 하나가 모자라거나 하나가 많아서 틀리는 경우
4. 스택 오버플로
5. 산술 오버플로

• int 20억

---

알고리즘의 시간 복잡도 분석

• 좀더 빠른 알고리즘을 만들기 위해 가장 먼저 해야 할 일은 바로 알고리즘의 속도를 어떻게 측정할지를 정하는 것
• 알고리즘의 수행시간을 지배하는 것은 바로 반복문
• 대개 우리는 알고리즘의 수행 시간을 반복문이 수행되는 횟수로 측정
• N번 수행되는 반복문이 두 개 겹쳐있다면 O(N^2)

선형 시간 알고리즘

• N이 두 배 커지면 실행도 두 배 오래 걸리고, 반으로 줄어들면 수행 시간도 반으로 줄어든다.
• 입력이 크기에 대비해 걸리는 시간을 그래프로 그려 보면 직선
• 이런 알고리즘을 선형 시간 알고리즘이라고 함

선형 이하 시간 알고리즘

• 이진 탐색

지수 시간 알고리즘

수행 시간 어림짐작하기

• 어떤 알고리즘이 이 문제를 해결할 수 있을지 알기 위해서는 프로그램을 작성하기 전에 입력의 최대 크기와 알고리즘의 시간 복잡도를 보고 수행 시간을 어림짐작할 수 있어야 함.

→ 입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억을 넘어가면 시간 제한을 초과할 가능성이 있다.

알고리즘 증명

• 귀납법
• 귀류법