입출력 제한
1. 입력이 100 이하인 경우
완전 탐색
백트래킹
2. 입력이 10,000 이하인 경우
최대 O(n^2) 이내로 끝내야하는 문제
문제에 따라 O(n^2 log n)까지는 허용
n*n 2차원 리스트를 모두 순회해야하는 문제가 많음
3. 입력이 1,000,000 이하인 경우
최대 O(n log n)으로 끝내야하는 문제
힙, 우선순위 큐
정렬
동적 계획법
위상 정렬
다익스트라 알고리즘
4. 입력이 100,000,000 이하인 경우
최대 O(n)으로 끝내야하는 문제
동적 계획법
그리디
5. 그 이상인 경우
최대 O(log n)으로 끝내야하는 문제가 많음
거의 안나오는 문제 유형
이진탐색문제 유형
1. 입력값이 작은 문제
위에서 적었듯 높은 확률로 완전 탐색 혹은 백트래킹 문제입니다.
구현력이 중요한 문제로 출제될 가능성이 높습니다.
2. 지도가 주어지고 채워진 영역을 찾아야하는 경우
높은 확률로 BFS, DFS 문제입니다.
3. 그래프 그림이 있는 경우
이 경우 높은 확률로 세 가지 유형 중 하나입니다.
- 최단 거리 찾기
- 최소 신장 트리
- 위상 정렬
문제에서 "가장 빠른 길", "최단 거리"와 비슷한 키워드가 나온다면
당연히 최단 거리 찾기 유형이고
"X 비용 내로 갈 수 있는 길을 찾아라"와 같은 키워드가 나와도
최단 거리 찾기 유형입니다. 다익스트라, BFS, DFS 등이 사용될 수 있습니다.
최소 신장 트리 문제는 보통 "가장 저렴한 방법으로 모든 경로 연결해라" 등의 키워드로 출제됩니다.
경로가 아니라 통신망, 전송 시간, 회로, 배관 등 다양한 용어로 나올 수는 있지만
핵심은 모든 경로를 "가장 싸게 연결해라"입니다.
그래프는 양방향일수도 단방향일수도 있습니다. 크루스칼, 프림 알고리즘을 사용할 수 있습니다.
위상 정렬은 순서를 정해야할 때 사용됩니다. 보통 "순서", "차례" 등의
키워드가 나오면 위상 정렬 문제입니다.
4. X라는 조건을 만족하는 가장 최대/최소값을 찾아라
이 경우 높은 확률로 결정 문제입니다. 파라메트릭 서치를 이용해서 풀 수 있습니다.
5. 실시간으로 정렬이 이루어져야 하는 경우
높은 확률로 우선순위 큐 혹은 힙을 사용하는 문제입니다.
6. DP 문제
보통 완전 탐색처럼 시간이 오래걸리면 안되는데 특별한 알고리즘을 사용하는 문제가 아닐거
같을 때는 높은 확률로 DP 문제입니다.
다른 문제처럼 "딱봐도 이거네!" 하는 특징이 없어서 보통 문제를 보고 바로
유형을 판단하기 힘든 경우 DP처럼 풀 수 있는지 생각해봐야 합니다.
종이를 꺼내고 다음과 같은 방식으로 해보셔도 괜찮을 것 같습니다.
문제를 따라 먼저 초기값을 적는다.
초기값을 포함해 모든 상태값을 적는다.
현재상태를 통해 다음 값을 구할 수 있는지 판단한다.
혹은 이전 상태들을 통해 현재 값을 구할 수 있는지 판단한다.
이런식으로 여러 번 해보고 식을 만들 수 있다면 100% DP 문제입니다.
7. 문자열이 주어지는 경우
구현력 문제인 경우가 많습니다. 문자열을 자르거나, 붙이거나 탐색하는 문제가 대부분입니다.
문자열을 탐색하는 알고리즘이 필요한 경우 KMP 알고리즘을 사용할 수 있지만
보통 파이썬과 같은 스크립트 언어에선 문자열 탐색이 빌트인으로 존재하기 때문에 구현에만
집중하면 됩니다.
8. 현재 상황에서 가장 최적인 선택을 해야하는 경우
문제에서 항상 최적의 선택을 해야하는 경우 혹은 "가장 많은 선택을 할 수 있는",
"가장 작은/큰" 등의 키워드가 들어가면 그리디 문제일 가능성이 높습니다.
위에서 잠깐 말했던 최소 신장 트리도 그리디의 일종입니다.메모
1. 아스키코드 변환
ord(value) # 역으로는 chr
2. 조합
from itertools import combinations
from itertools import permutations
list(map(''.join,combinations( arr , 1 )))
3. 절대값
abs(value)
4. 문자열 리스트 합치기
text = ''.join(arr)
5. 최대 공약수
import math
math.gcd(21, 14) #7
6. 펙토리얼 factorial
import math
math.factorial(5) #120
7. 제곱근, 제곱
import math
math.sqrt(16) #4
math.pow(2, 4) #16
6. 문자열 수식 자동계산
eval("(3 + 5) * 7") #56
7. bisect ?
이진 탐색을 쉽게 구현할 수 있도록 제공되는 라이브러리1.해시
key-value문제
from collections import defaultdict
dic = defaultdict(lambda: 'default value')2.스택/큐
LIFO,FIFO
1. push, pop이 빈번한 경우
from collections import deque
arr = deque()
2. deque 회전
arr.rotate(-1)3.힙
최소값, 최대값을 우선순위 큐로 확인
import heapq
arr = []
heapq.heappush( arr , value )
heapq.heappop( arr )
1. 제일 큰값, 제일 작은값
heapq.nlargest(1, arr )
heapq.nsmallest(1, arr )4.정렬
정렬문제
1. 기본정렬
sorted(arr, key = lambda x : x)
2. 정렬 기준이 여러개
sorted(arr, key = lambda x : (x[0], x[1]))5.완전탐색
완전탐색
6.탐욕법
부분계산으로 전체를 계산
7.동적계획법
점화식
8.DFS,BFS
깊이/너비 우선 탐색 ?
9.이분탐색
정렬이후 반씩 나눠가며 최적의 값을 접근
10.그래프
배열로 노드를 만들고 비용계산 ?
11.구현
구현
www