[TIL] 위상 정렬 문제 풀이 + Computer System2

1. 위상 정렬 문제 풀이

1. 2637번 - 장난감 조립

import sys
from collections import deque

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())

basic = [[] for _ in range(N)]
inDegree = [0] * N

for _ in range(M) :
    x, y, k = map(int, sys.stdin.readline().split())
    basic[y-1].append((x-1, k))
    inDegree[x-1] += 1

def topologicalsort() :
    # component[x][y] -> x를 만드는데 필요한 y의 개수
    component = [[0] * N for _ in range(N)]
    queue = deque()
    
    for i in range(N) :
        if inDegree[i] == 0 : # 차수 0 = 기본 부품
            queue.append(i)
    
    while queue :
        cur = queue.popleft()
        # cur를 이용하여 next를 만드는데 필요한 개수 = count
        for next, count in basic[cur] :
            # 기본 부품이거나 아직 필요한 기본 부품의 개수를 받지 못한 경우 
            if component[cur].count(0) == N : 
                component[next][cur] += count # next를 만드는데 필요한 cur의 개수
            else : # 위의 경우가 아닐 때 즉, cur이 중간 부품일 경우
                for i in range(N) :
                    # 예시) cur = 5 / next = 7 / i = 1
                    # 7을 만들기 위해 필요한 5의 개수 2 = count
                    # 5를 만들기 위해 필요한 1의 개수 2 = component[cur][i]
                    # 7을 만들기 위해 필요한 5를 위해 필요한 1의 개수 = 2 * 2
                    component[next][i] += component[cur][i] * count
            inDegree[next] -= 1
            if inDegree[next] == 0 :
                queue.append(next)
    for i in range(N) :
        # 마지막 완제품을 만들 때 필요한 부품들 = component[N-1]
        if component[N-1][i] > 0 : # 값이 0인 경우 중간 부품이다.
            print(f'{i+1} {component[N-1][i]}')

topologicalsort()

백준 예제1 입력 표현

 위상 정렬을 사용하기 위해 저장하고 진입 차수를 저장하는 이유까지는 알고 기본적인 BFS를 이용한 위상정렬의 틀은 구현할 수 있었다.
문제는 이를 활용하여 기본 부품의 개수를 업데이트하며 나아가는 과정이었는데 처음에는 딕셔너리를 사용해 기본 부품에 대한 결과만 저장하고 입력받은 그래프를 이용하면 계산할 수 있지 않을까 생각해 이곳에 필요한 부품의 수를 업데이트하려고 했다.
그러나 딕셔너리를 통해 하려고 보니까 연산을 할 때마다 필요한 값이 다 달라서 저장해둬야 할 값이 생겨나서 사용할 수 없었다.

그래서 다른 사람들의 풀이를 참고해보니 이차원 배열을 사용하여 그때그때 필요한 값들을 저장하고 이를 이용하여 최종적으로 구하는 것이다.  생각해보면 가장 간단하면서 후에 결과를 출력하기도 편한 방식이었다.

component[x][y] 배열의 값 : x를 만드는데 필요한 y의 개수 저장

< 참고 > https://velog.io/@qweadzs/BOJ-2637-장난감-조립Python

    for i in range(N) :
        if inDegree[i] == 0 : # 차수 0 = 기본 부품
            queue.append(i)
            # 기본 부품은 자기 자신을 1개 가지고 있으면 된다.
            component[i][i] = 1
    
    while queue :
        cur = queue.popleft()
        # cur를 이용하여 next를 만드는데 필요한 개수 = count
        for next, count in basic[cur] :
            for i in range(N) :
                # 이미 기본 부품의 개수를 1로 지정해줬기 떄문에 곱하기 연산을 할때 0이 되지 않는다.
                component[next][i] += component[cur][i] * count
            inDegree[next] -= 1
            if inDegree[next] == 0 :
                queue.append(next)

위의 코드는 애초에 기본 부품은 자기 자신의 1개만을 필요로 하므로 이를 1로 초기화 시켰다.
그러면 0으로 인해 곱셈의 결과값이 달라질 이유가 없으므로 조건문을 제거했다.

---

2. 1432번 - 그래프 수정

import sys
import heapq

N = int(sys.stdin.readline())
matrix = [list(sys.stdin.readline().strip()) for _ in range(N)]
degree = [0] * N
graph = [[] for _ in range(N)]

# 후에 사전적 정렬을 하기 위해 진출차수(Out Degree) 사용
for i in range(N) :
    for j in range(N) :
        if matrix[i][j] == '1' :
            # 입력된 값을 뒤집어서 새로 저장
            graph[j].append(i)
            degree[i] += 1

def topologySort() :
    queue = []
    result = [0] * N
    idx = N
    
    # 진출 차수가 존재하지 않는 경우 -> 노드 번호가 크다.
    for i in range(N) :
        if degree[i] == 0 :
            # 최대힙으로 저장
            heapq.heappush(queue, -i)
    
    while queue :
        # 현재 최대힙 안에서 우선순위가 가장 큰 노드를 pop
        # 같은 조건을 가진 노드 1, 2가 있다면 위상 정렬 후에도 3, 4와 같이 순서가 맞아야한다.
        cur = heapq.heappop(queue)
        result[-cur] = idx
        idx -= 1
        for i in graph[-cur] :
            degree[i] -= 1
            if degree[i] == 0 :
                heapq.heappush(queue, -i)
    # 만약 result[i] = 0 이라는 의미는 한번도 힙에 들어간적이 없다는 의미로 
    # 사이클이 존재하면 나타난다.
    if result.count(0) > 0 : 
        print(-1)
    else :
        print(*result)
    
topologySort()

처음에는 당연히 최소를 먼저 찾아가면서 답을 찾아갔다. 그러나 반례를 통과하지 못했다.
 답이 여러 개일 경우에는 사전 순으로 제일 앞서는 것을 출력 이 조건을 만족하려면 작은 것 부터 해야한다고 생각했는데 다른 블로그를 참고해보니 반대로 구현했다. 

정렬 우선순위가 높은 것부터 정렬하고 우선순위가 낮은 것을 사용하여 정렬하면 원하는 결과를 얻지 못할 수 있다.
그러나 반대로 낮은 우선순위로 먼저 정렬하고 높은 우선순위를 이용하여 정렬하면 항상 옳은 결과를 얻을 수 있다.

위의 내용은 정말 생각해 본적이 없었는데 아래 블로그들의 설명을 보니 달라지는 것을 볼 수 있었다.
< 참고 블로그 >
https://velog.io/@stthunderl/백준-1432-그래프수정-python-위상정렬
https://wonyoung2257.tistory.com/80

---

나중에 시도해볼 문제 : 1948번 - 임계경로

---

2. Computer System 공부

기본 용어 정리 : https://soo-note.tistory.com/40

1. Process

• 프로세스 상태
  • 생성(Create) : 프로세스 생성
  • 실행(Running) : 프로세스가 CPU를 차지하여 명령어 실행
  • 준비(Ready) : 프로세스가 CPU를 사용하고 있지는 않지만 언제든지 사용할 수 있는 상태,
                           우선순위가 높은 프로세스가 먼저 할당된다.
  • 대기(Waiting) = 보류(Block) : 프로세스가 입출력 완료, 시그널 수신 등 어떤 사건을 기다리고 있는 상태
  • 종료(Terminated) : 프로세스 종료
• 상태 전이
  • dispatch : ready → running
  • block : running → block
    • 실행 상태의 프로세스가 허가된 시간을 다쓰기 전에 입출력 동작을 필요로 하는 경우 스스로 CPU 반납하고 보류상태로 넘어간다.
  • wakeup : block → ready
    • 기다리던 사건이 일어났을 때 보류 상태를 준비상태로 넘어간다.
  • timeout : running → ready
    • 운영체제는 프로세스가 CPU를 독점해서 사용하지 못하게 하기위해 일정 시간만 프로세서를 점유할 수 있도록 한다.

출처 : https://bowbowbow.tistory.com/16

2. Thread

• 프로세스 내에서 실행되는 흐름의 단위
• 각각의 thread는 해당 프로세스의 context에서 실행되며 동일한 코드와 전역 데이터 공유
• 이는 다수의 프로세스를 사용하는 것보다 데이터 공유가 쉽고 전환 속도가 빠르다.
• Race Condition(경쟁 상태) : 동시에 접근하여 일관성을 해치는 결과가 나타날 수 있다.

https://ko.wikipedia.org/wiki/스레드_(컴퓨팅)

3. 동시성과 병렬성

• 동시성(Concurrency) : 다수의 동시에 벌어지는 일을 갖는 시스템에 관한 일반적인 개념
• 병렬성(Parallelism) : 동시성을 사용하여 시스템을 보다 빠르게 동작하도록 하는 것

출처 : https://seamless.tistory.com/42