어디까지 갈 수 있을까?
코테 풀 때 생각해야 할 것 본문
내가 부족한 것
- 입력수보고 알고리즘 유추하기
- 최고가 아니라도 내가 할 수 있는 최선으로
- in & not in 잘 쓰기
- 문제의 기초 정의에 입각해 푸는 것
- 부분적으로 쪼개서 생각하는 것
- 시간 복잡도를 낮추기 위해 메모리를 더 쓰기
- 최단거리 -bfs(가중치 동일), 다익스트라(가중치 다름)
- 가지치기 dfs
- 오래 걸리면 아이디어만 주석으로 달아놓고 넘어가기
DFS
- 종료조건
- 반복문을 간결하게 표현(반복문으로 될 것 같은데 인자값이 계속 변할 때)
- 트리로 이해하기
- depth=재귀함수 call하는 횟수
- 방향 없이 쭉 이어지는 느낌
DP
- 처음 : 다 만들어 볼까?
-> 너무 많으면 DP
-영향을 주는 요인 갯수에따라 배열 차원을 나눈다
-현재 값과 현재값의 이후면서 현재 값에 영향을 받는 것들로 범위가 나뉜다
BFS
visited[nr][nc]
구현
구현 순서 순차적으로 1,2,3,4 넘버링해서 생각한 다음 풀기
index가 필요하지 않은 자료구조 일 때 set 쓰는 것 추천
1초 = 10^8 번의 연산
728x90
'알고리즘' 카테고리의 다른 글
[구현] 프로그래머스 행렬 테두리 회전하기 (0) | 2021.05.02 |
---|---|
시간복잡도 O(logN) 빅오표기법 (0) | 2021.02.16 |
백준 10817번(세 수), 3가지 풀이법 (0) | 2020.03.04 |
Comments