내가 이해한 알고리즘 문제를 푸는 법
1. 문제를 이해하고 길을 깔아준다 = 데이터를 정렬해준다.
여기가 자료형 : 리스트, 튜플, 딕셔너리, 문자형, 숫자형
-
필드속성을 정해준다 = 자료구조를 뭘로 해야 가장 빠를지 생각한다.
여기가 자료구조 : 큐, 데크, 그래프, 스택 -
컴퓨터에게 어떤 길로 가야하는지 알려준다.
여기가 알고리즘 기법 : 백트래킹, 브루트포스, dfs, bfs -
컴퓨터가 가져온 걸 정답코드 형태로 출력할 수 있게 다시 바꿔준다.
가져올때 잘 가져오면 굳이 바꾸지 않아도 되지만
잘 가져오려다가 시간복잡도가 너무 높아져서 시험에 실패할 수 있으니까
1, 2, 3에서도 4를 고려하는게 좋다!
저 작업을 간편하게 만들어주는 라이브러리, 함수 등이 있지만 어쨌든 기본 구조는 저렇다.
오늘은 그래프를 이해해야 한다.
그래프는 자료구조다!
그래프는 객체들의 '일부' 페어가 연관되어 있는 객체집합구조를 말한다고 한다.
그래프를 표현하는 방법에는 인접행렬과 인접리스트가 있는데,
인접리스트는 연결리스트의 상위 개념이라고 생각하면 될것 같다. 모든 노드는 건너건너 넓게 보면 연결되어 있지만 한 노드와 다른 노드가 반드시 연결되어 있지는 않다!
어떤 자료구조를 이해한다는 것은
1. 그 구조가 어떤식으로 작동하는지 이해한다.
2. 그 구조의 예시를 구현할 수 있다.
3. 어떤 문제에 그 구조를 쓸 수 있을지 상상할 수 있게 된다!
앞서 스택은 후입선출 큐는 선입선출, 데크는 양쪽으로 출입가능하다는 것을 배웠다.
이제 개발자는 데이터 정렬 후에 컴퓨터가 데이터를 물어올때 어느 경로로 어떻게 갈지를 지정해줌으로써 좀더 빨리 물어오게 할 수 있는 능력을 얻은 것이다.
dfs와 bfs는 그래프를 탐색하는 방법이다!
dfs는 Depth-First-Search
하나를 깊이 판다!
1이 234로 연결되어 있다면
1찾고 2찾고 2의 자식노드(연결된 모든 하위노드)들을 다 찾은 다음에 3을 찾는다.
얘는 탐정같은 애다.
혼자서 실마리를 따라 돌진한다.
뭔가 찾아야 하는게 있을때 bfs보다 빠르다.
dfs에는 스택, 재귀를 사용할 수 있다.
bfs는 Breadth-First-Search
같은 단계에 있는 인접 노드를 풀스캔한다!
1이 234로 연결되어 있다면
1찾고 234찾고 234의 인접노드(딱한칸범위 =직접인접)들을 다 찾은 다음에
걔들이 인접한 노드가 있는지 찾는다.
코테에서는 dfs를 주로 쓴다고 한다.
얘는 실종자수색같은 애다.
손에 손을 잡고 한걸음씩 걸으면서 넓게 조금씩 전진한다.
어떤 길로 가는 최단경로 찾기에 자주 쓴다.
bfs에는 큐와 데크를 사용할 수 있다.
그래프를 실전에서 사용할 때
1) 그래프의 모든 정점을 방문하는 것이 중요할 때
단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 둘다 괜찮음
다만 그래프의 크기가 크다면 DFS를 고려하는게 좋고,
검색대상의 규모가 크지 않고, 검색 시작 노드로부터 하위노드가 멀지 않으면 BFS
2) 경로의 특징을 저장해둬야 하는 문제
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용.
3) 최단거리 구해야 하는 문제
미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리.
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문.
