✔️ 알고리즘 종류
1. 문제가 나왔을 때 (어려운 난이도 코테 빼고) 예상할 수 있는 유형들
- 시뮬레이션(구현)
- DFS / BFS
- DP
- 그리디
- 이분탐색
- 최단경로
- 자료구조 구현
- 정렬
- 백트래킹
- 브루트포스
- 분할정복
- 투포인터
2. 난이도 중일 경우 예상할 수 있는 유형들
- DFS / BFS
- 자료구조(힙,스택,큐,트리)
- 시뮬레이션 혹은 브루트포스
- DP
- 이분탐색
3. 난이도 중상일 경우 예상할 수 있는 유형들
- DP
- 자료구조(트리 포함)
- 투포인터
- 어려운 시뮬레이션
- 그리디 / 그래프
4. 난이도 상일 경우 예상할 수 있는 유형들
- 트리
- 어려운 시뮬레이션
- 문자열
- DP
- 이분탐색
- 그리디 등등...
✔️ 문제 분석
1. 문제 접근 순서
- 문제를 처음보자마자 알고리즘을 바로 떠올리긴 힘들기 때문에, 이 문제를 풀 수 있는 로직과 시간복잡도를 먼저 생각하자. 문제에 집중하며 한번 끝까지 쭉 읽어보자
1) 문제 설명을 들으면서 로직에 먼저 집중 한담에 그 담에 제약조건을 생각
2) 로직을 보면 알고리즘 후보들이 좁혀짐. 그 다음에 시간복잡도 등의 제약조건과 자료구조 등을 고려
ex) 그래프가 나오면 후보에 DFS/그리디/백트래킹/브루트포스/최단경로 등이 좁혀질 것. 시간복잡도를 보며 브루트포스는 안되겟다, 배열을 다 만들기 힘드니까 하나씩 왓다갓다하는 BFS는 힘들겟다..)
3) 남은 조건들 생각해서 내가 감이 오는(...)거로 사이즈 나오나 각을 본다.
4) 될것같다!하면 하는거고 그러다 안될것같으면 아까 생각해놧던 것도 생각해보거나 짬뽕하는 방식으로 해보자
2. 시간복잡도 계산
- 초당 2000만번 연산
| 500 (5백) | O(N³) |
| 2,000 (2천) | O(N²) |
| 100,000 (10만) | O(NlogN) |
| 10,000,000 (천만) | O(N) |
수행 시간 측정
import time
start_time = time.time() # 측정 시작
# 프로그램 소스코드
end_time = time.time() # 측정 종료
print('time:', end_time - start_time) # 수행 시간 출력3. 입출력
▶ 빠르게 입력받기
- import sys
input = sys.stdin.readline().rstrip()
▶ 재귀 범위 해제하기
import sys
sys.setrecursionlimit(10**6)
▶ sep / end 출력하기
- sep : print문의 출력문들 사이 값들 정의 ( default = "")
ex) print("I","Like","쿼카",seq = ",") ==> I,Like,쿼카
- end : print문으로 출력 완료 후의 값 정의 (default = \n)
ex) print(array,end = "!") ==> [1,2,3]!
▶ format 출력
- 특정 서식에 따라 문자를 출력
- print( "{0}월 {1}일 입니다.".format(8,2) ) #str.format(값1,값2)
- print( "나는 %s를 %d번째로 좋아한다.".format("쿼카",2)
▶ 특수 문자 출력
- \\ : '\' 출력
- \' : 작은따옴표 출력
- \" : 큰따옴표 출력
4. 라이브러리
1) itertools
▶ permutations (순열)
- result = list(permutation(data, 3))
▶ combinations (조합)
result = list(combinations(data, 2))
▶ products (중복순열)
result = list(product(data, repeat=2)) # 2개를 뽑는 모든 순열 구하기(중복 허용)
▶ combinations_with_replacement(중복조합)
- result = list(combinations_with_replacement(data, 2)) # 2개를 뽑는 모든 조합 구하기(중복허용)
2) heapq
O(NlogN)에 오름차순 정렬을 제공
▶ heappush() : 원소 삽입
▶ heappop() : 원소 꺼내기
> heapfiy() : 리스트를 heap형태로 바꿔줌(이 때, 반환하는 형태는 없고 원본 리스트를 바꾸는 것임)
3) bisect
O(logN)에 정렬된 배열에 맞는 위치를 찾아준다.
'정렬된 리스트'에서 특정 범위에 속하는 원소의 개수를 구하는데 효과적
▶ bisect_left(arr, x) : 리스트 arr에서 데이터 x를 삽입할 가장 왼쪽 인덱스. x가 a에 이미 있으면 기존 항목의 앞 (왼쪽)의 위치를 반환
▶ bisect_right(arr, x) : 리스트 arr에서 데이터 x를 삽입할 가장 오른쪽 인덱스. x가 a에 이미 있으면 기존 항목 뒤 (오른쪽)의 위치를 반환
from bisect import bisect_left, bisect_right
a = [1, 2, 4, 4, 8]
x = 4
print(bisect_left(a, x)) # 2
print(bisect_right(a, x)) # 4
4) collections
▶ deque
- 가장 앞/뒤에 데이터 삽입 삭제가 용이
- queue가 양방향으로 작동할 때
- 리스트의 경우는 가장 앞에 삽입삭제 시 O(N)
#리스트 형태를 뒤에 추가
d.extend(arr)
#리스트 형태를 왼쪽에 추가
d.extendleft(arr)
# 값 삭제
d.remove(val)
# 회전 (양후면 오른쪽,음수면 왼쪽9
d.rotate(n) #n만큼 회전▶ Counter
- 등장 횟수를 세는 기능
- Counter Dictionary 로 반환
lst = [1, 2, 3, 3, 2, 1, 1, 1, 2, 2, 3, 1, 2, 1, 1]
counter = Counter(lst)
print(counter)
# >>> Counter({1: 7, 2: 5, 3: 3})- counter.most_common(n) : 가장 개수가 많은 n개 값을 list 형태로 반환
▶ defaultdict
- dictionary와 유사하지만, 존재하지 않는 key에 접근해도 에러가 출력되지 않는다.
- arr = defaultdict(int)
5) math
- 종류
- math.factorial() : 팩토리얼
- math.sqrt() : 제곱근
- math.gcd() : 최대공약수
- math.pi : 파이
- math.e : 자연상수
6) 내장 함수
▶ filter()
- 원본 리스트에서 원하는 요소만 추출한 리스트
- arr2 = list(filter(lambda x : x<= K, arr1)) #arr1에서 K이하인 대상만 추출한 리스트
✔️ 알고리즘 별 예상 접근 방법
1. 시뮬레이션(구현)
- 인풋의 범위가 생각보다 크지 않는 경우가 많음
- 뭔가 문제가 복잡하고 은근히 꼼꼼하고 더럽게 자세히 알려줌(문제 읽으면서 슬쩍 눈치를 챌 수 도 있음)
- 이런문제는 째깐한 예외 케이스 처리하는게 어려운 것이기 때문에, 크게 수도코드를 잡고 나서 얼른 코드 작성해보고 테케 돌리면서 조금씩 완성도 높이기
2. DFS / BFS
- 길같은 문제가 나오거나, 먼가 애들이 자꾸 퍼지려(?) 함, 혹은 자꾸 어딘가 찾아가려 함
- 한 단계씩 방법을 거치면서 최종적으로 내가 원하는 방법에 도달할 수 있는지에 대한 문제에도 나옴
- 눈치껏 풀자
3. DP
- 그냥 구현하게 되엇을때 똑같은걸 또 확인해야하는 로직이 보임
- N번째 값을 알면 다음 값을 알수 잇을법한 같은 느낌이 들때
- 수학같기도 하고.. 뭔가 본인만의 규칙을 가지고, 최소값이나 최댓값을 구하려 함
- 난 쪼랩이므로 Top-down 방식 먼저 생각하자
- N번째 값을 알려면 몇번째 값들을 알아야 하나?를 생각하고, 재귀적으로 값들을 구하도록 함수를 재귀호출
- top-down을 사용한 경우 recursion depth 관련 오류 발생가능. 'setrecursionlimit()'함수를 호출하기
4. 그리디
- 패킷 처리, 콘센트등의 문제에서 했었음
-
5. 이분탐색
- 일단 인풋이 크면 1순위로 생각해보기
- 효율성이 중요할것 같으면 1순윅로 생각해보기
- 정렬이 자동으로 되어잇거나 필요하면 2순위 정도로 생각해보기
- 최대,최솟값 문제로 나오는 경우 있음
- 큰 틀은 left, right를 내가 문제로 지정이 가능한지를 먼저 보자. 그 담에 mid값으로 무언가 판단이 되어야 함
6. 최단경로
- 다익스트라 : 특정 노드 -> 모든 노드 // heap과 visited와 distance가 필요
- 플로이드 워셜 : 모든 노드 -> 모든 노드 // DISab = min(DISab,DISak + DISkb)
- 벨만포드 : 특정 노드 -> 모든 노드 // 음의 간선 가능, 매 반복마다 모든 간선 확인(visited 필요 없음)
7. 자료구조 구현
8. 정렬
9. 백트래킹
10. 브루트포스
- 사실상 구현과 다름 없음
- 기본적으로 브루트포스를 먼저 생각해보고, 거기서 개선이 가능하면 이제 다른 알고리즘으로 가는 형태
- 알고리즘계의 마지막을 지키는 아주 고마운 알고리즘
11. 분할정복
- 보드가 나오고, 뭔가 프렉탈같은게 나오면 일단 1순위 정도로 생각해보기
- 많이는 안나오지만 한번 나오면 존재감이 강한 친구이므로 알고잇으면 도움이되는 알고리즘
12. 투포인터
- 시간복잡도 개선이 필요할 때 생각할 수 있음(O(N)정도에 끝낼 수 있으므로..)
- 라인스위핑, 세그먼트등이 나오면 사실 난 못풀어. 중요한건 내가 못푸는 문제라는 걸 빨리 인지하는것!
- 정렬도 같이 서브로 묶어서 나올 수 있고, 뭔가 탐색은 해야하는데 인풋이 클때..
13. 집합
-- 알고리즘 별 예제 --
DP
'''
17291
새끼치기
홀수에 태어남: 3번 분열 후 사망
짝수에 태어남 : 4번 분열 후 사망
i번째 해에 존재하는 벌레 수 = (i-1)번째에 존재하는 벌레 수 * 2 - (짝수인경우, i-3,i-4번째에 태어난 벌레 수)
'''
import sys
input = sys.stdin.readline
if __name__ == "__main__":
N = int(input())
create_bugs = [0] * 21 # i번째 해에 태어난 벌레 수
all_bugs = [0] * 21 # i번째 해에 존재하는 벌레 수
all_bugs[1] = 1
all_bugs[2] = 2
all_bugs[3] = 4
all_bugs[4] = 7
create_bugs[1] = 1
create_bugs[2] = 1
create_bugs[3] = 2
create_bugs[4] = 4
for i in range(5, N + 1):
#i번째 해에 태어난 벌레 수
create_bugs[i] = all_bugs[i - 1]
#i번째 해에 존재하는 벌레 수
if i % 2 == 0:
all_bugs[i] = all_bugs[i - 1] * 2 - create_bugs[i - 3] - create_bugs[i - 4]
else:
all_bugs[i] = all_bugs[i - 1] * 2
print(all_bugs[N])
-- 구간합 구하기 5 (DP대표 예제!!꼭 알아두기)
'''
11660
구간합구하기5
(x1,y1)을 왼쪽 상단 꼭짓점, (x2,y2)를 오른쪽 하단 꼭짓점으로 하는 직사각형 범위의 합
'''
import sys
input = sys.stdin.readline
if __name__ == "__main__":
N, M = map(int,input().split())
# arr의 index를 맞추기 위해 맨 위 / 맨 왼쪽에 배열 삽입
arr = [[0] * (N + 1)]
for _ in range(N):
tmp = [0]
tmp.extend(list(map(int,input().split())))
arr.append(tmp)
#dp[i][j] = (1,1)에서 (i,j)까지 직사각형범위에 있는 수들의 합
dp = list([0] * (N + 1) for _ in range(N + 1))
for i in range(1, N + 1):
for j in range(1, N + 1):
dp[i][j] = arr[i][j] + (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1])
# M개의 테스트 케이스
for _ in range(M):
x1, y1, x2, y2 = map(int,input().split())
#x1,y1에 1씩 빼야 함
x1 -= 1
y1 -= 1
print(dp[x2][y2] - dp[x1][y2] - dp[x2][y1] + dp[x1][y1])
2. DFS / BFS
- 아기상어2 : 퍼지는 대상들과의 최단거리 중 가장 먼 거리를 구할 때도 BFS가 쓰일 수 있다!! 이 때, 퍼지는 대상들을 큐에 넣고 최단거리 update한 뒤 가장 큰 distance를 출력하면 됨
-- 알고리즘 별 주의 사항 --
1. 시뮬레이션(구현)
2. DFS / BFS
3. DP
4. 그리디
5. 이분탐색
6. 최단경로
- 브루트포스 : 만약 a->b로 가는 경로가 2가지 이상이면, visited[]배열 쓰면 안됨
7. 자료구조 구현
- heapfiy :
8. 정렬
9. 백트래킹
10. 브루트포스
11. 분할정복
12. 투포인터
-- 자료구조 별 접근 방식--
-- 자료구조 별 주의 사항--
- 리스트 : 만약 좌표가 (1,1)에서 시작한다면 사이즈도 (N+1)로 만들자(직관적으로 보기 편하게)
- extend : 1차원 리스트의 오른쪽에 "값"들을 추가하는 느낌
- append : 기존의 리스트는 끝나고, 그 다음에 새로운 "리스트"형태로 추가 []가 붙음
-- 맨 앞이랑 맨 왼쪽에 값 더하는 방법
# arr의 index를 맞추기 위해 맨 위 / 맨 왼쪽에 배열 삽입
arr = [[0] * (N + 1)] #이렇게 맨 밖에 []추가 해야 함!!!!!!!!!
for _ in range(N):
tmp = [0]
tmp.extend(list(map(int,input().split()))) #[0] 오른쪽에 배열 합치기
arr.append(tmp) #다음 줄에 tmp리스트 추가하기--자주 실수하는 에러들--
'알고리즘 > 코테 준비' 카테고리의 다른 글
| [코테 문제 유형 정리] (0) | 2021.10.08 |
|---|---|
| [코테 정리] (0) | 2021.10.08 |
| 코딩테스트 대비 백준 문제 뽀개기 : dp (0) | 2021.09.30 |
| 코딩테스트 대비 백준 문제 뽀개기 : 기초 백준 문제 추천 (0) | 2021.09.27 |
| 코딩테스트 대비 백준 문제 뽀개기 : 준비운동 PART2. 약점 체크 (0) | 2021.09.22 |
