TIL_20220926

오늘 할 일

🤗 코드 스테이츠 25일차

[자료구조/알고리즘] 자료구조

• 연습문제 - Daily Coding
• Chapter - Graph, Tree Search Algorithm
• Pair / 연습문제 - Coplit - Graph / Tree / BST

다른거

• 1일 1커밋
• 아침 운동

오늘 배운 것

🔎 Search Algorithm

Tree traversal

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다. 숫자를 찾기 위해 모든 노드를 방문하는 경우는 트리 순회의 한 예시이다.

트리 구조는 계층적 구조라는 특별한 특징을 가지기 때문에, 모든 노드를 순회하는 방법엔 크게 세 가지가 있다. 아래의 그림을 통해 하나씩 알아보자.

 

포화 이진 트리(Perfect Binary Tree)

전위 순회 (preorder traverse)

A → B → D → H → I → E → J → K → C → F → L → M → G → N → O

 

중위 순회 (inorder traverse)

H → D → I → B → J → E → K → A → L → F → M → C → N → G → O

 

후위 순회 (postorder traverse)

H → I → D → J → K → E → B → L → M → F → N → O → G → C → A

BFS / DFS

그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적이다. 원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 한다.

• 지하철 노선도를 보여주는 애플리케이션에서 경로를 탐색할 때에는, 최단 경로나 최소 환승 등 하나의 목적에도 여러 가지 방법이 있다. 이처럼 그래프의 모든 정점 탐색 방법에도 여러 가지가 있다.
• DFS와 BFS는 데이터를 탐색하는 순서만 다를 뿐, 모든 자료를 하나씩 확인해 본다는 점은 같다.
• 그래프가 굉장히 크다면 깊이 우선 탐색을 고려해야 한다. 너비 우선 탐색의 경우, 한 레벨을 모두 탐색할 때까지 다음 경로를 탐색하지 않기 때문에 더 오래 걸리는 편이다.
• 반대로, 그래프의 규모가 작고, depth가 얕다면 너비 우선 탐색을 사용한다. depth를 위주로 탐색하기 때문에 depth를 깊게 내려가는 깊이 우선 탐색보다 더 효율적이다.

 

BFS(Breadth-First Search)

너비를 우선적으로 탐색하는 방법을 Breadth-First Search, 너비 우선 탐색이라고 한다. 주로 두 정점 사이의 최단 경로를 찾을 때 사용한다. 만약, 경로를 하나씩 전부 방문한다면, 최악의 경우에는 모든 경로를 다 살펴보아야 한다.

 

장점

• 단지 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다.
• 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

단점

• 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제로는 미리 지정한 임의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이 우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

 

DFS(Depth-First Search)

깊이를 우선적으로 탐색하는 방법을 Depth-First Search, 깊이 우선 탐색이라고 한다. 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용한다. BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있다.

 

장점

• 최적 해를 찾음을 보장한다.

단점

• 최소 실행시간보다는 오래 걸린다는 것이 거의 확실하다.
• 최악의 경우, 실행에 가장 긴 시간이 걸릴 수 있다.

다른거

 - 1일 1커밋

프로그래머스 사이트에서 Lv.2 다음 큰 숫자 문제를 풀었다. 분명 잘 풀었다고 생각했는데, 효율성 검사에서 시간 초과가 생겼다. 원인으로는 while문에 탈출 조건으로 return을 사용해서 나타난 문제였다. 그래서 return문을 아예 while문 바깥으로 빼주고 탈출문을 작성해줬다.

 

GitHub - chaning49/algorithm: 코딩테스트를 위한 알고리즘 공부

 

- 아침 운동

느낀점

• 오늘은 탐색 알고리즘을 배웠습니다. 역시나 탐색 알고리즘은 어려웠습니다... 특히 DFS와 BFS는 알고리즘 학습을 했을 때도 찍먹만 했던 내용이라 너무 어려웠습니다. 구현을 하는 부분에 대해서는 예전에 듣던 인강을 들어서라도 해봐야겠습니다.
• 오늘 연습문제 또한 난이도가 상상++++++(feat. 라붐)이었습니다. 페어분과 코드를 고치면서 화기애애(?)하게 시작했지만 결국 나중에는 둘 다 묵언수행을 하며 "되셨나요?..."라는 외마디만을 남긴채 페어 프로그래밍이 끝났습니다. ㅠㅠ 그래도 라이브 세션에서 문제 해설을 들으니 확실히 이해가 더 갔고, 저녁에 복습도 하니까 어떤 느낌으로 코드가 흘러가는지 정도는 알게 되었습니다!!
• 연습문제에 지쳐서 알고리즘 문제를 쳐다도 보기 싫었지만 프로그래머스 사이트에서 풀던 문제가 시간 초과로 틀렸던 기억이 나서 다시 풀어봤습니다. 아예 지우고 새로 시작했습니다.
• 오늘 아침에는 헬스장에 사람이 없어서 행복 운동하고 왔습니다!

내일 할 일

😂 코드 스테이츠 26일차

[자료구조/알고리즘] 코딩 테스트 준비

• 연습문제 - Daily Coding
• Chapter - Introduction
• Chapter - Time Complexity
• Chapter - Greedy Algorithm / Implementation

다른거

• 1일 1커밋
• 아침 운동