전각 공백 ( ) 괄호 안에 공백을 복사해서 붙여 넣으세요
STEP 1 : 문제 이해하기
- 지문을 읽고 문제를 이해하는 단계이고, 기본적인 검증을 해봐야 한다
- 파이썬 기준으로 실행 시간 1초당 실행 횟수 1000만 번 정도로 가정하고, 이에 해당하는 자료구조, 알고리즘 선택하기
- 최대 실행 횟수를 10^8이라 가정(문제마다 실행 시간이 다를 수 있지만..)
- 효율성 테스트 통과를 위한 시간 복잡도를 계산해놔야 한다
- 예를 들면 input size가 10^5인데 내가 설계한 알고리즘의 시간 복잡도가 O(n^2)이라면, 계산해 볼 필요도 없이 효율성 테스트 Fail이다
- input size가 10^5면 설계할 수 있는 시간 복잡도는 O(n^2)미만으로 설계해야 한다.. O(nlogn) 혹은 O(n), O(1) 등등등이 가능할 것..
- input size가 10^2면 O(n^3)도 가능하고, O(n^4)도 가능할 수 있다. 그렇다면 완전 탐색도 고려할 수 있다는 말!
- O(n^2)은 2차원 for loop, 버블, 선택, 삽입 정렬
- O(nlogn)은 파이썬에서의 정렬 #중요# sort() // merge sort, quick sort 등등이 있다
- O(n)으로는 1차원 for loop
- O(logn)으로는 binary search
- int 자료형은 약 21억까지인데 이를 초과하지는 않는지?(파이썬은 해당사항 없다)
STEP 2 : 접근 방법 (가장 어려움)
-
직관적으로 생각하기(컴퓨터 없이 사람답게 문제를 푼다면 어떤 방식으로 풀어갈 것인가?)
- 보통 완전 탐색으로 시작
- 문제 상황을 단순화하여 생각하기
- 문제 상황을 극한화하여 생각하기
-
자료구조, 알고리즘 활용
- 문제 이해에서 파악한 내용을 토대로 어떤 자료구조를 사용하는 게 가장 적합한지 결정
- 대놓고 특정 자료구조와 알고리즘을 묻는 문제도 많음
- 자료구조에 따라 선택할 수 있는 알고리즘을 문제에 적용
-
메모리 사용
- 시간 복잡도를 줄이기 위해 메모리를 사용하는 방법
- 대표적으로 해시테이블
- 해시 테이블은 파이썬에서 딕셔너리, 핵심은 in 키워드 사용을 통해 시간 복잡도를 줄이는 것이다
- 리스트를 돌아서 어떤 값이 있는지 찾는 in 키워드의 시간 복잡도는 O(N), 하지만 딕셔너리에서 in 키워드는 시간 복잡도가 O(1)이다
- 이유는 리스트는 전부 뒤져봐야 알 수 있지만, 해시테이블은 해시 함수에 key 값을 넣어서 받은 값, hashFunction(key)로 가서 key 값에 해당하는 value가 있는지 바로 확인하러 가기 때문이다
STEP 3 - 코드 설계
- STEP 2에서 정한 걸 토대로 코드를 설계하기
- 슈도코드도 좋고, 글로 적어도 좋고, 그림을 그려도 좋고, 다 좋다
- 구현전에 검증하기 위함이다
STEP 4 - 코드 구현
- 코드 구현
문제 커밋하고, 리뷰 댓글로 문제 리뷰하기