Week03 : 개발 일지(알고리즘 공부)

Week 03(04.14 ~ 04.21) : DFS, BFS, 위상정렬

 

DFS(Depth First Search) : 깊이 우선 탐색

- 그래프에서 깊은 부분을 우선적으로 탐구하는 알고리즘, 맹목적으로 각 노드를 탐색할 때 주로 사용된다.

- Stack(선입후출, append, pop), 재귀함수로 구현

 

백준 문제 : 트리의 부모 찾기, 이분 그래프, 아침 산책, 빙산, 구슬 찾기

 

동작 과정

 1) 탐색의 시작노드를 스택에 삽입하고 방문 처리를 한다.

 2) 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

 3) 더이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

정점인 0을 visited 목록에 넣고 모든 정점을 스택에 넣는다.

다음으로 스택 맨 위에 있는 요소 1을 방문하여 인접한 노드로 이동

정점 2에는 4에 방문하지 않은 인접 정점이 있으므로 스택 상단에 추가하고 방문한다.

마지막 요소 3을 방문한 후에는 방문하지 않은 인접 노드가 없으므로 Depth First Traversal을 완료

BFS(Breadth First Search) : 너비 우선 탐색

- 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

- 보통 queue(선입선출, append, popleft, deque 라이브러리 import) 자료 구조를 사용하여 구현

- 인접 노드 방문, 주로 최단 거리 문제

 

백준 문제 : 미로 탐색, 특정 거리의 도시 찾기, 최소비용 구하기, 토마토, 탈출

 

동작 과정

 1) 방문하지 않은 정점(또는 선택한 한 정점)에서 시작한다

 2) 현재 정점에서 갈 수 있는 정점을 모두 queue에 넣는다

 3) 방문할 정점이 이미 방문했던 정점이라면 queue에 넣지 않는다.

먼저 방문 여부를 확인할 Visit 배열을 false로 초기화하고, queue 생성, 1번 정점부터 탐색 시작

1번 정점을 방문하고 재 검색하지 않기 위해 Visit 배열을 1로 바꿔줌, 그 후에 1번 정점에서 갈 수 있는 점(2,3,5)를 queue에 넣어준다.

queue의 front에 있는 정점을 탐색한다. 2번 정점으로 가서 Visit 배열의 값을 1로 바꿔준다. 그 후에 2번 정점에서 갈 수 있는 정점(7,6)을 다시 queue에 넣는다.

 

queue에서 다시 front를 꺼내 탐색을 이어 나간다. 2번 정점에서 6을 넣었기 때문에 queue에 넣지 않아도 됨. 4를 넣어주면 된다.

queue에서 5를 꺼내 방문처리를 한다. 1은 방문 처리가 되었고, 4는 queue에 있기 때문에 넘어간다.

queue에서 6을 꺼내고 방문처리를 한다. 마찬가지로 넘어가도록 한다.

queue에서 7을 꺼내고 방문처리를 한다. 마찬가지로 넘어가도록 한다.

4를 꺼내고 방문처리를 하면 정점의 탐색도 끝이난다.

위상 정렬(Topology Sort) : 순서가 정해져있는 작업 관련 알고리즘

- '순서가 정해져 있는 작업'을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘

- 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

 

백준 문제 : 줄 세우기, 장난감 조립, 그래프 수정, 임계경로

 

동작 과정

 1) 진입 차수가 0인 정점(즉, 들어오는 간선의 수가 0)을 선택

     - 진입 차수가 0인 정점이 여러 개 존재할 경우 어느 정점을 선택해도 무방

     - 초기에 간선의 수가 0인 모든 정점을 큐에 삽입

 2) 선택된 정점과 여기에 부속된 모든 간선을 삭제

      - 선택된 정점을 큐에서 삭제

      - 선택된 정점에 부속된 모든 간선에 대해 간선의 수를 감소

  3) 위의 과정을 반복해서 모든 정점이 선택, 삭제되면 알고리즘 종료

위상 정렬 알고리즘 순서도

 

공부를 통해 느낀점

1. 그래프 영역은 공부를 하고 시작하는 것이 많다.

완벽하게 개념을 이해하고 활용까지도 할 수 있어야 한다!!

시험을 통해 느낀점

1. 머릿속으로 설계를 잘하고 구현을 시작해야한다

긴가민가 하고 시작을 해버리면 틀렸을 때, 해결하기가 쉽지 않다.

정해진 유형이 어떤 것인지 파악하고, 설계를 잘해야할 것 같다.

 

2. 그래프 유형 특성상, 공부한 것을 활용해서 풀어야하기 때문에

완벽하게 개념을 이해하고, 자유자재로 활용해야겠다고 생각했다.

이렇게 하지 않으면 짧은 시간 내에 구현하는 것이 쉽지 않겠다고 생각했다.

 

Week 03 느낀점

하루하루 열심히 하지만 뒤를 돌아봤을 때, 멍하는 순간이 있다. 그런 느낌이 이번 주에 들었던 것 같다.
너무 생각을 많이 하지말고 꾸준히 계속 하다보면 쌓인다는 것을 잊지말자.
특히, 내 페이스대로 많은 것을 하려하지말고 천천히 해 내가자.

 

 

출처 : https://miracleground.tistory.com/entry/%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89

https://dongdd.tistory.com/81

https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html