WEEK03

yeopto·2022년 4월 23일

CSAPP SW사관학교 정글 algorithm python sw정글

SW사관학교 정글

목록 보기

5/14

22.04.14

알고리즘

그래프 탐색
- 파이썬에서는 그래프를 딕셔너리를 이용하여 나타낼 수 있다.
- 그래프의 키는 정점을, 값은 키와 연결된 정점을 나타낸다.
DFS
- 깊이 우선 탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 자료구조(혹은 재귀 함수)를 이용한다
- 동작 과정
  - 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
  - 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  - 더 이상 위의 과정을 수행할 수 없을 때까지 반복한다.
- 방문 기준 → 번호가 낮은 인접 노드부터
- 시작 노드 ‘1’을 스택에 삽입하고 방문 처리 → ‘1’에 방문하지 않은 인접 노드 ‘2’, ‘3’, ‘8’이 있다. → 이 중 가장 작은 노드인 ‘2’를 스택에 넣고 방문 처리 → ‘2’의 인접노드 ‘7’을 스택에 넣고 방문처리 → ‘7’인접노드는 ‘6’, ‘8’이 있는데 작은 인접노드인 ‘6’을 스택에넣고 방문처리 → ‘6’ 에서 방문하지 않은 인접노드가 없기 때문에 ‘6’을 pop 해줌 → 다시 ‘7’인접노드인 ‘8’을 스택에 넣고 방문 처리해준다. → 탐색순서는 1, 2, 7, 6, 8, 3, 4, 5
- 일반적으로 그래프 문제가 출제되면 그래프번호가 1번부터 시작이기때문에 그래프 0번째인덱스는 비워줌 → 리스트를 초기화할때 n + 1을 해준다.
- 2차원 리스트로 그래프를 인접 리스트형식으로 만들어준다.
- DFS 기본 구조
```
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False] * 9

dfs(graph, 1, visited)
```
BFS
- 너비 우선 탐색, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 큐 자료구조를 이용한다.
- 동작 과정
  - 탐색 시작 노드를 큐에 삽입하고 방문 처리
  - 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
  - 더 이상 2번의 과정을 수행할 수 없을 때까지 반복.
- 특정 최단 경로를 구할때 유용함.
- 시작 노드인 ‘1’을 큐에 삽입하고 방문 처리 → 큐에서 ‘1’을 꺼내 방문하지 않은 인접 노드 ‘2’, ‘3’, ‘8’을 큐에 삽입하고 방문 처리 → ‘2’를 꺼내서 인접한 노드 ‘1’ 과 ‘7’을 확인하는데 ‘1’은 방문했으니까 ‘7’을 큐에 넣고 방문처리 → ‘3’을 꺼내서 인접한 방문하지 않은 노드 ‘4’, ‘5’를 큐에 넣고 방문 처리 → ‘8’꺼내고 → ‘7’꺼내서 인접하고 방문하지 않은 노드 ‘6’을 큐에 넣고 방문처리 → 탐색순서 1, 2, 3, 8, 7, 4, 5, 6
- BFS 기본구조
```
from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    # 현재 노드를 큐에 넣고 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        # 아직 방문하지 않은 인접한 원소들을 싹다 큐에 삽입 후 방문처리
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False] * 9

bfs(graph, 1, visited)
```

22.04.15

자료구조

트리 구조

트리의 가장 위쪽에 있는 노드를 루트라고 한다. (루트는 트리에 하나만 존재)
가장 아래쪽에 있는 노드를 리프라고 한다. (가지가 더 이상 뻗어나갈 수 없는 마지막에 노드가 있다는 것)
순서 트리의 검색
- 전위 순회 : 노드 방문 → 왼쪽 자식 → 오른쪽 자식
- 중위 순회 : 왼쪽자식 → 노드 방문 → 오른쪽 자식
- 후위 순회 : 왼쪽 자식 → 오른쪽 자식 → 노드 방문

BOJ 1991 트리순회

import sys

input = sys.stdin.readline

N = int(input())
tree = {} # 딕셔너리로 루트와 자식 관계를 표현 {'A':['B','C']}

for n in range(N):
    root, left, right = input().split() 
    tree[root] = [left, right]

# 재귀로 순회해준다
def pre_order(root): # 전위
    if root != '.': # 자식 노드가 있을때
        print(root, end='') # 루트 방문하고
        pre_order(tree[root][0]) # 왼쪽자식 
        pre_order(tree[root][1]) # 오른쪽자식

def in_order(root): # 중위
    if root != '.':
        in_order(tree[root][0])
        print(root, end='')
        in_order(tree[root][1])

def post_order(root): # 후위
    if root != '.':
        post_order(tree[root][0])
        post_order(tree[root][1])
        print(root, end='')

pre_order('A')
print()
in_order('A')
print()
post_order('A')

이진 탐색 트리
- 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종
- 이진 탐색 트리의 특징 : 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

22.04.16 ~ 17

자료구조

서로소 집합 자료구조

여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정
- 노드의 개수 크기의 부모 테이블을 초기화한다. (부모가 자기 자신)
- Union(1, 4) 연산을 처리하면 노드 1과 노드 4의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 1과 4이므로 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 설정한다.
- Union(2, 3) 3의 부모값은 2
- Union(2, 4) 노드 2와 노드 4의 루트 노드는 각각 2와 1이므로 더 큰 번호에 해당하는 루트 노드 2의 부모를 1로 만든다.
- Union(5, 6) 을 연산하면 6의 부모값은 5가 됨.
- 1,2,3,4 가 집합 한개 5, 6이 집합 한개라 집합은 총 2개가 된다.
기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근할 수 없다.
- 루트 노드를 찾기 위해 부모 테이블을 계속해서 확인하며 거슬러 올라가야함.
구현 코드

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
	# 루트 노드를 찾을 때까지 재귀
	if parent[x] != x: # 루트노드가 자기 자신이 아니라면
		return find_parent(parent, parent[x])
	return x

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
	a = find_parent(parent, a)
	b = find_parent(parent, b)
	if a < b:
		parent[b] = a
	else:
		parent[a] = b

# 노드의 개수와 간선의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
	parent[i] = i

# Union 연산을 각각 수행
for i in range(e):
	a, b = map(int, input().split())
	union_parent(parent, a, b)

# 각 원소가 속한 집합 출력하기
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1)
	print(find_parent(parent, i), end='')

print()

# 부모 테이블 내용 출력
print('부모 테이블: ', end='')
for i in rnage(1, v + 1):
	print(parent[i], end='')

경로 압축
- 찾기 함수를 최적화 하기 위한 방법
- 찾기 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신한다.
- 코드
```
def find_parent(parent, x):
	if parent[x] != x:
		parent[x] = find_parent(parent, parent[x])
	return parent[x]
```

알고리즘

서로소 집합을 활용한 사이클 판별
- 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.
- 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별할 수 있다.
- 판별 알고리즘
  - 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인한다.
    - 루트 노드가 서로 다르다면 두 노드에 대하여 합집합 연산을 수행
    - 서로 부모값이 같다면 사이클이 발생한 것
  - 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복.
최소 신장 트리(MST)
- 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.
크루스칼 알고리즘
- 대표적인 최소 신장 트리 알고리즘
- 그리디 알고리즘으로 분류됨.
- 동작 과정
  - 간선 데이터를 비용에 따라 오름차순으로 정렬한다.(비용 순으로)
  - 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생 시키는지 확인한다.
    - 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다
    - 사이클이 발생하는 경우 최소 신장 트리에 포함 시키지 않는다.
  - 모든 간선에 대해 2번의 과정을 반복함.
- 최종적으로 만들어지는 최소신장트리에 포함되어있는 간선의 개수는 전체 노드의 갯수 N - 1이다. 이는 기본적으로 트리가 가지는 특징이며, 사이클 또한 존재하지 않는다는 특징이있다.
최단 경로 알고리즘
- 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘
- 다양한 문제 상황
  - 한 지점에서 다른 한 지점까지의 최단 경로
  - 한 지점에서 다른 모든 지점까지의 최단 경로
  - 모든 지점에서 다른 모든 지점까지의 최단 경로
- 각 지점은 그래프에서 노드로 표현
- 지점 간 연결된 도로는 그래프에서 간선으로 표현
- 다익스트라 알고리즘
  - 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산
  - 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작
  - 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다.
- 다익스트라 알고리즘 동작과정
  - 출발 노드를 설정한다.
  - 최단 거리 테이블을 초기화한다. → 처음엔 모든 노드까지 가기 위한 비용을 무한으로 설정한다. 자기 자신에 대한 노드는 0으로 → Why? 자기 자신에서 자기 자신한테까지는 0이기 때문
  - 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
  - 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
  - 위 과정에서 3번과 4번을 반복한다.
- 다익스트라 알고리즘 개선된 방법(최소 힙 사용)
  - 힙을 사용하지 않은 다익스트라 알고리즘은 시간복잡도가 O(v^2)이다. 노드 수가 5000개 이하면 가능하지만 10000개가 넘어가면 힘들다.
  - 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙 자료구조를 사용하면 시간 복잡도를 줄일 수 있다.
  - 기본 원리는 동일
    - 현재 가장 가까운 노드를 저장하기 위해 힙 자료구조를 추가적으로 이용
    - 현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙(우선 순위 큐)을 사용한다.

22.04.18 ~19

알고리즘

위상정렬
- 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미
- 동작과정(queue를 사용)
  - 진입차수가 0인 모든 노드를 큐에 넣는다
  - 큐가 빌 때까지 다음 과정을 반복한다.
    - 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다
    - 새롭게 진입차수가 0이 된 노드를 큐에 넣는다
    - 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다.
- 위상 정렬의 특징
  - 위상 정렬은 순환하지 않는 방향 그래프에서만 수행할 수 있다.
  - 위상 정렬에는 여러 가지 답이 존재할 수 있다.
    - 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있을 때
  - 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다.
  - 사이클에 포함된 원소 중에서 어떠한 원소도 큐에 들어가지 못함.
  - 스택을 활용한 DFS를 이용해 위상 정렬을 수행할 수도 있다.

22.04.20

Computer System(CSAPP)

1.8 시스템은 네트워크를 사용하여 다른 시스템과 통신한다
- 인터넷과 같은 글로벌 네트워크의 출현으로 하나의 컴퓨터에서 다른 컴퓨터로 정보를 복사하는 것이 가장 중요한 컴퓨터의 응용이 되었다. 일례로, 이메일, 메신저, 웹 페이지, FTP, telnet 같은 응용들은 네트워크를 통해 정보를 복사하는 기능을 이용한 것이다.
- “hello” 스트링을 telnet 클라이언트에 입력하고 엔터키를 누른다 → 클라이언트 프로그램은 이 스트링을 telnet 서버로 보낸다. → telnet 서버가 네트워크에서 스트링을 받은 후에, 원격 쉘 프로그램에 이들을 전달 → 원격 쉘은 hello 프로그램을 실행하고 출력을 다시 telnet 서버로 전달 → telnet 서버는 네트워크를 거쳐 출력 스트링을 telnet 클라이언트로 전달함 → 클라이언트 프로그램은 출력 스트링을 자신의 로컬 터미널에 표시함.
1.9.2 동시성과 병렬성
- 동시성
  - 다수의 동시에 벌어지는 일을 갖는 시스템에 관한 일반적인 개념을 말할 때 사용
- 병렬성
  - 동시성을 사용해서 시스템을 보다 빠르게 동작하도록 하는 것

참고 - 컴퓨터 시스템(Coputer Systems A Programmer's Perspective 3rd)

WEEK03에는 한 문제를 풀었다. 지난 주에 한 문제도 구현하지 못해 뒤쳐지는 느낌이 들어 굉장히 괴로웠는데, 이번 주엔 풀었으니 지난주보다는 성장했구나라는 생각이 들었다. 점점 알고리즘이 이런것이구나하며 맛을 알아가는 단계라고 생각한다. 공부를 어떻게 해야할지 감이 온다. 욕심내지말고 알고리즘 단계가 끝나더라도 조금씩이라도 꾸준히 하다보면 할 수 있을거란 믿음을 가지고 어제보다 나은 오늘이 되기 위해 열심히 해야겠다는 생각이 들었다.

WEEK03 풀었던 문제 소스코드 - https://github.com/yeopto/SW-jungle/tree/main/WEEK03