Published 2022. 12. 1. 01:47

크래프톤 정글 3주차 TWIL..

dev-log/크래프톤 정글

3주차 학습 내용

컴퓨터 시스템 책(Compouter Systems - A Programmer's Perspective / CSAPP) 1.8, 1.9
백준 문제 풀이 + 관련 이론 학습
- 트리, 이진 트리, 이진 검색 트리
- DFS
- BFS
- 위상 정렬

CSAPP 1.8, 1.9

시스템은 네트워크를 사용하여 다른 시스템과 통신한다

한 시스템의 데이터는 네트워크를 통해서 다른 시스템으로 이동(복사)할 수 있다. 즉 네트워크를 통해 시스템 간 통신을 할 수 있다.
네트워크 응용의 전형적 사례: 클라이언트와 서버 간의 데이터 교환

중요한 주제들

Amdahl의 법칙
- 어떤 시스템의 "한 부분"의 성능을 개선할 때, "전체" 시스템 성능에 대한 효과는 그 부분의 중요도와 그 부분이 얼마나 빨라졌는지와 관련 있다.
- 전체 시스템을 상당히 빠르게 하기 위해선 전체 시스템의 "상당히 큰 부분"의 성능을 개선해야 한다.
동시성(concurrency)과 병렬성(parallelism)
- 동시성은 "동시에(여러 개)", 병렬성은 "빠르게"
- 쓰레드 수준 동시성
  - 1960년대 초반, time-sharing 기법의 출현: 동시 실행이 시뮬레이션 형태로 실행됨. 한 개의 컴퓨터가 실행하는 프로세스를 빠르게 전환.
  - 프로세서 유형
    - 단일 프로세서 시스템(Uniprocessors): 한 개의 프로세서를 가지고 동작하는 시스템
    - 멀티프로세서 시스템(Multiprocessors): 여러 개의 프로세서를 가지고, 하나의 운영체제 커널의 제어 하에 동작하는 시스템
      - 멀티코어 프로세서(Multi-core processor): 여러 개의 CPU(코어)를 하나의 칩에 내장
      - 멀티쓰레딩 또는 하이퍼쓰레딩(Hyper-threaded): 하나의 CPU가 여러 개의 제어 흐름을 실행할 수 있도록 하는 기술 / 실행할 쓰레드를 매 사이클마다 결정
- 인스트럭션 수준 병렬성
  - 최근 프로세서들은 여러 개의 인스트럭션을 한 번에 실행하는 특징이 있는데, 이러한 특징을 인스트럭션 수준 병렬성이라고 한다.
  - 파이프라이닝: 하나의 인스트럭션 실행을 위해, 그에 요구되는 일들을 여러 단계로 나누고 하나씩 수행한다. 이때 각 단계는 병렬로 동작할 수 있다.
  - super-scalar: 사이클당 한 개 이상의 인스트럭션을 실행할 수 있는 프로세서
- 싱글 인스트럭션, 다중 데이터 병렬성(SIMD)
  - Single Instruction Multiple Data
  - 최신 프로세서들은 SIMD 모드로 한 개의 인스트럭션이 병렬로 다수의 연산을 수행할 수 있는 특수한 하드웨어를 가지고 있다.
  - 이러한 SIMD 인스트럭션은 응용프로그램의 속도를 개선하기 위해 제공된다.
컴퓨터 시스템에서 추상화의 중요성 (컴퓨터 시스템은 실제 구현의 복잡성을 감추기 위해 다음과 같은 여러 추상화를 제공한다.)
- 파일: 입출력 장치의 추상화
- 가상메모리: 프로그램 메모리의 추상화
- 프로세스: 실행 중인 프로그램의 추상화
- 가상머신: 컴퓨터 전체의 추상화

자료구조, 알고리즘

트리

그래프의 한 종류로서, 방향성이 있는 비순환 그래프라고 할 수 있다.
- 방향성: 부모 노드에서 자식 노드로 향한다.
- 비순환: 자식 노드 간에는 간선이 존재하지 않는다.
일반적인 그래프에는 기본적으로 부모 자식 개념이 존재하지 않으며, 루트 노드도 존재하지 않음.
형제 노드의 순서 관계가 있는지에 따라 순서 트리(ordered tree)와 무순서 트리(unordered tree)로 분류된다.
- 형제 노드의 순서 관계가 있다면 순서 트리, 그렇지 않다면 무순서 트리
순서 트리의 노드를 스캔하는 방법은 크게 2가지가 있다.
- 너비 우선 검색(BFS, breadth-first search): 낮은 레벨부터 왼쪽에서 오른쪽으로 검색하며, 한 레벨에서 검색을 마치면 다음 레벨로 넘어간다. 즉 주목 중인 노드의 같은 레벨에 있는 노드들(형제 노드들) 먼저 탐색하는 방식이다.
- 깊이 우선 검색(DFS, depth-first search): 리프에 도달할 때까지 아래로 내려가면서 검색하는 것을 우선으로 한다. 즉 주목 중인 노드의 자식 노드들 먼저 탐색하는 방식이다. 리프에서 더 이상 검색할 곳이 없다면 우선 부모 노드로 돌아간다.
이와 같은 노드 검색 방법을 볼 때 헷갈릴 수 있는 부분은, 단순히 지나가는 것과 '방문'하는 것은 다른 개념이라는 것이다. 어떤 노드를 이미 방문했더라도 단순히 지나가는 것은 문제 없다. 하지만 이미 방문한 노드를 또 '방문'하는 것은 안된다. 예를 들어 왼쪽 자식과 오른쪽 자식이 있는 어떤 A라는 노드에서부터 스캔을 시작할 때, 왼쪽 자식을 먼저 방문한 상태에서 오른쪽 자식도 방문하려면 A 노드를 지나가는 것은 불가피하다. 이렇게 단순히 지나가는 것은 가능하다는 것이다.
깊이 우선 검색은 노드를 어느 시점에 실제로 방문하는지에 따라 3가지 방법으로 또 나뉜다.
- 전위 순회(preorder): 노드 방문 → 왼쪽 자식으로 내려감 → 오른쪽 자식으로 내려감
- 중위 순회(inorder): 왼쪽 자식으로 내려감 → 노드 방문 → 오른쪽 자식으로 내려감
- 후위 순회(postorder): 왼쪽 자식으로 내려감 → 오른쪽 자식으로 내려감 → 노드 방문
용어 정리
- 루트(root): 트리의 가장 위쪽에 있는 노드
- 리프(leaf): 가지가 더 이상 뻗어나갈 수 없는 마지막에 있는 노드로서, terminal node(단말 노드) 또는 external node(외부 노드)라고도 한다.
- 비단말 노드(non-terminal node): 리프를 제외한 노드로서, internal node(내부 노드)라고도 한다.
  - 루트도 포함
- 레벨(level): 루트에서 얼마나 멀리 떨어져 있는지를 나타낸다. 루트의 레벨은 0이고, 간선이 하나씩 아래로 내려갈 때마다 레벨이 1씩 증가한다.
- 차수(degree): 각 노드가 갖는 자식의 수
  - 만약 모든 노드의 자식이 2개 이하면 이진 트리
- 높이(height): 리프 레벨의 최댓값
- 서브트리(subtree): 어떤 노드를 루트로 하고 그 자손들로 구성된 트리를 의미한다.
- 빈 트리(None tree): 노드와 간선이 전혀 없는 트리로서, 널 트리(Null tree)라고도 한다.
  - 루트조차 없는 트리

이진 트리

노드가 왼쪽 자식 또는 오른쪽 자식만을 갖는 트리를 이진 트리(binary tree)라고 한다.
- 왼쪽 자식을 루트로 하는 서브트리 👉 왼쪽 서브트리(left subtree)
- 오른쪽 자식을 루트로 하는 서브트리 👉 오른쪽 서브트리(right subtree)
완전 이진 트리(complete binary tree)
- 완전: 부모는 왼쪽 자식부터 추가하여 모양을 유지한다.
- 이진: 부모가 가질 수 있는 자식의 최대 개수는 2개 뿐이다.

이진 탐색 트리

이진 탐색 트리(binary search tree)에선 모든 노드가 다음 조건을 만족해야 한다.
- 어떤 노드의 왼쪽 서브트리 노드의 키값은 자신의 키값보다 작아야 한다.
- 어떤 노드의 오른쪽 서브트리 노드의 키값은 자신의 키값보다 커야 한다.
이진 탐색 트리 구현에 필요한 함수
- search 함수
  - 이진 검색 트리에서 검색을 수행하는 함수
  - 루트에서부터 검색을 시작하며, 키값의 대소 관계를 판단한 결과에 따라 왼쪽 또는 오른쪽 서브트리를 따라가며 검색을 수행한다. 찾고 있는 키값을 key, 주목 중인 노드를 p라고 하면;
    - key == p.key 👉 검색을 성공하고 종료한다.
    - key > p.key 👉 주목 중인 노드를 p의 오른쪽 자식으로 변경한다.
    - key < p.key 👉 주목 중인 노드를 p의 왼쪽 자식으로 변경한다.
- add 함수
  - 노드를 삽입하는 함수
  - 노드를 삽입한 뒤에도 이진 검색 트리의 조건을 유지해야 한다. 삽입할 위치를 먼저 찾아낸 뒤에 삽입을 수행해야 한다.
  - 삽입할 위치를 찾는 작업은 루트에서부터 시작한다. 즉 루트부터 주목한다. 삽입할 키값을 key, 주목 중인 노드를 p라고 하면;
    - key == p.key 👉 동일한 키가 트리에 이미 존재한다는 의미이므로, 삽입 실패하고 종료
    - key < p.key
      - p가 왼쪽 자식 노드가 없으면 👉 p의 왼쪽 자식 노드의 자리에 key를 키값으로 값는 새로운 노드를 삽입하고 종료
      - p가 왼쪽 자식 노드가 있으면 👉 p의 왼쪽 자식 노드를 주목한다.
    - key > p.key
      - p가 오른쪽 자식 노드가 없으면 👉 p의 오른쪽 자식 노드의 자리에 key를 키값으로 값는 새로운 노드를 삽입하고 종료
      - p가 오른쪽 자식 노드가 있으면 👉 p의 오른쪽 자식 노드를 주목한다.
- remove 함수
  - 자식 노드가 없는 노드를 삭제하는 경우 👉 삭제하려는 노드의 부모 노드의 포인터가 해당 노드를 가리키지 않도록 업데이트
  - 자식 노드가 1개인 노드를 삭제하는 경우 👉 삭제하려는 노드의 부모 노드와 자식 노드를 맺어준다.
  - 자식 노드가 2개인 노드를 삭제하는 경우
    - 삭제할 노드의 왼쪽 서브트리에서 키값이 가장 큰 노드를 검색한다.
    - 검색한 노드를 삭제 위치로 옮긴다. 검색한 노드의 데이터를 삭제할 노드 위치에 복사한다.
    - 옮긴 노드를 삭제한다.
- min_key, max_key 함수
  - 최소 키, 최대 키를 찾아서 반환하는 함수
  - 루트부터 주목하면서 시작한다.
  - 최소 키를 구하는 경우에는 왼쪽 자식이 없는 노드를 만날 때까지 왼쪽 자식을 따라간다. 왼쪽 자식이 없는 노드의 키값이 최소 키다.
  - 최대 키를 구하는 경우에는 오른쪽 자식이 없는 노드를 만날 때까지 오른쪽 자식을 따라간다. 오른쪽 자식이 없는 노드의 키값이 최대 키다.

그래프와 DFS, BFS

그래프 기본 개념 및 DFS, BFS 학습할 때 굉장히 도움 많이 되었던 영상: https://youtu.be/tWVWeAqZ0WU

DFS
- 방향 바꾸기 전까지 가능한 한 같은 방향으로 멀리 순회
- stack으로 구현한다.
- 구현하기
  - 1. 맨 처음 지나가는 노드를 stack에 push한다.
  - 2. stack에서 노드를 pop한다. 이 노드에 주목한다. 주목 중인 노드는 p라고 한다.
  - 3. 여기서 방문 여부를 확인하는데, 이미 방문한 노드라면 이하 작업은 진행하지 않고 다음 노드를 pop한다.
  - 4. p를 출력하고, 이 노드를 또 지나가는 경우에 다시 출력하지 않게 하도록 하기 위해 이미 방문한 노드임을 표시한다. (예: set에 해당 노드의 키를 추가)
  - 5. p의 이웃 노드들을 모두 stack에 push한다.
  - 6. stack이 비어있는 상태가 되기 전까지 2. ~ 5.의 작업을 반복한다.
- stack이 비어있는 상태가 되었다는 것은 "가능한" 모든 노드를 방문했다는 의미이며, 이는 방문하지 못한 노드도 있을 수 있다는 의미가 된다. (예: 다른 노드와 이어진 간선이 없는 노드)
- 위와 같이 iteration으로 구현할 수도 있고, 재귀(recursion) 용법을 사용하여 아예 함수 콜스택을 이용해서 구현할 수도 있다.
BFS
- 이웃 노드들부터 전부 방문
- queue로 구현한다.
- 구현하기
  - 1. 맨 처음 지나가는 노드를 queue에 삽입한다.
  - 2. queue가 비어있는 상태가 되기 전까지 front를 dequeue한다. 이렇게 빼낸 노드에 주목한다. 주목 중인 노드는 p라고 한다.
  - 3. 여기서 방문 여부를 확인하는데, 이미 방문한 노드라면 이하 작업은 진행하지 않고 다음 노드를 dequeue한다.
  - 4. p를 출력하고, 이 노드를 또 지나가는 경우에 다시 출력하지 않게 하도록 하기 위해 이미 방문한 노드임을 표시한다. (예: set에 해당 노드의 키를 추가)
  - 5. p를 프린트하고, p의 이웃 노드들을 queue로 enqueue한다.
  - 6. queue가 비어있는 상태가 되기 전까지 2. ~ 5.의 작업을 반복한다.
- 여기서도 DFS를 구현하는 경우와 마찬가지로, queue가 비어있는 상태가 되었다는 것은 "가능한" 모든 노드를 방문했다는 의미이며, 이는 방문하지 못한 노드도 있을 수 있다는 의미가 된다. (예: 다른 노드와 이어진 간선이 없는 노드)
- DFS와 달리 BFS의 경우 재귀 용법을 이용하게 되면 스택을 사용하게 되는 꼴이라 큐의 동작 방식과 맞지 않아 그냥 iteration으로 구현한다.
그래프 문제 접근 방식
- 문제에서 간선 리스트가 주어질 경우, 인접 리스트로 변환하여 작업하는 것이 좋다. 이때 주의할 점은, 무방향 그래프의 경우에는 inverse connection도 고려해줘야 한다는 점이다.
- 무방향(undirected 또는 bidirected) 그래프의 경우에는 cycle이 있는 경우가 많다. 문제에서 따로 언급을 하지 않더라도 늘 염두에 두고 처리를 해줘야 한다.
  - cycle이 있을 때 별도 처리를 하지 않을 경우 무한 순회(infinite traversal)하게 된다.
  - 그렇다면 어떻게 처리를 하면 될까?
    - visited 노드를 관리한다. (set으로 구현)
위상 정렬
- 위상 정렬(topological sort)은 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때 그 순서를 결정해주는 알고리즘이다.
- 위상 정렬은 dag(방향 비순환 그래프)에 대해서만 수행할 수 있다.
- 어떤 dag G = (V,E)을 위상 정렬하면, G의 모든 노드를 선형으로 나열할 때 어떤 간선 (u,v)에 대해 노드 u가 노드 v보다 순서 상으로 먼저 나타나게 된다.
- DFS의 탐색 결과를 역으로 나타낸 결과가 위상정렬 결과와 동일하다.

문제 풀면서 마주친 그래프 문제 유형들

has path 유형 - 어떤 노드A(출발지)부터 노드B(목적지)까지 가는 경로가 존재하는지
- 그래프를 순회(DFS, BFS)한다.
- 목적지와 동일한 노드에 방문하게 되면 True를 반환한다.
- 목적지와 동일한 노드를 마주치지 못했는데 더 방문할 노드가 남아있지 않다면 False를 반환한다.
connected components count 유형 - "연결 요소" 개수를 카운트하는 유형
- 우선 섬처럼 떨어져 있는 각각의 그룹을 하나의 "컴포넌트"로 본다. (아래 그림 참고)
  - 이때 연결된 간선이 하나도 없는 노드를 싱글톤(singleton - '단독 개체', '한 개의 것') 노드라고 한다.
- 노드를 차례로 순회(DFS, BFS)하는데, 각 노드를 시작점으로 하는 순회를 진행한다.
  - visited 목록을 관리해서, 이전 순회에서 이미 방문한 노드들에선 순회 시작 X
- 하나의 컴포넌트에 대한 순회가 끝나면 개수를 하나 카운트한다.

최소 스패닝 트리(MST, minimum spanning tree)
- 백준 1197. 최소 스패닝 트리
- 크루스칼 알고리즘으로 풀든 프림 알고리즘으로 풀든 차이 없다고 한다.
- MST ⊆ 연결 그래프(connected graph) ⊆ 그래프
  - 연결 그래프: 그래프의 상태를 나타내는 용어로서, 임의의 두 노드가 어떻게든(=몇 다리 건너서라도) 모두 연결되어있는 그래프를 의미한다.
- MST는 무방향 그래프다.
- MST는 모든 간선에 가중치(w)가 존재한다.
- MST는 연결 그래프 중에서도 가중치의 합이 제일 작은 간선들로만 노드를 연결한 것이다.
- 간선을 가중치 순으로 정렬한다. 그 다음, cycle이 생기지 않을 때까지 계속해서 edge를 그래프에 추가해준다.
- MST를 만들려면 이와 같이 cycle이 없어야 하고, cycle을 감지하려면 union find 알고리즘을 사용해야 한다.
  - cycle을 어떻게 감지한다는 것인지? 👉 만약 부모가 이미 합쳐진 상태라면, 간선을 더 연결하는 순간 cycle이 생겨버리게 된다.
- union find 알고리즘(동빈나 강의 참고)
  - union find 알고리즘은 대표적인 그래프 알고리즘으로, 크루스칼 알고리즘(갓빈나 강의 참고) 등에도 적용이 된다.
    - 크루스칼 알고리즘은 그리디 알고리즘에 해당한다. 가중치가 작은 간선부터 시작해서 cycle 발생 전까지 계속해서 간선을 추가해나가기 때문! 구현하려면 min heap(우선순위 큐)에 모든 간선을 다 때려박으면 된다.
  - 여러 노드가 존재할 때, 두 개의 노드를 선택해서 현재 이 두 노드가 서로 같은 그래프에 속하는지를 판별한다.
  - 부모를 합칠 때(👉 union parent), 더 작은 값 쪽으로 합침.
    - 두 노드 각각의 부모를 찾은 후(👉 get parent), 값이 더 작은 부모로 통일한다. (아래 그림 참고)
  - 최종적인 부모를 찾는는 get parent 함수는 재귀로 구현한다.
    - 최초 부모는 자기 자신이며, 이게 재귀 함수의 탈출 조건(base case)가 된다.
  - 부모가 같다는 것은 결국 서로 연결되어있다는 것이다.
    - 바꿔 말하면 컴포넌트 간에는 부모가 다르다는 뜻

최초 부모는 자기 자신이며, 1과 2중 1이 더 작으므로 1로 통일한다.

import heapq
import sys
input = sys.stdin.readline

# V는 노드 개수
# N은 간선 개수
V, N = list(map(int, input().split()))
edges = []
heapq.heapify(edges)

for _ in range(N): # N은 간선 개수
    A, B, C = list(map(int, input().split()))
    heapq.heappush(edges, (C, A, B))

parent = [i for i in range(V + 1)] # V는 노드 개수
def union_parent(x, y):
    parent_x = get_parent(x)
    parent_y = get_parent(y)

    if parent_x < parent_y:
        parent[y] = parent_x
    else:
        parent[x] = parent_y

def get_parent(x):
    if parent[x] == x:
        return x

    return get_parent(parent[x])

cnt = 0
while len(edges):
    C, A, B = heapq.heappop(edges)
    # 부모가 동일하다면 노드 간에 이미 연결되어 있는 상태이며,
    # 그 상태에서 또 다른 간선을 연결하면 cycle이 생겨버림.
    parent_A = get_parent(A)
    parent_B = get_parent(B)
    if parent_A != parent_B:
        cnt += C
        union_parent(parent_A, parent_B)
        # 부모의 대표격끼리 union 해줘야 함.

print(cnt)

3주차 소회

2주 지난 시점에서 쓰느라 잘 기억이 안 나지만.. ^^ 기억나는 것 위주로 써보면:

동기분들과 아침 러닝?조깅?을 시작했다. 나는 2.5키로 뛰면 많이 뛰는 건데 같이 뛰시는 분들은 진짜 잘 뛰셔서 맨날 뒤쳐진다ㅠ

다들 별로 안 힘들어보여서 안 힘드시냐고 물어봤는데 힘든데도 참고 달리는 거라고 해서 반성했다. 스스로 한계가 2키로 정도라고 생각하니 그 쯤 뛰면 뭔가 몸이 급 엄살부리는 게 느껴진다;;

그리고 3주차의 일주일 평균 수면시간은 5시간이었다. (이번 주차는 6시간이다. 어제랑 그제 늦잠 잤는데도 6시간..?)

기분은 어땠는지 잘 기억이 안 난다. ㅠ_ㅠ 이래서 일기를 써야 하는데 ..!

'dev-log > 크래프톤 정글' 카테고리의 다른 글

크래프톤 정글 4, 5주차 회고 (2)	2022.12.23
CSAPP 9장. 가상메모리 - 9.1 ~ 9.8 내용 정리 (0)	2022.12.05
크래프톤 정글 2주차 TWIL.. (1)	2022.11.18
크래프톤 정글 1주차 TWIL.. (3)	2022.11.05
크래프톤 정글 1주차 에세이 (8)	2022.10.31