어디까지 갈 수 있을까?

코테 풀 때 생각해야 할 것 본문

알고리즘

코테 풀 때 생각해야 할 것

_Min 2021. 4. 28. 22:07

내가 부족한 것

- 입력수보고 알고리즘 유추하기

- 최고가 아니라도 내가 할 수 있는 최선으로

- in & not in 잘 쓰기

- 문제의 기초 정의에 입각해 푸는 것

- 부분적으로 쪼개서 생각하는 것

- 시간 복잡도를 낮추기 위해 메모리를 더 쓰기

- 최단거리 -bfs(가중치 동일), 다익스트라(가중치 다름)

- 가지치기 dfs

- 오래 걸리면 아이디어만 주석으로 달아놓고 넘어가기

 

DFS

- 종료조건

- 반복문을 간결하게 표현(반복문으로 될 것 같은데 인자값이 계속 변할 때)

- 트리로 이해하기

- depth=재귀함수 call하는 횟수

- 방향 없이 쭉 이어지는 느낌

 

DP

- 처음 : 다 만들어 볼까?

-> 너무 많으면 DP

-영향을 주는 요인 갯수에따라 배열 차원을 나눈다

-현재 값과 현재값의 이후면서 현재 값에 영향을 받는 것들로 범위가 나뉜다

 

BFS

visited[nr][nc]

 

구현

구현 순서 순차적으로 1,2,3,4 넘버링해서 생각한 다음 풀기

 

index가 필요하지 않은 자료구조 일 때 set 쓰는 것 추천

 

1초 = 10^8 번의 연산

 

728x90
Comments