회고록(20) - BFS, DFS

1. 데일리 일기

오늘은 알고리즘 공부와 선참시에 대해 써보려고 한다.

알고리즘 공부 관점

점점 알고리즘 공부의 난이도가 올라가면서 교육에서 알려주는 모든 알고리즘을 이해하기에는 시간이 부족해지고 있다. 배우는 자료구조, 알고리즘의 개념들도 많고 문제들도 쌓이고 있다. 현재까지는 어떻게든 내 손으로 좀 풀어보려고 했으나 해당 전략은 적어도 부트캠프기간동안 하기에 좋은 공부법은 아니란 생각이 들었다.

어떻게 공부해야 할까?

일단 내가 현재 알고리즘을 배우는 이유가 무엇일까?

지금 당장 코딩 테스트를 통과하기 위해서? 알고리즘에 대한 호기심? 알고리즘을 이용한 효율적인 코드작성??

아니다. 언젠간 위의 목적을 위해 알고리즘을 사용해야 하지만 현재 내 상황에서 배우는 이유는 다음과 같다.

• 이러한 알고리즘과 자료구조의 존재를 알고 구현해보기
• 다양한 알고리즘 문제들을 접하며 해결하는 과정 경험하기
• 구현하고 활용해보면서 Java 언어의 숙련도 높이기

그래서 어떻게 공부할 것인가?

1. 자료구조 또는 알고리즘 문제를 30분~1시간 정도 고민하며 수도코드와 코드를 작성한다.
2. 만약 방향이 잡히지 않는다면 레퍼런스코드를 보고 핵심 로직을 파악하고, 혼자서 핵심 로직을 구현해 본다.
3. 나중에 해당 문제를 또 다시 풀어본다.

순수한 목적으로 과거의 수학자들이 수학을 공부했듯이 알고리즘을 공부하면 좋겠지만, 나에게 주어진 재능과 시간은 너무 짧다. 다양한 유형을 경험해보고 구현해보며, 필요한 유형들에 먼저 익숙해지도록 하자. 응용은 그 다음이다.

2. 오늘 배운 내용

BFS

정의

너비 우선 탐색으로 루트 정점과 가까이 있는 정점들을 우선적으로 탐색하는 방식이다.

주로 Queue를 통해 구현한다.

장단점

장점

• 여러 원하는 정점까지의 여러 경로들 중 루트정점과의 최단 거리를 알 수 있다.

단점

• 경로가 매우 많아지게 되는 경우, 보다 많은 메모리 낭비를 일으키고 실행자체가 느려질 수 있다.

DFS

정의

깊이 우선 탐색으로 루트 지점에서 처음 지정한 경로의 최대 깊이를 먼저 탐색하고 다음 경로로 넘어가는 방식이다.

주로 재귀와 스택을 통해 구현한다.

장단점

장점

• 원하는 정점이 깊은 곳에 위치한 경우, 사용하면 BFS 보다 훨씬 빠르다.

단점

• 원하는 정점을 발견했을때 해당 정점까지가 최단거리라고 보장할 수 없다.

Deque

정의

Queue와 Stack의 장점을 모두 합친 자료구조로, 양방향으로 입출력 가능한 자료 구조입니다.

특징

1. 각 방향에 Queue 또는 Stack 구조로 만들어 양방향 입출력이 가능하다.
2. 양방향 끝에서 데이터 추가/삭제가 가능합니다.
3. 양방향이 아닌 임의의 위치에서 데이터 추가, 삭제는 불가능합니다.

LinkedList

정의

요소로 데이터와 다음 데이터가 존재하는 주소값을 선형으로 저장하고 있는 자료구조입니다.

특징

1. 주소값만 바꾸면 되므로 데이터의 추가 및 삭제가 매우 빠릅니다.(시간복잡도 : O(1))
2. 원하는 노드 값을 탐색할때는 비효율 적입니다.(시간복잡도 : O(1) ~ O(N))
   • Head node(첫 요소)의 정반대인 맨끝의 노드 값을 탐색해야한다면 최대 O(N)의 시간복잡도를 가집니다.
3. 주로 삽입과 삭제를 주로 필요로 하는 클래스나 메서드에 구현되어 사용됩니다.

HashTable

정의

keys 를 해시함수에 통과시켜 해쉬로 만든 후, 그 해쉬를 인덱스로 하여 키와 데이터를 저장하고 있는 자료구조를 말한다.

쉽게 말해서 핸드폰 단축번호의 개념이다.

특징

장점

• 해쉬를 저장, 삭제 검색하는 시간 복잡도가 O(1) 밖에 되지 않는다. 그러므로 데이터를 다루는 작업이 매우 빠르다.

단점

• 해쉬 충돌의 경우 시간 복잡도가 O(N) 까지 올라 갈 수 있다.
• 데이터가 저장되기 전에 미리 저장공간을 만들어야 하므로, 공간효율성이 떨어진다.
• 해시 함수에 대한 의존도가 높다.
  • 함수가 너무 복잡하면, 해시를 만드는데 오랜 시간이 걸린다.

해시 알고리즘

• Division Method : Number type 의 key를 저장소의 크기로 나누어 index(해시)로 사용하는 알고리즘
• Digit Folding : 문자열을 ASCII로 바꾸고 , 전부 합하여 그 값을 색인으로 쓰는 방법
• Multiplication Method : 숫자 key = K, 0~1 사이의 숫자 = 실수 A, 2의 제곱수인 m 을 사용하여 index = (KA mod 1)m 를 사용하는 알고리즘
• Universal Hashing : 다수의 해시함수를 만들고, 무작위로 해시함수를 적용시켜 색인을 만드는 알고리즘

해시 충돌을 해결하는 방법 3가지

1. 개방 연결법(Open Addressing) : 해시 충돌 발생시, 다른 색인에 중복되는 자료를 넣는 방식
2. 분리 연결법(Seperate Chaining) : 해시 인덱스가 나타내는 요소값(bucket)에 중복값들을 연결리스트나 트리등의 자료구조로 저장하는 방식
3. 저장소 확장(Resize)

Hash Table의 실사용 예제

• Address Book(주소록)
• BlockChain
• JavaScript 실행엔진(크롬)
• DNS 시스템

Heap Tree

정의

트리 구조로 구현되있는 구조있지만, 우선순위가 존재하여 빠르게 데이터 자료를 검색할 수 있는 구조입니다.

특징

1. 완전 이진트리입니다.
   • 완전 이진트리는 중간에 빈 노드값이 없기때문에 배열로 나타낼 수도 있습니다.
   • 왼쪽 자식 노드의 index : 부모노드(index) * 2, 오른쪽 자식노드의 index : 부모노드(index) * 2 + 1
2. 중복된 값을 저장할 수 있다.
3. 최대힙/ 최소힙으로 구현한다.
   • 우선순위를 최대값을 루트에 놓을지, 최소값을 루트에 놓을지 결정하여 구현할 수 있다.

활용처

1. 우선순위 큐
2. 힙 정렬

3. 새로 알게 된 내용

우선순위 큐 : FIFO의 특징을 가진 큐와 다르게, 우선순위가 높은 요소들 부터 poll() 되는 큐를 말한다.