• n * n 격자에 담긴 1 * 1의 계란틀

  • 정사각형 모양 계란틀에 담긴 계란의 양 제공
  • 계란틀을 이루는 4개의 선은 분리 가능

• 규칙

  1. 계란의 양이 너무 차이나지 않게 하기 위해 하나의 선을 맞대고 있는 두 계란틀의 양의 차이가 L이상 R이하라면 계란틀의 해당 선 분리

  2. 모든 계란틀에 대해 검사 실시, 1 규칙에 해당하는 모든 계란틀의 선 분리

  3. 선의 분리를 통해 합쳐진 계란틀의 계란은 하나로 합치고 이후에 다시 분리

  4. 합쳤다 다시 분리한 이후의 계란틀 별 계란의 양은 (합쳐진 계란 총 합)/(합쳐진 계란틀 수), 편의상 소수점 버림

     

- 위 과정이 1번의 계란 이동이며, 더 이상 이동이 필요 없을 때까지 과정 반복

**⇒  n*n 격자의 계란 틀에 있는 계란의 양 주어질 때, 계란의 이동이 몇 번 일어나는지 출력**

2. 풀이

• BFS!
  • 더이상 계란의 이동이 일어나지 않을 때까지 이동할 계란이 있는 칸을 찾고 계란을 이동하기 (반복문)
    • 이 때 이동할 계란이 있는 칸을 찾기 위해 매 탐색마다 격자의 각 칸의 방문 여부를 확인하며, 방문하지 않은 칸은 BFS를 통해서 주변에 계란틀의 양의 차이가 L이상 R이하인 칸들을 모두 찾아 group변수에 저장한다
    • 탐색이 끝난 후 group의 길이가 2이상이면 (==BFS탐색을 시작한 칸 주변에 계란을 이동할 칸이 존재한다면) 해당 계란들을 이동시킨다.
  • 만약 전체 격자에 대해 탐색 후에 계란이 이동했다면 결과 변수 answer += 1하며, 탐색을 했음에도 이동할 계란이 아예 없었다면 반복문을 중단시키고 결과를 출력한다

3. 코드

from collections import deque
n, L, R = map(int, input().split())
eggs = [ list(map(int, input().split())) for _ in range(n)]
answer = 0

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]

def bfs(r, c):
    group = [(r,c)]
    queue = deque()
    queue.append((r,c))

    while queue:
        cr, cc = queue.popleft()
        for i in range(4):
            nr = cr + dr[i]
            nc = cc + dc[i]

            if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
                if L <= abs(eggs[nr][nc] - eggs[cr][cc]) <= R: 
                    visited[nr][nc] = True
                    group.append((nr, nc))
                    queue.append((nr, nc))
    return group 

while True:
    # find groups that have L < diff < R
    stop = True
    visited = [[False for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:                
                visited[i][j] = True
                group = bfs(i, j)

                if len(group) > 1:
                    stop = False
                    egg = sum([eggs[r][c] for r,c in group]) // len(group)
                    for r, c in group:
                        eggs[r][c] = egg
    if stop:
        break

    answer += 1

print(answer)

+α

• 유사/동일 문제 : 백준 #16234 인구이동

• 도시 n * n

  • 각 칸 : 사람, 병원, 빈칸

  • 각 사람의 병원 거리 = 가장 가까운 병원까지 거리 : |x2 - x1| + |y2 - y1|

  • m개의 병원 남겨두고 나머지 폐업

    • m개의 병원 대한 각 사람들의 병원거리가의 총 합이 최소가 되도록

  • ⇒ m개의 병원을 잘 골라 병원 거리의 총 합을 최소화하는 프로그램 작성*

2. 풀이

• 백트래킹

• 주어진 병원들 중 m개를 골라서 병원거리 측정

  ⇒ dfs함수, visited배열을 통해서 depth == m일 때만 병원 거리 계산

• 비슷한 문제 : 조삼모사

3. 코드

n, m = map(int, input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
 # 0:blank, 1:person, 2:hospital
people = []
hospital = []

for r in range(n):
    for c in range(n):
        if graph[r][c] == 1:
            people.append((r,c))
        elif graph[r][c] == 2:
            hospital.append((r,c))

len_h = len(hospital)
visited = [False] * len_h
result = float("INF")

def calc():
    res = 0
    for pr,pc in people:
        minh = 2 * n
        for i in range(len_h):
            if visited[i]:
                hr, hc = hospital[i][0], hospital[i][1]
                h = abs(pr - hr) + abs(pc - hc)
                minh = min(minh, h)
        res += minh
    return res


def dfs(depth, last_idx):
    global result, remain
    if depth == m:
        result = min(result, calc())
        return

    for i in range(last_idx + 1, len_h):
        visited[i] = True
        dfs(depth + 1, i)
        visited[i] = False

dfs(0, -1)

print(result)

+α

• 도로 : n * m

• 자동차 : 1 * 1

• 다음 규칙에 따라서 이동

  1. 현재 방향을 기준으로 왼쪽으로 간 적이 없으면 좌회전 + 1칸 전진

     

2. 왼쪽이 인도/이미 방문한 경우 **좌회전 + 1번 과정 시도**

    <img src=https://velog.velcdn.com/images/kim_sunnnny/post/32cdd171-a191-4715-b864-1167e034f29d/image.png width=50%>


3. 2번에 대해 4방향 모두 확인해도 전진 불가하다면 
    1. 현재 방향 유지한 채로 **1칸 후진 + 1번 과정**

        <img src=https://velog.velcdn.com/images/kim_sunnnny/post/5fade859-6227-4dfe-b38d-3aae2a8efd06/image.png width=50%>


    2. 후진을 못하는 상황이면 작동 **stop** 

        <img src=https://velog.velcdn.com/images/kim_sunnnny/post/3accb752-abc6-45d2-88f3-b13aa180168f/image.png width=25%>


- 입력
    - 도로의 세로 크기 `n,` 가로 크기 `m`
    - 자율주행 자동차의 초기 위치 (`x`, `y`)와 바라보는 방향 d
        - `d` :  0부터 3까지 숫자로 주어지고, 순서대로 북쪽, 동쪽, 남쪽, 서쪽
        - `x` : 위쪽에서부터 아래쪽까지 0부터 n-1까지 차례대로 번호
        - `y` : 왼쪽에서 오른쪽까지 차례대로 번호
    - 셋째줄부터 n+2번째 줄까지는 도로의 상태가 주어집니다. 도로는 0, 인도는 1으로 주어집니다.
    - 3 ≤ n, m ≤ 50
    - 자율주행 자동차가 있는 칸은 도로일 것이라 가정해도 좋습니다.
    - 격자의 첫번째 행과 마지막 행, 첫번째 열과 마지막 열은 항상 인도일 것이라고 가정해도 좋습니다.

⇒ 자율주행 자동차가 작동을 멈췄을 때 거쳐갔던 도로의 총 면적? (처음 위치의 도로 포함)

2. 풀이

• simulation
• while 반복문 내에서 좌회전 가능 여부 후 이동 및 후진 진행
• 좌회전 시 방향은 N(0) → W(3), W(3) → S(2), S(2) → E(1), E(1) → W(0) 이므로, 좌회전 후 방향은 d = (d + 3) % 4 와 같다

3. 코드

n, m = map(int, input().split()) #  n = height, m = width
x, y, d = map(int, input().split())                             # d = 0 ~ 3 : N E S W
roads = [ list(map(int, input().split())) for _ in range(n)]    # 0 : road, 1: sidewalk
visited = [[0]*m for _ in range(n)]

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def can_move(x, y):
    move = False 
    if  0 <= x < n and 0 <= y < m and roads[x][y] == 0 and not visited[x][y]:
        move = True
    return move

visited[x][y] = 1
trial = 0
while True:
    d = (d + 3) % 4
    nx = x + dx[d]
    ny = y + dy[d]
    trial += 1

    if can_move(nx, ny): # if can move, (in range, is a road, not visited),  move (change x, y, reset trial, change visited)#  
        x, y = nx, ny
        trial = 0
        visited[x][y] = 1

    else:   # if can't move, (already visited, out of range)
        if trial == 4 :     #   if trial == 4 
            nx = x - dx[d]
            ny = y - dy[d]            
            if 0 <= nx < n and 0 <= ny < m and roads[nx][ny] == 0:  #if can go backwards, go backwards(change x, y, reset trial)
                x = nx
                y = ny
                visited[x][y] = 1
                trial = 0                
            else:       # if can't move backwards, (already visited, out of range)
                break

        else:       # if trial <4 
            continue

answer = 0
for i in range(n):
    for j in range(m):
        answer += visited[i][j]
print(answer)

+α

• 놀이기구 : n * n

  

• 학생 : n * n 명

  • 각 학생별로 좋아하는 학생 4명씩 (동일한 학생에 대해 좋아하는 학생 번호 중복 가능

    

- 입력으로 주어진 학생들의 순서대로 다음 조건에 따라 가장 우선순위가 높은 칸으로 탑승  ( 항상 비어있는 칸으로만 이동)
    1. 격자를 벗어나지 않는 4방향으로 인접한 칸 중 앉아있는 좋아하는 친구의 수가 가장 많은 위치로
    2. 1번 조건을 만족하는 칸이 여러 곳이라면 인접한 칸 중 비어있는 칸의 수가 가장 많은 위치로
    3. 2번 조건을 만족하는 칸이 여러 곳이라면 행 번호가 가장 작은 위치로
    4. 3번 조건을 만족하는 칸이 여러 곳이라면 열 번호가 가장 작은 위치로 

    <img src=https://velog.velcdn.com/images/kim_sunnnny/post/541d32cb-2da7-4951-a612-3433d9b1cc84/image.png width = 90%>


- 최종 점수 계산
    - 각 학생의 인접한 곳에 앉아있는 좋아하는 친구의 수

        <img src=https://velog.velcdn.com/images/kim_sunnnny/post/4a102877-4265-4aef-9c8c-2af851f57ef1/image.png width=40%>

⇒ 들어오는 학생의 순서와 각 학생마다 좋아하는 4명의 학생 번호가 주어졌을 때, 최종 점수?

2. 풀이

• like_info : 입력으로 주어진 학생-좋아하는 친구에 대한 리스트
• ride : n * n 크기의 놀이기구 탑승 공간
• 자리에 앉는 기준 : 주변에 좋아하는 친구 수 > 빈칸 수 > 행 번호 > 열 번호
• like_info를 한 행씩 읽으면서, 각 학생이 앉을 자리를 탐색
  • ride의 각 칸마다 탐색하며 candidates 리스트를 채우기
    • 칸이 비어 있다면 해당 칸 위, 아래, 왼쪽, 오른쪽 탐색하며 빈칸 수와 좋아하는 학생의 수를 확인함
    • (좋아하는 친구 수, 탐색한 빈칸 수, 행번호, 열번호) 를 candidates리스트에 넣음
    • candidates를 정렬한 뒤 맨 첫번째 원소에 해당되는 위치에 학생 정보 입력

3. 코드

def look_around(r, c, favorites):
    fav, blanks = 0, 0
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]

        if 0 <= nr < n and 0 <= nc < n:
            if ride[nr][nc] in favorites:
                fav += 1
            elif ride[nr][nc] == 0:
                blanks += 1
    return fav, blanks

n = int(input())
like_info = [ list(map(int, input().split())) for _ in range(n*n) ]

ride = [ [0]*(n) for _ in range(n)]

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]

for i in range(n * n):
    student = like_info[i][0]
    favorites = like_info[i][1:]

    candidates = []

    for r in range(n):
        for c in range(n):

            if ride[r][c] == 0:
                fav, blanks = look_around(r, c, favorites)
                candidates.append([fav, blanks, r, c])

    candidates.sort(key= lambda x: (-x[0], -x[1], x[2], x[3]))
    seat = candidates[0]
    ride[seat[2]][seat[3]] = student

students = [x[0] for x in like_info]

answer = 0
for i in range(n):
    for j in range(n):
        student_idx = students.index(ride[i][j])
        fav, blanks = look_around(i, j, like_info[student_idx][1:])
        if fav > 0:
            answer += 10 ** (fav - 1)
print(answer)

+α

• 총 8개의 톱니를 가지고 있는 톱니바퀴 4개

  • 톱니의 N극은 0, S극은 1

• 톱니바퀴에는 번호가 매겨져 있음

  • 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번

• 톱니바퀴 A를 회전할 때,

  • 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전

  • 서로 맞닿은 톱니의 극이 같다면, B는 회전하지 않음

    

    - 입력:
        - 4줄에 걸쳐 각 톱니바퀴 상태 입력 (N극은 0, S극은 1, 12시방향부터 시계 방향 순서대로)
        - 회전횟수 K (1≤ K ≤ 100)
        - K개 줄 동안 회전시킨 방법
            - 각 방법은 두 개의 정수 :
                - 회전시킨 톱니바퀴 번호
                - 방향 (1: 시계방향, -1: 반시계 방향)

    **⇒  톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때,**  K번 회전시킨 이후에 네 톱니바퀴의 점수의 합?

    - 점수 계산
        - 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
        - 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
        - 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
        - 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

2. 풀이

• 회전한다 == “기준이 바뀐다”

  • 12시 방향을 나타내는 배열 top 을 활용 (4개의 톱니바퀴지만, 1번부터 처리하므로 길이를 5로 설정)

  • 시계 방향 : -1

  • 반시계 방향 : +1

    

• 주어진 회전 정보 마다 (회전 톱니바퀴 idx, 회전방향)
  • idx 톱니바퀴의 오른쪽과 왼쪽으로 나누어서, idx의 회전에 따라 회전하는 톱니들을 조사
    • idx 톱니와 거리가 홀수만큼 차이나는 톱니는 반대방향으로 회전, 짝수만큼 차이나는 톱니는 같은 방향으로 회전
    • 회전할 톱니들은 tlst 배열에 담아서 오른쪽 왼쪽 조사를 모두 마친 뒤 한번에 회전

3. 코드

N = 4

arr = [[0] * 8] + [list(map(int, input())) for _ in range(N)]
K = int(input())

top = [0] * (N+1)

for _ in range(K):
    idx, dr = map(int, input().split())     #dr : cw = 1, ccw = -1 
    tlst = [(idx, 0)]                       # => but when rotating, ccw has to add to top[idx], cw has to subtract

    # right side of idx wheel
    for i in range(idx + 1, N + 1):        
        if arr[i-1][(top[i - 1] + 2) % 8] != arr[i][(top[i] + 6) % 8] :
            tlst.append((i, (i - idx) % 2))
        else:
            break
    #left side of idx wheel
    for i in range(idx-1, 0, -1):
        if arr[i][(top[i] + 2) % 8] != arr[i + 1][(top[i+1] + 6) % 8] :
            tlst.append((i, (idx - i)%2 ))
        else:
            break

    for i, rot in tlst:
        if rot == 0:    #rotate same direction ( abs(idx - i) % 2 == 0 )
            top[i] = (top[i] - dr + 8) % 8
        else:
            top[i] = (top[i] + dr + 8) % 8

answer = 0
calc = [0, 1, 2, 4, 8]

for i in range(1, N+1):
    answer += arr[i][top[i]] * calc[i]

print(answer)

+α

• 참고
  • https://www.youtube.com/watch?v=0VfhMu6s21w&t=1s

• n * n 격자에 서로 다른 높이를 가진 리브로수 나무 키우기

  • 특수 영양제 : 나무 키우기 위해 필요
    • 1 * 1 땅에 있는 나무 높이를 + 1
    • 씨앗만 있으면 높이 1의 나무 생성
    • 초기 특수 영양제 : n * n 격자 최하단 4개의 칸
    • 이동 규칙에 따라 움직임 : 이동 방향 + 이동 칸 수
      • 이동방향 : 1~8번 ➡️ ↗ ⬆️ ↖ ⬅️ ↙ ⬇️ ↘
      • n번 열에서 오른쪽으로 이동 : 1번열로 이동

  • 1년 동안 다음 단계를 거쳐 성장

    1. 특수 영양제를 이동 규칙에 따라 이동
    2. 특수 영양제를 이동 시킨 후 해당 땅에 특수 영양제를 투입
       • 투입 후 땅에 있던 특수 영양제는 소멸
    3. 특수 영양제를 투입한 리브로수의 대각선으로 인접한 방향에 높이가 1 이상인 리브로수가 있는 만큼 높이가 더 성장
       • 대각선으로 인접한 방향이 격자를 벗어나는 경우에는 세지 않음
    4. 특수 영양제를 투입한 리브로수를 제외하고 높이가 2 이상인 리브로수는 높이 2를 베어서 잘라낸 리브로수로 특수 영양제를 사고, 해당 위치에 특수 영양제를 올려둡니다.

    

⇒ n x n 격자의 칸에 리브로수의 각자 다른 높이와 각 년도의 이동 규칙이 주어질 때, 해당 년수가 모두 지나고 난 뒤 남아있는 리브로수 높이들의 총 합?

2. 풀이

• 이동규칙에 따라 이동했을 때 행과 열이 격자 범위 밖을 나갔을 때

  • if idx < 0 ⇒ idx += n
  • if idx > n ⇒ idx %= n

• 시간 복잡도 줄이기

  • 매년 기존의 특수 영양제는 제거하고 특수 영양제가 이동하는 과정에서 위치 정보값을 저장하는 구조를 list보다 set으로 저장하여 중간에 생기는 중복 값을 제거하며 진행!!

    - 시간 복잡도 줄이기 전 코드 (list)

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

        trees = [ list(map(int, input().split())) for _ in range(n) ]
        moves = [ tuple(map(int, input().split())) for _ in range(m) ]

        #     → ↗  ↑  ↖  ← ↙ ↓ ↘
        dr = [0, -1, -1, -1, 0, 1, 1, 1]
        dc = [1, 1, 0, -1, -1, -1, 0, 1]

        sur_r = [-1, -1, 1, 1]
        sur_c = [-1, 1, -1, 1]

        def moved(x):
            if x < 0:
                x =  x + n
            elif x >= n:
                x = x % n
            return x

        nutri = [[n-1, 0], [n-1, 1], [n-2, 0], [n-2, 1] ]

        for move in moves:
            d_idx, leng = move[0]-1, move[1]

            for i in range(len(nutri)):
                nutri[i][0] = moved(nutri[i][0] + dr[d_idx] * leng)
                nutri[i][1] = moved(nutri[i][1] + dc[d_idx] * leng)

            for i in range(len(nutri)):
                trees[nutri[i][0]][nutri[i][1]] += 1

            for n_r, n_c in nutri:
                surround = 0
                for i in range(4):
                    r = n_r + sur_r[i]
                    c = n_c + sur_c[i]
                    if 0 <= r < n and 0 <= c < n and trees[r][c] >= 1:
                        surround += 1
                trees[n_r][n_c] += surround

            new_nutri = []
            for i in range(n):
                for j in range(n):
                    if [i,j] not in nutri and trees[i][j] >= 2:
                        trees[i][j] -= 2
                        new_nutri.append([i,j])

            nutri = new_nutri

        answer = 0
        for row in trees:
            answer += sum(row)

        print(answer)
        ```

        ![](https://velog.velcdn.com/images/kim_sunnnny/post/d6efa60b-69ad-4178-a9c8-20cdba971685/image.png)

3. 최종 코드

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

trees = [ list(map(int, input().split())) for _ in range(n) ]
moves = [ tuple(map(int, input().split())) for _ in range(m) ]

#     → ↗  ↑  ↖  ← ↙ ↓ ↘
dr = [0, -1, -1, -1, 0, 1, 1, 1]
dc = [1, 1, 0, -1, -1, -1, 0, 1]

sur_r = [-1, -1, 1, 1]
sur_c = [-1, 1, -1, 1]

def moved(x):
    if x < 0:
        x =  x + n
    elif x >= n:
        x = x % n
    return x

nutri = [[n-1, 0], [n-1, 1], [n-2, 0], [n-2, 1] ]

for move in moves:
    d_idx, leng = move[0]-1, move[1]

    for i in range(len(nutri)):
        nutri[i][0] = moved(nutri[i][0] + dr[d_idx] * leng)
        nutri[i][1] = moved(nutri[i][1] + dc[d_idx] * leng)

    for i in range(len(nutri)):
        trees[nutri[i][0]][nutri[i][1]] += 1

    for n_r, n_c in nutri:
        surround = 0
        for i in range(4):
            r = n_r + sur_r[i]
            c = n_c + sur_c[i]
            if 0 <= r < n and 0 <= c < n and trees[r][c] >= 1:
                surround += 1
        trees[n_r][n_c] += surround

    new_nutri = []
    for i in range(n):
        for j in range(n):
            if [i,j] not in nutri and trees[i][j] >= 2:
                trees[i][j] -= 2
                new_nutri.append([i,j])

    nutri = new_nutri

answer = 0
for row in trees:
    answer += sum(row)

print(answer)

• 1~3 과정 중 n번 칸 위치에 사람이 위치하면 즉시 하차

• 각 칸의 안정성은 시간이 지남에 따라 다시 상승하지 않음

• ex) 각 칸의 안정성 = 2, 0인 칸이 1 이상일 때 실험 종료

  

- 위 과정이 1번의 실험

**⇒  과정이 종료될 때 몇 번째 실험을 하고 있었는지?**

2. 풀이

• 시뮬레이션 : 조건문과 엣지 케이스를 고려하자

  • 무빙워크의 각 위치별 안정도를 담은 배열 stability

    • stability[0] : 0번째 위치의 안정도

  • 실험에 참여한 사람에 대한 정보를 담은 배열 people

    • people[0] : 0번째 위치에 사람이 있으면 1, 없으면 0

  • zeros 변수로 안정도가 0인 위치의 개수를 추적하여 simulate가 끝난 후 zeros가 k이상이 되면 실험 종료 (while 반복문 탈출)

  
  
  

  • simulate 함수 1회 = 실험 1회

    • 무빙워크를 이동시킨 후, (stability 배열, people 배열 모두 회전)

    • n번칸에 사람이 있으면 ( people[n-1] == 1) 하차시키기

    • 사람 이동 시키기

      • 현재 index 전에 사람이 있고, 현재 위치에 사람이 없고, 안정도가 0보다 클 경우 이동
      • 이동 :
        • stability[index] -=1
        • people[index] = 1
        • people[index-1] = 0
        • stability[index] == 0이면 zeros+1

    • 이동 후에도 n번칸에 사람이 있으면 내리기

    • 0번째 칸에 (사람은 이동해서 비어있을 것이므로) 안정도가 0보다 크면 사람 새롭게 올리기

      • 이 행위로 0번째 칸의 안정도가 0이 되면 zeros + 1
        
        

        3. 코드

from collections import deque

n, k = map(int, input().split())
stability = deque(list(map(int, input().split())))
people = deque([0 for i in range(n)])

zeros = 0

def simulate():
    global zeros

    # 무빙워크 이동
    stability.appendleft(stability.pop())
    people.appendleft(people.pop())

    # n번칸 사람 내리기
    if people[n - 1]:
        people[n - 1] = 0

    # 사람 이동
    for i in range(n - 1, 0, -1):
        # 현재 위치에 사람이 없고 내구도는 남아 있으면서 이전 위치에 사람이 있는 경우
        if people[i] == 0 and people[i - 1] and stability[i]:
            people[i] = 1
            people[i - 1] = 0

            stability[i] -= 1

            if stability[i] == 0:
                zeros += 1
    # n번칸 사람 내리기
    if people[n - 1]:
        people[n - 1] = 0

    # 사람 올리기
    if stability[0]:
        stability[0] -= 1
        people[0] = 1

        if stability[0] == 0:
            zeros += 1

answer = 0
while True:
    simulate()
    answer += 1

    if zeros >= k:
        break

print(answer)

+α

• 1차 시도 : 실패 - 시간 초과, 문제 해석 오류

  • people이라는 빈 list에 사람을 append하는 방식, people[0]은 1번째 사람의 위치

      n, k = map(int, input().split())
      stability = list(map(int, input().split()))
      zeros = stability.count(0)
    
      people = [] # people[0] = location on moving walk of 1st person
    
      exp = 0
      stop = False
    
      while True:
          exp += 1
          #rotate
          stability = [stability[-1]] + stability[1:2*n-1]
    
          #move people on moving walk
          for idx, p in enumerate(people):
              if p == n-1:
                  people.pop(i)
              elif p + 1 in people or stability[p+1] == 0:
                  continue
              else:
                  people[idx] += 1
                  stability[p+1] -= 1
                  if stability[p+1] == 0:
                      zeros +=1 
    
              if zeros >= k:
                  stop = True
                  break
    
          if not stop and 0 not in people:
              people.append(0) 
              stability[0] -= 1
              if stability[0] == 0:
                  zeros += 1
          if zeros >= k:
              stop = True
    
          if stop:        
              break
    
      print(exp)

참고

• https://tight-sleep.tistory.com/38
• https://velog.io/@jimeaning/코드트리-불안한-무빙워크

• n개의 정수 순서대로 (순서 바꿀 수 없음)

• n-1개의 연산자 배치

  • 덧셈, 뺄셈, 곱셈

  • 연산자 간 우선 순위 무시, 앞에서부터 차례대로 연산

  • ⇒ 가능한 식의 최솟값, 최댓값?*

2. 풀이

• 1차 시도: 백트래킹을 시도해 봄…

  • 조삼모사를 백트래킹으로 했던 것처럼 순열을 구하는 함수 구조를 이용해서 dfs/백트래킹과 연산값을 구하는 함수를 이용해서 풀어보려고 함
  • 입력받은 연산자의 개수를 기반으로 연산자 배열을 만들고, 해당 배열의 인덱스에 대해 순열을 만들어서 해결해보려고 하였으나 연산자 순서의 중복을 고려하지 않아서 연산횟수도 쓸데없이 많아지고 점점 산으로 가버림..!

• 정답 코드 해설:

  • dfs를 이용한 백트래킹을 할 때 depth와 연산자 개수에 대한 변수를 함께 이용
    • depth는 입력으로 받은 정수 배열의 인덱스와 동일함
    • 연산자 조합을 만들 때 개수를 1개씩 차감하고 depth를 1개씩 더해가며, 바로 연산을 하면서 최솟값과 최댓값을 구함!

3. 코드

def dfs(depth, total, plus, sub, multi):
    global MIN, MAX
    if depth == n:
        MIN = min(MIN, total)
        MAX = max(MAX, total)

    if plus:
        dfs(depth + 1, total + num[depth], plus - 1, sub, multi)

    if sub:
        dfs(depth + 1, total - num[depth], plus, sub - 1, multi)

    if multi:
        dfs(depth + 1, total * num[depth], plus, sub, multi - 1)

n = int(input())

num = list(map(int, input().split()))
plus, sub, multi = map(int, input().split())

MIN, MAX = float("INF"), -float("INF")
dfs(1, num[0], plus, sub, multi)
print(MIN, MAX)

+α

정답 코드가 아주 예술적이고 예쁘다… :)

언젠가 저런 코드를 내 손으로 작성할 수 있기를,,,ㅠ_ㅠ

• 참고 : https://velog.io/@jimeaning/%EC%BD%94%EB%93%9C%ED%8A%B8%EB%A6%AC-%EC%97%B0%EC%82%B0%EC%9E%90-%EB%B0%B0%EC%B9%98%ED%95%98%EA%B8%B0

• n개의 일 → 아침/저녁으로 n/2씩 처리

• 업무 강도 / 업무 간 상성 Pij

  • ex)

    

    - 1, 2번 일을 아침 +  3, 4번 일을 저녁
        - 아침에 하는 일의 총 업무 강도는 *P*12 + *P*21 = 8
        - 저녁의 경우 *P*34 + *P*43 = 13
    - 1,4번 일을 아침 + 2, 3번 일을 저녁
        - 아침의 경우 *P*14 + *P*41 = 2
        - 저녁의 경우 *P*23 + *P*32 = 9

    ⇒ 1,2번 일과 3, 4번의 일로 나누어서 하는 것이 힘듦의 합의 차이가 5로 최솟값

⇒ 아침의 하는 일의 업무 강도와 저녁에 하는 일의 업무 강도의 차이의 최솟값?

2. 풀이

1. 구현… →

   • 아침/저녁에 작업할 일의 조합을 구해서 각각에 대한 업무 강도를 모두 계산

   • 조합을 구하고 정렬을 할 경우, i번째 원소가 아침에 작업할 일이라면 -i-1번째 원소가 저녁에 작업할 일이다

     • ex) [1,2,3,4] 에서 일의 조합을 구한다면
       • [ [1,2] , [1,3], [1,4] [2,3], [2,4], [3,4] ] 이므로
       • 아침 저녁의 조합은 [1,2] + [3,4], [1,3] + [2,4], [1,4] + [2,3] 일 것이다

   • 너무나도 당연히 시간복잡도가 엄청나다

     

2. DFS / 백트래킹
   • 조합을 다 구하고 일의 강도를 계산하는 것이 아니라, 조합을 구하면서 강도를 계산하고, 업무 강도 차이의 최솟값을 구한다!
     • 1부터 n까지의 업무들에 대한 배열의 index를 이용해서
     • 업무 강도를 구하는 함수에서 depth 변수를 이용하여 아침 업무가 n//2개 될 때만 저녁의 업무를 조건문으로 구하고 각각의 업무의 강도를 계산한다
     • 아침/저녁 업무 조합에 대한 업무의 강도 차이를 현재의 최솟값 ans와 비교하여 최종적으로 가장 작은 값을 최종적으로 반환한다

3. 코드

1. 조합 구현

    def combinations(arr, r):
        for i in range(len(arr)):
            if r == 1:
                yield [arr[i]]
            else:
                for next in combinations(arr[i+1:], r-1):
                    yield [arr[i]] + next
   
    def solution():
        n = int(input())
        half = n//2
   
        work = [ list(map(int, input().split())) for _ in range(n) ]
   
        task = [i for i in range(n)]
        combo = sorted(list(combinations(task, half)))
   
        balance = []
   
        for jobs in combo:
            intensity = 0
            intensities = list(combinations(jobs, 2))
   
            for i, j in intensities:
                intensity += work[i][j]
                intensity += work[j][i]
   
            balance.append(intensity)
   
        min_diff = abs(balance[0] - balance[-1])
   
        for i in range(1, len(balance)//2):
            diff = abs(balance[i] - balance[-i-1])
            if min_diff > diff : 
                min_diff = diff
   
   

    print(min_diff)

solution()
```

1. DP/백트래킹

    # 일의 양 (2의 배수)
    n = int(input())
   
    # 업무 간의 상성 Pij
    work = [list(map(int, input().split())) for _ in range(n)]
   
    def work_intensity(day):
        res = 0
        for i in range(n//2):
            for j in range(i+1, n//2):
                res += work[day[i]][day[j]]
                res += work[day[j]][day[i]]
        return res
   
    def dfs(idx, depth):
        global ans
        if depth == n//2:
            temp2 = [i for i in range(n) if i not in temp]
            ans = min(ans, abs(work_intensity(temp) - work_intensity(temp2)))
   
        for i in range(idx + 1, n): #idx = 0 부터 시작하면 
            temp.append(i)
            dfs(i, depth+1)
            temp.pop()
   
    total = set(range(n))
    temp = [0]
    ans = float("INT")
    dfs(0,1)
   
    print(ans)

+α

• 동일 문제 : 백준 14889 스타트와 링크

• 참고

  • https://developer-ellen.tistory.com/50

• generator를 만드는데 사용

return? yield?

• 함수의 반환 : return or yield
• 예제
  • A, B, C 반환하는 함수

  1.  def return_abc() :
          return list("ABC")
         print(return_abc()

  2.  def yield_abc():
          yield ("A")
          yield ("B")
          yield ("C")
       print(yield_abc())

  • 출력 결과 1 : ['A', 'B', 'C'] 2 : <generator object yield_abc at 0x7f4ed03e6040>

Generator

• 여러 개의 데이터를 미리 만들어 놓지 않고 필요할 때마다 즉석해서 하나씩 만들어낼 수 있는 객체

• ex) time.sleep() 이용한 예제

      import time
  
      # ------------------------ 1: return 출력 -----
      def return_abc():
        alphabets = []
        for ch in "ABC":
          time.sleep(1)
          alphabets.append(ch)
      return alphabets  
  
      for ch in return_abc():
          print(ch)
  
      # ------------------------ 2: yield 출력 -----
  
      def yield_abc():    # yield from ["A", "B", "C"]와 동일
        for ch in "ABC":
          time.sleep(1)
          yield ch
  
  
  

  for ch in yield_abc():
      print(ch)
```

• 1 출력 : 3초 경과 후 A, B, C 차례대로 출력
• 2 출력 : 1초 후 A 출력, 1초 후 B 출력, 1초 후 C 출력

generator의 효율성

• 제너레이터를 통해서는 결과값을 나누어서 얻을 수 있기 때문에 성능 측면에서 큰 이점

• memory 측면

  • return 키워드를 사용할 때는 모든 결과 값을 메모리에 올려놓아야 함
  • yield 키워드를 사용할 때는 결과 값을 하나씩 메모리에 올려놓음

• 출처 https://www.daleseo.com/python-yield/

1. 문제

• 총 n개의 층 식당 고객 체온 측정

• 각 층 : 검사 팀장 + 검사 팀원

  • 1가게당 팀장 1명 (필수), 팀원 여러명 (각 층 검사원은 해당 층만 검사)

  • ⇒ n개의 식당 고객들의 체온을 측정하기 위해 필요한 검사자 수의 최솟값?*

2. 풀이

• 설명대로 구현
• 백준 시험감독과 동일한 문제!
  
  

3. 코드

import math

n = int(input())
clients = list(map(int, input().split()))
lead, member = map(int, input().split())

answer = 0

for client in clients:
    if lead >= client :
        answer += 1

    else:
        answer += 1 + math.ceil((client - lead)/member)

print(answer)

+α

• N+1일 째 퇴사

• 남은 N일 동안 최대한 많은 상담

• 상담 기간 Ti

• 상담 시 받을 수 잇는 금액 Pi

  • 예

    

    - 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.
    - 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.
    - 또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

    퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.


**⇒ 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성**

• 입력 :
  • N (1 ≤ N ≤ 15)
  • Ti Pi (1일부터 N일까지 순서대로, 1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)
• 출력 : 백준이 얻을 수 있는 최대 이익

2. 풀이

• DP

  • n번째 일에 최대 이익을 구하기 위해서는 (i일 전날의 최대 이익 + i일의 금액) 중 최대 이익을 구해야 함

  • 1~7일을 차례대로 선택해서 그날의 수익을 받았을 때의 최대 수익들을 차례대로 구하면 N+1째 날에 얻을 수 있는 최대 수익을 구할 수 있다.

    

    	1일	2일	3일	4일	5일	6일	7일
    1일 상담 진행시	0	0	0	10	0	0	0
    1일 + 4일				10	30	0	0
    1일 + 4일 + 5일				10	30	0	45
    1일 + 5일				10	10	0	25

  • 1일 + 6일 상담 진행 시 상담이 끝나면 6 + 4일 = 10일이므로 해당 조합으로는 상담 진행이 불가하다

  • 이런 방식으로 i번째 일의 상담을 진행할 경우, 현재 날짜+i일 이후부터 n일까지의 최댓 수익을 순차적으로 구하여 최종적으로 백준이가 얻을 수 있는 최대 수익을 구할 수 있다.

3. 코드

def solution():

  N = int(input())
  T = []
  P = []

  for _ in range(N):
    t, p = map(int, input().split())
    T.append(t)
    P.append(p)

  day = [0] * (N + 1)

  for i in range(N):
    for j in range(i + T[i], N + 1):
      if day[j] < day[i] + P[i]:
        day[j] = day[i] + P[i]

  print(day[-1])

solution()

+α

• DP 다시 연습하기
• 재귀적 + 반복적인 구조를 찾고 그것을 코드로 구현하는 것 연습하기

• Virtual machines = EC2
• Virtual drives = EBS (Elastic Block Store)
• Distributing load across machines = ELB (Elastic Load Balancer)
• Auto-Scaling Group = ASG

Sizing / Configuration options

• OS : Linux / Windows / Mac

• CPU : Compute power & cores

• RAM

• Storage space

  • Network-Attached : EBS, EFS
  • HW : EC2 Instance Storage

• Network card : public IP address, speed of card

• Firewall rules : Security Group

• Bootstrap script : *EC2 User Data : run with root user *

  • run only once at instance's first start, to automate boot tasks

• ssh connection

  • .pem : OpenSSH - mac, linux, Windows10
  • .ppk : PuTTy - Windows 7,8

EC2 instance types

• aws의 작명규약 ex) m5.2xlarge

  • m : instance class
  • 5 : generation (continuously updated)
  • 2xlarge : size within instance class ( more memory, ...)

• Instance Class

  Class	purpose	use cases
  General Purpose	for diversity of workloads, good balance btwn compute, memory, networking)	•web servers • code repositories
  Compute Optimized	for compute-intensive tasks	• Batch processing workloads • Media transcoding • High performance web server • High performance computing (HPC) • Dedicated gaming servers
  Memory Optimized	for workloads that process large data sets in memory	• High performance, relational/non-relational databases • Distributed web scale cache stores • In-memory databases optimized for BI (Business Intelligence) • Applications performing real-time processing of big unstructured data
  Storage Optimized	for tasks that require high,sequential read/write access to large data sets on local storage	• High frequency OLTP systems • Relational & NoSQL DB • Cache for in-memory DB (ex: Redis) • Distributed file systems
  Accelerated Computing	-	-
  HPC Optimized

EC2 Instance Purchasing options

1. On-Demand

• 사용한 만큼 가격 발생

• Linux / Windows : 첫 1분 이후 초단위로 청구

• 다른 OS : 1시간 단위로 청구

    **⇒ 가장 비싼 plan, 선불 요금 X 장기 렌탈 필요 x (X Commitment)**

• [추천] 짧고 방해받지 않으며, 예측 가능한 workload

2. Reserved Instance

• 1 & 3년 단위로 렌탈

• Reserved Instances

  • On-demand 대비 약 72% 할인가

  • Instance Type, Region, Tenancy, OS 등 명시하여 대여

  • 요금결제 : 후불 / 부분 선불 / 전부 선불 (먼저 많이 지불할 수록 할인)

  • scope : Regional / Zonal

  • Buy & Sell in the reserved instance marketplace

  • [추천] : 안정적인 앱 사용 / 장기적인 workload

• Convertible Reserved Instances

  • 장기적인 workload + flexible한 instance type
  • 변경 가능 : EC2 instance type, instance family, OS, scope, tenancy

3. Savings Plans

• 장기사용에 따른 할인

• 특정 사용량에 따라 약정
  (ex: 1년 혹은 3년 간 $10/시간)

• 약정 기간 이후 사용량은 On-Demand 가격으로 책정

• 고정 : instance family, Region

• 변경 가능 :

  • Instance size (ex: m5.xlarge, m5.2xlarge)
  • OS (ex: Linux, Windows, …)
  • Tenancy (Host, Dedicated, Default)

  
  
  
  
  

*Dedicated Host

• 물리적 서버 자체에 접근 가능, HW의 lovw level까지 가시성 확보 ⇒ 가장 비쌈!

• compliance 요구사항 만족 가능

• 서버를 경계로 하는 자체 라이센스 사용 가능 (socket 단위, core 단위, VM 단위 라이센스 등)

• instance placement 지정 가능

• 구매 옵션

  • On-Demand : active한 host 초단위로 계산
  • Reserved : 1년 혹은 3년 - 후불 / 부분 선불 / 전체 선불

• [추천]

  • 복잡한 라이센싱 모델을 가진 sw (BYOL license)
  • 강한 regulatory/compliance가 요구되는 회사

*Dedicated Instances

• Instances run on HW dedicated to you
• 같은 계정 내 다른 instance와 HW 공유 가능
• instance placement 지정 불가

*Capacity Reservations

• 특정 AZ 내 "On-Demand" instances capacity를 예약 (for any duration)
• 필요할 때 언제든 EC2 capacity에 접근 가능
• time commitment 필요 없음 (언제든 생성/중단)
• instance 작동여부와 상관없이 On-Demand rate으로 과금
• Regional Reserved Instance와 Savings Plans과 함꼐 사용 시 할인
• [추천] 단기간, 특정 AZ에 있어야하는 안정적인 workload

* Spot Instances

• 중요한 작업이나 DB의 목적의 workload로는 부적합

• 아주 싸다~! 단기간 workload로 좋음

• Max spot price (budget) 지정

• hourly spot price는 수요와 공급에 의해 변동

  • current spot price가 max spot price보다 낮으면 instance 보유
  • current spot price가 더 비싸지면 2분 간 유예 시간 동안 instance 상태를 결정해야 함
    • stop instance : hourly spot price가 max spot price 보다 내려가면 다시 instance 시작
    • terminate instance : 아예 종료
    • Spot Block **: (2021년 7월 기준 신규 고객에게는 Spot Block 서비스 제공 x, 시험에는 나올 수 있음!)
      • 시간을 정해서 지정한 용량을 유지해주는 옵션 - 해당 시간 동안은 Reserved Instance보다 유리

• [추천] failure에 강한 작업

  • ex) Batch Jobs / Data analysis / Image Processing / Any distributed workloads

Spot Instance Request 과금없이 종료하는 법!

• Spot Instance request 종류 : One-time / persistent

  

• Spot Instance 종료시키기 when persistent request

  1. request 상태가 open / active / disabled 중 하나 (failed, cancelled, closed는 종료 불가)
  2. Cancel spot instance
  3. 동작 중인 instance를 별도로 직접 terminate (request 취소 ≠ instance 종료)

Spot Fleets

• 최저가에 Spot Instance를 request하는 것을 자동화

  1. Budget, capacity, launch pool 정의

     • launch pool : Instance type, OS, AZ 지정

  2. 가격 제한과 Target capacity를 만족하도록 instance를 구축

  3. budget 한도에 도달했을 때 instance 구축 중단
     
     

• Spot instance 구축 위한 구성 전략

  1. 최저가 : pool 내 가장 최저가 (가격 최적화, 단기 workload용)
  2. diversified : 모든 pool에 걸쳐 분산 구축 (good availability, 장기 workload용)
  3. capacity Optimized : 필요한 instance들을 수용할 수 있는 적합한 capacity를 가진 pool 선택

Security Groups

• 방화벽 역할 : EC2를 오고 가는 트래픽 관리
• Allow 규칙 정의
  • 관리 대상 :
    • Access to Ports
    • Authorized IP ranges - IPv4, IPv6
    • Inbound network (default : all blocked)
    • Outbound network (default : all authorized)
• IP 참조 가능
• 여러 Instance들에 attach 가능
• region/VPC 내에서만 유효
• SSH 접근 관련 SG 별도로 관리하는 것이 유리함

Classic Ports

SSH (Secure SHell)

※ IP - IPv4 / IPv6, Private IP / Public IP

• IPv4 : 32bit , still most common format (강좌에서 주로 다룰 주소)

  • [0-255].[0-255].[0-255].[0-255]

• IPv6 : 128bit, 고정header, 암호화 기능 기본

• Public IP

  • can be identified on the internet
  • must be unique
  • can be geo-located easily

• Private IP

  • can only be identified on a private network
  • unique accross the private network
  • 2 diff private networks can have same private IPs
  • machines connect to internet by NAT + internet gateway (as a proxy)
  • only a certain range of IPs can be used as private IP

Elastic IP

: fixed public IPv4 for your instance (only 1 instance)

• with Elastic IP address, you can mask the failure of an instance/software by rapidly remapping the address to another instance in your account

• 5개 제한 있지만, AWS에 늘려달라고 요청할 수 있음

• AVOID ELASTIC IP : often reflect poor architectural decision

  ⇒ use a random public IP and register a DNS name to it

  ⇒ or use a Load Balancer & don’t use a public IP

EC2 Placement Groups

• control over the EC2 Instances are going to be placed within the AWS infrastructure
• when creating a placement group, specify 1 of 3 strategies for the group :

1. **Cluster**    

    - grouped together in a low-latency HW setup within the same rack within a single AZ
    - Use Case :
        - Big Data job that needs to complete fast
        - Application that needs extremely **low latency, high network** throughput

     **⨁**   high performance  : 10 Gbps bandwidth btwn instances

     **Θ**    high  risk  : If the rack fails, all instances fails at the same time
    <br><br/>
2. **Spread**   

   - spreads instances across underlying HW    ( Instances on diff physical HW )
    - Use Case :
        - applications that needs **high availability**
        - critical application where instances must be isolated from failure from one another

     **⨁**   span across AZs  , Reduced risk of simultaneous failure

     **Θ**   limited to **max 7 instances per AZ per placement group**   
           (ex: 1 region w/ 3 AZ ⇒ 7 instances in each AZ ⇒ total 21 instances in that region) 
    <br><br/
3. **Partition**  : spread instances across many diff partitions within an AZ
 (rely on diff sets of racks of HW, EC2 ) 
  - EC2 instances get access to partition information as meta data
  - spread groups are just single individual instances spread through different racks or AZs, partition placement group : made of several instances on each partition)
  - Use Cases : HDFS, HBase, Cassandra, Kafka

     **⨁**   can span across multiple AZs in the same region

     **⨁**   Scales to 100s of EC2 instances per group     

     **Θ**   partition failure can affect many EC2, but won’t affect other partitions

Elastic Network Interfaces (ENI)

• logical component in a VPV that represents virtual network card ⇒ gives EC2 access to the network (EC2 밖에서도 사용됨)

• ENI can have following attributes:

  • Primary private IPv4 , 1개 이상의 secondary IPv4
  • 1 Elastic IP (IPv4) per private IPv4
  • 1 public IPv4
  • 1개 이상의 security groups
  • Mac 주소

• bound to specific AZ

• Failover를 위해 ENI를 독립적으로 생성하여 다른 instance로 옮길 수 있음 (“attach them on the fly” )

  • Failover : the redirection of traffic from a primary system to a secondary system (백업 목적) 원래 등록되어있던 instance에 문제 발생 시 private IP가 다른 instance로 이동함

EC2 Hibernate

• Stop & Terminate
  • Stop : data on EBS (disk) is kept intact(not injured) in the next start
  • Terminate : if you set root volume to be destroyed w/ instance, it will be destroyed

                   (if not set to be destroyed, it will be kept)

• Start
  • 1st start : OS boots up ⇒ User Data script is run
  • following starts : OS boots up ⇒ applications start / caches get warmed up ⇒ takes time

• EC2 Hibernate
  • write in-memory (RAM) state to a file in the root EBS volume ⇒ RAM state preserved!

    - *when launching instance*
    - *root EBS volume must be encrypted*

- Use cases:
    - long-running processing
    - saving RAM state   (RAM ≤ 150GB)
    - Services that take up time to initialize

- good to know,,,,,, :
    - Hibernate supports many kinds of instance families, instance RAM Sizes, Instance Sizes, all kinds of instances(on-demand, reserved, spot)
    - Root Volume must be a large & encrypted EBS
    - can not be hibernated more than 60 days

※ EC2 Instance Storage Section : EBS, EC2 Instance store, EFS

EBS Volume (Elastic Block Store)

: network drive you can attach to your instance while they run

• uses network to communicate the instance ⇒ latency might occur

• can be detached from an instance and attached to another one quickly

• allows your instance to persist data even after termination

• some EBS can be “multi-attached” to more than 1 instances
  (mostly mounted at 1 instance at a time)

• bound to AZ ⇒ use snapshots to move volume across AZ

• provisioned capacity : size in GBs and IOPS (I/O Ops Per Second - 저장장치의 속도 측정 단위) ⇒ EBS Volume의 용량을 provision할 때 명시해야 하지만 나중에 늘릴 수 있음

• Free tier : 30 GB of free EBS storage of type General Purpose(SSD) or Magnetic per month
  
  
  
  

  EBS : Delete on Termination attribute

• controls the EBS behavior when an EC2 instance terminates, by AWS console / AWS CLI

• Delete on Termination by Default :

  • root EBS volume : enabled (deleted on termination)
  • any other attached EBS volume : disabled (not deleted on termination)

• Use case : preserve root volume when instance is terminated (exam scenario)

EBS Snapshots

• backup (snapshot) of EBS volume at a point in time

• X necessary to detach volume to do snapshot, but recommended

• Can copy snapshots across AZ or Region

• Features :

1. EBS **Snapshot Archive** 
    - move snapshot to “archive tier”  :  75% cheaper
    - takes 24~72 hours for restoring   (restore :  *to bring back existence*)

1. **Recycle Bin** for EBS Snapshots
    - setup rules to retain deleted snapshots so you can recover after accidental deletion
    - specify retention from 1 day ~ 1 year    (retention :  ******************************the ability to keep and hold)******************************


1. **Fast Snapshot Restore (FSR)**
    - Force full initialization of snapshot to have x latency on the first use (cost $$$)
        - good when snapshot is very big and need a quick instance initialization

EBS Volume Types

• SSD (Solid State Drive) vs HDD (Hard Disk Drive)

• Types - depending on Size / Throughput / IOPS

  1. st1 (Low cost HDD) : for frequently accessed, throughput-intensive workloads
     
     

  2. s1 (Lowest cost HDD)* : for less frequently accessed workloads

     • HDD EBS features

       ⇒ only gp2/gp3, io1/io2 can be used as boot volumes
       
       

  3. gp2 / gp3 (SSD) : General Purpose SSD volume

     • cost effective & low latency ⇒ balance price & performance
     • 1 GiB ~ 16Tib
     • ex) system boot volumes, virtual desktops, Development and test env’ts
     • gp3 (newer ver.)
       • Baseline of 3,000 IOPS and throughput of 125 MiB/s
       • Can increase IOPS up to 16,000 and throughput up to 1000 MiB/s independently
     • gp2 (older ver.)
       • Small gp2 volumes can burst IOPS to 3,000
       • Size of the volume and IOPS are linked, max IOPS is 16,000
       • 3 IOPS per GB, means at 5,334 GB we are at the max IOPS
         
         

  4. io1 / io2 (SSD) : Provisioned IOPS - Highest-performance SSD volume

     • for mission-critical low-latency or high-throughput workloads
       • Critical business applications with sustained IOPS performance
       • applications that need more than 16,000 IOPS
     • Great for databases workloads (sensitive to storage perf and consistency)
     • Supports EBS Multi-attach
     • io1/io2 (4 GiB - 16 TiB)
       • Max PIOPS: 64,000 for Nitro EC2 instances & 32,000 for other
       • Can increase PIOPS independently from storage size
       • io2 have more durability and more IOPS per GiB (at the same price as io1)
     • io2 Block Express (4 GiB – 64 TiB):
       • Sub-millisecond latency
       • Max PIOPS: 256,000 with an IOPS:GiB ratio of 1,000:1

EBS Multi-Attach - io1/io2 family

• Attach the same EBS volume to multiple EC2 instances in the same AZ

  ⇒ Each instance has full Read & Write permissions to high-performance volume

• Up to 16 EC2 Instances at a time

• Must use a file system that’s cluster-aware (not XFS, EX4, etc…)

• Use Cases:

  • Achieve higher application availability in clustered Linux applications (ex: Teradata)
  • Applications must manage concurrent write operations

EBS Encryption

• list of encryption in an encrypted EBS volume :
  • Data at rest inside the volume
  • All data flow btwn the instance and the volume
  • All snapshots
  • All volumes created from the snapshot
• Encryption and decryption are handled transparently (user has nothing to do)
• minimal impact on latency
• EBS Encryption leverages keys from KMS (AES-256)
• Copying an unencrypted snapshot allows encryption

Encrypt an unencrypted EBS volume

1. Create EBS Snapshot of the volume
2. Using copy, encrypt the EBS snapshot
3. create new EBS volume from the encrypted snapshot ⇒ encrypted snapshot
4. attach encrypted volume to original instance

AMI = Amazon Machine Image

: customization of an EC2 instance -

• add your own software, configuration, OS, monitoring, …

• all software is pre-packaged ⇒ faster boot / faster configuration time

• built for specific region & can be copied across regions

• types

  1. Public AMI : AWS provided
  2. Your own AMI : you make and maintain them yourself
  3. AWS Marketplace AMI : AMI someone else made (and potentially sells)

• Creating AMI from an EC2 instance

  1. Start an EC2 instance and customize it
  2. stop the instance for data integrity
  3. Build an AMI : this will also create EBS snapshots
  4. Launch instance from AMI

EC2 Instance Store : high-performance HW attached volume

• EBS volumes : network drives → “limited performance”
• Features :
  • Better I/O performance
  • lose storage if stopped (ephemeral - lasting for a very short time)
  • good for buffer / cache / scratch data / temporary content
  • risk of data loss if HW fails
  • Backups / Replication are your responsiblity

Amazon EFS : Elastic File System

: Managed NFS (Network File System) that can be mounted on many EC2

• work w/ EC2 instance in multi-AZ

• Highly available, scalable, pay per use, expensive (3 * gp2)

• NFSv4.1 protocol

• use Security to control access to EFS

• compatible w/ Linux based AMI (Windows)

• Encryption at rest using KMS

• standard file system on Linux - POSIX - has standard file API

• X plan capacity in advance - File system scales automatically

• Scale

  • 1000s of concurrent NFS clients, 10 GB+ /s throughput
  • Grow to Petabyte-scale network file system, automatically

• Use cases :

  • Content management
  • web serving
  • data sharing
  • wordpress
    
    

    EFS - Storage Classes at EFS creation time

• Availability and Durability

  1. Standard (구 Regional) : Multi-AZ
     • great for prod
  2. One Zone : One AZ
     • great for development
     • backup enabled by default
     • compatible with IA (EFS One Zone-IA)
     • Over 90% in cost s뜐avings

• Storage Classes - Tiers : move files to a different tier after a few days (lifecycle management feature)

  1. Standard Tier : for frequently accessed files

  2. EFS-IA (Infrequent Access Tier) : cost to retrieve files, lower price to store

     • Must use Lifecycle Policy to enable EFS-IA

       
       
       

• Performance Modes

  1. General Purpose (default) : latency-sensitive use cases (web server, CMS, etc…)
  2. Max I/O – higher latency, throughput, highly parallel (big data, media processing)
     
     

• Throughput Mode

  1. Bursting : growing in throughputs as we have more storage
  2. Provisioned : set your throughput regardless of storage size
  3. Elastic : automatically scales throughput up or down based on your workloads
     • Used for unpredictable workloads
       
       
       
       

       EBS vs EFS

Program vs Process

• Code : 자신을 실행하는 코드 저장
• Data : 전역 변수와 정적(static)변수 저장
• Stack : 지역 변수와 함수 호출 시 필요한 정보 (매개변수와 돌아갈 주소) 저장
• Heap : 동적 메모리 할당 시 사용
  • ex) c 언어 - malloc() free()

코드 → 메모리 → 프로세스 과정

• code

    #include <stdio.h>
    void main()
    {
        int a = 1;
        int b = 2;
        int c = a + b
        }

  • .c file → 컴파일

    1. c언어는 compile언어이므로 컴파일이 되어야 실행가능

    2. 전처리기 : 매크로로 정의한 숫자를 치환, 필요한 파일 로딩 ⇒ 파일 확장자 : .i

    3. 컴파일러 : compile - C언어 ⇒ assembly language (명령어 : 기계어 = 1: 1) ⇒ 파일 확장자 : .s

    4. Assembler : Assembly language ⇒ machine language(0,1) ⇒ 파일 확장자 : .o

    5. Linker : linking - 여러 library나 다른 source code들 연결

       ⇒ 파일 확장자 : .exe

- `exe.` 파일 실행 → 하드 디스크에 있는 해당 파일이 메모리에 올라감  ⇒  “**Process”**

CPU 관점) OS의 전략에 따른 Process의 관리

• CPU : 0,1로 이루어진 Machine language만 실행 ⇒ Assembly Language로 고려해보기 (for 가독성)

  1. CPU 내의 Control Unit이 숫자 5와 7을 memory에 저장
  2. 방금 메모리에 저장한 값을 **edx , eax Register**로 가져옴
  3. Control Unit이 “Register에 저장된 5와 7을 더하라”는 명령을 하면
  4. ALU(산술논리연산장치)가 연산을 한 뒤, eax Register에 저장
  5. Control Unit이 eax Register에 저장된 12를 가져와 memory에 저장
     
     
     
     

Uni-Programming vs Multi-Programming vs Multi-Processing

• Process가 만들어지면 OS는 해당 process의 정보를 갖고 있는 PCB를 만들고 저장

• Linked List 형태로 저장 (각 데이터가 다음 데이터를 연결)

  • Process 종료 시 Linked List에서 해당 Process의 PCB 제거

  • 이전의 PCB가 방금 제거된 PCB를 가리키도록 수정하여 Linked List 구조 유지

    출처 : https://yoongrammer.tistory.com/52

    PCB	저장 데이터
    Pointer	- 부모와 자식 process에 대한 pointer, 할당된 자원에 대한 pointer 등 - process의 한 상태에서 다른 상태로 전환될 때 저장하는 pointer 보유 ( for 효율적인 접근)
    Process State	현재 process의 5가지 상태 (생성, 준비, 실행, 대기, 완료)
    PID (Process ID)	Process를 식별하기 위한 숫자
    Program Counter	다음에 실행될 명령어의 주소를 포함하는 Program Counter 시분할 처리로 여러 프로세스를 짧은 시간씩 번갈아 실행하기 때문에, 해당 프로세스로 다시 전환됐을 때 실행할 명렁어를 알아둬야 함)
    Registers	process가 실행될 때 사용했던 Register 값들이 저장 (Program Counter와 마찬가지로 CPU를 뺏기고 다시 시작할 때 이전에 사용하던 값을 복구하기 위한 용도)
    Memory Limits	process가 memory에 있는 위치 정보, memory 침범을 막기 위한 경계 register값 등
    Open File Lists	=CPU 스케쥴링 정보 : 우선순위, 최종 실행시간, CPU 점유시간 등이 저장

Process State

• CPU의 시분할 시스템 ⇒ process의 5가지 상태

  

출처 : https://medium.com/@sohailk1999/five-state-process-model-6e83d7428c8c

Context Switching

• Process를 실행하는 중에 다른 process를 실행하기 위해 실행 중인 process의 상태를 저장하고 다른 process의 상태 값으로 교체하는 작업

• cause of Context switching

  1. CPU 점유시간 초과
  2. I/O 요청
  3. 다른 종류의 Interrupt가 있을 때 발생

• if) Process A → Process B

  • PCB의 내용 변경! : Process state, Program Counter, Registers , Memory Limits

    • 실행중인 process의 작업 내용을 PCB에 저장

      • 현재 CPU의 register값 등을 PCB A에 저장

    • 실행될 process의 PCB 값으로 CPU가 다시 세팅

Process 생성과 종료

• 0번 Process 생성 과정 : OS 부팅 후 딱 1번 실행
  1. .exe 파일 실행
  2. OS가 해당 프로그램의 Code 영역과 Data 영역을 memory에 load, 빈 Stack & 빈 Heap을 만들어 공간 확보
  3. 해당 Process를 관리하기 위한 PCB를 만들어 값을 초기화

⇒ 나머지 프로세스는 새로 생성하지 않고 0번 process를 복사해서 사용 : fork() 함수 이용

• ∵ process 복사하여 이용하는 것이 생성하는 것보다 빠름

• 0번 process를 복사 ⇒ 부모 process(0번) & 자식 process

  • 부모 process의 code영역, data 영역, stack 영역, PCB의 내용 전부 복사

  • 복사한 0번 process와 다르게, 원하는대로 작동하도록 **exec())함수 이용**

    ⇒ 부모를 복사한 자식 프로세스의 코드와 데이터 영역을 원하는 값으로 덮어씀

• 부모 process & 자식 process

  
    #include <stdio.h>
    #include <unistd.h>
  
    int main()
    {
        int pid;
        pid = fork();    // 자식 process에게는 0, 부모 process에게는 0이 아닌 값 반환
  
      // 이 후 2개의 process는 cpu scheduling에 따라 실행, 
      //어느 것이 먼저 실행될지는 OS의 결정에 따름
  
        if (pid == 0) // 자식 process
        {
            // InternetBrowser 프로그램에서 코드와 데이터 영역을 가져와 자식 process를 덮어씀
            execlp("InternetBrowser", "0", NULL); 
            exit(0); // InternetBrowser 프로그램 실행에 실패하면 exit()함수 호출 후 종료
        }
        else // 부모 process
        {
            wait(NULL);// 자식 process에게서 exit()신호를 받으면 자식 process를 완전히 종료 시킴
            printf("인터넷 브라우저 닫힘"); 
            exit(0);
        }
    }

  • execlp() : 인자로 들어온 프로그램에서 코드와 데이터 영역을 가져와 자식 process를 덮어씀 (from parent’s copied data to the program’s data)

    • 실패 시에만 -1 반환하고 성공하면 반환 x
    • 위 예시의 경우 인터넷 브라우저를 실행하면 exit()은 실행하지 않고 실패시에만 exit()함수가 호출

  • wait() : context switching을 거쳐 부모 process에게 cpu가 할당되어도 자식 process에게서 exit()신호가 올 때까지 다른 코드를 실행하지 않고 기다리는 system 함수

  • exit() : 자식 process가 부모 process에게 정상종료를 알리는 함수

    • 부모 process는 자식 process의 exit status를 읽고 자식 process 정리

  • zombie process : 자식 process가 정상적으로 종료되지 못해 memory에 계속 살아있는 상태

    • 부모 process가 자식 process보다 먼저 종료
    • 자식 process가 비정상적으로 종료돼, exit() 신호를 주지 못해서 exit status를 읽지 못함

Thread

• Process : OS가 작업을 처리하는 단위 ⇒ Process 내 Thread

• Thread : Process가 할당받은 자원을 이용하는 실행 단위 / Process의 특정한 수행 경로 / Process 내 실행되는 여러 흐름의 단위

  • Main thread : Process 내 존재하는 최소 1개 thread

  • 독자적인 Stack memory & register 보유

  • Code, Data, Heap 공유

  • Process 내의 주소공간/자원들 공유

  • TCB (Thread Control Block) 로 관리

  • 1 thread가 process 자원을 변경하면 다른 sibling thread(이웃 thread)도 그 변경 결과를 즉시 볼 수 있다

  • memory를 공유하기 때문에 동기화 , deadlock 등의 문제 발생 가능

  • 관련 library : POSIX Pthreads, Windows threads, Java threads

    	Process	Thread
    정의	실행 중인 program	Process의 실행 단위
    생성/종료시간	많은 시간 소요	적은 시간 소요
    Context Switching	많은 시간 소요	적은 시간 소요
    상호작용	IPC 사용	공유 memory 사용
    자원소모	많음	적음
    메모리 내 독립성	각각 독립적
    안정성 굳!	프로세스 내 stack/register 독립적, 이외 공유

multi-processing vs multi-threading

User Level Thread & Kernel Level Thread (https://www.crocus.co.kr/1404)

• 스케줄러가 컨텍스트 스위칭 하는 단위는 커널 스레드이고 컨텍스트 스위칭을 당하며 저장되는 정보가 PCB임을 알고 있어야한다.
• User Level Thread : programming 과정에서 Thread를 code에 적는 것
• Kernel Level Thread : OS가 관리하는 thread들

주제와 관련한 cs 질문

• context switching과 시분할 시스템에 대해서 설명하시오.

  • 시분할 시스템은, 입출력 처리가 끝날 때까지 대기해야 했던 cpu의 사용률을 높일 수 있도록 고안된 시스템

    • 메모리에 적재된 여러 프로그램들을 짧은 시간씩 할당하여 처리함으로써, cpu가 대기했어야하는 시간에 다른 작업을 하게 하여 cpu 사용률을 높임

  • Process를 실행하는 중에 다른 process를 실행하기 위해 실행 중인 process의 상태를 저장하고 다른 process의 상태 값으로 교체하는 작업을 context switching이라고 함

    • 실행중인 process의 작업 내용을 (현재 CPU의 register값 등) 실행 중인 process의 PCB에 저장하고, 실행될 process의 PCB 값으로 CPU가 다시 세팅됨
      
      
      
      

• 좀비 프로세스가 생기는 이유에 대해서 설명하시오

  • 부모 프로세스와 자식 프로세스 관계의 프로세스는 부모 프로세스가 자식 프로세스를 온전히 종료시켜야한다.

  • 자식 프로세스가 성공적으로 종료될 경우 exit()신호를 부모 프로세스에 보냄으로써 부모 프로세스가 자식 프로세스를 종료시킬 수 있는데, 만약 부모 프로세스가 자식 프로세스보다 먼저 종료되거나, 자식 프로세스가 비정상적으로 종료되어 exit()신호를 보내지 못할 경우 메모리에 계속 남아있게 되면서 좀비 프로세스가 생성되게 된다

• when choosing region, you should consider
  1. Compliance w/ data governance & legal requirements
  2. Proximity to customer - ↓ latency
  3. Services' availability within a region
  4. Pricing

※ AZ (Available Zone) : 1개 이상의 discrete center w/ Redundant power, networking, connectivity

• 같은 region 내 AZ 간에는 high bandwidth + ultra-low latency networking

• Region마다 평균 3개의 AZ (min 3, max 6)

• Points of Presence (사용자에게 low latency로 전달하는 것에 도움 주는 service)

  • Edge
  • Regional Cache

• Global service ↮ regional service
  • 일부 service는 global service로서 region/AZ 선택을 필요로 하지 않음
  • ex) IAM, ...

※ IAM : Identity and Access Management

• Root account : default 로 생성, 함부로 사용/공유되지 않도록 주의
• AWS login option : root user / IAM user
  • IAM user :
    • Account ID/alias
    • account user name
    • password

IAM Users : 조직 내 구성원

• Account ID : 고유값, 번호로만 구성 ⇒ Account Alias : 닉네임, 로그인 시 사용 가능

IAM Group : User만 등록 가능 (X contain other groups)

IAM Roles : specific permissions with credentials that are valid for short durations

• 일반적으로 특정 AWS resource에 권한이 없는 users/applications/services에 권한을 대리 (delegate access)
  • perform actions on your behalf
• password나 access key를 요구하는 standard long-term credential이 없음
  • (user와 유사하지만 특정 사람과 associated될 필요x)
• provides you w/ temporary security credentials for your role session
• common roles:
  • EC2 Instance Roles
  • Lambda Functions Roles
  • Roles for CloudFormation

IAM Policy

• JSON 문서로 user/group의 permission 정의 ⇒ “Grant/apply the least privilege principle” (필요한 권한만 최소한으로 부여해라)

• Inheritance : 특정 policy가 부여된 group에 할당/추가되면 해당 policy를 상속받음

  • group에 속해있지 않은 user는 해당 user에 할당된 policy만 보유
  • 속해있던 group에서 배제될 경우 해당 group의 policy 속 권한들을 상실하게 됨

• Policy Structure
  1. Version : policy language version - “2012-10-17”
  2. Id (optional) : 고유값
  3. Statement : 1개 이상
     • Sid (optional) : statement의 id
     • Effect : “Allow” / “Deny”
     • Principle : 해당 policy가 적용될 account/user/role의 id
     • Action : 해당 policy가 허용/금지할 action의 list
  • * : all actions
    • Resource : 위 action들이 적용될 resource의 list
  • * : all resources
    • Condition (optional) : 해당 policy가 적용될 조건들
      
      

IAM Defense mechanism -

1. Password Policy
   • 비밀번호가 강력할수록 보안 강화
   • AWS에서 원하는 password policy를 직접 정할 수 있다 :
     • password 최소 길이 정하기
     • 특정 문자 포함시키기 (대문자 / 소문자 / 숫자 / 특수문자)
     • 모든 IAM user들의 비밀번호 변경 허용하기
     • 일정 시간 후 user들의 비밀번호 변경 요청하기 (password expiration)
     • 비밀번호 재사용 방지

2. Multi Factor Authentication (MFA)

   • Users 가 보유한 권한으로 설정값들을 변경하거나 resource를 삭제할 수 있음
   • Root account와 IAM user를 보호하기 위한 MFA
   • MFA = password you know + security device you own
   • 최대장점 : Even if a password is stolen or hacked, the account is not compromised
   • options
     1. Virtual MFA device : support for multiple tokens on a single device
     • Google Authenticator (phone only)
     • Authy (multi-device)
       2. U2F Security Key (Universal 2nd Factor) : support for multiple root and IAM users using a single security key
     • YubiKey by Yubico (3rd party)
   1. Hardware Key Fob MFA device
      • Gemalto (3rd party)
      • for AWS GovCloud (US) - SurePassID (3rd party)

※ AWS CLI , SDK, Access Keys

• AWS에 접속하는 법 3가지
  1. AWS Management Console : password + MFA
  2. AWS CLI : access keys
  3. AWS SDK (Software Developer Kit) : for code - access keys

Access Keys

• AWS Console에서 발급, Users마다 관리, 공유 하지마!!!
• Access Key ID ≌ username
• Secret Access Key ≌ password
  • ※ never put Access Key in your EC2 instance’s aws configure ⇒ Use IAM Roles

AWS CLI

• Command line shell에서 AWS 서비스들과 interact할 수 있도록 하는 tool
• direct access to public API of AWS service
• develop scripts to manage resources

AWS SDK

• software development kit
• language-specific APIs (set of libraries) = different SDKs for different programming languages
• 프로그램적으로 access/manage AWS services - embedded within application
• supports

AWS CloudShell - 다른 terminal 옵션 for AWS CLI

• not yet available in all regions

• 사용 중인 user의 credentials와 region을 기준으로 응답을 반환

• linux server 처럼 파일 생성하면 cloudshell restart해도 유지됨 (download/upload file 도 가능)

IAM Security Tools - IAM Credentials Report , Access Advisor

• IAM Credentials report (account level)

  : account의 user들과 그들의 credential 정보들에 대한 report

• IAM Access Advisor (user-level)

  : user에 허가된 service permission들과 각 service들의 최근 접속 시간

  
  
  
  
  

IAM 가이드라인, best practices

• AWS account setup 목적 외에 root 계정 사용하지 않기
• 1 물리적 사용자 = 1 AWS user
• user를 group에 할당, group에 permissions 할당
• 강한 password policy 정하기
• MFA를 사용하고 강조해라
• AWS service에 대한 권한 부여는 Roles를 만들어 사용하라
• CLI/SDK와 같은 programmatic access에 Access Key를 사용하라
• IAM Credentials Report로 account의 권한들을 관리해라 (audit permissions ~`)
• Never share IAM users & Access keys

• 지역의 높이 정보에 따라 비가 왔을 때 물에 잠기지 않는 “안전영역”의 최대 개수는?
  • 잠기지 않은 부분들의 최대 영역이 안전지대

    - 높이가 4이하가 모두 물에 잠겼을 경우 ⇒ 5개

      <img src =https://velog.velcdn.com/images/kim_sunnnny/post/6120a331-e3f5-4227-af0f-2feab1e2cb36/image.png width=50%>



    - 높이가 6이하인 지점이 모두 잠겼을 경우 ⇒ 4개

        <img src=https://velog.velcdn.com/images/kim_sunnnny/post/cb1cb37f-4bb9-4a3c-af34-e02447bdbe42/image.png width=50%>

• 입력

    1| 행/열의개수

이후 |  높이 정보

• 출력

  안전한 영역의 최대 개수

  

2. 풀이

• BFS! - queue를 활용해서 안전지대의 개수를 구한다

• 최대 개수를 구해야하므로, 주어진 높이들 중 최대 높이를 구한 뒤 0부터 최대높이-1까지 강수량을 설정하여 각 강수량에 따른 안전지대 개수를 구하고, 그 중 최댓값을 찾아 반환한다
  
  
  
  

  3. 코드

• 복습 코드 → 함수, 지역변수로 실행시간 줄이기

    import sys
    from collections import deque
  
    input = sys.stdin.readline
  
    def bfs(i, j, heights, visited, N, rain):
        dr = [1, -1, 0, 0]
        dc = [0, 0, 1, -1]
  
        visited[i][j] = True
  
        queue = deque()
        queue.append((i,j))
  
        while queue:
            r, c = queue.popleft()
            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]
  
                if 0 <= nr < N and 0 <= nc < N and not visited[nr][nc] and heights[nr][nc] > rain:
                    visited[nr][nc] = True
                    queue.append((nr,nc))
  
    def solution():
        N = int(input())
        heights = []
        Max_height = 0
        for _ in range(N):
            row = list(map(int, input().split()))
            heights.append(row)
            Max_height = max(Max_height, max(row))
  
        safe_zone = []
  
        for rain in range(1,Max_height):
            visited = [ [False for _ in range(N)] for _ in range(N) ]
            zones = 0
            for i in range(N):
                for j in range(N):
                    if not visited[i][j] and heights[i][j] > rain:
                        bfs(i,j, heights, visited, N, rain)
                        zones += 1
            safe_zone.append(zones)
  
        if not safe_zone:
            print(1)
        else:
            print(max(safe_zone))
        return
  
    solution()

• BFS

    from collections import deque
  
    n = int(input())
  
    graph = [ [] for _ in range(n)]
    MAX = 0
  
    for i in range(n):
        graph[i] = list( map( int, input().split()) )
        MAX = max( max(graph[i]), MAX )
  
    dx = [ -1, 1, 0, 0 ]
    dy = [ 0, 0, -1, 1 ]
  
    def bfs(x,y,h):
        queue = deque()
        queue.append((x,y))
        visited[x][y] = 1
  
        while queue:
            x_, y_ = queue.popleft()
            for i in range(4):
                nx = x_ + dx[i]
                ny = y_ + dy[i]
                if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and graph[nx][ny] > h:
                    queue.append( (nx, ny) )
                    visited[nx][ny] = 1
  
    result = 0
  
    for i in range(MAX):
        count = 0
        visited = [ [0] * n for _ in range(n) ]
        for j in range(n):
            for k in range(n):
                if graph[j][k] > i and visited[j][k] == 0:
                    bfs(j, k, i)
                    count += 1
  
        result = max(result, count)
  
    print(result)

+α

• DFS

    import sys
    sys.setrecursionlimit(100000)
  
    n = int(input())
  
    graph = [ [] for _ in range(n)]
    MAX = 0
  
    for i in range(n):
        graph[i] = list( map ( int, input().split() ) )
        MAX = max( max(graph[i]), MAX )
  
    dx = [ -1, 1, 0, 0 ]
    dy = [ 0, 0, -1, 1 ]
  
    def dfs(x,y,h):
        visited[x][y] = 1
  
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and graph[nx][ny] > h:
                dfs(nx,ny,h)
  
    result = 0
  
    for i in range(MAX):
        count = 0
        visited = [ [0] * n for _ in range(n) ]
        for j in range(n):
            for k in range(n):
                if graph[j][k] > i and visited[j][k] == 0:
                    dfs(j, k, i)
                    count += 1
  
        result = max(result, count)
  
    print(result)

• tuple : 셀 수 있는 수량의 순서있는 열거 / 순서를 따르는 요소들의 모음

  • n-tuple : n개의 요소를 가진 tuple

  • 중복 원소 가능

  • 순서 있음

  • 원소 개수 유한

  • ⇒ 특정 튜플을 표현하는 문자열 s가 표현하는 튜플을 배열에 담아 반환*

  • 제한 사항

    • s의 길이는 5 이상 1,000,000 이하입니다.
    • s는 숫자와 '{', '}', ',' 로만 이루어져 있습니다.
    • 숫자가 0으로 시작하는 경우는 없습니다.
    • s는 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있습니다.
    • s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수입니다.
    • return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어집니다.

  • 예제 입력

    | s | result |
    | --- | --- |
    | "{{2},{2,1},{2,1,3},{2,1,3,4}}" | [2, 1, 3, 4] |
    | "{{1,2,3},{2,1},{1,2,4,3},{2}}" | [2, 1, 3, 4] |
    | "{{20,111},{111}}" | [111, 20] |
    | "{{123}}" | [123] |
    | "{{4,2,3},{3},{2,3,4,1},{2,3}}" | [3, 2, 4, 1] |

2. 풀이

• 파싱 이용하기
  • 주어진 문자열 s에서 숫자로 이루어진 부분 집합들을 뽑아낸 후,
  • 길이가 1인 것부터 (== 튜플의 가장 첫번째 원소) 부분집합의 길이를 기준으로 튜플의 다음 원소들을 추가
    
    

3. 코드

def solution(s):
    s = s[2:-2]
    ls = [ list(map(int,x.split(','))) for x in s.split('},{') ]
    ls = sorted(ls, key = lambda x: len(x))

    answer = []

    for e in ls:
        for num in e:
            if num not in answer:
                answer.append(num)

    return answer

+α

• 파싱 외에 정규표현식을 사용해보자 ⇒ 역시… 찾는 origin이 길어지면 드라마틱하게 시간을 줄일 수 있다..!

    import re
    from collections import Counter
    def solution(s):    
        answer = []
  
        nums = dict(Counter(re.findall('\d+', s)))
  
        answer = list(map(int, sorted(nums.keys(), key= lambda x : nums[x], reverse=True)))
  
        return answer

• 뱀과 사다리 게임 ⇒ 도착점에 도착할 수 있는 최소 횟수?
• 게임판 10 x 10, 1 ~100까지 수 순서대로 적혀있음
  • ex) i번 칸 ⇒ 주사위 4 나옴 ⇒ i+4칸

• 1번 ⇒ 100번 칸으로 이동

  • 주사위 굴린 결과가 100 넘어가면 이동 불가
  • 도착한 칸이 사다리면 사다리 타고 위로 (원래 있던 칸보다 크게)
  • 도착한 칸이 뱀이라면 뱀 타고 아래로 (원래 있던 칸보다 적게)

• 1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아님

• 모든 칸은 최대 하나의 사다리 또는 뱀 → 동시에 두 가지를 모두 가지고 있는 경우는 없다.

• 항상 100번 칸에 도착할 수 있는 입력만 주어진다.

⇒ 게임판의 상태가 주어졌을 때, 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값?

• 입력 : | 사다리의 수 **N** 뱀의 수 **M** (1 ≤ N ≤ 15, 1 ≤ M ≤ 15) | N개 줄 : 사다리의 정보 x, y (x < y) (x번 칸에 도착하면 y번 칸으로 이동) | M개 줄 : 뱀의 정보 u, y (u > v) (u번 칸에 도착하면 v번 칸으로 이동)

• 출력 : 100번 칸에 도착하기 위해 주사위를 굴려야 하는 최소 회수

• 예제 입력

  

2. 풀이

• BFS
  • 현재 위치 cur과 주사위를 돌린 횟수 rolls를 queue 에 담아서 이용하며, queue에서 원소를 하나씩 빼서 목적지 100인지 확인하거나 주사위를 굴린다
  • 만약 현재 위치가 목적지 100이라면 여태 주사위를 굴린 횟수 rolls를 출력하고 while문 탈출한다.
  • 아직 목적지에 도달하지 않아, 주사위를 굴린다면 1~6 사이의 숫자를 현재 위치에 더해서,
  • 다음 위치가 100 이하의 숫자라면
    • 해당 위치가 사다리에 해당된다면 or 뱀에 해당된다면 다음 위치를 다시 갱신
    • 방문하지 않은 위치라면 주사위를 1번 굴렸으므로, queue에 해당 위치와 굴린횟수+1을 추가하고, 방문 처리
      
      
      
      

3. 코드

import sys
from collections import deque

def solution():

    input = sys.stdin.readline

    N, M = map(int, input().split())
    ladders = dict()
    snakes = dict()

    for _ in range(N):
        x, y = map(int, input().split())
        ladders[x] = y

    for _ in range(M):
        u, v = map(int, input().split())
        snakes[u] = v

    visited = [False] * 101

    rolls = 0

    #BFS
    cur = 1
    queue = deque()
    queue.append((cur, rolls))
    visited[1] = True

    while queue:
        cur, rolls = queue.popleft()
        if cur == 100:
            print(rolls)
            break

        for dice in range(1,7):
            next = cur + dice

            if next <= 100:
                if next in ladders.keys():
                    next = ladders[next]
                elif next in snakes.keys():
                    next = snakes[next]
                if not visited[next] :
                    queue.append((next, rolls+1))
                    visited[next] = True

solution()

+α

• 1차 시도
  • 문제에 나온 대로 10*10 board를 만들고 번호에 따라 i행 j열을 계산하고,,, 문제를 너무 복잡하게 생각해서 삽질을 많이 함…
  • • 사다리를 타고 이동한 위치가 뱀의 시작 위치일 수도 있다고 문제를 해석해서 ( 단순히 시작 위치만 겹치지 않는 것으로 해석해서) 주사위를 굴린 후 말의 위치를 계산해내는 것만으로도 별도의 함수를 제작해야한다고 생각했다…^__^

BFS/DFS 문제 오랜만에 풀었더니 감 다까먹었다.. 열공하자,,

• 운영체제 없는 컴퓨터?
  • 동작 가능, but 처음 설계한대로만 동작 ⇒ 다른 기능 추가 불가, X 유연

운영체제가 하는 일

1. 프로세스 관리

   • 여러 프로세스들을 관리 : 프로세스의 CPU 독차지 방지
   • 사용자 상호작용이 이루어지는 프로세스 외에는 백그라운드로 실행

2. 메모리 관리

   • 모든 프로그램은 메모리에 올려서 관리하며 동작

3. 하드웨어 관리

   • 사용자의 하드웨어에 대한 직접적인 접근 방지

   • 하드디스크의 특정 영역에 다른 중요한 데이터 보호

   • ⇒* 운영체제의 판단 하에, 적절한 위치에 사용자의 데이터 저장

4. 파일 시스템 관리

   • 하드디스크에 파일들을 효율적으로 저장 & 관리

운영체제의 역사

• 1940 : ENIAC

  • 스위치와 배선 작업 → HW의 비용 ↑↑

    ⇒ CPU를 최대한 많이 사용할 수 있는 법?

• 1950초 : IC (직접 회로) - 진공관과 전선으로 만들어진 논리 회로를 아주 작은 크기로 만듧

  • programmer : 펀치카드로 프로그램 작성

  • operator : 컴퓨터에 카드를 넣고 결과가 나오면 프로그래머에게 전달

    
    
    

1950중후반 : Single Stream Batch system

• programmer가 펀치카드를 여러 개 제작 → operator가 여러 개를 한 번에 컴퓨터에 전달 → 컴퓨터는 여러 개의 프로그램을 순서대로 실행해서 결과를 한번에 확인할 수 있도록 개발

• 한계 : CPU와 입출력을 분리하여도, 입력을 받기 위한 대기 시간에는 CPU의 사용률이 떨어진다

  • I/O Device Controller (입출력 관리자)

    • 입출력 시 CPU를 사용할 수 없는 점을 개선
    • 입출력 작업이 끝나면 CPU에게 interrupt 신호를 발신 ⇒ interrupt 신호 받은 CPU가 처리할 수 있도록

  • CPU와 입출력의 분리했지만 still 1 more problem

    • 입출력에도 CPU를 기다려야 하는 작업 있음

      • ex) 입력을 처리하는 작업일 때 입력이 전부 완료되어야만 처리할 수 있음

        ⇒ 이렇게 기다리는 시간에는 CPU의 사용률이 떨어짐

1960년도 : Time Sharing System (시분할 시스템)

• **memory에 여러 program을 올려두고 시간을 나누어, 각 프로그램을 짧은 시간씩 돌아가며 실행

• Single Stream Batch system의 한계 개선

  • 프로그램을 순서대로 하나씩 실행 X
  • 매우 빠르게 번갈아가며 실행 ⇒ 사용자에게는 전부 동시에 실행되는 것처럼 보이게 됨
  • A작업에서 필요한 입력 처리 위해 cpu가 대기할 때 b,c 작업 ⇒ cpu 사용률 높임

• Terminal

  • 프로그램을 동시에 여러 개 실행할 수 있으니, 당시 비싼 컴퓨터 1대를 여러 사용자가 Terminal이라는 단말기를 통해 접근하여 사용

• File System

  • 컴퓨터의 개인화 ⇒ 필요한 문서와 같은 개인 정보를 컴퓨터에 저장 ⇒ file system 등장

• UNIX

  • C언어로 UNIX 운영체제 개발 (AT&벨 연구소)

  • Multi-programming, Multi-user, File system 구현

    
    
    

    Time Sharing System의 한계 (Base Register의 등장)

1. 메모리 침범

   • 한 program이 다른 program 메모리 침범 시 원하지 않는 결과 발생, OS영역까지 침범할 경우 치명적인 오류 발생 가능

2. 메모리 주소 할당

   • 기존 1 메모리 : 1 program) 메모리 주소를 program 1개로 가정하고 개발

   • Time Sharing System) program이 어느 메모리 위치에서 실행할지 모름

*⇒ Base Register : program의 시작주소를 저장 *⇒ “모든 프로그램은 0번지에서 실행한다”고 가정

1970년도 이후 : 개인 컴퓨터 → GUI

운영체제의 구조

이미지 출처 : https://math-coding.tistory.com/80

1. Kernel : process, memory, storage를 관리하는 핵심 기능

2. Interface : 사용자는 interface를 통해서 OS의 Kernel에 접근 가능 (직접 접근 불가)

   • GUI, CLI

⇒ user/application - system call - kernel - driver - HW

• system call

  • kernel이 사용자로부터 자신을 보호하기 위한 interface
  • application은 system call을 통해 Kernel에 접근가능
    • kernel에서 제공하는 write함수를 사용 → OS가 알아서 하드디스크의 빈 공간에 정보 저장

  • driver

    • 보통 HW 제조사에서 driver 제공 (OS는 많은 종류의 HW를 전부 지원해야 하기 때문에 각각의 하드웨어에 맞는 프로그램을 Kernel이 모두 갖고 있기 어려움)

    • mouse, keyboard 같은 기본적인 HW 장치들은 kernel에 포함

컴퓨터 하드웨어와 구조 (CPU, RAM/ROM, BUS)

von Neumann (폰 노이만 구조) : *CPU - BUS - Memory(RAM) *

• BUS : 데이터를 전달하는 통로
  • 프로그램 내장 방식 : 프로그램을 메모리에 올려서 사용 (↔️ 하드웨어로 프로그램 만들기 = 프로그램이 달라질 때마다 스위치와 배선 재조정 필요
    
    

*0. Main Board *: 다른 하드웨어를 연결하는 장치

• 장치 간 데이터 전송 ⇒ 메인보드의 BUS가 담당
  
  

1. CPU (중앙처리장치)

• ALU (Arithmetic and Logic Unit) : 실제 데이터 연산 담당 (산술논리 연산장치)

• Control Unit : 모든 장치들의 동작을 지시하고 제어하는 장치

• Register : CPU 내 계산 위해 임시로 보관하는 장치

  • Program Counter (PC)
  • Memory Address Register
  • Memory Buffer Register
  • Instruction Register (IR)

        …

*2. Memory (주기억장치) : RAM & ROM *

*2-1) Cache Memory *: CPU와 주기억장치 사이의 속도차이 완화 시키기 위한 고속 buffer memory

2-2) 주기억장치(RAM/ROM) & 보조기억장치

컴퓨터의 부팅과정

• 전원 → ROM에 저장된 BIOS 실행 → 하드디스크에 있는 MBR (Master Boot Record)에 저장된 Boot Loader를 RAM으로 가져와 실
  → OS 2개 이상일 경우 OS 선택 → OS를 RAM으로 불러와 실행 → 이후 실행되는 모든 program은 OS가 관리

• BIOS : 전원, CPU, 메모리, 하드디스크 등 주요 HW에 이상이 없는지 체크

  • 이상 발견 시 오류 내며 부팅 X

Interrupt (인터럽트)

• if) CPU가 입출력장치에 데이터를 Read/Write하는 상황

  • CPU : 입출력 작업이 들어오면 → 입출력 관리자에게 입출력 명령
  1. Polling 방식 : CPU 입장에서는 입출력 명령이 언제 완료될 지 알 수 없기 때문에 주기적으로 확인 필요
     • 단점 : 주기적으로 CPU가 확인해줘야 하기 때문에 성능 좋지 못함

2. Interrupt 방식 : CPU가 입출력 관리자에게 입출력 명령을 내리고 다른 작업 지속

   • 입출력 관리자는 입출력이 완료됐을 때 CPU에게 신호를 전송 ⇒ CPU는 그 신호를 받아 ISR (Interrupt Service Routine)을 실행시켜 작업을 완료함
     • ISR (Interrupt Service Routine) : 특정 Interrupt가 들어오면 그것을 처리하는 함수

- **HW Interrupt  :**  keyboard, 마우스 입력, 디스크 입출력, 프린터

- **SW Interrupt   :**  사용자 program에서 발생한 interrupt
  - ex) 유효하지 않은 메모리 접근, 0으로 나누기

+α

Q. Program vs Process vs Thread

• Program : 컴퓨터 디스크에 저장된 정적인 file (보조기억 장치)
  
  

• Process : 프로그램이 메모리에 올라가, 실제로 실행 중인 동적인 entity

  • Program + 실행에 필요한 자원 할당 ⇾ Process

  • OS로부터 할당 받는 자원 :

    1. CPU 시간
       2. 운영되기 위해 필요한 주소 공간
       3. 독립된 메모리 영역 (Code/Data/Stack/Heap 구조)
       • ** 각 Process 별 별도의 주소 공간 & 독자적인 메모리 공간 ⇾ ** 다른 Process의 변수/자료구조에 접근 불가
       • IPC (Process간 통신) : 다른 Process의 자원에 접근 허용
       • Process : min 1 Thread = Main Thread

• Thread : Process가 할당받은 자원을 이용하는 실행 단위 / Process의 특정한 수행 경로 / Process 내 실행되는 여러 흐름의 단위

  • Main thread : Process 내 존재하는 최소 1개 thread

  • 각 thread 별 독자적인 register & stack memory 보유

  • thread들은 Code, Data, Heap 공유

  • Process 내의 주소공간/자원들 공유

  • 1 thread가 process 자원을 변경하면 다른 sibling thread(이웃 thread)도 그 변경 결과를 즉시 볼 수 있다

  • memory를 공유하기 때문에 동기화 , deadlock 등의 문제 발생 가능

  • 관련 library : POSIX Pthreads, Windows threads, Java threads

  	Process	Thread
  정의	실행 중인 program	Process의 실행 단위
  생성/종료시간	많은 시간 소요	적은 시간 소요
  Context Switching	많은 시간 소요	적은 시간 소요
  상호작용	IPC 사용	공유 memory 사용
  자원소모	많음	적음
  메모리 내 독립성	각각 독립적	프로세스 내 stack/register 독립적, 이외 공유

Q. Processor & Multi-Processing & Multi-Threading

• Processor = CPU : computer 내 program을 수행하는 HW Unit (명령어 해석하는 한 부분)

• Process의 동시성 & 병렬성 (Concurrency & Parallelism)

  • processor는 한번에 1개의 process만 실행

  • 동시성 = Context Switching : processor 하나가 program 1,2,3,4 여러 작업을 돌아가며 일부분씩 수행하는 방식

  • 병렬성 = Processor 1에 Core 여러 개가 달려서 각각 동시에 작업하는 방식

    • "dual-core"/"quad-core"/"octa-core" 등의 명칭의 processor가 달린 컴퓨터에서만 할 수 있는 방식

• Multi-tasking : 동시에 여러 개의 program 실행
• Multi-processing : 응용프로그램을 여러 개의 process로 구성 ⇒ 각 process가 1개의 task 처리하도록

주제와 관련한 cs 질문

• CPU 사용률 관점에서 시분할 시스템과 입출력 관리자의 역할에 대해 설명하시오

  • 시분할 시스템과 입출력 관리자 모두 CPU의 사용률을 높이기 위해 고안된 것
  • 기존의 single stream batch system은 입출력이 모두 끝날 때까지 CPU를 사용할 수 없었기 때문에 입출력 관리자를 통해 입출력을 분리함으로써, cpu의 사용률을 높일 수 있었다
  • 하지만 여전히 입출력이 끝날 때까지 cpu가 대기해야

• 멀티 프로세싱과 멀티 스레딩의 장단점에 대해서 설명하시오

  • 멀티 프로세싱의 경우, 프로세스가 독자적인 메모리와 주소 공간을 갖고 있으므로, 하나의 프로세스의 오류가 다른 프로세스에 영향을 주지 않아 안정적이다. 하지만 프로세스 간 메모리가 공유 되지 않아, context switching 비용과과 ipc 비용이 크다
  • 반면 멀티 스레딩의 경우, 스레드들이 stack영역을 제외한 메모리를 공유하여 스레드 간 데이터 교환이나 context switching이 빠르게 이루어질 수 있다. 반면 이것이 단점이 되어 동기화, deadlock 등의 오류가 발생할 수 있다.

Q. Interrupt : 비동기 방식 ⇒ 성능에 이점? DMA Controller?

Q. booting -> BIOS vs UEFI?

Q. core 란?

• Reference
  • https://velog.io/@gparkkii/ProgramProcessThread

  • https://change-words.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%A8%EA%B3%BC-%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4%EC%9D%98-%EC%B0%A8%EC%9D%B4%EC%A0%90#:~:text=%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%A8%20%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4%20%EC%B0%A8%EC%9D%B4,%EC%97%90%20%EC%9E%88%EB%8B%A4%EA%B3%A0%20%EC%9D%B4%ED%95%B4%ED%95%A0%20%EC%88%98%20%EC%9E%88%EC%8A%B5%EB%8B%88%EB%8B%A4.

• “N x N”크기의 격자에 있는 번호가 부여된 인형들을 바구니에 옮기는 인형뽑기 게임

• 인형은 바구니의 가장 아래 부터 순서대로 쌓임

• 같은 모양의 인형이 바구니에 연속해서 쌓이게 되면 두 인형은 바구니에서 사라짐

  ⇒ 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수?

• 입력 :

  • 게임 화면의 격자의 상태가 담긴 2차원 배열 board
  • 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves

• 출력 : 터트려져 사라진 인형의 개수

2. 풀이

• 바구니 ⇒ stack!

• moves의 원소들을 m이라고 할 때, 입력으로 주어진 board를 그대로 사용하게 된다면, m번째 위치의 원소를 매번 조회하고, 인형을 뽑게 됐을 경우의 처리 등이 코드적으로 비효율적

• 따라서 move마다 board에서 m번에 위치한 인형들을 crane이라는 list로 생성하여 사용한다.
  

• 이 때, crane의 가장 윗부분에 있는 인형을 뽑기 위해 for loop을 이용

  • 만약 basket이 비어있거나, basket의 가장 위에 위치한 인형이 방금 뽑은 인형과 다를 경우, basket에 방금 뽑은 인형을 append
  • 만약 basket의 가장 위에 위치한 인형이 방금 뽑은 인형과 같을 경우 인형을 없앤 후 answer +=2

3. 코드

def solution(board, moves):
    answer = 0

    basket = []

    width = len(board)

    for m in moves:
        crane = [ board[x][m-1] for x in range(width) ] 

        for i in range(width):
            if crane[i] != 0:
                board[i][m-1] = 0

                if not basket or crane[i] != basket[-1]:
                    basket.append(crane[i])
                else:
                    basket.pop(-1)
                    answer += 2
                break

    return answer

+α