매일 성장하는 블로그

BFS : Breadth-First Search(너비 우선 탐색)

DFS : Depth-First Search(깊이 우선 탐색)

최단 경로나 순위 선정 같은 문제에서 만날 수 있는 탐색 알고리즘들이다.

그래프의 개념과 표현법(인접 리스트, 인접 행렬)에 대해서는 아래 글을 참고하면 된다.

one-step-a-day.tistory.com/116

간단한 예시를 통해 각 방법이 어떻게 그래프를 탐색하는지 보자.

아래와 같이 트리가 주어진다고 하자.

BFS와 DFS를 사용하여 전체 트리를 탐색하는 과정을 보자. 특정 노드에 도착하면 노드의 색을 칠한다.

BFS(Breadth-First-Search) : 너비 우선 탐색

  주어진 트리를 BFS로 방문하는 과정은 위 그림과 같다. BFS의 경우 Level을 기준으로 탐색을 진행하게 된다.

Level 1 탐색이 완료되면 Level 2를 순차적으로 탐색하고, Level 2 탐색이 완료되면 Level 3를 탐색한다. (이 때 각 Level에서 오른쪽부터 검색할지, 왼쪽부터 검색할지는 알고리즘에 따라 달라진다.)

위와 같은 탐색을 진행하려면 다음과 같이 시작하면 된다.

1. 시작 노드를 방문한다.(Level 1)

2. 방문한 노드의 자식 노드들을 추가한다.(Level 2)

3. 추가된 자식 노드들을 차례로 방문하며 손자 노드들을 추가한다(Level 3)

4. 추가된 손자 노드들을 차례로 방문한다.

위와 같은 기능은 큐로 아래와 같이 구현할 수 있다.

1. 우선 빈 큐를 생성한 뒤 시작 노드를 추가한다.

2. 큐가 비어있지 않은 경우 아래 과정을 반복한다.

3. (Loop Start) 큐에서 Dequeue한다.(큐의 Front에 있는 원소를 pop) 

4. Dequeue한 원소의 자식 노드들을 큐에 append한다. (Loop end)

5. 큐가 비어있으면 종료한다.

위를 코드로 구현하면 아래와 같다. Visited를 표시하는 이유는 방문한 곳을 다시 방문하지 않기 위함이다.

(하나의 자식 노드가 2개의 부모 노드를 갖는 경우 중복 탐색이 발생할 수 있다.)

def bfs(arr, start):
    visited = defaultdict(bool)
    deq = deque([start])
    answer = []
    visited[start] = True
    while deq:
        x = deq.popleft()
        answer.append(x)
        for i in v_list[x]:
            if visited[i] == False:
                visited[i] = True
                deq.append(i)
    return answer

DFS(Depth-First-Search) : 너비 우선 탐색

BFS는 트리의 Level 순서대로 방문하는 알고리즘이었다면, DFS는 경로 순서대로 끝까지 탐색하는 알고리즘이다.

DFS로 위에서 주어진 노드 방문 순서는 아래와 같다.

처음 방문한 노드를 기준으로 모든 경로들을 따라나간 뒤, 다음 노드를 방문한다.

DFS는 스택을 사용하여 아래와 같이 구현할 수 있다.

1. 우선 빈 스택를 생성한 뒤 시작 노드를 추가한다.

2. 스택이 비어있지 않은 경우 아래 과정을 반복한다.

3. (Loop Start) 스택에서 pop한다.(스택의 Top에 있는 원소를 pop)

4. pop한 원소의 자식 노드들을 스택에 append한다. (Loop end)

5. 큐가 비어있으면 종료한다.

위의 코드를 구현해보면 아래와 같다.

def dfs(arr, start):
    visited = defaultdict(bool)
    stk = [start]
    answer = []
    while stk:
        x = stk.pop()
        if visited[x] == False:
            visited[x] = True
            answer.append(x)
            stk.extend(v_list[x][::-1])
    return answer

큐(Queue)는 데이터를 넣고빼는 자료구조 중 하나로, 먼저 삽입된 데이터가 먼저 추출되는 FIFO(First In First Out) 구조를 가지고 있다. 큐는 Front, Rear라는 두개의 포인터를 사용하여 데이터를 관리한다.

Front : 다음 추출될 데이터를 가리킨다.

Rear : 다음 데이터가 저장될 공간을 가리킨다.

데이터를 삽입하는 행위를 enque, 추출하는 행위를 deque라고 부른다. enque 및 deque 실행 시 포인터 관리에 유의해야 한다.

(구현 방법에 따라 포인터의 증감 순서는 조금씩 다를 수 있다.)

1. 변수

  1) Capacity : 크기

  2) Front : 큐의 맨 앞

  3) Rear : 큐의 맨 뒤

  4) No : 큐에 들어있는 데이터의 갯수

2. 함수

  1) enque() : 큐에 데이터를 넣는 함수

  2) deque() : 큐에서 데이터를 빼는 함수

  3) __len__() : 큐에 넣어있는 데이터의 갯수를 반환하는 함수

  4) dump() : 큐 안에 있는 데이터를 순차적으로 모두 읽는 함수

  5) peek() : 맨 앞 데이터를 들여다보는 함수

  6) find() : 큐에서 특정 값을 찾아 인덱스를 반환하는 함수

  7) count() : 큐 안에서 특정 값의 갯수를 찾아 반환하는 함수

  8) contains() : 큐 안에 특정 값의 존재 여부를 찾아 반환하는 함수

  9) clear() : 큐를 초기화하는 함수

  10) is_full() : 큐가 가득 찼는지 확인하는 함수

  11) is_empty() : 큐가 비었는지 확인하는 함수

3. Exception

  1) Empty : 큐가 빈 경우 발생하는 Exception

  2) Full : 큐가 가득 찬 경우 발생하는 Exception

* 구현 내용

class FixedQueue:
    
    class Full(Exception):
        pass

    class Empty(Exception):
        pass

    def __init__(self, c : int):
        self.capacity = c
        self.front = 0
        self.rear = 0
        self.no = 0
        self.queue = [None] * self.capacity

    def is_full(self) -> bool:
        if self.no >= self.capacity:
            return True
        else:
            return False

    def is_empty(self) -> bool:
        if self.no <= 0:
            return True
        else:
            return False

    def enque(self, data):
        if self.is_full():
            raise FixedQueue.Full
        self.queue[self.rear] = data
        self.rear += 1
        self.no += 1
        if self.rear == self.capacity:
            self.rear = 0

    def deque(self):
        if self.is_empty():
            raise FixedQueue.Empty
        r_data = self.queue[self.front]
        self.front += 1
        self.no -= 1
        if self.front == self.capacity:
            self.front = 0
        return r_data
        
    def __len__(self):
        return self.no

    def dump(self):
        if self.is_empty():
            print('큐가 비었습니다.')
        else:
            for i in range(self.no):
                print(self.queue[(i + self.front)%self.capacity])

    def peek(self):
        if self.is_empty():
            raise FixedQueue.Empty
        return self.queue[self.front]

    def find(self, value):
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            if self.queue[idx] == value:
                return idx
        return -1

    def count(self, value):
        c = 0
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            if self.queue[idx] == value:
                c += 1
        return c

    def contains(self, value):
        return self.count(value)

    def clear(self):
        self.no = 0
        self.front = 0
        self.rear = 0

www.acmicpc.net/problem/2493

탑들이 일렬로 서있다. 각 탑의 꼭대기에서 왼쪽을 보았을 때, 높이가 같거나 높은 가장 가까운 탑을 출력하는 문제이다. 만약 없다면, 0을 출력한다.

* 힌트

1. 스택을 활용한다.

2. i번째 탑의 높이보다 i+1번째 탑의 높이가 높다면, i번째 탑은 i+1번 이후 탑들의 신호를 수신하지 못한다.

* 풀이

스택을 생성하고, 신호를 수신할 가능성이 있는 탑들은 스택에 추가한다. 

  1. 앞에서부터 순차적으로 탐색한다. 0<=i<len(tower_list)

  2. 스택이 비었을 때는 수신 가능한 탑이 없다는 뜻이므로 0을 출력하고 스택에 i번째 탑의 [높이, index]를 추가한다. 

  3. 스택이 비지 않았다면, 스택에 들어있는 탑들에 대하여 높이가 현재 탑의 높이보다 같거나 높은지 비교한다.(현재 탑의 신호를 수신할 수 있는지 확인)

  4. 현재 탑보다 높이가 낮은 것은 스택에서 pop하고, 높은 것이 있다면 해당 탑의 Index를 출력하고 스택의 현재 탑을 추가한다. 스택 탐색을 멈춘다.

  5. 1~4번을 tower_list의 끝까지 반복한다.

* 예제  

탑들이 위 그림과 같이 주어져 있다.

각 탑들의 신호를 몇번째 탑에서 수신하는지 확인해본다.

첫번째 탑의 신호 : 받을 수 있는 탑이 없다. → 0을 출력

두번째 탑의 신호 : 받을 수 있는 탑이 없다. → 0을 출력

세번째 탑의 신호 : 두번째 탑이 수신한다.  → 2을 출력

네번째 탑의 신호 : 두번째 탑이 수신한다. → 2을 출력

다섯번째 탑의 신호 : 네번째 탑이 수신한다 → 4을 출력

정답 : 0 0 2 2 4

그럼 위의 예제를 실제 코드로 테스트해본다.

* Index에 주의 : 첫번째 탑의 Index  0* 

tower_list = [6, 9, 5, 7, 4]

[1] 첫번째 탑 : index = 0, 탑의 높이 = 6, 스택 = []

  1) 스택이 비어 있으므로, 스택에 [6(탑의 높이), 0(탑의 Index)]를 추가한다.

  2) 스택이 비어있다는 뜻은, index 0번 탑의 신호를 수신할 수 있는 탑이 없다는 것을 의미하므로 0을 출력한다.

output = '0'

[2] 두번째 탑 : index = 1, 탑의 높이 = 9 스택 = [ [6,0] ]

  1) 스택이 비지 않았으므로, 비교를 시작한다. 

  2) 스택의 첫번째 원소 : [6,0]

      현재 탑의 높이 : 9 > 6 이므로 첫번째 원소를 pop한다.

  3) 스택이 비었으므로 두번째 탑의 신호를 수신할 수 있는 탑은 없다.

     현재 탑의 높이와 인덱스를 스택에 추가한다.

output = '0 0'

[3] 세번째 탑 : index = 2, 탑의 높이 = 5 스택 = [ [9,1] ]

  1) 스택이 비지 않았으므로, 비교를 시작한다.

  2) 스택의 첫번째 원소 : [9,1]

      현재 탑의 높이 : 5 < 9 이므로 해당 탑에서 세번째 탑의 신호를 수신한다.

      높이 9인 탑의 index +1(2)를 출력하고, 현재 탑의 높이와 인덱스 [5,2]를 스택에 추가한다.

output = '0 0 2'

[4] 네번째 탑 : index = 3, 탑의 높이 = 7, 스택 = [ [9,1], [5,2] ]

  1) 스택이 비지 않았으므로, 비교를 시작한다. (스택의 오른쪽부터 탐색한다. 이는 가장 가까운 탑부터 탐색한다는 의미이다.)

  2) 스택의 첫번째 원소 : [5,2]

      현재 탑의 높이 : 7 > 5이므로, 해당 탑을 pop하고 다음 탑과 비교한다.

  3) 스택의 두번째 원소 : [9,1]

      현재 탑의 높이 : 7 < 9이므로, 해당 탑에서 네번째 탑의 신호를 수신한다.

      높이가 9인 탑의 index + 1(2)을 출력하고, 현재 탑의 높이와 인덱스 [7,3]을 스택에 추가한다.

output = '0 0 2 2'

[4] 다섯번째 탑 : index = 4, 탑의 높이 = 4, 스택 = [ [9,1], [7,3] ]

  1) 스택이 비지 않았으므로, 비교를 시작한다.

  2) 스택의 첫번째 원소 : [7,3]

      현재 탑의 높이 : 4 < 7이므로, 해당 탑에서 다섯번째 탑의 신호를 수신한다.

      높이가 7인 탑의 index + 1(4)를 출력하고 현재 탑의 높이와 인덱스 [4,4]를 스택에 추가한다.

최종 output = '0 0 2 2 4'

스택 : [ [9,1], [7,3], [4,4] ]

import sys
r = sys.stdin.readline

# 입력 받기
n = int(r())
t_list = list(map(int, r().split()))
answer = []
stk = []
for i in range(n):
    h = t_list[i]
    if stk:
        #print(stk)
        while stk:
            if stk[-1][0] < h :
                stk.pop()
                if not stk:
                    print(0, end=' ')
            elif stk[-1][0] > h:
                print(stk[-1][1]+1, end=' ')
                break
            else : 
                print(stk[-1][1]+1, end=' ')
                stk.pop()
                break
        stk.append([h, i])
    else:
        print(0, end=' ')
        stk.append([h,i])

 

www.acmicpc.net/problem/9012

괄호의 조합들을 입력받았을 때, 쌍이 제대로 맞으면 'YES', 아니면 'NO를 출력하는 문제이다.

* 힌트

1. 스택의 개념을 사용한다.

* 풀이

end = 0

1. 입력을 받아 차례로 스택에 넣는다.

2. 스택의 원소들을 하나씩 pop하며 아래 조건에 따른다.

  1) pop한 원소 = ')'

     : end + 1 을 해준다.

  2) pop한 원소 = '('

     : end - 1을 해준다.

  3) end <0일 경우 break

3. for문이 끝났을 때 end가 0인지 확인한 후 0이면 'YES', 아니면 'NO'를 출력한다.

해당 문제는 알고리즘 문제에 자주 등장하는데, 스택의 개념을 활용해서 풀 수 있다는 것을 처음 알았다.

import sys
r = sys.stdin.readline

n = int(r())
# (이면 end - 1
# )이면 end + 1
# 두번째 for문 내에서 end 가 0보다 작아지면 No를 출력하고, 마지막에 end가 0인지 확인한다.
for i in range(n):
    string = list(r().strip())
    end = 0

    for i in range(len(string)):
        x = string.pop()
        if x == ')':
            end += 1
        else:
            end -= 1
        if end <0:
            break
    if end !=0:
        print('NO')
    else:
        print('YES')
    

스택(Stack)은 데이터를 넣고 뺄 수 있는 자료구조의 형태 중 하나이다. 

스택에 데이터를 넣고 빼는 방법은 총알을 탄창에 넣고 총을 쏘는 것과 똑같다.

아래의 맨 왼쪽과 같이 빈 탄창과 총알 4개가 있다고 하자. 총알 4개를 1번부터 순서대로 넣으면 가운데 그림처럼 될 것이다. 이후 총을 쏘기 시작하면 맨 마지막에 넣은 4번 총알부터 발사가 될 것이다. 

  (탄창 = Stack, 총알 = Data) 과 같이 생각하면 된다. 스택에 데이터를 넣는 과정은 탄창에 총알을 넣는 과정과 동일하며, 스택에서 데이터를 빼는 과정은 탄창에서 총알이 발사되는 과정과 동일하다.

스택에 데이터를 넣는 행위를 Push, 스택에서 데이터를 빼는 행위는 Pull이라고 부른다. 4개의 데이터를 스택에 넣고 빼는 과정을 생각해보면, 가장 먼저 넣은 데이터(1번)이 가장 마지막에 나오는 것을 알 수 있다. 이런 데이터 구조를 FIFO(First In Last Out, = 선입후출)이라고 부른다. 

스택은 크기 제한(Top = capacity)을 가지고 있으며, 데이터는 맨 아래(Bottom)부터 꼭대기까지 하나씩 순차적으로 들어간다. 데이터를 꺼낼 때는 맨 위에서부터(가장 최근에 넣은 것부터) 하나씩 뺄 수 있다. 이제 해당 자료구조를 파이썬으로 구현하기 위한 함수, 변수들을 생각해보자.

* 변수

1. 스택 포인터(ptr)

 : 현재 스택에 데이터가 어디까지 쌓여있는지 나타내는 포인터. 

2. 크기(capacity)

 : 스택의 크기를 나타내는 변수. 스택 생성 시 지정해준다.

* 함수

1. __init__() : 변수 초기화

2. push() : 스택에 데이터를 한개 삽입한다.

3. pop() : 스택에서 데이터를 한개 꺼낸다.

4. __len__() : 현재 쌓여있는 데이터의 크기를 반환한다.

5. is_empty() : 스택의 empty 여부를 확인한다.

6. is_full() : 스택이 가득 찼는지 확인한다.

7. peek() : 가장 최근에 쌓인 데이터를 읽는다.

8. clear() : 스택을 초기화한다.

9. find() : 스택 내에서 특정 값을 찾는다.

10. count() : stack에 있는 특정 값의 개수를 찾는다.

11. contains() : 특정 값을 포함하고 있는지 확인한다.

12. dump() : 스택 내의 모든 데이터를 출력한다.

구현은 아래와 같다. 스택 포인터(ptr)이 작동하는 방식을 잘 봐야 한다.

1. 스택 포인터는 항상 빈 공간을 가리키고 있다.

2. 포인터의 위치만을 수정하여 스택초기화, 데이터 제거가 가능하다.

#Fixed스택 직접 구현해보기
from typing import Any

class FixedStack:
    ##Stack Pointer는 미리 다음 빈 공간을 가리키고 있다.

    class Empty(Exception):
        pass
    class Full(Exception):
        pass

    def __init__(self , c : int) -> None:
        ## 변수 초기화 함수.
        ## stack의 크기를 생성 시 전달받는다.
        self.ptr = 0
        self.capacity = c
        self.stk = [None] * c

    def __len__(self) -> int:
        ## Stack의 길이를 반환하는 함수
        ## ptr은 다음 빈 공간을 가리키고 있기 때문에 길이와 같다.
        return self.ptr

    def is_empty(self) -> bool:
        ## Stack이 비었는지 확인하는 함수
        return self.ptr <= 0

    def is_full(self) -> bool:
        ## Stack이 가득 찼는지 확인하는 함수
        return self.ptr >= self.capacity

    def push(self, data: int) -> None:
        if self.is_full():
            raise FixedStack.Full
        self.stk[self.ptr] = data
        self.ptr += 1
    
    def pop(self) -> any:
        ## Stack의 가장 바깥에 쌓여있는 데이터를 Stack에서 빼는 함수.
        ## 비었는지 확인하고 data를 return한다. 이 때 ptr만 하나 줄여주면 된다.
        if self.is_empty():
            raise FixedStack.Empty
        self.ptr -= 1
        return self.stk[self.ptr]

    def peek(self):
        ## 가장 바깥에 쌓여있는 데이터를 읽어오는 함수
        ## 비어있는지 확인 후 data를 return한다.
        if self.is_empty():
            raise FixedStack.Empty
        return self.stk[self.ptr-1]

    def clear(self):
        ## Stack을 초기화하는 함수
        self.ptr = 0
    
    def find(self, value: Any) -> Any:
        ## 전달받은 값을 찾는 함수.
        ## 찾으면 index를 반환한다.
        for i in range(self.ptr - 1, -1, -1):
            if self.stk[i] == value:
                return i
        return -1

    def count(self, value : Any) -> int:
        ## Stack 안에 찾고자 하는 값이 몇개인지 찾는다.
        count = 0
        for i in range(self.ptr):
            if self.stk[i] == value:
                count += 1
        return count

    def __contains__(self, value: Any) -> bool:
        ## Stack이 특정 값을 포함하고 있는지 확인하는 함수
        return self.count(value)

    def dump(self) -> None:
        ## 데이터를 바닥부터 꼭대기까지 출력한다.
        ## ptr까지 출력해야 하는 이유는 그 뒤에 삭제하지 않고 남은 데이터가 있을 수도 있기 때문!
        if self.is_empty():
            raise FixedStack.Empty
        else:
            print(self.stk[:self.ptr])
        

12월 7일.

4년간 몸담았던 회사의 마지막 출근일이자 SW사관학교 정글 입소일.

  인수인계, 이사, 인간관계 정리를 하다보니 눈깜짝할새에 3주가 지나가버렸고, 새로운 시작을 위한 첫 발걸음을 떼는 날이 다가왔다. 회사 생활을 하며 불만이 많았지만, 마지막 퇴근 때 눈물이 찔끔 났던걸 생각해보면 미운 정이 들었나보다. 막상 모든걸 새롭게 시작하려니 살짝 두렵기도 한 지금, 초심을 잃지 않고자 내 각오를 적어본다.

  지나온 삶을 돌아보면, 언제나 안정적인 길을 그럭저럭 잘 걸어왔던 것 같다. 정규 교육을 이수하고 대학교에 진학하여, 졸업 뒤 취직. 이대로 안정적인 길을 가다보면 회사에서 퇴직을 했을테고, 퇴직 후에도 삶에 대해 고뇌했겠지만 가족들과의 행복을 위안삼으며 여생을 살았을 것 같다. 하지만 나는 늘 안정적인 길을 걸어오면서 의문이 가득했다. '나는 뭘 좋아하지?', '이렇게 사는 것이 행복한 것인가?' 같은 것들이다. 물론 요즘은 잊고 사는게 더 나은 질문들도 있다고 생각하지만, 이런 질문들에 대한 고뇌가 나를 여기로 이끌었음을 부정할 수 없다.

  지금까지 파악한 나의 지향점은 '기술을 통해 세상의 좋은 변화에 기여하는 사람'이다. (이 간절함이 극에 달하면 창업의 길로 뛰어들겠지만, 내가 그 지경까지 도달할 수 있을지는 의문이 든다.) 어떻게 목표를 이룰 수 있을까 고민하다가, '더 많은 기여를 하려면 뛰어난 사람이 되어야 하고, 뛰어난 사람이 되려면 열심히 일을 통해 배워야 하며, 열심히 하려면 자기가 좋아하는 일이여야 한다.' 라는 생각이 들어 회사를 뛰쳐나왔다.

  시작으로부터 일주일이 지난 지금, 밤이라도 새서 했어야 할 과제들을 조금씩 미루고 있는 내 자신을 보며 의구심이 드는 것도 사실이다. 하지만 믿어야 한다. 나를 믿고 조금 더 채찍질하며 남은 기간동안 열심히 달려서, SW 엔지니어로서 훌륭한 소프트 랜딩을 할 것이다. 열심히 하고 난 이후의 일은 그때 가서 생각하고, 우선 내 인생을 바꿀 수 있는 17주가 내 앞에 주어졌다. 열심히 달려서 5개월 뒤에 축배를 들 수 있기를.

최근 주식/채권 등 상품들의 변동성이 엄청납니다.

돈을 일정시간 한군데 묶어두기에는 투자기회를 놓칠 것만 같고, (정기예금)

정기 적금은 많은 돈을 넣을 수 없어 요즘엔 파킹통장이 인기가 많은 것 같습니다.

파킹 통장이란, 말 그대로 돈을 Parking(주차)해놓는 곳입니다.

언제든지 돈을 뺄 수 있으며, 넣어놓은 기간동안 이자를 지급해줍니다.

물론 적금보다는 이율이 매우 낮지만, 정기예금과 비슷한 수준으로 투자 대기금을 넣어놓기에는 매우 좋은 선택 같습니다.

그럼 파킹 통장의 이율을 비교해보겠습니다.

최근 파킹통장들의 이율은 보통 1~1.8%이며, 비대면 계좌개설을 해야하는 경우가 대부분입니다.

(비대면 계좌개설 = 핸드폰으로 계좌 개설)

1. 사이다 저축은행

기존에 2%의 이율을 주며 각광받았지만 최근 1.7%로 이자가 내려갔습니다. 일본계 은행이라는 점이 조금 걸립니다. (그냥 일본으로 내 자금이 흘러간다는 찜찜함..)

이율 : 1.7%

2. 에큐온 저축은행

기본금리 1.6%에 모바일 가입 및 멤버십 동의 시 0.2% 이율이 추가됩니다.

이율 : 1.8%(1.6 + 0.2)

https://www.acuonsb.co.kr/

3. 페퍼저축은행

이율 : 1.7%

https://www.pepperbank.kr/deposite/product.do?sub_category=10

4. 웰컴저축은행

웰컴저축은행은 2가지 상품이 있습니다.

1) 직장인사랑보통예금

이율 : 최대 2.5%

최대 2.5%이지만 기본 0.5%이며, 급여 이체(+1%)와 자동납부(+0.5%), 마케팅 이용목적 동의(+0.5%)를 하셔야 총 2.5%가 되어서 조금 까다롭습니다. 즉 주거래은행으로 이용할 경우 2.5%까지 이율을 받을 수 있습니다.

https://www.welcomebank.co.kr/ib20/mnu/IBNFPMDSP001#none

2) 비대면 보통예금

이율 : 1.7%

https://www.welcomebank.co.kr/ib20/mnu/IBNFPMDSP004#none

기타 SH은행, 등이 있지만 이율이 1% 초반대로 상대적으로 낮습니다.

저축은행들은 파산의 위험이 있지만, 그런 경우가 발생하더라도 예금보호공사(국가에서 보증한다고 생각하면 됨)에서 은행 계좌당 5000만원씩은 무조건 보장해주기 때문에, 받는 이자를 생각하면 4500~4900만원 정도를 넣어두는게 안전합니다.

Linux의 프로그램, 프로세스, 쓰레드

1. 실행환경 

  1.1) Foreground Process : 실행 후 종료시까지 사용자가 다른 입력을 하지 못하는 프로세스

      * Foreground Process는 프로세스 실행 도중에 사용자의 입력을 받지 않기 때문에 입력을 넣기 위해서는 기존 실행중인 프로세스를 중지시켜야 하고, 이 명령은 [Ctrl + Z]로 가능하다. 이렇게 중지시킨 프로세스는 jobs 명령어를 통해 확인이 가능하고, bg 명령어를 통하여 재시작할 수 있다.

  1.2) Background Process : 사용자 입력과 상관없이 실행되는 프로세스

      * ex) find / -name '*.py' > list.txt & 

             와 같이 맨 뒤에 &를 붙이면 Background Process로 실행된다.

2. 프로세스

 : 메모리에 적재되어 실행중인 프로그램

1) 프로세스의 생성 : 

* 프로세스 ID : 파일의 inode처럼 각 프로세스는 해당 시점에 unique한 값을 가진다. 최초의 프로세스는 init으로 프로세스 id가 1이며 운영체제에 의해 생성된다. 프로세스 id의 최대값은 32768(2의 15승, 16비트)이다.

1) 기존 프로세스에서 fork() 시스템 콜을 호출하면, 기존 프로세스를 복사하여 새로운 프로세스 공간을 만든다. 

(부모 프로세스 : 기존 프로세스, 자식 프로세스 : 기존 프로세스를 복사하여 생성된 프로세스)
2) fork() 시스템 콜 이후 자식 프로세스 → 부모 프로세스 순으로 코드를 실행한다.

( 자식 프로세스의 pid = 0)
3) 이 때 부모 프로세스가 먼저 종료되는 일이 없도록 wait()함수를 사용한다. 
4) 프로세스가 종료되면 exit()을 통하여 종료 상태가 기록되고, 부모 프로세스에 SIGCHLD 시그널이 보내지며, wait()가 풀리면서 부모 프로세스의 코드가 실행된다. 

* 부모 프로세스 : 기존에 존재하는 프로세스

* 자식 프로세스 : fork()를 통해 기존에 존재하는 프로세스를 복제하여 생성되는 프로세스

* 프로세스 관련 시스템콜

* getpid() : 프로세스 id를 리턴한다.
* getppid() : 부모 프로세스의 프로세스 id를 리턴한다.
* fork() : 새로운 프로세스 공간을 별도로 만들고, fork()시스템콜을 호출한 프로세스(부모 프로세스)공간을 모두 복사한다.
자식 프로세스는 pid가 0으로 리턴, 부모 프로세스는 실제 pid리턴, 두 프로세스의 변수 및 PC 값은 동일하다. fork 이후의 코드만 두번 실행된다. * exec() 시스템콜 : 시스템콜을 호출한 현재 프로세스 공간의 text, data, bss 영역을 새로운 프로세스의 이미지로 덮어씌움, 시스템 콜 여러가지가 있다.

* exec(실행파일이름/인자) : 해당 실행 파일의 데이터를 현재 프로세스에 덮어씌운다. 일반적으로 fork 후에 자식 프로세스에서 exec를 실행하여 부모 프로세스와 다른 프로세스를 만든다. exec는 다양한 종류의 함수가 존재한다.

1) execl("파일이름", "argv[0]", "argv[1]", ...., NULL(맨 마지막은 무조건 null))
2) execlp : 파일 이름이 path에 있으면 path 안써줘도 된다.
3) execle 는 직접 환경변수 지정
4) execvp()
5) execv()
6) execve()

* wait(int *status) : fork()함수 호출 시, 자식 프로세스가 종료될 때까지 부모 프로세스가 기다리게 된다. 이 때, 부모 프로세스가 자식 프로세스보다 먼저 죽는 경우를 막기 위해 사용한다. 자식 프로세스가 종료될 때 exit(int *status) 시스템 콜을 통하여 status 정보가 전달되고, wait()에서 해당 값을 읽고 진행한다. 
(부모 프로세스는 status & 0377 계산값으로 자식 프로세스 종료 상태 확인 가능하다.)

* exit() : 시스템 콜, 프로세스를 강제로 즉시 종료시킨다. 인자로 프로세스 종료 상태 번호를 전달한다.  
프로세스 종료 상태 번호 :  
1) 0 : 정상 종료 
2) 1 : 비정상 종료 

주요 동작 과정 :  
1) atexit()에 등록된 함수 실행(등록한 함수를 역순으로 실행한다.) 
2) 열려있는 모든 입출력 스트림 버퍼 삭제 
3) 프로세스가 오픈한 파일을 모두 닫음 
4) tmpfile() : 함수를 통해 생성한 임시 파일 삭제 

* nice(int num) : 현재 실행중인 프로세스의 우선순위 변경, 변경할 숫자를 인자로 전달한다. 
* getpriority(int which, id_t who) : 현재 프로세스의 우선순위 조회 
* setpriority(which, id_t who, int num) : 특정 프로세스의 우선순위 변경 

3. 프로세스간 커뮤니케이션 : IPC

1) 파이프 : 프로세스에서 파이프를 만들고 fork()를 하면, 부모가 자식에게 단방향 통신 가능하다.

* pipe(int arr) : 파이프 생성
-> pipe를 생성한 뒤 인자값으로 int형 배열 int arr[2]를 전달한다. 이 때 부모는 arr[1]에다 write하고, 자식은 arr[0]을 읽는다.

2) 메시지 큐

* msgget(key, msgflg) : 메세지 큐 생성
* msgsnd(msqid, &sbuf, buf_length, IPC_NOWAIT) : 메시지 전송
* msgrcv() : 메시지 읽기, 읽는 메시지 타입 지정할 수 있음

* ftok() : 키 생성을 위한 함수

3) 공유메모리 : kernel space에 메모리 공간을 만들고, 해당 공간을 변수처럼 쓰는 방식

* shmget(key_t key, size_t size, int shmflg) : 공유 메모리 생성
* shmat(int shmid, const void *shmaddr, int shmflg) : 공유 메모리 연결
* shmdt(int shmid) : 공유메모리 해제

*ipcs : 리눅스 명렁어, 현재 message queue, shared memory, semaphore 등 생성된 것들을 확인할 수 있다.

4) 시그널 : 커널 또는 프로세스에서 다른 프로세스에 어떤 이벤트가 발생되었는지를 알려주는 전통적인 기법
프로세스는 PCB에 해당 프로세스가 블록 또는 처리해야하는 시그널 정보를 관리한다. 

시그널의 종류 : 
1) SIGKILL : 프로세스를 죽여라
2) SIGALARM : 알람을 발생한다.
3) SIGSTP : 프로세스를 멈춰라(Ctrl + z)
4) SIGCONT : 멈춰진 프로세스를 실행하라
5) SIGINT : 프로세스에 인터럽트를 보내서 프로세스를 죽여라(Ctrl + c)
6) SIGSEGV : 프로세스가 다른 메모리 영역을 침범했다.
(이것 외에도 많다)

* signal(SIGINT, SIG_IGN) : 받은 시그널에 따른 동작 정의
SIG IGN - TLRMSJF ANTL, SIG_DFL - 디폴트 동작

3) 기타

* copy-on-write : fork()는 새로운 프로세스 공간을 생성하고 기존 프로세스를 복사한다. 복사할 때, 4GB나 복사하는 것은 많은 자원의 소모를 야기한다. 따라서 자식 프로세스에서 데이터 사용 시, 부모 프로세스의 페이지를 우선 사용한다.(내용은 동일하기 때문) 읽기에 대해서는 부모 페이지를 계속 참조하고, 쓰기를 할 때 부모 페이지를 복사하고 분리한다. 
(필요한 페이지만 새로 생성하여 사용)

ex) 리눅스의 프로세스에 할당된 4GB의 가상 메모리 중 1GB는 커널 메모리인데, 해당 메모리는 각 프로세스마다 모두 공유한다.(물리적으로 동일) 

* Pthread : 유닉스 시스템 핵심 스레딩 라이브러리 

pthread.h에 정의되어 있으며, 모든 함수는 pthread_로 시작한다.

1) 스레드 관리 

1. pthread_create() 
2. pthread_exit() 
3. pthread_join() : 특정 쓰레드가 끝나는 시점을 결정, 해당 함수 아래 코드는 해당 함수에 인자로 전달된 쓰레드가 종료될때까지 실행되지 않는다.(이 때 쓰레드 종료 시 상태값을 전달하며, 리소스 해제) 
4. pthread_detach() : 특정 쓰레드가 종료되면 즉시 관련 리소스를 해제한다. 종료 후 추가 처리 없음 

2) 동기화 : 임계영역 관리를 위해서 mutex와 같은 방법을 사용해야 한다. 

1. pthread_mutex_lock() 
2. pthread_mutex_unlock() 

* 파일시스템 

1) 동적 메모리 생성 : 
  1.1) malloc : heap 영역에 동적 메모리 할당 
  1.2) free : 메모리 해제 
  1.3) mmap : 파일의 특정 공간을 메모리의 특정 공간에 mapping해둔다. 따라서 시간,자원이 많이 걸리는 프로세스와 파일간의 interaction을 최소화한다.(메모리의 주소값을 리턴) 
  1.4) munmap : mapping된 물리 메모리 주소를 해제한다. 
  1.5) msync : 메모리와 파일의 데이터를 동기화 

2) inode 
  2.1) stat() : inode 상태값들을 가져온다.