📕 자료구조와 알고리즘(심화)

✅ 트라이와 자동완성

📌 개념

• 자동완성 기능을 구현할 수 있는 최적의 자료구조

• retrieval에서 유래되었다.

이진트리는 아니라 자식 노드의 개수 제한이 없음

저장하려는 단어를 한 글자씩 저장해서 key엔 글자, value에는 자식 노드를 저장한다.

📌 성능

해시테이블 검색 시간 복잡도 = O(1)

트라이 시간 복잡도 = O(k) - 트라이에 저장된 노드 수에 따라 다름

✅ 그래프

📌 개념

트리는 그래프의 종류 중 하나이다. 트리는 그래프이지만 그래프는 트리가 아니다.

트리

• 노드는 부모와 자식으로 계층적 구조를 가지며

• 그래프에서 사이클이 없어야 한다.

• 연결되지 않는 노드가 있으면 안된다.

용어

• 정점: 노드

• 간선: 노드를 연결하는 선

• 인접(adjacent): 간선으로 연결된 정점

• 이웃(neighbor): 인접한 정점

a와 b는 인접해있으며 a는 b의 이웃이며 b는 a의 이웃이다.

방향 그래프: 양방향으로 간선의 방향이 정해져있음

무방향 그래프: 간선의 방향이 없음

📌 깊이 우선 탐색 알고리즘(DFS)

방문한 정점을 해시 테이블에 저장한다.

• 사이클이 있는 경우 무한 루프에 걸릴 수 있음

1. 현재 정점을 해시테이블에 방문한 정점으로 저장

2. 현재 정점의 인접 정점들을 순회 (방문한 정점이라면 순회하지 않는다)

3. 방문하지 않은 정점이면 재귀적으로 깊이 우선 탐색 수행

📌 너비 우선 탐색 알고리즘(BFS)

1. 방문한 정점을 저장하고 큐에 삽입

2. 큐에 dequeue

3. dequeue한 인접 정점을 순회한다

1. 이미 방문한 정점이라면 건너뛰고

2. 방문하지 않은 경우 첫 번째 경우 반복

📌 DFS vs BFS

DFS는 깊이를 우선 탐색

BFS는 너비를 우선 탐색

상황에 맞게 적절하게 사용하는 것

• 친구 추천을 제공: 너비 우선 탐색 사용

• 특정 지인을 찾는 경우: 깊이 우선 탐색 사용

성능

그래프의 성능은 정점 뿐만 아니라 간선에 따라서도 달라질 수 있다.

O(V + E)

V: 정점

E: 간선

✅ 가중 그래프

📌 개념

간선의 크기를 저장한다.

- 크기는 사용자가 정하기 나름(정점 간의 거리나 비용이 될 수 있음)

간선은 방향도 있으며 방향에 따라 가중치가 달리질 수도 있음

📌 다익스트라 알고리즘

최적의 경로를 찾을 때 최적의 알고리즘

1. shorted_path_table에 목표 정점과 거리를 초기화

2. visited와 unvisited 배열로 구분

3. unvisited에서 차례로 visited로 이동하면서 표 업데이트

1. 인접도시의 거리들을 shorted_path_table에 저장하고

2. 가까운 거리의 정점을 선택하여 visited로 이동

3. 표의 값 + 인접 도시 거리 > 표의 값이면 표 수정 X

✅ 알고리즘

📌 탐욕 알고리즘

최적해를 구하는데 사용되는 근사적인 방법

• 최적해를 구하는 보장은 없지만 단순하게 구할 수 있음

• 매 선택지에서 가장 좋은 선택을 고름

조건

1. 탐욕스러운 선택 속성

1. 앞의 선택이 이후의 선택에 영향을 주지 않음

2. 최적 부분 구조 조건

1. 문제에 대한 최적해는 부분에 대해서도 최적해이다

=> '매트로이드'

📌 최소 신장 트리

신장 트리

• 그래프에 순환 구조없이 모든 정점이 연결되어 있음

• 최소 신장 트리: 간선의 길이가 가장 짧은 신장 트리

1. 크루스칼 알고리즘

2. 프림 알고리즘

1. 다익스트라 알고리즘과 비슷

2. 최소 비용으로 연결

3. 무방향 그래프에서 동작

📌 최대 유량 문제(Network Flow)

용량이 다른 여러 상수관을 통해 Source에서 Sink까지 최대한 많은 양의 물을 보내는 문제

1. 용량(Capacity): 한 상수관에 최대한 흐를 수 있는 물의 양

2. 유량(Flow): 현재 상수관에 흐르고 있는 물의 양

3. 잔여 용량 = 용량 - 유량

탐색 알고리즘

1. 포드 폴커슨 알고리즘: DFS

1. Source에서 Sink로 가는 경로 하나를 DFS로 찾는다. (증가경로 찾긴)

2. 증가 경로에 흐를 수 있는 최대 유량을 찾는다

3. 찾은 증가 경로에서 보낼 수 있는 최대 유량을 흘린다.

2. 에드몬드 카프 알고리즘: BFS

📕 컴퓨터 구조

✅ 제어장치

📌 명령어

제어장치: RAM에 저장된 데이터를 가져와 정해진 동작을 수행하는 장치이다.

명령어, 데이터 모두 제어장치에 저장되어 있음.

• 상위 4비트 명령어, 하위 4비트 데이터(주소, 값)

📌 프로그램 카운터

RAM에서 메모리 주소를 이동시키거나 원하는 주소로 바로 접근할 수 있게 해주는 장치

다음 실행한 명령어의 주소를 가리킨다.

JK Flip-Flop을 통해 메모리 주소 1씩 카운팅

혹은 JUMP를 통해 원하는 주소로 바로 이동

📌 스탭 카운터

명령어 인출, 해석 및 실행 단계를 카운팅해주는 장치

후기

이번 주차에서는 그래프와 다양한 알고리즘에 대해서 배웠다. 매일 알고리즘 문제를 풀면서 개념은 알지 못하였지만 dfs나 bfs 혹은 그래프 문제를 해결하면서 접한 풀이과정에 대해 익혀가면서 단순히 재귀적인 문제의 심화 과정이라고 생각을 하였지만 이번 과정에서 해당 개념에 대해 깊이 있게 배울 수 있었고 간단한 풀이 예시와 함께 공부하다보니 더 쉽게 체감해볼 수 있었다. 컴퓨터 구조에서는 지금까지 배웠던 개념들을 토대로 본격적인 CPU 를 간단하게 제작해볼 수 있는 실습이 진행되었다. 개념적인 내용은 실습을 진행하면서 깊이 있게 다루지는 못하였지만 실제 동작되는 과정을 보면서 CPU의 명령과 연산 하나하나가 어떻게 동작하는 지 확인해볼 수 있었다. 점점 다양한 입력 핀들과 동작들을 혼합하여 제작하니 점점 구조가 복잡해지고 이해하는 것이 어려워지긴 하였지만 복습과 미션을 통해서 더 깊이 있게 이해해보려고 한다.