알고리즘 문제 해결 과정

1. 지문 읽기 및 컴퓨터적 사고
   문제를 해석하고 재정의한 후 문제를 풀기 위한 작은 단계들로 쪼개기
2. 요구사항(복잡도) 분석
   이 문제를 주어진 요건에 맞게 풀기 위해서는 어느 정도의 성능이 필요한지 판단
3. 문제 해결을 위한 아이디어 찾기
4. 소스코드 설계 및 코딩
   문제의 풀이 방향이 나왔다면 방향에 맞게 최대한 간결하고 깔끔하게 코드 작성
   문제의 정의부터 하고 코드 작성을 하는 것을 권장

알고리즘 성능 평가

복잡도

알고리즘의 성능을 나타내는 척도
복잡도가 낮을수로 좋으며, 코드의 가독성과는 구분되는 개념

시간 복잡도

특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

• 빅오 표기법
  - 시간 복잡도를 표현하는 표기 방법
  - 가장 빠르게 증가하는 항만을 고려하는 표기법(함수의 상한만을 나타냄)
  - 연산 횟수를 식으로 나타냈을 때, O(가장 빠르게 증가하는 항)
  ex) 연산 횟수가 3n3 + 5n2 + 10000000 인 알고리즘의 시간 복잡도를 빅오 표기법으로 나타내면 O(N3)

• 시간 복잡도를 고려한 알고리즘 설계 Tip
  - 일반적인 컴퓨터에서 연산 횟수가 5억을 넘을 경우 C언어는 1~3초, 파이썬은 5~15초 정도가 소요(PyPy는 일반적으로 좀 더 빠름)
  - 코딩 테스트는 일반적으로 1~5초의 시간제한을 명시해 두며, 문제에 명시되지 않은 경우에는 대략 5초 정도의 제한이 있음
  - 문제를 풀기 전 시간제한(수행시간 요구사항)을 먼저 확인 후 어느 정도의 시간이 걸리는(시간 복잡도를 가진) 알고리즘으로 문제를 풀지 설계해야 함
  - 일반적으로 문제에서는 자료(데이터)의 갯수가 몇 개인지 문제나 문제 조건에 명시해 줌 -> 이를 고려해서 시간 복잡도를 계산할 수 있음
  

• 코드 소요 시간 측정 예시

import time
start_time = time.time()
# ... 소스코드 ...
end_time = time.time()
print('time : ', end_time - start_time)

• 대표적인 리스트 메서드의 시간 복잡도
  

공간 복잡도

특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

파이썬 문법

문법

파이썬 문법 정리

자주 사용되는 라이브러리

• itertools : 순열, 조합을 비롯한 데이터 처리 기능 제공
• heapq : 힙(Heap) 자료구조 제공. 일반적으로 우선순위 큐 기능을 구현하기 위해 사용
• bisect : 이진 탐색(Binary Search) 기능 제공
• collections : 덱(deque), 카운터(Counter) 등의 유용한 자료구조 포함
• math : 팩토리얼, 제곱근, 최대공약수, 삼각함수 관련 함수, 파이(pi) 상수등을 비롯한 필수적인 수학적 기능 제공

Etc.

하나의 문제가 하나의 유형에 대응되는 것이 아니라, 하나의 문제가 여러 유형에 속하는 경우가 많음
자신의 알고리즘 코드 모아서 깃허브에 노트해두는 것 추천 - 자주 사용하는 코드 위주로(공식, cheat sheet)
기업에서 시행했던 코딩테스트들의 역대 커트라인 참고(몇 문제 중 몇 개)

Reference

이코데 강의 링크