수학과의 개발자 도전기

공부한 날짜: 2021. 11. 04

-신장트리(Spanning Tree): 그래프의 모든 정점을 연결하는 트리

-최소 신장 트리, 최소 가중치 신장트리: 각 간선이 갖고 있는 가중치의 합이 최소가 되는 신장 트리

*최소 신장트리는 각 구성 요소가 서로 연결되어 있고 간선에 가중치가 실려있는 연결된 가중치 그래프로부터 만들어짐 

최소 신장트리를 만드는 알고리즘: 프림 알고리즘(Prim's algorithm), 크루스칼 알고리즘(Kruskal's algorithm)

* 구현부분에 어려운 부분이 있어서 여러번 보면서 이해해야할 것 같음 

1. 프림 알고리즘(Prim's algorithm)

• 과정

ㄱ. 그래프와 최소 신장 트리를 준비

ㄴ. 그래프에서 임의의 정점을 시작 정점으로 선택하여 최소 신장트리의 루트노드로 삽입

ㄷ. 최소 신장 트리에 삽입되어 있는 정점들과 이 정점들의 모든 인접 정점 사이에 있는 간선의 가중치 조사.  간선 중에 가장 가중치가 작은 것을 골라 이 간선에 연결되어 있는 인접 정점을 최소 신장 트리에 삽입. 단, 새로 삽입되는 정점은 최소 신장 트리에 삽입되어 있는 기존의 노드들과 사이클을 형성해서는 안됨 

ㄹ. ㄷ.의 과정 바복하다 최소 신장 트리가 그래프의 모든 정점을 연결하게 되면 알고리즘 종료

• 프림 알고리즘의 문제 

(1) 최소 신장 트리의 자료구조(배열,링크드리스트,트리)로 무엇을 사용할 것인가? 

: 이 책에서는 그래프를 사용

(2)조사 대상 간선에서 최소 가중치를 가진 간선을 골라는 과정에서 성능저하 

: 정점 하나를 추가할 때마다 최소 가중치를 찾기 위해 그래프 내의 정점 n개를 순회해야하므로, n^2만큼의 탐색을 해야함 

이걸 해결하기 위해 삽입 삭제가 빠르고, 최소 값을 찾는데에 거의 비용이 들지 않는 우선순위 큐를 이용함 

2. 크루스칼 알고리즘(Kruskal's algorithm)

: 그래프 내의 모든 간선들의 가중치 정보를 사전에 파악하고, 이 정보를 토대로 최소 신장 트리를 구축해나가는 알고리즘

• 과정

ㄱ. 그래프 내의 모든 간선을 가중치의 오름차순으로 목록을 만듦

ㄴ. ㄱ.에서 만든 간선의 목록을 차례대로 순회하면서 간선을 최소 신장트리에 추가함. 단, 이때 추가된 간선으로 인해 최소 신장 트리 내에 사이클이 형성 되면 안됨 

• 크루스칼 알고리즘의 문제 

: 최소 신장 트리에 생기는 사이클을 어떻게 효율적으로 감지할 것인가-> 깊이 우선 탐색 / 분리집합 -> 분리집합으로 진행 -> 모든 간선들을 가중치의 오름차순으로 정렬 -> 각 정점 별로 분리 집합 만듦 -> 알고리즘 진행순서대로 진행 

-크루스칼 구현

(1) 깊이 우선 탐색 이용시 

: 하나의 정점을 기준으로 탐색을 실행하고, 방문한 정점을 visited로 표시한뒤 해당 정점에서 실행한 깊이 우선 탐색  시 visted를 만나면 그 정점들은 사이클을 형성한다는 걸 알 수 있음

단점으로는 탐색 비용이 큰 것 

(2) 분리 집합 이용

: 간선으로 연결되어 있는 정점들에 대해서는 합집합 수행. 간선으로 이어야할 두 정점이 같은 집합에 속해 있다면 그 정점들이 사이클을 생성한다는 걸 알 수 있다. 

공부한 날짜: 2021. 11. 03

-위상: 어떤 정점이 다른 정점과의 관계속에서 가지는 위치

-위상 정렬의 조건

(1) 그래프에 방향성이 있어야 한다

(2) 그래프 내의 사이클이 없어야 한다 

-정점이 가질 수 있는 방향성 간선

(1) 진입간선

(2) 진출간선 

-위상정렬 과정

ㄱ. 리스트 하나 준비

ㄴ. 그래프에서 진입간선이 없는 정점을 리스트에 추가, 해당 정점 자신과 진출간선을 제거

ㄷ. 모든 정점에 대해 ㄴ.을 반복하고 그래프에 정점이 남아 있지 않으면 정렬 종료. 리스트에는 위상 정렬된 그래프가 저장됨

-깊이 우선 탐색으로 위상 정렬하기

ㄱ. 리스트 하나 준비

ㄴ. 그래프에 진입 간선이 없는 정점에 대해 깊이 우선 탐색 시행, 탐색 중에 인접 정점이 없는 정점을 만나면 해당 정점을 리스트의 새로운 '헤드'로 입력

ㄷ. ㄴ. 반복하다 더이상 방문할 정점이 없으면 깊이 우선 탐색을 종료함. 깊이 우선 탐색이 끝난 후 리스트에는 위상 정렬된 그래프가 남음

공부한 날짜: 2021. 11. 02

1. 그래프 

• 그래프: 정점의 모음과 간선의 모음의 결합

인접,이웃관계: 간선으로 연결되어 있는 두 정점이 이루는 관계

길이: 정점과 정점 사이의 간선의 수

사이클: 정점 하나를 두번 이상 거치는 경로

종류: 방향성 그래프(Directed Graph), 무방향성 그래프(Undirected Graph)

연결성: 그래프 내의 각 정점들이 모든 정점들과 연결되어 있는 경우

간선: 정점과 정점이 인접관계에 있음을 나타내는 존재

• 정점사이의 인접 관계를 표현하는 방법(인접 행렬/리스트)

(1) 인접 행렬(Adjacency Matrix)

:정점끼리의 인접 관계를 나타내는 행렬

행렬이 대칭이면 무방향 그래프, 대칭이 아니면 방향 그래프
장점: 정점간의 인접 여부 빠르게 알 수 있음

단점: 메모리를 많이 차지함(크기 정점 x N^2)

(2) 인접 리스트 (Adjacancy List)

:정점끼리의 인접 관계를 나타내는 리스트, 모든 정점의 목록을 리스트로 관리하도록 한다. 

장점: 사용하는 메모리의 양 적음

단점: 정점 간의 인접 여부를 알아내기 위해 인접 리스트를 타고 순차탐색을 해야함

-> 어느 것이 더 낫다라고 말할 수는 없고, 그때그때 상황에 따라 최적인 방법으로 사용하는 것이 중요하다

-그래프구현

2. 그래프 순회

-그래프를 순회하는 방법:  깊이 우선 방식/ 너비 우선 방식

(1) 깊이 우선 방식-> 그래프 정렬 알고리즘 

:"더 나아갈 길이 보이지 않을 때까지 깊이 들어간다"의 원칙으로 그래프 내의 정점을 방문하는 알고리즘, 스택을 이요함 

동작방식: 

ㄱ. 시작 정점을 밟은 후 이 정점을 '방문했음'으로 표시

ㄴ. not visited 인접 정렬을 시작 정점으로 정하고, 깊이 우선 탐색 시작( ㄱ단계 반복)

ㄷ. 정점에 더이상 방문하지 않은 인접 정점이 없으면 이전 정점으로 돌아가서 ㄴ단계 수행

ㄹ. 이전 정점으로 돌아가도 더 이상 방문할 이웃이 없다면 그래프의 모든 정점을 모두 방문했다는 뜻 -> 탐색 종료

(2) 너비 우선 방식 -> 최단 경로 찾기 알고리즘

:"꼼꼼하게 좌우를 살피며 다니자" (깊이가 1인 정점을 모두 방문하고, 그다음 깊이가 2인 정점 모두 방문,,,), 큐를 이용함 

ㄱ. 시작 정점을 'visted'로 표시하고 큐에 삽입(enqueue)

ㄴ. 큐로부터 정점을 제거(dequeue). 제거한 정점이 이웃하고 있는 인접 정점 중 아직 방문하지 않은 곳들을 '방문했음'으로 표시하고 큐에 삽입

ㄷ. ㄴ단계 반복하다 큐가 비게되면 종료

• 공부한 날짜: 2021. 10. 28

• 해시: 데이터를 입력 받으면 완전히 다른 모습의 데이터로 바꾸어 놓은 작업
• 해시테이블: 데이터의 해시 값을 테이블 내의 주소로 이용하는 알고리즘/ 
• 데이터를 담을 테이블을 미리 크게 확보해 놓은 후, 입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것
• 암호화: 데이터를 해시를 통해 변환하는 과정, 예시 SHA
• 데이터 축약: 해시를 통해 같은 길이의 데이터로 변환함으로써 데이터를 축약할 수 있음 

• 해시함수: 나눗셈법/ 자릿수 접기

1. 나눗셈법: 주소 = 입력값 % 테이블의 크기

가능한 주소는 0~N-1

테이블 크기는 소수 이용

문제점: 충돌 발생(다른 데이터, 동일한 주소값 가짐) & 클러스터 발생(데이터들이 한 곳에 모임)

**까먹고 구현 안해서 나중에 구현하고 붙여넣기 

2. 자릿수 접기: 숫자를 접어 일정한 크기 이하의 수로 만드는 방법 

접는 것: 숫자의 각 자릿수를 더해 해시 값을 만드는 것

• 충돌해결하기: 체이닝/ 개방 주소법(선형탐사, 제곱탐사, 이중해싱, 재해싱)

충돌 해결 하는 방법:

(1) 개방 해싱(open hashing): 해시 테이블 주소 바깥에 새로운 공간을 할당하여 문제 수습

(2) 페쇄 해싱(closed hashing): 처음에 주어진 해시 테이블 공간 안에서 문제 해결하는 방법

1. 체이닝: 충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 기법 

연산: 삽입은 앞으로 충돌할 것을 고려해서 작성, 탐색/삭제는 충돌했다는 가정하에 작성

*체이닝 기반 해시 테이블의 탐색

(1) 찾고자 하는 목표값을 해싱하여 링크드 리스트가 저장되어 있는 주소를 찾는다

(2) 이 주소를 이용하여 해시 테이블에 저장되어 있는 링크드 리스트에 대한 포인터를 생성

(3) 링크드 리스트의 앞에서부터 뒤까지 차례대로 이동하며 목표값이 저장되어 있는지 비교. 목표값과 링크드 리스트 내의 노드 값이 일치하면 해당 노드의 주소를 반환한다.

*체이닝 기반 해시 테이블의 삽입

: 충돌 발생 시 삽입은 같은 주소에 있는 링크드리스트의 헤드 부분에 새노드를 삽입하면 된다.(테일을 찾으려면 순차탐색을해야하므로 비효율적)