[알고리즘 특강 1일차] 알고리즘이란, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 이해와 활용

 

 

알고리즘 특강을 들으면서 인상 깊었던 내용을 정리합니다.
자세한 개념보다는 알고리즘의 '이해' 그리고 '활용'(팁)에 중점을 두었습니다.
내용이 이상하다면 지적해주시면 감사하겠습니다. 👍

 

 

 

 

 

 

 

안녕하세요 오늘은 알고리즘 1일차로 DFS와 BFS를 공부하였습니다.

아직 알고리즘 초보자로 많은 고생을 하고 있었는데

아래 내용을 듣고 배우면서 너무 유익하다고 느껴 기록하고 공유하고 싶어서 포스팅 합니다 !

 

 

 

 

 

---

먼저 알고리즘 이란 ?

 

 

 

 

알고리즘이란 뭘까요 ?

 

알고리즘은 수학자 알콰리즈미(Al-Khwarizmi)에서 유래했고

'문제를 해결하기 위한 여러 동작들의 모임'을 의미합니다.

 

먼저 알고리즘은 완전탐색이 시작입니다.

저희는 이런 알고리즘을 이용하기 위해서는 복잡한 구조의 코드를 정확하게 구현할 수 있어야 합니다.

 

물론 쉬운 일이 아니지만 이를 빠르게 배울 수 있는 방법이 있을까 했지만 돌아온 답변은...

 

 

👩‍🏫 : 구현력은 항상 연습하고 연습하고 연습한 다음에 연습해야 한다.

 

라고 하셨습니다 ㅋㅋㅋㅋㅋ

 

이러한 구현력 향상을 위해서는 알고리즘의 조건을 항상 생각하면서 코딩하는 것이 좋습니다.

다음과 같이 6가지 조건이 있습니다.

1. 정밀성
2. 유일성
3. 입력
4. 출력
5. 유한성
6. 일반성

이러한 6가지 조건 중 저는 '유한성'과 '일반성'이 정말 가장 중요하다고 생각합니다.

 

알고리즘을 구현할 때 우리는 특정 조건이 작업 되면 이후에 '정지'해야 하고

알고리즘에 입력할 값들에 대해서 '일반적'으로 사용이 가능해야 하기 때문입니다.

 

 

저는 오늘부로 '구현력' 연습과 '지식' 그리고 그를 토대로 '응용력'도 높이려고 합니다.

 

 

 

 

 

 

 

---

 

깊이 우선 탐색 (DFS) 란?

깊이 우선 탐색은 그래프 탐색 방법 중 한가지 입니다.

한 경로로 탐색하다 특정한 상황에서 최대한 깊숙하게 들어가서 확인 후 돌아가 다른 경로로 탐색합니다.

 

 

 

 

 

 

구현 방법

일반적으로 재귀함수를 이용하여 구현합니다.

 

 

 

주의점

구조상 StackOverflow를 주의해야 합니다.

만약 스택오버플로우(Stack Overflow)가 발생한다면 루프를 탈출하지 못하여 계속해서 함수를 호출하고 있을 가능성이 높습니다.

 

 

 

DFS 구현 팁 👍

TIP 1

dfs 메서드에 다음 6가지 순서를 주석으로 두고 조건들을 생각하여 적은 후에 구현합니다.

이 때 들여쓰기가 구현할 때 조건문으로 들어가기 때문에 헷갈리지 않고 작성해야 합니다.

1. 체크인
2. 목적지인가 ?
3. // 목적지면 return
4. 연결된 곳 순회
   1. 갈 수 있는가 ?
      1. 간다
      2. // dfs() 호출
5. 체크 아웃

 

 

 

TIP 2

DFS는 함수를 호출하면 Stack에 함수가 쌓이게 됩니다.

이 때 Stack에 있는 것들은 ‘내가 이미 방문 한 곳’ 임을 기억해둡시다.

 

 

 

TIP 3

“연결"과 “갈 수 있다" 는 엄연히 다른 의미를 가지고 있습니다.

예시로 방향 그래프를 생각하면 좋습니다.

노드와 노드가 “연결"이 되어 있는 것만 보고 무조건 “갈 수 있다"라고 생각하는 것은 큰 착각임에 주의합시다.

 

 

 

 

TIP 4

알고리즘 구현할 때 아래와 같은 절차로 접근해봅시다.

1. 먼저 TIP 1에서 나온 주석을 작성합니다.
2. dfs 코드를 작성합니다.
   1. 이 때 전체를 다돌게 가장 간단하게 구현합니다.
   2. 전체를 다 돌게 되었을 때 이제 조건을 걸어 날릴 수 있는 부분을 날려줍니다.
3. 나머지 디테일 한 내용을 작성해 줍니다.
   1. 메서드 분리 가능하면 분리해줍니다.

 

 

 

재귀 함수를 이용한 완전 탐색 정리

알고리즘은 완전탐색이 첫 시작입니다.

완전 탐색은 시간복잡도를 작게 만들어 주는 것이 목표입니다.

완전 탐색을 설계, 구현 할 수 있다는 것은 문제의 정의와 조건을 정확하게 파악했음을 의미합니다.

결국 완전 탐색을 구현하려면 재귀 함수를 자유롭게 다뤄야 합니다.

 

 

 

 

---

 

 

너비 우선 탐색 (BFS) 란 ?

너비 우선 탐색도 깊이 우선 탐색과 마찬가지로 그래프 탐색 방법의 한가지 입니다.

시작 노드에서 인접한 노드를 먼저 탐색하는 방식입니다.

 

 

 

구현 방법

보통 큐(Queue) 자료구조를 이용합니다.

 

 

 

BFS와 DFS 구별하는 법

 

 

보통 두 가지 일이 동시에 벌어지는 상황에서는 BFS를 사용합니다.

예를 들면 2차원 배열에 각각 두 지점이 동시에 배열 내에서 움직인다고 했을 때는 BFS를 사용하는 것이 좋습니다.

DFS로 구현하게 되면 훨씬 많은 조건 구현 때문에 매우 까다로울 수 있습니다.

 

 

 

BFS 구현 팁 👍

TIP 1

bfs를 구현할 때 다음 6가지 순서를 주석으로 두고 조건들을 생각하여 적은 후에 구현합니다.

이 때 들여쓰기는 구현할 때 조건문으로 들어가기 때문에 헷갈리지 않고 작성해야 합니다.

1. 큐에서 꺼내옴 (*디큐 : 방문을 의미한다.)
2. 목적지 인가 ?
3. 연결된 곳 순회
   1. 갈 수 있는가 ? (*중복방지)
      1. 체크인
      2. 큐에 넣음

 

 

TIP 2

BFS는 Queue에 데이터가 쌓이게 됩니다.

이 때 Queue에 있는 것들은 ‘내가 이후 방문 할 곳’ 임을 기억해둡시다.

 

 

 

TIP 3

“연결"과 “갈 수 있다" 는 엄연히 다른 의미를 가지고 있습니다.

예시로 방향 그래프를 생각하면 좋습니다.

노드와 노드가 “연결"이 되어 있는 것만 보고 무조건 “갈 수 있다"라고 생각하는 것은 큰 착각임에 주의합시다.

 

 

 

 

TIP 4

알고리즘 구현할 때 아래와 같은 절차로 접근해봅시다.

1. 먼저 TIP 1에서 나온 주석을 작성합니다.
2. bfs 코드를 작성합니다.
   1. 이 때 전체를 다돌게 가장 간단하게 구현합니다.
   2. 전체를 다 돌게 되었을 때 이제 조건을 걸어 날릴 수 있는 부분을 날려줍니다.
3. 나머지 디테일 한 내용을 작성해 줍니다.
   1. 메서드 분리 가능하면 분리해줍니다.

 

 

 

 

 

 

 

---

BFS 연습 문제

[백준] 3005번 - 탈출

 

 

DFS 연습 문제

[백준] 1062번 - 가르침

 

 

1759번: 암호 만들기