신장 트리는 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미합니다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 합니다.

최소 신장 트리

최소한의 비용으로 구성되는 신장 트리를 찾아야 할 때 어떻게 해야 할까요?

N개의 도시가 존재한다고 가정할 때 두 도시 사이에 도로를 놓아 전체 도시가 연결될 수 있게 도로를 설치한다고 생각할 수 있습니다. 즉, 두 도시 A,B를 선택했을 때 A에서 B로 이동하는 경로가 반드시 존재하도록 도로를 설치합니다.

이때 사용할 수 있는 알고리즘이 바로 크루스칼 알고리즘입니다.

크루스칼 알고리즘

크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘이며, 그리디 알고리즘으로 분류됩니다.

동작 과정

1. 간선 데이터를 비용에 따라 오름차순으로 정렬합니다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인합니다. 1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킵니다. 2) 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않습니다.
3. 모든 간선에 대해 2번의 과정을 반복합니다.

동작 예시

[초기 단계] 그래프의 모든 간선 정보에 대하여 오름차순 정렬을 수행합니다.

[Step 1] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (3,4)를 선택하여 처리합니다. [Step 2] 아직 처리하지 않은 간선 중 가장 짧은 간선인 (4,7)을 선택하여 처리합니다. [Step 3] 아직 처리하지 않은 간선 중 가장 짧은 간선인 (4,6)을 선택하여 처리합니다. [Step 4] 아직 처리하지 않은 간선 중 가장 짧은 간선인 (6,7)을 선택하여 처리합니다. 6번 노드와 7번 노드는 이미 같은 집합에 속해있으므로 간선을 포함한다면 사이클이 생깁니다. 따라서 해당 간선은 무시하고 넘어갑니다. [Step 5] 아직 처리하지 않은 간선 중 가장 짧은 간선인 (1,2)을 선택하여 처리합니다. 이 과정을 반복하면 다음과 같은 결과를 얻게 됩니다.

결과로 얻은 최소 신장 트리에 포함되어있는 간선의 비용을 모두 더하면, 그 값이 최종 비용에 해당합니다.

구현

import sys
input = sys.stdin.readline

v,e = map(int,input().split())
parent = [i for i in range(v+1)]
graph=[]
result = 0

for _ in range(e):
  a,b,c = map(int,input().split())
  graph.append((c,a,b))

# 비용 순으로 정렬
graph.sort()

# 특정 원소가 속한 집합을 찾을 때까지 
def find_parent(parent,x):
  if parent[x] != x:
    parent[x] = find_parent(parent,parent[x])
  return parent[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

for i in graph:
  cost,a,b = i
  # 사이클이 발생하지 않는 경우에만 집합에 포함
  if find_parent(parent,a)!=find_parent(parent,b):
    union_parent(parent,a,b)
    result += cost

print(result)

성능 분석

크루스칼 알고리즘은 간선의 개수가 E개일 때, O(ElogE)의 시간 복잡도를 가집니다. 크루스칼 알고리즘에서 가장 많은 시간을 요구하는 곳은 간선을 정렬하는 부분입니다.

그렇다면 음수 간선이 포함되는 경우에는 어떻게 문제를 해결해야 할까요?

단순히 음수 간선이 포함되는 것만으로는 다익스트라 알고리즘을 이용하여 문제를 해결할 수 있습니다. 하지만 음수 간선의 순환이 포함된다면 최단 거리가 음의 무한인 노드가 발생할 것입니다.

이 경우에 사용하는 방법이 벨만 포드 알고리즘입니다. 벨만 포드 알고리즘은 다익스트라 알고리즘을 알고 있다는 가정 하에 설명합니다.

최단 경로 문제 분류

최단 경로 문제는 다음과 같이 분류할 수 있습니다.

1. 모든 간선이 양수인 경우
2. 음수 간선이 있는 경우 a. 음수 간선 순환이 없는 경우 b. 음수 간선 순환이 있는 경우

벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있습니다. 또한, 음수 간선의 순환을 감지할 수 있습니다. 벨만 포드의 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느립니다.

벨만 포드 알고리즘

동작은 다음과 같습니다.

1. 출발 노드를 설정합니다.
2. 최단 거리 테이블을 초기화합니다.
3. 다음의 과정을 N-1번 반복합니다. 1) 전체 간선 E개를 하나씩 확인합니다. 2) 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다.

만약 음수 간선 순환이 존재하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행합니다. 이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것입니다.

구현

import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 모든 간선에 대한 정보를 담는 리스트 만들기
edges = []
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    edges.append((a, b, c))

def bf(start):
    # 시작 노드에 대해서 초기화
    distance[start] = 0
    # 전체 n - 1번의 라운드(round)를 반복
    for i in range(n):
        # 매 반복마다 "모든 간선"을 확인하며
        for j in range(m):
            cur_node = edges[j][0]
            next_node = edges[j][1]
            edge_cost = edges[j][2]
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if distance[cur_node] != INF and distance[next_node] > distance[cur_node] + edge_cost:
                distance[next_node] = distance[cur_node] + edge_cost
                # n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
                if i == n - 1:
                    return True
    return False

# 벨만 포드 알고리즘을 수행
negative_cycle = bf(1) # 1번 노드가 시작 노드

if negative_cycle:
    print("-1")
else:
    # 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리를 출력
    for i in range(2, n + 1):
        # 도달할 수 없는 경우, -1을 출력
        if distance[i] == INF:
            print("-1")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(distance[i])

벨만 포드 알고리즘 vs 다익스트라 알고리즘

1. 다익스트라 알고리즘
   • 매번 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택합니다.
   • 음수 간선이 없다면 최적의 해를 찾을 수 있습니다.
2. 벨만 포드 알고리즘
   • 매번 모든 간선을 전부 확인합니다.

   • 따라서 다익스트라 알고리즘에서의 최적의 해를 항상 포함합니다.

   • 다익스트라 알고리즘에 비해 시간이 오래 걸리지만 음수 간선 순환을 탐지할 수 있습니다.

• 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산합니다.
• 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작합니다.
• 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류됩니다.
  • 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복합니다.

동작 과정

1. 출발 노드를 설정합니다.
2. 최단 경로 테이블을 초기화합니다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택합니다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다.
5. 3번과 4번 과정을 반복합니다.

동작 예시

[초기 상태] 그래프를 준비하고 출발 노드를 설정합니다. [Step 1] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 1번 노드를 처리합니다. 1번 노드에 인접한 노드를 확인하여 최단 경로 테이블을 갱신합니다. [Step 2] 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드인 4번 노드를 처리합니다.

[Step 3] 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드인 2번 노드를 처리합니다. 거리가 같은 노드가 있다면 일반적으로 번호가 낮은 노드부터 처리합니다. [Step 4] 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드인 5번 노드를 처리합니다. [Step 5] 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드인 3번 노드를 처리합니다. [Step 5] 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드인 6번 노드를 처리합니다.

다익스트라 알고리즘의 특징

• 매 상황에서 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택해 임의의 과정을 반복합니다. -> 그리디 알고리즘
• 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않습니다.
• 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장됩니다.

성능 분석

위 동작 과정대로 탐색한다면 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 합니다. 따라서 전체 시간 복잡도는 O(V^2)입니다.

일반적으로 코딩 테스트의 최단 경로 문제에서 전체 노드의 개수가 5,000개 이하라면 이 코드로 문제를 해결할 수 있습니다. 하지만 노드의 개수가 10,000개를 넘어가는 문제라면 어떻게 해야 할까요?

이 문제를 해결하기 위해 힙(Heap) 자료구조를 이용합니다. 힙 자료구조를 이용하여 단계마다 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택합니다. 다익스트라 알고리즘이 동작하는 기본 원리는 동일합니다.

• 현재 가장 가까운 노드를 저장해 놓기 위해 힙 자료구조를 추가적으로 이용한다는 점이 다릅니다.
• 현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용합니다.

  구현 방법

  [최소 힙 이용]

  import heapq
  import sys
  input = sys.stdin.readline
  INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
  

노드의 개수, 간선의 개수를 입력받기

n, m = map(int, input().split())

시작 노드 번호를 입력받기

start = int(input())

각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기

graph = [[] for i in range(n + 1)]

최단 거리 테이블을 모두 무한으로 초기화

distance = [INF] * (n + 1)

모든 간선 정보를 입력받기

for _ in range(m): a, b, c = map(int, input().split()) # a번 노드에서 b번 노드로 가는 비용이 c라는 의미 graph[a].append((b, c))

def dijkstra(start): q = [] # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입 heapq.heappush(q, (0, start)) distance[start] = 0 while q: # 큐가 비어있지 않다면 # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기 dist, now = heapq.heappop(q) # 현재 노드가 이미 처리된 적이 있는 노드라면 무시 if distance[now] < dist: continue # 현재 노드와 연결된 다른 인접한 노드들을 확인 for i in graph[now]: cost = dist + i[1] # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우 if cost < distance[i[0]]: distance[i[0]] = cost heapq.heappush(q, (cost, i[0]))

다익스트라 알고리즘을 수행

dijkstra(start)

모든 노드로 가기 위한 최단 거리를 출력

for i in range(1, n + 1): # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력 if distance[i] == INF: print("INFINITY") # 도달할 수 있는 경우 거리를 출력 else: print(distance[i]) ```

대표적인 트리 순회 방법은 전위 순회, 중위 순회, 후위 순회가 있습니다.

위 그림의 트리를 예제로 구현해보겠습니다.

트리 구현을 위해 다음과 같은 클래스를 정의합니다.

class Node:
    def __init__(self, data, left, right):
    self.data = data
    self.left = left
    self.right = right

n = int(input())
tree = {}

for i in range(n):
    data, left, right = input().split()
    if left == "None":
        left = None
    if right == "None":
        right = None
    tree[data] = Node(data, left, right)

# 전위 순회 실행 
pre_order(tree['A']) # A는 시작 노드 

전위 순회(pre-order traverse)

: 루트를 먼저 방문합니다.

def pre_order(node):
    print(node.data, end=' ')
  if node.left != None:
    in_order(tree[node.left])
  if node.right != None:
    in_order(tree[node.right])

중위 순회(in-order traverse)

: 왼쪽 자식을 방문한 뒤에 루트를 방문합니다.

def in_order(node):
  if node.left != None:
    in_order(tree[node.left])
  print(node.data, end=' ')
  if node.right != None:
    in_order(tree[node.right])

후위 순회(post-order traverse)

: 오른쪽 자식을 방문한 뒤에 루트를 방문합니다.

def post_order(node):
  if node.left != None:
    in_order(tree[node.left])
  if node.right != None:
    in_order(tree[node.right])
  print(node.data, end=' ')

전략 패턴은 정책(policy) 패턴이라고도 하며, 객체의 행위를 바꾸고 싶은 경우 '직접' 수정하지 않고 전략이라고 부르는 '캡슐화한 알고리즘'을 컨텍스트 안에서 바꿔주면서 상호 교체가 가능하게 만드는 패턴입니다.

컨텍스트 : 프로그래밍에서의 컨텍스트는 상황, 맥락, 문맥을 의미하며 개발자가 어떠한 작업을 
         완료하는데 필요한 모든 정보를 말한다. 

예시

우리가 어떤 아이템을 살 때 LUNACard로 사는 것과 KAKAOCard로 사는 것을 구현한 예제입니다. 결제 방식의 '전략'만 바꿔서 두 가지 방식으로 결제하는 구현 방식입니다.

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.List;
interface PaymentStrategy { 
    public void pay(int amount);
} 

class KAKAOCardStrategy implements PaymentStrategy {
    private String name;
    private String cardNumber;
    private String cvv;
    private String dateOfExpiry;

    public KAKAOCardStrategy(String nm, String ccNum, String cvv, String expiryDate){
        this.name=nm;
        this.cardNumber=ccNum;
        this.cvv=cvv;
        this.dateOfExpiry=expiryDate;
    }

    @Override
    public void pay(int amount) {
        System.out.println(amount +" paid using KAKAOCard.");
    }
} 

class LUNACardStrategy implements PaymentStrategy {
    private String emailId;
    private String password;

    public LUNACardStrategy(String email, String pwd){
        this.emailId=email;
        this.password=pwd;
    }

    @Override
    public void pay(int amount) {
        System.out.println(amount + " paid using LUNACard.");
    }
} 

class Item { 
    private String name;
    private int price; 
    public Item(String name, int cost){
        this.name=name;
        this.price=cost;
    }

    public String getName() {
        return name;
    }

    public int getPrice() {
        return price;
    }
} 

class ShoppingCart { 
    List<Item> items;

    public ShoppingCart(){
        this.items=new ArrayList<Item>();
    }

    public void addItem(Item item){
        this.items.add(item);
    }

    public void removeItem(Item item){
        this.items.remove(item);
    }

    public int calculateTotal(){
        int sum = 0;
        for(Item item : items){
            sum += item.getPrice();
        }
        return sum;
    }

    // 전략에 따라 결제 방식이 달라짐 
    public void pay(PaymentStrategy paymentMethod){
        int amount = calculateTotal();
        paymentMethod.pay(amount);
    }
}  

public class HelloWorld{
    public static void main(String []args){
        ShoppingCart cart = new ShoppingCart();

        Item A = new Item("kundolA",100);
        Item B = new Item("kundolB",300);
        // 카트에 아이템 추가 
        cart.addItem(A);
        cart.addItem(B);

        // pay by LUNACard
        cart.pay(new LUNACardStrategy("kundol@example.com", "pukubababo"));
        // pay by KAKAOBank
        cart.pay(new KAKAOCardStrategy("Ju hongchul", "123456789", "123", "12/01"));
    }
}
/*
400 paid using LUNACard.
400 paid using KAKAOCard.
*/

passport의 전략 패턴

전략 패턴을 활용한 라이브러리로는 passport가 있습니다. https://www.passportjs.org/

passport는 Node.js에서 인증 모듈을 구현할 때 쓰는 미들웨어 라이브러리로, 여러 가지 '전략'을 기반으로 인증할 수 있게 합니다. 예를 들어 서비스 내의 회원가입된 id, pw를 기반으로 인증하는 LocalStrategy 전략과 소셜 로그인 서비스를 기반으로 인증하는 OAuth 전략 등을 지원합니다.

팩토리 패턴(factory pattern)은 객체를 사용하는 코드에서 객체 생성 부분을 떼어내 추상화한 패턴이자 상속 관계에 있는 두 클래스에서 상위 클래스가 중요한 뼈대를 결정하고, 하위 클래스에서 객체 생성에 관한 구체적인 내용을 결정하는 패턴입니다.

상위 클래스와 하위 클래스가 분리되기 때문에 느슨한 결합을 가지며 상위 클래스에서는 인스턴스 생성 방식에 대해 전혀 알 필요가 없기 때문에 더 많은 유연성을 갖게 됩니다. 그리고 객체 생성 로직이 따로 떼어져 있기 때문에 코드를 리팩터링하더라도 한 곳만 고칠 수 있게 되니 유지 보수성이 증가됩니다.

자바스크립트의 팩토리 패턴

커피 팩토리를 기반으로 커피를 생산하는 코드를 보겠습니다.

// 상위 클래스 
class CoffeeFactory {
    static createCoffee(type) {
        const factory = factoryList[type]
        return factory.createCoffee()
    }
}   

// 하위 클래스 
class Latte {
    constructor() {
        this.name = "latte"
    }
}
//하위 클래스 
class Espresso {
    constructor() {
        this.name = "Espresso"
    }
} 

class LatteFactory extends CoffeeFactory{
    static createCoffee() {
        return new Latte()
    }
}
class EspressoFactory extends CoffeeFactory{
    static createCoffee() {
        return new Espresso()
    }
}
const factoryList = { LatteFactory, EspressoFactory } 


const main = () => {
    // 라떼 커피를 주문한다.  
    const coffee = CoffeeFactory.createCoffee("LatteFactory")  
    // 커피 이름을 부른다.  
    console.log(coffee.name) // latte
}
main()

CoffeeFactory라는 상위 클래스가 중요한 뼈대를 결정하고 하위 클래스인 LatteFactory가 구체적인 내용을 결정하고 있습니다.

참고로 이는 의존성 주입이라고도 볼 수 있습니다. CoffeeFactory에서 LatteFactory의 인스턴스를 생성하는 것이 아닌 LatteFactory에서 생성한 인스턴스를 CoffeeFactory에 주입하고 있기 때문입니다.

또한, static 키워드를 통해 createCoffee() 메서드를 선언함으로써 클래스를 기반으로 객체를 만들지 않고 호출이 가능해 메모리 할당을 한 번만 할 수 있는 장점이 있습니다.

자바의 팩토리 패턴

이를 자바로 구현하면 다음과 같습니다.

enum CoffeeType {
    LATTE,
    ESPRESSO
}

abstract class Coffee {
    protected String name;

    public String getName() {
        return name;
    }
}

class Latte extends Coffee {
    public Latte() {
        name = "latte";
    }
}

class Espresso extends Coffee {
    public Espresso() {
        name = "Espresso";
    }
}

class CoffeeFactory {
    public static Coffee createCoffee(CoffeeType type) {
        switch (type) {
            case LATTE:
                return new Latte();
            case ESPRESSO:
                return new Espresso();
            default:
                throw new IllegalArgumentException("Invalid coffee type: " + type);
        }
    }
}

public class Main {
    public static void main(String[] args) { 
        Coffee coffee = CoffeeFactory.createCoffee(CoffeeType.LATTE); 
        System.out.println(coffee.getName()); // latte
    }
}

싱글톤 패턴(singleton pattern)은 하나의 클래스에 오직 하나의 인스턴스만 가지는 패턴으로, 보통 데이터베이스 연결 모듈에 많이 사용됩니다.

하나의 인스턴스를 다른 모듈들이 공유하며 사용하기 떄문에 인스턴스를 생성할 때 드는 비용이 줄어들지만, 의존성이 높아진다는 단점이 있습니다.

객체 : 소프트웨어 세계에 구현할 대상 
클래스 : 구현을 위한 설계도
인스턴스 : 설계도에 따라 소프트웨어 세계에 구현된 실체 

데이터베이스 연결 모듈

// js
// DB 연결을 하는 것이기 때문에 비용이 더 높은 작업 
const URL = 'mongodb://localhost:27017/kundolapp' 
const createConnection = url => ({"url" : url})    
class DB {
    constructor(url) {
        if (!DB.instance) { 
            DB.instance = createConnection(url)
        }
        return DB.instance
    }
    connect() {
        return this.instance
    }
}
const a = new DB(URL)
const b = new DB(URL) 
console.log(a === b) // true

이렇게 DB.instance라는 하나의 인스턴스를 기반으로 a, b를 생성합니다. 이를 통해 데이터베이스 연결에 관한 인스턴스 생성 비용을 아낄 수 있습니다.

싱글톤 패턴의 단점

싱글톤 패턴은 TDD(Test Driven Development)를 할 때 걸림돌이 됩니다. TDD를 할 때 단위 테스트를 주로 하는데, 단위 테스트는 서로 독립적이어야 하며 테스트를 어떤 순서로든 실행할 수 있어야 합니다.

하지만 싱글톤 패턴은 하나의 인스턴스를 기반으로 구현하는 패턴이므로 각 테스트마다 '독립적인' 인스턴스를 만들기가 어렵습니다.

의존성 주입

싱글톤 패턴은 모듈 간의 결합을 강하게 만들 수 있다는 단점이 있습니다. 이때 의존성 주입(DI, Dependency Injection)을 통해 모듈 간의 결합을 좀 더 느슨하게 만들어 해결할 수 있습니다.

의존성(종속성) : A가 B에 의존성이 있다는 것은 B의 변경 사항을 A도 따라야 한다는 것

위 그림처럼 의존성 주입자(dependency injector)가 중간에 의존성을 가로채 메인 모듈이 간접적으로 의존성을 주입하는 방식입니다.

이를 통해 메인 모듈(상위 모듈)은 하위 모듈에 대한 의존성이 떨어지게 됩니다. 이를 '디커플링이 된다'고도 합니다.

의존성 주입의 장점

• 모듈들을 쉽게 교체할 수 있는 구조가 되어 테스팅하기 쉬움
• 마이그레이션하기 수월함
• 구현할 때 추상화 레이어를 넣고 이를 기반으로 구현체를 넣어주기 때문에 애플리케이션 의존성 방향이 일관됨
• 애플리케이션을 쉽게 추론 가능
• 모듈 간의 관계들이 조금 더 명확해짐

마이그레이션 : 데이터나 소프트웨어를 한 시스템에서 다른 시스템으로 이동하는 것

의존성 주입의 단점

• 모듈들이 더 분리되므로 클래스 수가 늘어가 복잡성 증가
• 약간의 런타임 페널티 생김

의존성 주입 원칙

• 상위 모듈은 하위 모듈에서 어떠한 것도 가져오지 않아야 함
• 상위 모듈과 하위 모듈 모두 추상화에 의존해야 함
• 이때 추상화는 세부 사항에 의존하지 말아야 함

의존성을 주입할 때는 위 세 가지 원칙을 지켜주면서 만들어야 합니다.

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

풀이

물건의 수 N, 버틸 수 있는 무게 K에 대하여 N*K의 2차원 배열을 이용한다. d[n][k]는 n번째 물건까지 살펴보았을 때, 무게가 k인 배낭의 최대 가치이다.

물건을 배낭에 담을 때,

1. 허용 무게가 넣을 물건의 무게보다 작다면 넣지 않는다.
2. 그렇지 않다면, 두 가지 중 더 높은 가치를 선택한다.

• 현재 넣을 물건의 무게만큼 배낭에서 뺀 후 현재 물건을 넣는다.
• 이전 배낭을 그대로 유지한다.

위 과정을 코드로 나타내면 다음과 같다. 현재 담을 물건의 인덱스를 i, 현재 가방 허용 용량이 j, 현재 담을 물건의 무게를 weight, 가치 value라고 할 때,

if j<weight 
    -> d[i][j] = d[i-1][j]
else 
    -> d[i][j] = max(d[i-1][j], d[i-1][j-weight]+value)

소스코드

import sys
input = sys.stdin.readline

n,k = map(int,input().split())
d = [[0]*(k+1) for _ in range(n+1)]
we = [[0,0]]
for _ in range(n):
  we.append(list(map(int,input().split())))

for i in range(1,n+1):
  for j in range(1,k+1):
    w,v = we[i][0], we[i][1]

    if j<w:
      d[i][j] = d[i-1][j]
    else:
      d[i][j] = max(d[i-1][j], d[i-1][j-w]+v) 

print(d[n][k])

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다.

아이디어

이 문제에서 n의 값은 매우 크기 때문에 피사노 주기라는 방법을 활용한다.

피사노 주기는 피보나치 수를 K로 나눈 나머지는 항상 주기를 갖게된다는 원리이다.

주기의 길이가 P 일 때, N번째 피보나치 수를 M으로 나눈 나머지는 N%P번째 피보나치 수를 M을 나눈 나머지와 같다.

M = 10^k 일 때, k>2 라면 주기는 항상 15*10^(k-1) 이다.

소스코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
Q = 1000000

n = int(input())
p = 15*Q//10  # 나머지 주기
d = [0]*(p+1)
d[1] = 1

for i in range(2,p):
  d[i] = d[i-1]+d[i-2]
  d[i] %= Q

print(d[n%p])

• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 알고리즘입니다.
  • 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능합니다.
• 데이터의 개수가 N, 데이터(양수) 중 최대값이 K일 때, 최악의 경우에도 수행 시간 O(N+K)를 보장합니다.

동작 예시

정렬할 데이터 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

[Step 0] 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성합니다.

[Step 1] 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킵니다. 결과적으로 최종 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록됩니다.

[Step 2] 결과를 확인할 때는 리스트의 첫 번째 데이터부터 하나씩 그 값 만큼 반복하여 인덱스를 출력합니다.

출력 결과 : 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

소스코드

# 모든 원소의 값이 0보다 크거나 같다고 가정 
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array)+1)

for i in range(len(array)):
    count[array[i]] += 1

for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=" ")

복잡도

계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(N+K)입니다.

• 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있습니다.
  • 데이터가 0과 999,999로 단 두개만 존재하는 경우
• 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있습니다.

기준 데이터를 설정하고 그 기준보다 작은 데이터의 위치를 바꾸는 방법입니다.

일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘입니다. 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘입니다. 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정합니다.

동작 예시

[Step 0] 현재 피벗의 값은 5입니다. 왼쪽에서부터 5보다 큰 데이터를 선택하므로 7이 선택되고, 오른쪽에서부터 5보다 작은 데이터를 선택하므로 4가 선택됩니다. 이제 이 두 데이터의 위치를 서로 변경합니다. [Step 1] 현재 피벗의 값은 5입니다. 왼쪽에서부터 5보다 큰 데이터를 선택하므로 9가 선택되고, 오른쪽에서부터 5보다 작은 데이터를 선택하므로 2가 선택됩니다. 이제 이 두 데이터의 위치를 서로 변경합니다. [Step 2] 현재 피벗의 값은 5입니다. 왼쪽에서부터 5보다 큰 데이터를 선택하므로 6이 선택되고, 오른쪽에서부터 5보다 작은 데이터를 선택하므로 1이 선택됩니다. 단, 이처럼 위치가 엇갈리는 경우 피벗과 작은 데이터의 위치를 서로 변경합니다. [분할 완료] 이제 5의 왼쪽에 있는 데이터는 모두 5보다 작고, 오른쪽에 있는 데이터는 5보다 크다는 특징이 있습니다. 이렇게 피벗을 기준으로 데이터를 나누는 작업을 분할(Divide)이라고 합니다. [왼쪽 데이터 묶음] 왼쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행합니다.

이러한 과정을 반복하면 전체 데이터에 대해 정렬이 수행됩니다.

시간 복잡도

퀵 정렬은 평균의 경우 O(NlogN)의 시간복잡도를 가집니다. 너비 X 높이 = N x logN = NlogN

하지만 최악의 경우 O(N^2)의 시간복잡도를 가집니다.

소스코드

[일반적인 방식]

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end:
        return 
    pivot = start
    left = start + 1
    right = end
    while (left <= right):
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while(left <= end and array[left] <= array[pivot]):
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while(right > start and array[right] >= array[pivot]):
            right += 1
        if (left > right)    # 엇갈렸다면 피벗과 작은 데이터 교체
            array[right], pivot = pivot, array[right]
        else:    # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체 
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행 
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

quick_sort(array, 0, len(array)-1)
print(array)

# 실행 결과 
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[파이썬의 장점을 살린 방식]

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    if len(array) <= 1:
        return array
    pivot = array[0]
    tail = array[1:]

    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]

    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

# 실행 결과 
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다.

삽입 정렬은 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작합니다.

동작 예시

[Step 0] 첫 번째 데이터 7은 그 자체로 정렬이 되어있다고 판단하고, 두 번째 데이터인 5가 어떤 위치로 들어갈지 판단합니다. 7의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재합니다. [Step 1] 이어서 9가 어떤 위치로 들어갈지 판단합니다. [Step 2] 이어서 0이 어떤 위치로 들어갈지 판단합니다. [Step 3] 이어서 3이 어떤 위치로 들어갈지 판단합니다. 이러한 과정을 반복하면 다음과 같이 정렬이 완료됩니다.

소스코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1,len(array)):
    for j in range(i,0,-1):    # 인덱스 i부터 1까지 1씩 감소하며 반복
        if array[j] < array[j-1]:    # 한 칸 씩 왼쪽으로 이동
            array[j], array[j-1] = array[j-1], array[j]
        else:    # 자기보다 작은 데이터를 만나면 break
            break
print(array)

# 실행 결과 
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

시간 복잡도

삽입 정렬의 시간 복잡도는 O(N^2)이며, 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용됩니다.

삽입 정렬은 현재 리스트 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작합니다. 최선의 경우 O(N)의 시간복잡도를 가집니다.

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다.

동작 예시

[Step 0] 처리되지 않은 데이터 중 가장 작은 0을 선택해 가장 앞인 7과 바꿉니다. [Step 1] 처리되지 않은 데이터 중 가장 작은 1을 선택해 가장 앞인 5와 바꿉니다. [Step 2] 처리되지 않은 데이터 중 가장 작은 2을 선택해 가장 앞인 9와 바꿉니다. [Step 3] 처리되지 않은 데이터 중 가장 작은 3을 선택해 가장 앞인 7과 바꿉니다. 이러한 과정을 반복하면 다음과 같이 정렬이 완료됩니다.

소스코드

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)):
    min_idx = i
    for j in range(i+1,len(array)):
        if array[min_idx] > array[j]:
            min_idx = j
    array[i], array[min_idx] = array[min_idx],array[i]

print(array)

# 실행 결과 
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

시간 복잡도

선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 합니다.

전체 연산 횟수는 N + (N-1) + (N-2) + ... + 2와 같고 이는 빅오 표기법에 따라 O(N^2)라고 작성합니다. 1

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법입니다.

이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다.

예시

이미 정렬된 10개의 데이터 중 값이 4인 원소를 찾는 예시를 살펴봅시다.

[Step 1] 시작점 : 0, 끝점 : 9, 중간점 : 4 (소수점 이하 제거) 이때 중간점인 8이 4보다 크므로 끝점을 3으로 바꿉니다.

[Step 2] 시작점 : 0, 끝점 : 3, 중간점 : 1 (소수점 이하 제거)

[Step 2] 시작점 : 2, 끝점 : 3, 중간점 : 2 (소수점 이하 제거)

이렇게 탐색 범위를 절반씩 줄여가며 탐색하는 방법을 이진 탐색이라고 합니다.

시간 복잡도

단계마다 탐색 범위를 2로 나누는 것과 동일하므로 밑이 2인 로그, log2 N에 비례합니다.

소스코드

위 예시의 이진 탐색 함수 코드는 다음과 같습니다.

# 이진 탐색
def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start+end)//2

    # 찾은 경우 
    if array[mid] == target:
        return mid
    # 중간점이 찾고자하는 값보다 큰 경우 왼쪽 탐색 
    elif array[mid] > target:
        return binary_search(array, target, start, mid-1)
    # 중간점이 찾고자하는 값보다 작은 경우 오른쪽 탐색 
    else:
        return binary_search(array, target, mid+1, end)

라이브러리

• bisect_left(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
• bisect_right(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

아이디어

먼저, 이 문제를 풀기 위해서는 트리의 지름을 구하는 방법을 알아야 한다.

트리의 지름은 다음과 같이 구할 수 있다.

1. 임의의 정점 하나에 대해 가장 먼 정점을 구한다.
2. 새로 구한 정점에 대해 가장 먼 정점을 한 번 더 구한다.
3. 2번 과정에서 나온 두 정점의 거리가 트리의 지름이 된다.

이렇게 2번의 dfs를 통해 트리의 지름을 구할 수 있다.

풀이

[틀린 풀이] 이 풀이는 2%에서 틀렸다고 나왔다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

v=int(input())
graph = [[] for _ in range(v+1)]

# 틀린 위치
for j in range(v):
  n = list(map(int,input().split()[1:-1]))
  for i in range(0,len(n)-1,2):
    graph[j+1].append((n[i],n[i+1]))
# 여기까지

visited=[False]*(v+1)
dist=[0]*(v+1)

def dfs(x):
  visited[x] = True
  for i in graph[x]:
    if not visited[i[0]]:
      dist[i[0]] = dist[x]+i[1]
      dfs(i[0])

# 첫 번째 dfs
dfs(1)
m = dist.index(max(dist))

visited=[False]*(v+1)
dist=[0]*(v+1)

# 두 번째 dfs
dfs(m)
print(max(dist))

예시 입력을 보면 2~v+1의 줄에서 첫 번째 숫자는 정점의 번호를 의미한다. 이 번호가 주어질 필요가 없다고 생각했는데 입력 조건을 자세히 들여다보면 입력되는 정점의 순서가 고정되지 않았다는 사실을 알 수 있었다. 따라서 정점 번호는 꼭 필요한 조건이었다.

[맞은 풀이]

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

v=int(input())
graph = [[] for _ in range(v+1)]
# 고친 부분
for _ in range(v):
  n = list(map(int,input().split()[:-1]))
  for i in range(1,len(n)-1,2):
    graph[n[0]].append((n[i],n[i+1]))
# 여기까지

visited=[False]*(v+1)
dist=[0]*(v+1)

def dfs(x):
  visited[x] = True
  for i in graph[x]:
    if not visited[i[0]]:
      dist[i[0]] = dist[x]+i[1]
      dfs(i[0])

dfs(1)
m = dist.index(max(dist))
visited=[False]*(v+1)
dist=[0]*(v+1)
dfs(m)
print(max(dist))

• 참고하면 좋을 반례들 https://www.acmicpc.net/board/view/67245

++ 참고로 dfs같이 재귀함수를 이용하는 경우에, 파이썬은 재귀가 1000으로 제한되어 있어서 sys.setresursionlimit()를 꼭 설정해주어야 한다.

프로그램이 실행될 때는 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정합니다. 이 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐에 있는 프로세스는 적게, 응답 시간은 짧게 설정하는 것을 목표로 합니다.

비선점형 방식

비선점형 방식(non-preemptive)은 프로세스가 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않습니다. 따라서 컨텍스트 스위칭으로 인한 부하가 적습니다.

FCFS(First Come, First Served)

FCFS(First Come, First Served)는 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘입니다. 길게 수행되는 프로세스 때문에 '준비 큐에서 오래 기다리는 현상(convoy effect)'이 발생하는 단점이 있습니다.

SJF(Shortest Job First)

SJF(Shortest Job First)는 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘입니다. 긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 일어나며 평균 시간이 가장 짧습니다. 하지만 실제로는 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용합니다.

우선순위

오래된 작업일수록 '우선순위를 높이는 방법(aging)'을 통해 긴 시간을 가진 프로세스가 실행되지 않는 단점을 보안한 알고리즘입니다.

선점형 방식

선점형 방식(preemptive)은 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식으로 현대 운영체제가 쓰는 방식입니다.

라운드 로빈

라운드 로빈(RR, Round Robin)은 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘으로 우선순위 스케줄링의 일종입니다.

일반적을 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아진다는 특징이 있습니다. 또한, 이 알고리즘은 로드밸런서에서 트래픽 분산 알고리즘으로도 쓰입니다.

SRF(Shortest Remaining Time First)

SJF는 중간에 실행 시간이 더 짧은 작업이 들어와도 기존 짧은 작업을 모두 수행한 후 그 다음 짧은 작업을 이어나가는데, SRF는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘입니다.

다단계 큐

다단계 큐는 우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 다른 스케줄링 알고리즘을 적용한 것을 말합니다. 큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특징이 있습니다.

멀티프로세싱은 여러 개의 프로세스, 즉 멀티프로세스를 통해 동시에 두 가지 이상의 일을 수행할 수 있는 것을 말합니다. 이를 통해 하나 이상의 일을 병렬로 처리할 수 있으며 특정 프로세스의 메모리, 프로세스 중 일부에 문제가 발생되더라도 다른 프로세스를 이용해서 처리할 수 있으므로 신뢰성이 높은 강점이 있습니다.

웹 브라우저

웹 브라우저는 멀티프로세스 구조를 가지고 있습니다.

구조

• 브라우저 프로세스 : 주소 표시줄, 북마크 막대, 뒤로 가기 버튼 등을 담당하며 네트워크 요청이나 파일 접근 같은 권한을 담당합니다.
• 렌더러 프로세스 : 웹 사이트가 보이는 부분의 모든 것을 제어합니다.
• 플러그인 프로세스 : 웹 사이트에서 사용하는 플러그인을 제어합니다.
• GPU 프로세스 : GPU를 이용해서 화면을 그리는 부분을 제어합니다.

IPC

IPC(Inter Process Communication)는 프로세스끼리 데이터를 주고받고 공유 데이터를 관리하는 메커니즘을 뜻하며, 멀티프로세스는 IPC가 가능합니다.

IPC의 종류로는 공유 메모리, 파일, 소켓, 익명 파이프, 명명 파이프, 메시지 큐가 있습니다. 이들은 모두 메모리가 완전히 공유되는 스레드보다는 속도가 떨어집니다.

공유 메모리

공유 메모리(shared memory)는 여러 프로세스에 동일한 메모리 블록에 대한 접근 권한이 부여되어 프로세스가 서로 통신할 수 있도록 공유 메모리를 생성해서 통신하는 것을 말합니다.

공유 메모리를 통해 여러 프로세스가 하나의 메모리를 공유할 수 있으며, 메모리 자체를 공유하기 때문에 불필요한 데이터 복사의 오버헤드가 발생하지 않아 가장 빠릅니다. 같은 메모리 영역을 여러 프로세스가 공유하기 때문에 동기화가 필요합니다.

파일

파일은 디스크에 저장된 데이터 또는 파일 서버에서 제공한 데이터를 말합니다.

소켓

동일한 컴퓨터의 다른 프로세스나 네트워크의 다른 컴퓨터로 네트워크 인터페이스를 통해 전송하는 데이터를 의미하며 TCP와 UDP가 있습니다.

익명 파이프

익명 파이프(unamed pipe)는 프로세스 간에 FIFO 방식으로 읽히는 임시 공간이 파이프를 기반으로 데이터를 주고받으며, 단방향 방식의 읽기 전용, 쓰기 전용 파이프를 만들어서 작동하는 방식입니다. 이는 부모, 자식 프로세스 간에만 사용할 수 있습니다.

명명된 파이프

명명된 파이프(named pipe)는 파이프 서버와 하나 이상의 파이프 클라이언트 간의 통신을 위한 명명된 단방향 또는 양방향 파이프를 말합니다. 클라이언트/서버 통신을 위한 별도의 파이프를 제공하며, 여러 파이프를 동시에 사용할 수 있습니다. 컴퓨터의 프로세스끼리 또는 다른 네트워크 상의 컴퓨터와도 통신을 할 수 있습니다.

메시지 큐

메시지 큐는 메시지를 큐 데이터 구조 형태로 관리하는 것을 의미합니다. 이는 커널의 전역변수 형태 등 커널에서 전역적으로 관리되며 다른 IPC 방식에 비해서 사용 방법이 매우 직관적이고 간단하며 다른 코드의 수정 없이 단지 몇 줄의 코드를 추가시켜 간단하게 메시지 큐에 접근할 수 있는 장점이 있습니다.

스레드와 멀티스레딩

스레드

스레드는 프로세스의 실행 가능한 가장 작은 단위입니다. 프로세스는 여러 스레드를 가질 수 있습니다.

프로세스는 코드, 데이터, 스택, 힙을 각각 생성하고 스레드는 그 중 코드, 데이터, 힙을 스레드끼리 서로 공유합니다. 그 외의 영역은 각각 생성됩니다.

멀티스레딩

멀티스레딩은 프로세스 내 작업을 여러 개의 스레드로 처리하는 기법이며 스레드끼리 서로 자원을 공유하기 때문에 효율성이 높습니다. 예를 들어 웹 요청을 처리할 때 스레드를 사용하는 웹 서버의 경우 훨씬 적은 리소스를 소비하며, 한 스레드가 중단되어도 다른 스레드는 실행 상태일 수 있기 때문에 중단되지 않은 빠른 처리가 가능합니다. 또한, 동시성에도 큰 장점이 있습니다. 하지만 한 스레드에 문제가 생기면 다른 스레드에도 영향을 끼쳐 프로세스에 영향을 줄 수 있습니다.

동시성 : 서로 독립적인 작업들을 단위로 나누고 동시에 실행되는 것처럼 보여주는 것 

공유 자원과 임계 영역

공유 자원

공유 자원(shared resource)은 시스템 안에서 각 프로세스, 스레드가 함께 접근할 수 있는 자원(모니터, 프린터, 메모리, 파일, 데이터 등)이나 변수 등을 의미합니다. 이 공유 자원을 두 개 이상의 프로세스가 동시에 읽거나 쓰는 상황을 경쟁 상태(race condition)라고 합니다.

임계 영역

임계 영역(critical section)은 둘 이상의 프로세스, 스레드가 공유 자원에 접근할 때 순서 등의 이유로 결과가 달라지는 코드 영역을 말합니다.

임계 영역을 해결하기 위한 방법은 크게 뮤텍스, 세마포어, 모니터 세 가지가 있으며, 이 방법 모두 상호 배제, 한정 대기, 융통성이란 조건을 만족합니다.

상호 배제 : 한 프로세스가 임계 영역에 들어갔을 때 다른 프로세스는 들어갈 수 없다. 

한정 대기 : 특정 프로세스가 영원히 임계 영역에 들어가지 못하면 안된다. 

융통성 : 한 프로세스가 다른 프로세스의 일을 방해해서는 안된다. 

뮤텍스

뮤텍스(mutex)는 프로세스나 스레드가 공유 자원을 lock()을 통해 잠금 설정하고 사용한 후에는 unlock()을 통해 잠금 해제하는 객체입니다. 뮤텍스는 잠금 또는 잠금 해제라는 상태만을 가집니다.

세마포어

세마포어(semaphore)는 일반화된 뮤텍스입니다. 간단한 정수 값과 두 가지 함수 wait(P 함수) 및 signal(V 함수)로 공유 자원에 대한 접근을 처리합니다. wait()는 자신의 차례가 올 때까지 기다리는 함수이며, signal()은 다음 프로세스로 순서를 넘겨주는 함수입니다.

세마포어에는 조건 변수가 없고 프로세스나 스레드가 세마포어 값을 수정할 때 다른 프로세스나 스레드는 동시에 세마포어 값을 수정할 수 없습니다.

바이너리 세마포어

바이너리 세마포어는 0과 1의 두 가지 값만 가질 수 있는 세마포어입니다. 구현의 유사성으로 인해 뮤텍스는 바이너리 세마포어라고 할 수 있지만 뮤텍스는 잠금을 기반으로 상호배제가 일어나는 '잠금 메커니즘'이고, 세마포어는 신호를 기반으로 상호 배제가 일어나는 '신호 메커니즘'입닏다.

카운팅 세마포어

카운팅 세마포어는 여러 개의 값을 가질 수 있는 세마포어이며, 여러 자원에 대한 접근을 제어하는 데 사용됩니다.

모니터

모니터는 둘 이상의 스레드는 프로세스가 공유 자원에 안전하게 접근할 수 있도록 공유 자원을 숨기고 해당 접근에 대해 인터페이스만 제공합니다.

모니터는 모니터큐를 통해 공유 자원에 대한 작업들을 순차적으로 처리합니다.

모니터는 세마포어보다 구현하기 쉬우며 모니터에서 상호 배제는 자동인 반면, 세마포어에서는 상호 배제를 명시적으로 구현해야 하는 차이점이 있습니다.

교착 상태

교착 상태(deadlock)는 두 개 이상의 프로세스들이 서로가 가진 자원을 기다리며 중단된 상태를 말합니다. 예를 들어 프로세스 A가 프로세스 B의 어떤 자원을 요청할 때 프로세스 B도 프로세스 A가 점유하고 있는 자원을 요청하는 것이죠. 이에 대한 원인과 해결 방법은 다음과 같습니다.

교착 상태의 원인

• 상호 배제 : 한 프로세스가 자원을 독점하고 있으며 다른 프로세스들은 접근이 불가능합니다.
• 점유 대기 : 특정 프로세스가 점유한 자원을 다른 프로세스가 요청하는 상태입니다.
• 비선점 : 다른 프로세스의 자원을 강제적으로 가져올 수 없습니다.
• 환형 대기 : 프로세스 2개가 서로의 자원을 요구하는 상황을 말합니다.

교착 상태의 해결 방법

1. 자원을 할당할 때 애초에 조건이 성립되지 않도록 설계합니다.
2. 교착 상태 가능성이 없을 때만 자원 할당되며, 프로세스당 요청할 자원들의 최대치를 통해 자원 할당 가능 여부를 파악하는 '은행원 알고리즘'을 씁니다.
3. 교착 상태가 발생하면 사이클이 있는지 찾아보고 이에 관련된 프로세스를 한 개씩 지웁니다.
4. 교착 상태는 매우 드물게 일어나기 때문에 이를 처리하는 비용이 더 커서 교착 상태가 발생하면 사용자가 작업을 종료합니다.

은행원 알고리즘 
: 총 자원의 양과 현재 할당한 자원의 양을 기준으로 안정 또는 불안정으로 나누고 
  안정 상태로 가도록 자원을 할당하는 알고리즘 

프로그램이 메모리에 올라가면 프로세스가 되는 인스턴스화가 일어나고, 이후 운영체제의 CPU 스케줄러에 따라 CPU가 프로세스를 실행합니다.

프로세스와 컴파일 과정

[프로그램의 컴파일 과정]

전처리

소스 코드의 주석을 제거하고 헤더 파일을 병합하여 매크로를 치환합니다.

컴파일러

오류 처리, 코드 최적화 작업을 하며 어셈블리어로 변환합니다.

어셈블러

어셈블리어는 목적 코드(object code)로 변환됩니다.

링커

프로그램 내에 있는 라이브러리 함수 또는 다른 파일들과 목적 코드를 결합하여 실행 파일을 만듭니다. 실행 파일의 확장자는 .exe 또는 .out이라는 확장자를 갖습니다.

정적 라이브러리와 동적 라이브러리

라이브러리는 정적 라이브러리와 동적 라이브러리로 나뉩니다.

정적 라이브러리는 프로그램 빌드 시 라이브러리가 제공하는 모든 코드를 실행 파일에 넣는 방식으로 라이브러리를 쓰는 방법입니다. 시스템 환경 등 외부 의존도가 낮은 장점이 있지만 코드 중복 등 메모리 효율성이 떨어지는 단점이 있습니다.

동적 라이브러리는 프로그램 실행 시 필요할 때만 DLL이라는 함수 정보를 통해 참조하여 라이브러리를 쓰는 방법입니다. 메모리 효율성에서의 장점을 지니지만 외부 의존도가 높아진다는 단점이 있습니다.

프로세스의 상태

프로세스의 상태는 여러 가지 상태 값을 갖습니다.

생성 상태

생성 상태(create)는 프로세스가 생성된 상태를 의미하며 fork() 또는 exec() 함수를 통해 생성합니다. 이때 PCB가 할당됩니다.

fork()

fork()는 부모 프로세스의 주소 공간을 그대로 복상하여 새로운 자식 프로세스를 생성하는 함수입니다.

exec()

exec()는 새롭게 프로세스를 생성하는 함수입니다.

대기 상태

대기 상태(ready)는 메모리 공간이 충분하면 메모리를 할당받고 아니면 아닌 상태로 대기하고 있으며 CPU 스케줄러로부터 CPU 소유권이 넘어오기를 기다리는 상태입니다.

대기 중단 상태

대기 중단 상태(ready suspended)는 메모리 부족으로 일시 중단된 상태입니다.

실행 상태

실행 상태(running)는 CPU 소유권과 메모리를 할당받고 인스트럭션을 수행 중인 상태를 의미합니다. 이를 CPU burst가 일어났다고도 표현합니다.

중단 상태

중단 상태(blocked)는 어떤 이벤트가 발생한 이후 기다리며 프로세스가 차단된 상태입니다. I/O 디바이스에 의한 인터럽트로 이런 현상이 많이 발생하기도 합니다.

일시 중단 상태

일시 중단 상태(blocked suspended)는 대기 중단과 유사합니다. 중단된 상태에서 프로세스가 실행되려고 했지만 메모리 부족으로 일시 중단된 상태입니다.

종료 상태

종료 상태(terminated)는 메모리와 CPU 소유권을 모두 놓고 가는 상태를 말합니다. 종료는 자연스럽게 종료되는 것도 있지만 부모 프로세스가 자식 프로세스를 강제시키는 비자발적 종료(abort)로 종료되는 것도 있습니다. 자식 프로세스에서 할당된 자원의 한계치를 넘어서거나 부모 프로세스가 종료되거나 사용자가 process.kill 등 여러 명령어로 프로세스를 종료시킬 때 발생합니다.

프로세스의 메모리 구조

위에서부터 스택, 힙, 데이터 영역(BSS segment, Data segment), 코드 영역으로 나눠집니다. 스택은 위 주소부터 할당되고 힙은 아래 주소부터 할당됩니다.

스택과 힙

스택과 힙은 동적 할당이 되며, 동적 할당은 런타임 단계에서 메모리를 할당받는 것을 말합니다. 스택은 지역 변수, 매개변수, 실행되는 함수에 의해 늘어나거나 줄어드는 메모리 영역입니다. 함수가 호출될 때마다 호출될 때의 환경 등 특정 정보가 스택에 계속해서 저장됩니다. 또한, 재귀 함수가 호출된다고 했을 때 새로운 스택 프레임이 매번 사용되기 때문에 함수 내의 변수 집합이 해당 함수의 다른 인스턴스 변수를 방해하지 않습니다.

힙은 동적으로 할당되는 변수들을 담습니다. malloc(), free() 함수를 통해 관리할 수 있으며 동적으로 관리되는 자료 구조의 경우 힙 영역을 사용합니다.

데이터 영역과 코드 영역

이 영역은 정적 할당되는 영역입니다. 정적 할당은 컴파일 단계에서 메모리를 할당하는 것을 말합니다. 데이터 영역은 BSS segment와 Data segment, code/text segment로 나뉘어서 저장됩니다.

BSS segment는 전역 변수 또는 static, const로 선언되어 있고 0으로 초기화 또는 초기화가 어떠한 값으로도 되어있지 않은 변수들이 이 메모리 영역에 할당됩니다. Data segment는 전역 변수 또는 static, const로 선언되어 있고 0이 아닌 값으로 초기화된 변수가 이 메모리 영역에 할당됩니다. code segment는 프로그램의 코드가 들어갑니다.

PCB

PCB(Process Control Block)는 운영체제에서 프로세스에 대한 메타데이터를 저장한 데이터를 말하며 프로세스 제어 블록이라고도 합니다. 프로세스의 상태 정보를 저장하는 구조체이며 프로세스의 상태 관리와 문맥교환을 위해 필요합니다.

PCB는 프로세스 생성 시 만들어지며 주기억장치에 유지됩니다.

PCB에 데이터가 저장되는 과정은 다음과 같습니다. 프로그램이 실행되면 프로세스가 생성되고 프로세스 주소 값들이 스택, 힙 등의 구조로 메모리가 할당됩니다. 그리고 이 프로세스의 메타데이터들이 PCB에 저장되어 관리됩니다. 이는 프로세스의 중요한 정보를 포함하고 있기 때문에 일반 사용자가 접근하지 못하도록 커널 스택의 가장 앞부분에서 관리됩니다.

메타데이터 : 데이터에 관한 구조화된 데이터이자 데이터를 설명하는 작은 데이터

PCB의 구조

PCB는 프로세스 스케줄링 상태, 프로세스 ID 등의 다음과 같은 정보로 이루어져 있습니다.

• 프로세스 스케줄링 상태 : 준비, 대기, 실행 등의 상태
• 프로세스 ID(PID) : 프로세스 ID, 해당 프로세스의 자식 프로세스 ID
• 프로세스 권한 : 컴퓨터 자원 또는 I/O 디바이스에 대한 권한 정보
• 프로그램 카운터 : 프로세스에서 실행해야 할 다음 명령어의 주소에 대한 포인터
• CPU 레지스터 : 프로세스를 실행하기 위해 저장해야 할 레지스터에 대한 정보
• CPU 스케줄링 정보 : CPU 스케줄러에 의해 중단된 시간 등에 대한 정보
• 계정 정보 : 프로세스 실행에 사용된 CPU 사용량, 실행한 유저의 정보
• I/O 상태 정보 : 프로세스에 할당된 I/O 디바이스 목록

컨텍스트 스위칭

컨텍스트 스위칭(context switching)은 앞서 설명한 PCB를 교환하는 과정을 말합니다. 한 프로세스에 할당된 시간이 끝나거나 인터럽트에 의해 발생합니다. 컴퓨터는 많은 프로그램을 동시에 실행하는 것처럼 보이지만 어떠한 시점에서 실행되고 있는 프로세스는 단 한 개이며, 많은 프로세스가 동시에 구동되는 것처럼 보이는 것은 다른 프로세스와의 컨텍스트 스위칭이 아주 빠른 속도로 실행되기 때문입니다. 위 그림을 보면 P0이 실행하다 멈추게 되면 운영체제는 프로세스 P0의 PCB를 먼저 저장을 합니다. 실행중이던 프로세스 P0이 대기 상태가 되면 프로세스 P1을 로드하여 실행합니다. 이후 프로세스 P1이 멈추게 되면 똑같이 P1의 PCB를 저장하고 프로세스 P0의 PCB를 로드합니다.

정리하면 컨텍스트 스위칭이란 CPU가 이전에 실행 중이던 프로세스 상태 및 정보를 PCB에 저장하고, 다음에 실행할 프로세스의 상태 및 정보를 PCB에서 읽어 레지스터에 옮기는 과정이라고 할 수 있습니다.

컨텍스트 스위칭이 일어날 때 유휴 시간(idle time)이 발생하고 컨텍스트 스위칭에는 캐시미스가 발생합니다.

유휴 시간 : 컴퓨터가 작동 가능한데도 작업을 하지 않는 시간
캐시미스 : 구성 요소 또는 애플리케이션이 처리하도록 요청한 데이터가 캐시 메모리에 없는 상태

비용: 캐시미스

컨텍스트 스위칭이 일어날 때 프로세스가 가지고 있는 메모리 주소가 그대로 있으면 잘못된 주소 변환이 생기므로 캐시클리어 과정을 겪게 되고 이 때문에 캐시미스가 발생합니다.

스레드에서의 컨텍스트 스위칭

컨텍스트 스위칭은 스레드에서도 일어나며 스레드는 스택 영역을 제외한 모든 메모리를 공유하기 때문에 비용이 더 적고 시간도 더 적게 걸립니다.

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

아이디어

이 문제를 풀기 위해서는 나머지 분배 법칙을 알고있어야 한다.

나머지 분배 법칙 
(A + B) % p = ((A % p) + (B % p)) % p
(A * B) % p = ((A % p) * (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p

문제의 예시를 사용하여 a=10, b=11, c=12라고 하자. 구하고자 하는 것은 (10^11)%12이고 이 식을 다음과 같은 과정으로 바꿀 수 있다.

(10^5 x 10^5 x 10)%12 
= ((10^5%12) x (10^5%12) x (10%12))%12
= {((10^2%12) x (10^2%12) x (10%12))%12 
  x ((10^2%12) x (10^2%12) x (10%12))%12 x (10%12)}%12

코드

import sys
input = sys.stdin.readline

a,b,c = map(int,input().split())

def f(x,n):
  if n==1:
    return x%c
  t = f(x,n//2)
  if n%2==0:
    return (t*t)%c
  else:
    return (t*t*x)%c

print(f(a,b))

BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다.

동작 과정

BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같습니다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.
2. 큐에서 노드를 꺼낸 후 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 합니다.
3. 더 이상 2번 과정을 수행할 수 없을 때까지 반복합니다.

동작 예시

[Step 0] 그래프를 준비합니다. (방문 기준 : 번호가 낮은 인접 노드부터)

• 시작 노드 1

[Step 1] 시작 노드인 1을 큐에 삽입하고 방문 처리를 합니다.

[Step 2] 큐에서 노드 1을 꺼내 방문하지 않은 인접 노드 2,3,8을 큐에 삽입하고 방문 처리를 합니다.

[Step 3] 큐에서 노드 2를 꺼내 방문하지 않은 인접 노드 7을 큐에 삽입하고 방문 처리를 합니다. [Step 4] 큐에서 노드 3을 꺼내 방문하지 않은 인접 노드 4,5을 큐에 삽입하고 방문 처리를 합니다.

[Step 5] 큐에서 노드 8을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시합니다.

이러한 과정을 반복했을 때 전체 노드의 탐색 순서(스택에 들어간 순서)는 다음과 같습니다.

1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6

구현 예시

[python]

from collections import deque

# bfs 메서드 정의 
def bfs(graph, start, visited):
    # 큐 구현을 위해 deque 라이브러리 사용
    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 함수 호출
bfs(graph, 1, visited)