요약: 주어진 행동을 수행할 수 있는 기능 구현

"시간초과 코드"입니다!

문제에 dual linked list를 써야한다고 써있다. 하지만, 다르게 풀어보고 싶었다. 결과는 시간초과이기는 하지만...

아무래도 지속적인 dictionary 업데이트가 원인인 것 같다.

이 문제는 다음 6가지 기능을 구현해야한다.

1. 공장 설립
    - n개의 벨트 설치
    - m개 물건 준비
    - m개의 선물 위치
    - 각각 선물의 번호는 오름차순으로 벨트에 쌓임

2. 물건 모두 옮기기
    - m_src 번째 벨트에 있는 선물들을 모드 m_dst번째 벨트로 이동
    - m_src에 없으면 안옮겨도 됨
    - 옮겨진 선물들은 m_dst 벨트 앞에 위치
    - 옮긴뒤 m_dst에 있는 선물 개수 출력

3. 앞 물건만 교체하기
    - m_src 벨트에 있는 선물 중 가장 앞에 있는 선물을 m_dst 벨트의 가장 앞 선물과 교체
    - 둘 중 하나에 선물이 없으면 교체 없이, 있는 것만 옮김
    - 옮긴뒤 m_dst에 있는 선물 개수 출력

4. 물건 나누기
    - m_src 벨트에 있는 선물개수 n개 -> floor(n/2) 번째 까지 선물을 m_dst벨트 앞으로 옮기기
    - 옮긴뒤 m_dst에 있는 선물 개수 출력

5. 선물 정보 얻기
    - 선물 번호 p_num이 주어질 때, 
    - 해당 선물의 앞 선물의 앞번호 a와 뒤 번호 b라고 할 때, a + 2*b 출력
    - 없을 경우 -1

6. 벨트 정보 얻기
    - 벨트 번호 b_num이 주어질 떄, 
    - 해당 벨트의 맨앞 a, 맨뒤 선물 번호를 b, 선물개수 c
    - a + 2*b + 3*c 값 출력
    - 선물이 없으면 a와 b 모두 -1

선물 아이디 리스트를 가진 벨트들이 있어야 한다.

그리고 선물 정보를 위해, 각 선물이 어디 있는지를 알아야한다. 이것을 dictionary를 통해 관리해보고 싶었다. 그렇기 때문에 선물이 옮겨질 때마다, 영향이 있는 벨트의 선물들의 정보를 모두 업데이트 해주어야 했다. (그 결과는 시간초과 였다...)

그래도, 정답은 맞췄다. 작성한 코드는 다음과 같다.

전체 코드

"""
Author:
    Name: KyungHyun Lim
    Email: lkh1075@gmail.com
"""

from collections import defaultdict

def make_factory(belts, gift_loc, n, infos):
    for _ in range(n + 1):
        belts.append(list())

    for idx, belt_num in enumerate(infos):
        gift_loc[idx + 1] = [belt_num, len(belts[belt_num])]
        belts[belt_num].append(idx + 1)

def move_all(belts, gift_loc, src, dst): ##
    src_list = belts[src]
    belts[dst] = src_list + belts[dst]
    belts[src] = list()

    for idx, gift in enumerate(belts[dst]):
        gift_loc[gift] = [dst, idx]

    print(len(belts[dst]))

def move_front(belts, gift_loc, src, dst): ##
    src_front = belts[src][0] if len(belts[src]) > 0 else -1
    dst_front = belts[dst][0] if len(belts[dst]) > 0 else -1

    if src_front != -1 and dst_front != -1: # 둘다 있는 경우
        belts[src] = [dst_front] + belts[src][1:]
        gift_loc[dst_front] = [src, 0]

        belts[dst] = [src_front] + belts[dst][1:]
        gift_loc[src_front] = [dst, 0]
    elif src_front == -1 and dst_front != -1: # src가 빈경우
        belts[dst] = belts[dst][1:]
        belts[src] = [dst_front] + belts[src][1:]
        gift_loc[dst_front] = [src, 0]
    elif src_front != -1 and dst_front == -1: # dst가 빈경우
        belts[src] = belts[src][1:]
        belts[dst] = [src_front] + belts[dst][1:]
        gift_loc[src_front] = [dst, 0]

    for idx, gift in enumerate(belts[dst]):
        gift_loc[gift] = [dst, idx]

    for idx, gift in enumerate(belts[src]):
        gift_loc[gift] = [src, idx]

    print(len(belts[dst]))

def divide(belts, gift_loc, src, dst):
    amount = len(belts[src]) // 2

    belts[dst] = belts[src][:amount] + belts[dst]
    belts[src] = belts[src][amount:]

    for idx, gift in enumerate(belts[dst]):
        gift_loc[gift] = [dst, idx]

    for idx, gift in enumerate(belts[src]):
        gift_loc[gift] = [src, idx]

    print(len(belts[dst]))

def get_gift_info(belts, gift_loc, gift):
    belt, index = gift_loc[gift]

    if index == 0: a = -1
    else: a = belts[belt][index - 1]

    if index == len(belts[belt]) - 1: b = -1
    else: b = belts[belt][index + 1]

    print(a + (2*b))

def get_belt_info(belts, belt):
    c = len(belts[belt])
    if c > 0:
        a, b = belts[belt][0], belts[belt][-1]
    else:
        a, b = -1, -1  

    print(a + (2*b) + (3*c))

# 선물 위치 관리
gift_loc = defaultdict(list)

# 벨트 관리
belts = list()

# 명령 실행 횟수
q = int(input())
for _ in range(q):
    infos = list(map(int, input().split()))
    if infos[0] == 100:
        # 1. 공장 설립
        n, m, infos = infos[1], infos[2], infos[3:] 
        make_factory(belts, gift_loc, n, infos)
    elif infos[0] == 200:
        # 2. 물건 모두 옮기기
        m_src, m_dst = infos[1], infos[2]
        move_all(belts, gift_loc, m_src, m_dst)
    elif infos[0] == 300:
        # 3. 앞 물건만 교체하기
        m_src, m_dst = infos[1], infos[2]
        move_front(belts, gift_loc, m_src, m_dst)
    elif infos[0] == 400:
        # 4. 물건 나누기
        m_src, m_dst = infos[1], infos[2]
        divide(belts, gift_loc, m_src, m_dst)
    elif infos[0] == 500:
        # 5. 선물 정보 얻기
        gift = infos[1]
        get_gift_info(belts, gift_loc, gift)
    elif infos[0] == 600:
        # 6. 벨트 정보 얻기
        belt = infos[1]
        get_belt_info(belts, belt)

요약: 사람들이 위와 같은 방식으로 움직일 때 총 몇 분 후에 모두 편의점에 도착하는지를 구하는 프로그램을 작성해보세요.

문제에서 주어진 조건을 잘 구현해야하는 시뮬레이션 문제이다.

총 m명의 사람들이 각 m분에 각자의 베이스캠프에서 출발해 편의점으로 이동한다.

1분동안 다음과 같은 행동 진행
    1. 본인이 가고 싶은 편의점 방향을 향해서 1칸 이동
        - 최단거리로 움직임
        - 최단거리가 여러가지 이면, 상, 좌, 우, 하 순서로 움직임
    2. 편의점에 도착하면, 해당 편의점에서 멈춤
        - 이때부터 다른 사람들은 이곳을 지나갈 수 없음
    3. 현재 시간이 t분이고, t <= m을 만족하면, t번 사람은 자신이 가고 싶은 편의 점과 가장 가까이 있는 베이스 캠프에 입장
        - 여러가지면, 행이 작은순, 열이 작은 순
        - t번 사람이 베이스 캠프로 이동하는 데에는 시간이 소요되지 않음
        - 이때부터 다른 사람들은 이곳을 지나갈 수 없음

문제의 조건에 맞게 구현을 하면 된다. 먼저 주어진 입력을 받기 위한 변수들을 선언한다.

• n, m (int, int): 맵의 크기, 사람의 수
• gird (list[list]): 맵의 상태 표시 (0: 빈공간, 1: 베이스캠프, -1: 지나갈수없는 곳)
• store (list): idx번째 사람이 가고 싶은 편의점 좌표 (입력에서 -1 해주어야함 (1,1)부터 시작함으로)
• person (dict): 맵에 들어온 사람의 번호 및 위치, 최종 도착여부 관리

모든 사람이 도착할 때 까지 1 ~ 3 과정을 반복해야한다. 따라서 다음과 같이 조건을 잡아 주었다.

while arrived < m:

다음으로는 우선 큰 틀을 구현 하였다. 먼저 모든 사람이 가고 싶은 편의점을 향해 최단거리 방향으로 1만큼 움직인다. 따라서 person dictionary에 있는 정보를 기반으로 움직일지 말지 결정하고(cord[-1]) 최단거리 경로를 찾는다. (find_road) 최단거리 경로를 이용해 편의 점에 도착했으면, cord[-1]을 -1로 업데이트해 더이상 해당 사람은 움직이지 않도록 설정해주고, 맵(grid)에도 -1로 값을 바꾸어 다른 사람들이 지나갈 수 없도록 설정해준다. 만약, 도착하지 않았다면 위치값만 업데이트 해준다.

# 1. 가고 싶은 편의점 최단거리 방향을 향해 1칸 이동
    for order, cord in person.items():
        if cord[-1] != -1:
            path = find_road(n, grid, cord, store[order])
            # print(f'{order + 1} move:', path, f'target: {store[order]}')
            if path[1][0] == (store[order][0] - 1) and path[1][1] == (store[order][1] -1):
                # 편의점에 도착한 것이면
                grid[path[1][0]][path[1][1]] = -1 # 지나갈 수 없는 곳
                person[order][-1] = -1 # 더이상 움직이지 않도록
                arrived += 1 # 도착한 사람 증가
            else: 
                # 위치 업데이트
                person[order] = [path[1][0], path[1][1], 1]

다음으로는 맵에 새로운 사람이 들어오는 경우를 처리해준다. store 변수를 이용해, 해당 사람이 가야할 편의점 위치를 가져온다. 그리고 이 편의점에서 가장 가까운 베이스캠프를 찾는다. (find_road) 찾은 베이스캠프 정보를 person 정보에 업데이트 해준다. 마지막으로 더이상 다른사람들이 지나갈 수 없도록 맵(grid)를 업데이트 해준다.

# 2. t <= m을 만족하면, t번 사람 베이스 캠프로 이동
    if time <= m:
        store_x, store_y = store[time - 1] # 사람이 가야할 편의점 위치
        path = find_road(n, grid, [store_x-1, store_y-1], None) # 베이스 캠프 찾기
        # print(f'{time} base camp:', path[-1])
        person[time - 1] = [path[-1][0], path[-1][1], 1] # 사람 추가
        grid[path[-1][0]][path[-1][1]] = -1 # 지나 갈 수 없는 곳

이제 문제의 조건을 구현하는 부분이 완료되었다. 마지막으로 시작지점으로부터 목표지점까지 최단거리경로를 찾아줄 find_road 함수를 완성해야 한다.

기본적인틀은 BFS 탐색방식을 활용하였다. 큐에는 [x, y, 경로길이, 경로 리스트] 정보를 넣어 관리하였다. (경로 리스트가 있으면 경로 길이를 알 수 있지만, 매번 len을 이용하는 것보다 하나씩 값을 더해 관리하는 것이 더 효율적이라고 판단했다.)

경로를 탐색하며 store_cord 변수의 값을 이용해, 편의점을 찾는 것인지 베이스캠프를 찾는 것인지 구분해주었다.

다음 경로 조건으로는 3가지를 활용했다.

1. 맵을 벗어나지 않음
2. 방문한 적이 없음
3. grid[x][y] 값이 -1이 아님

나머지 부분은 기본적인 BFS와 형태가 동일하다.

def find_road(n, grid, cord, store_cord):
    # 상, 좌, 우, 하
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]
    visited = [[False] * n for _ in range(n)]

    q = deque()
    q.append((cord[0], cord[1], 0, [[cord[0], cord[1]]]))
    visited[cord[0]][cord[1]] = 0

    g_cost = n * n + 1
    g_path = []

    while q:
        cx, cy, cost, path = q.popleft()
        if store_cord: 
            # 편의점 도착 검사
            if cx == (store_cord[0]-1) and cy == (store_cord[1]-1):
                if cost < g_cost:
                    g_cost = cost
                    g_path = path
        else:
            # 베이스 캠프 도착 검사
            if grid[cx][cy] == 1:
                if cost < g_cost:
                    g_cost = cost
                    g_path = path

        for d in range(4):
            nx, ny = cx + dx[d], cy + dy[d]
            if 0 <= nx < n and 0 <= ny < n: # 맵 벗어나지 않음
                if not visited[nx][ny]: # 방문한 적이 없으면
                    if grid[nx][ny] != -1: # 갈수 있는 곳이면
                        n_path = path[:]
                        n_path.append([nx, ny])
                        q.append([nx, ny, cost + 1, n_path])
                        visited[nx][ny] = True

    return g_path

전체 코드

"""
Author:
    Name: KyungHyun Lim
    Email: lkh1075@gmail.com
"""

from collections import defaultdict, deque

def find_road(n, grid, cord, store_cord):
    # 상, 좌, 우, 하
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]
    visited = [[False] * n for _ in range(n)]

    q = deque()
    q.append((cord[0], cord[1], 0, [[cord[0], cord[1]]]))
    visited[cord[0]][cord[1]] = 0

    g_cost = n * n + 1
    g_path = []

    while q:
        cx, cy, cost, path = q.popleft()
        if store_cord: 
            # 편의점 도착 검사
            if cx == (store_cord[0]-1) and cy == (store_cord[1]-1):
                if cost < g_cost:
                    g_cost = cost
                    g_path = path
        else:
            # 베이스 캠프 도착 검사
            if grid[cx][cy] == 1:
                if cost < g_cost:
                    g_cost = cost
                    g_path = path

        for d in range(4):
            nx, ny = cx + dx[d], cy + dy[d]
            if 0 <= nx < n and 0 <= ny < n: # 맵 벗어나지 않음
                if not visited[nx][ny]: # 방문한 적이 없으면
                    if grid[nx][ny] != -1: # 갈수 있는 곳이면
                        n_path = path[:]
                        n_path.append([nx, ny])
                        q.append([nx, ny, cost + 1, n_path])
                        visited[nx][ny] = True

    return g_path

n, m = list(map(int, input().split())) # 맵크기, 사람수
grid = [list(map(int, input().split())) for _ in range(n)] # 맵 상태 (0: 빈공간, 1: 베이스캠프)
store = [list(map(int, input().split())) for _ in range(m)] # idx번째 사람이 가고싶은 편의점 좌표 (-1 필수)
person = defaultdict(list) # 맵에 들어온 사람의 번호 및 위치

arrived = 0
time = 0

while arrived < m:
    time += 1
    # print(f'time: {time} /', arrived)
    # 1. 가고 싶은 편의점 최단거리 방향을 향해 1칸 이동
    for order, cord in person.items():
        if cord[-1] != -1:
            path = find_road(n, grid, cord, store[order])
            # print(f'{order + 1} move:', path, f'target: {store[order]}')
            if path[1][0] == (store[order][0] - 1) and path[1][1] == (store[order][1] -1):
                # 편의점에 도착한 것이면
                grid[path[1][0]][path[1][1]] = -1 # 지나갈 수 없는 곳
                person[order][-1] = -1 # 더이상 움직이지 않도록
                arrived += 1 # 도착한 사람 증가
            else: 
                # 위치 업데이트
                person[order] = [path[1][0], path[1][1], 1]

    # 2. t <= m을 만족하면, t번 사람 베이스 캠프로 이동
    if time <= m:
        store_x, store_y = store[time - 1] # 사람이 가야할 편의점 위치
        path = find_road(n, grid, [store_x-1, store_y-1], None) # 베이스 캠프 찾기
        # print(f'{time} base camp:', path[-1])
        person[time - 1] = [path[-1][0], path[-1][1], 1] # 사람 추가
        grid[path[-1][0]][path[-1][1]] = -1 # 지나 갈 수 없는 곳

    # print('p:', person)
print(time)

요약: 주사위를 놓은 곳의 좌표와 이동시키는 명령이 주어졌을 때, 주사위가 이동했을 때 마다 상단에 쓰여 있는 값을 구하는 프로그램을 작성

해당 문제의 포인트는 "굴러가는 주사위 값의 변화를 어떻게 나타낼것인가?" 라고 생각한다. 다양한 방법이 있겠지만, 가장 직관적인 방법은 전개도를 기반으로 미리 값의 변화를 정의하는 것이다.

동쪽(1), 서쪽(2), 북쪽(3), 남쪽(4), 각 방향에 따라 값이 어떻게 변하는지 정의한코드이다.

def roll_dice(dice, d):
    if d == 1:
        dice[1], dice[3], dice[4], dice[6] = dice[3], dice[6], dice[1], dice[4]
    elif d == 2:
        dice[1], dice[3], dice[4], dice[6] = dice[4], dice[1], dice[6], dice[3]
    elif d == 3:
        dice[1], dice[2], dice[5], dice[6] = dice[2], dice[6], dice[1], dice[5]
    elif d == 4:
        dice[1], dice[2], dice[5], dice[6] = dice[5], dice[1], dice[6], dice[2]

그 다음은 어렵지 않다. 주어지는 움직임 리스트에 따라서 주사위를 굴려주기만 하면 된다.

그리고 추가 조건인, 값의 복사 처리만 해주면 된다.

보드 값이 0이면 주사위값 복사, 0이 아니면 주사위로 값 복사

이것을 구현한 코드는 다음과 같다.

전체 코드

def roll_dice(dice, d):
    if d == 1:
        dice[1], dice[3], dice[4], dice[6] = dice[3], dice[6], dice[1], dice[4]
    elif d == 2:
        dice[1], dice[3], dice[4], dice[6] = dice[4], dice[1], dice[6], dice[3]
    elif d == 3:
        dice[1], dice[2], dice[5], dice[6] = dice[2], dice[6], dice[1], dice[5]
    elif d == 4:
        dice[1], dice[2], dice[5], dice[6] = dice[5], dice[1], dice[6], dice[2]

def solution():
    dice = [0 for _ in range(7)]

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

    N, M, x, y, K = map(int, input().split())
    board = [[0]*M for _ in range(N)]
    for i in range(N):
        board[i] = list(map(int, input().split())) 

    orders = list(map(int, input().split()))

    for order in orders:
        # 1. 이동 좌표 확인
        nx = x + dx[order]
        ny = y + dy[order]

        # 2. 지도 안쪽이면 진행
        if 0 <= nx < N and 0 <= ny < M:
            # 주사위 굴리기
            roll_dice(dice, order)

            # 보드 값이 0이면 주사위값 복사, 0이 아니면 주사위로 값 복사
            if board[nx][ny] == 0:
                board[nx][ny] = dice[6]
            else:
                dice[6] = board[nx][ny]
                board[nx][ny] = 0

            print(dice[1])

            x, y = nx, ny

def main():
    solution()

if __name__ == '__main__':
    main()

요약: K시간 후 살아있는 줄기 세포(비활성 상태 + 활성 상태)의 총 개수를 구하는 프로그램을 작성

이 문제에서 가장 어려운점 하나는 배양할 수 있는 공간이 무한정이라는 것이다. 따라서 2차원 배열이 무한정 늘어날 수 있기 때문에 색다른 접근 방식이 필요할 것이라고 생각했다.

그래서 defaltdict의 key를 활용해 세포가 있는 cell의 좌표를 관리해보았다. 다음과 같이

• dictionary의 key -> cell의 좌표
• dictionary의 value -> [시작 시간, 수명]
  • 따라서 초기 세포들은 [0, 입력값]으로 설정

for i in range(N):
    for j in range(M):
        # [시작 시간, 수명]
        if grid[i][j] != 0: can_active[(i, j)] = [0, grid[i][j]]

이 기본 셋팅을 바탕으로 세포들을 관리한다.

• can_active: 비활성화 상태의 세포들
• generate: 막 활성화 되어, 증식해야하는 세포들
• activate: 증식은 끝났지만, 수명이남은 세포들
• dead_cell: 수명이다한 세포들

dead_cell은 유지되는 정보이기 때문에 test_case가 변할때만 초기화 해주면된다. generate의 경우 막활성화된 다음 time에만 증식을 하기 때문에 매시간 초기화 해주어야한다. activate can_active의 경우, 매시간 new_를 붙인 변수를 활용해 정보를 업데이트 해주어야 한다.

매시간 일어나는 일은 다음과 같다.

1. 이번 시간에 증식하는 세포들 증식 및 activate에 추가
  - 세포가 있는 곳에는 증식 불가능
  - 증식한 세포는 활성화 되어있기 때문에 activate에 추가
2. generate 초기화 
  - 증식은 최초 1시간만 하기 때문에 초기화해주어야 한다.
3. 이번 시간에 활성화 되는 세포, generate에 추가, 비활성화 상태 유지 new_can_activate에 추가
  - 생성시간(put_time) + 수명(life) 이 현재 time과 같으면 genrate에 추가
  - 아니면, 비활성화 상태 유지
4. activate에서 수명을 다한 세포들 new_active에 추가
  - 현재 time이 최종 수명(put_time + (life*2)) 보다 작으면 new_activate에 추가
  - 크면 죽은 세포임으로 dead_cell에 추가
5. activate, can_activate 값 업데이트

상세코드는 다음과 같다.

전체 코드

"""
Author:
    Name: KyungHyun Lim
    Email: lkh1075@gmail.com
"""
from collections import defaultdict

def simulation(can_active, activate, K):
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]
    generate = defaultdict(list)
    dead_cell = defaultdict(list)
    for time in range(K + 1):
        new_can_active = defaultdict(list)
        # 이번 시간에 생성되는 세포 추가
        for cord, item in generate.items():
            put_time, life = item
            for d in range(4):
                nx, ny = cord[0] + dx[d], cord[1] + dy[d]
                if (nx, ny) not in can_active and (nx, ny) not in activate and (nx, ny) not in generate and (nx, ny) not in dead_cell: # 세포가 있는 자리가 아니면
                    if (nx, ny) in new_can_active:
                        life = max(life, new_can_active[(nx, ny)][1]) # 주변에 세포 생성
                        new_can_active[(nx, ny)] = [time, life]
                    else:
                        new_can_active[(nx, ny)] = [time, life]

            activate[cord] = item

        # 이번 시간에 활성화 되는 세포, 다음 타임에 생성하도록 추가
        generate = defaultdict(list)
        for cord, item in can_active.items():
            put_time, life = item
            if put_time + life == time: # 활성화됨, + 1 time에 생성
                generate[(cord)] = item
            else: # 활성화 되지 않으면 유지
                new_can_active[(cord)] = item

        new_active = defaultdict(list)
        # 죽음 처리
        for cord, item in activate.items():
            put_time, life = item
            if time < put_time + (life*2):
                new_active[cord] = item
            else:
                dead_cell[cord] = item

        activate = new_active
        can_active = new_can_active

        # print(f'T: {time}')
        # print(f'activated cell: {generate}')
        # print(f'deactivated cell: {can_active}')
        # print(f'alive cell: {activate}')
        # print(f'dead_cell: {dead_cell}')


    return len(activate) + len(can_active) + len(generate)

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # 세로크기, 가로크기, 시뮬레이션 시간
    N, M, K = list(map(int, input().split()))
    grid = [list(map(int, input().split())) for i in range(N)]

    activate = defaultdict(list)
    can_active = defaultdict(list)

    for i in range(N):
        for j in range(M):
            # [시작 시간, 수명]
            if grid[i][j] != 0: can_active[(i, j)] = [0, grid[i][j]]

    print(f'#{test_case} {simulation(can_active, activate, K)}')

요약: 원자들이 소멸되면서 방출하는 에너지의 총합을 구하는 프로그램을 작성

원자들이 좌표공간안에서 이동하고, 충돌 여부를 검사해야하는 문제이다.

원자들은 -1000 ~ 1000 사이의 좌표에 존재할 수 있다. 하지만 원자는 이동중에도 충돌할 수가 있다. 예를 들어

• A: (0, 0) 오른쪽 방향
• B: (1, 0) 왼쪽 방향

두 원자는 (0.5, 0) 지점에서 충돌할 수 있다. 만약 문제의 조건대로 1씩 원자를 움직인다면 이러한 충돌을 고려 할 수 없다. 즉 모든 공간을 트랙킹 하려고 하면 최소 4000 * 4000 만큼의 좌표 공간을 고려해야한다. 하지만 이것은 공간 복잡도를 매우 증가시킨다.

따라서 원자들의 위치를 관리할 아이디어가 필요하다.

가장 간단하게 사용할 수 있는 것이 python의 dictionary(map) 이다.

모든 원자가 서로 다른 위치에 있다고 한다고 해도, 제한이 1000개이기 때문에 1000개의 좌표만 관리하면 된다.

따라서 grid = defaultdict(list) 를 활용해서 좌표공간을 관리한다.

원자가 더이상 충돌할 수 없을 때 까지 1-3을 반복한다.

1. grid에 각 원자들을 배치한다.
2. grid의 정보를 토대로 동일한 좌표에 있는 원자들을 충돌시킨다. (에너지 sum)
3. 충돌하지 않은 원자들은 다시 리스트화한다.

이를 구현하면 아래와 같다.

전체 코드

"""
Author:
    Name: KyungHyun Lim
    Email: lkh1075@gmail.com
"""

from collections import defaultdict

# 원자 이동 가능 방향
# 상, 하, 좌, 우
dx = [0, 0, -0.5, 0.5]
dy = [0.5, -0.5, 0, 0]

N = 0 # 원자개수
energy = 0 # 에너지 총량

def move(atom_info, ):
    global dx, dy, N, energy

    while len(atom_info) > 1:
        grid = defaultdict(list)
        for atom in atom_info: # 원자 위치 표시
            x, y, d, k = atom
            grid[(x + dx[d], y + dy[d])].append([x + dx[d], y + dy[d], d, k])
        atom_info = []

        for cord, atoms in grid.items():
            if len(atoms) > 1: # 동일 위치에 있는 원자 제거
                for values in atoms:
                    energy += values[-1]
            else: # 범위 내 원자 정보 저장
                if -1000 <= cord[0] <= 1000 and -1000 <= cord[1] <= 1000:
                    atom_info += atoms

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N = int(input()) # 원자 개수 입력

    atom_info = []
    energy = 0
    for _ in range(N): # 원자 정보 입력
        # x, y, d(이동 방향), k(에너지)
        atom_info.append(list(map(int, input().split())))

    move(atom_info)
    print(f'#{test_case} {energy}')

요약: 경과된 시간이 주어질 때 탈주범이 위치할 수 있는 장소의 개수를 계산하는 프로그램을 작성하라.

복잡한 조건을 가지고 격자를 탐색할 수 있어야한다. 총 7 가지 모양의 파이프가 있고, 각 파이프마다 연결된 방향이 다르다. 따라서 이 각각의 파이프 모양과 조건을 간단하게 표현할 수 있어야 한다.

이를 pipes와 connected 두가지 변수를 이용해서 나타냈다. pipes는 해당 파이프 모양이 어떤 방향으로 연결되어있는지 나타낸다. connected는 탐색할 곳의 파이프와 현재 파이프가 연결될 수 있는 지를 나타낸다.

이 두 정보를 활용해서 도둑이 있을 수 있는 곳을 알아낼 수 있다.

기본적인 탐색방법은 BFS 알고리즘을 활용했다.

이것을 구현한 코드는 다음와 같다.

전체 코드

'''
Author:
    Name: KyungHyun Lim
    Email: lkh1075@gmail.com
'''
from collections import deque

# NxM 맵크기
# (R, C) 맨홀 뚜껑 위치
# L시간 후 가능한 위치
N, M, R, C, L = 0, 0, 0, 0, 0

grid = [[0] * 50 for _ in range(50)] # 맵정보
visited = [[0] * 50 for _ in range(50)] # 맵 탐색용
c = 0 # 탈주범이 있을 수 있는 곳 위치 개수

pipes = [ # 파이프별 이동 가능 방향
    [],
    [0, 1, 2, 3], # 1. 상하좌우
    [0, 1], # 2. 상하
    [2, 3], # 3. 좌우
    [0, 3], # 4. 상우
    [1, 3], # 5. 하우
    [1, 2], # 6. 하좌
    [0, 2], # 7. 상좌
]

# 0: 상, 1: 하, 2: 좌, 3: 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
connected = [
    [0, 1, 1, 0, 0, 1, 1, 0],
    [0, 1, 1, 0, 1, 0, 0, 1],
    [0, 1, 0, 1, 1, 1, 0, 0],
    [0, 1, 0, 1, 0, 0, 1, 1]    
]

def search(x, y):
    global grid, visited, pipes, connected, c, N, M, dx, dy
    q = deque()
    q.append((1, x, y))
    visited[x][y] = 1

    while q:
        l, cx, cy = q.popleft()
        kind = grid[cx][cy]
        visited[cx][cy] = 1

        if l >= L: continue # 시간 초가 지나면 못감

        for i in range(len(pipes[kind])):
            nx, ny = cx + dx[pipes[kind][i]], cy + dy[pipes[kind][i]]
            if nx < 0 or nx >= N or ny < 0 or ny >= M: continue # 격자 벗어난 경우
            if visited[nx][ny]: continue # 중복 방문인 경우
            if grid[nx][ny] == 0: continue # 파이프가 아닌 경우
            if connected[pipes[kind][i]][grid[nx][ny]] != 1: continue # 연결된 파이프가 아닌 경우

            q.append((l + 1, nx, ny))
            visited[nx][ny] = 1
            c += 1

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):

    N, M, R, C, L = list(map(int, input().split()))
    visited = [[0] * 50 for _ in range(50)] # 맵 탐색용
    for i in range(N):
        grid[i] = list(map(int, input().split()))

    c = 1
    search(R, C)

    print(f'#{test_case} {c}')

요약: 게임의 규칙대로 오토 플레이가 모두 끝났을 때 획득한 점수의 합을 구해보자.

2차원 배열을 탐색하고, 중력이라는 시스템으로 내부 값들을 이리저리 옮겨야 하는 전형적인 시물레이션 문제이다.

시물레이션 문제는 조건을 확실히 하는 것이 중요하다.

블록 그룹의 정의

- 인접한 블록의 집합 
  - 일반블록이 적어도 하나 필요
  - 일반 블록의 색은 모두 같아야함
  - 검은색 블록은 포함하면 안됨
  - 무지개 블록은 여러개 있을 수 있음
  - 총 블록수는 2 이상이어야함
- 그룹의 메인 블록
  - 무지개 블록이 아닌 블록
    - 1 순위 행의 번호가 가장 작은 블록
    - 2 순위 열의 번호가 가장 작은 블록

다음 중요한 포인트는 중력이 작용하는 방식이다.

중력 작용
- 검은색 블록을 제외, 모든 블록이 행의 번호가 큰칸으로 이동
- 다른 블록이나 격자의 경계를 만나기 전까지 계속 이동

게임의 순서는 다음과 같다.

1. 크기가 가장 큰 블록 그룹을 찾는다. (기준은 다음과 같음)
  - 블록 크기
  - 무지개 블록 수
  - 메인 블록 행이 가장 큰 것
  - 메인 블록 열이 가장 큰 것
2. 1에서 찾은 블록 그룹의 모든 블록(B개) 제거 (B^2의 점수 획득)
3. 격자에 중력 작용
4. 90도 반시계 방향 회전
5. 다시 격자에 중력이 작용

1. 크기가 가장 큰 그룹을 찾기 위해 BFS 알고리즘을 이용한다.
   • 탐색되지 않은 지점들을 시작으로, 전체 격자를 탐색
   • 가장 큰 그룹을 선택
   • 주의할점은 무지개 블록은 새로운 그룹 탐색전 재방문이 가능하도록 조건을 초기화 해주어야한다는 점이다.
2. 가장 큰 그룹에 속한 블럭들을 제거
3. 중력 적용, 회전, 다시 중력 적용
   • 특수한 알고리즘이 필요하기 보단, 조건에 맞추어 값을 이동시켜주면 된다.

이를 구현한 코드는 다음과 같다.

전체 코드

"""
Author:
    Name: KyungHyun Lim
    Email: lkh1075@gmail.com
"""

from collections import deque

def rotation(N, board):
    nemo_cnt = N // 2
    sx, sy, ex, ey = 0, 0, N-1, N-1
    length = N - 1
    for nemo in range(nemo_cnt):
        #print(sx, sy, ex, ey, length)

        backup = [board[sx][sy + i] for i in range(length)]
        for i in range(length): board[sx][sy + i] = board[sx + i][ey]
        for i in range(length): board[sx + i][ey] = board[ex][ey - i]
        for i in range(length): board[ex][ey - i] = board[ex - i][sy]
        for i in range(length): board[ex - i][sy] = backup[i]

        length -= 2
        sx, sy = sx + 1, sy + 1
        ex, ey = sx + length, sy + length

def apply_gravity(N, board):
    for i in range(N-2, -1, -1):
        for j in range(N):
            if board[i][j] != -1:
                tmp = i
                while tmp + 1 < N and board[tmp+1][j] == -5:
                    board[tmp+1][j] = board[tmp][j]
                    board[tmp][j] = -5
                    tmp += 1

def remove_block(board, block_info):
    for x, y in block_info['blocks']:
        board[x][y] = -5

def search(N, board, visited, x, y):
    dx, dy = [[0, 0, 1, -1], [-1, 1, 0, 0]]

    q = deque()
    q.append((x, y))

    color = board[x][y]

    blocks = [(x, y)]
    rainbows = []

    while q:
        cur_x, cur_y = q.popleft()

        for d in range(4):
            nx, ny = cur_x + dx[d], cur_y + dy[d]
            if 0 <= nx < N and 0 <= ny < N:
                # 방문한적 없고, 무지개 색이나 타겟 색일 경우
                if (not visited[nx][ny]) and (board[nx][ny] in [0, color]):
                    q.append((nx, ny))
                    visited[nx][ny] = True
                    # 그룹에 포함된 무지개색 블록 따로 저장
                    if board[nx][ny] == 0: 
                        rainbows.append((nx, ny))
                    else:
                        # 그룹에 포함된 일반 블록 저장
                        blocks.append((nx, ny))

    for x, y in rainbows:
        visited[x][y] = False

    return rainbows, blocks

def find_block(N, board):
    visited = [[False]*N for _ in range(N)]

    big_block = {
        "size": 0,
        "rainbow_size": 0,
        "main_col": 0,
        "main_row": 0,
        "blocks": []
    }
    for i in range(N):
        for j in range(N):
            # 그룹에 포함(방문하지) 않았고, 검은색 또는 무지개색이 아니면
            if (not visited[i][j]) and (board[i][j] not in [-1, 0, -5]):
                flag = False
                visited[i][j] = True
                rainbows, blocks = search(N, board, visited, i, j)

                rainbow_counts = len(rainbows)
                whole_counts = len(blocks) + rainbow_counts
                col, row = sorted(blocks)[0]

                if big_block['size'] < whole_counts:
                    flag = True
                elif big_block['size'] == whole_counts:
                    if big_block['rainbow_size'] < rainbow_counts:
                        flag = True
                    elif big_block['rainbow_size'] == rainbow_counts:
                        if big_block['main_col'] < col:
                            flag = True
                        elif big_block['main_col'] == col:
                            if big_block['main_row'] < row:
                                flag=True

                if flag:
                    big_block['size'] = whole_counts
                    big_block['rainbow_size'] = rainbow_counts
                    big_block['main_col'] = col
                    big_block['main_row'] = row
                    big_block['blocks'] = blocks + rainbows

    return big_block

def debug(board):
    for item in board:
        print(item)

def solution():
    # 격자 크기, 색상 개수
    answer = 0
    N, M = map(int, input().split())

    board = []
    for _ in range(N):
        board.append(list(map(int, input().split())))

    while True:
        block_info = find_block(N, board) # 큰 블록 찾기
        # print(block_info)
        # print('-'*100)

        if block_info['size'] <= 1: # 블록이 존재할때 까지 반복
            break
        answer += (block_info['size']**2)

        remove_block(board, block_info) # 블록 제거

        # debug(board)
        # print('-'*50)

        apply_gravity(N, board) # 중력 작용

        # debug(board)
        # print('-'*50)

        rotation(N, board) # 90도 반시계 회전S

        # debug(board)
        # print('-'*50)

        apply_gravity(N, board) # 중력 작용

        # debug(board)
        # print('-'*50)

    return answer

if __name__ == "__main__":
    answer = solution()
    print(answer)

    # gravity test
    # board = [
    #     [2, 1, 2, 3, 4],
    #     [2, 1, -5, -5, 4],
    #     [-5, -5, 2, 3, -5],
    #     [-5, -1, -5, -1, -1],
    #     [-5, -5, -5, -5, -5],
    # ]
    # apply_gravity(5, board)
    # debug(board)

요약: 규칙에 따라 학생들을 배치했을 때, 학생의 만족도의 총 합을 구해보자.

규칙에 맞추어 좌표를 잘 정렬해주는 것이 핵심이다.

학생을 배치하기 위한 규칙은 다음과 같다.

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리 정함
2. 1을 만족하는 칸이 여러개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리 정함
3. 2를 만족하는 칸이 여러개이면, 행의 번호가 가장 작은 칸으로, 그것도 많으면, 열의 번호가 가장 작은 칸으로 자리 정함

즉, 우선순위를 정리하면 다음과 같다. 우선순위: 좋아하는 학생이 많은칸 -> 비어있는 칸이 많은 칸 -> 행번호가 작은칸 -> 열번호가 작은칸

따라서, 학생 순서마다, 다음 과정을 반복해준다. 1. 각 칸의 정보 저장 (좋아하는 학생 수, 비어있는 칸수, 행번호, 열번호) 2. 정렬 3. 자리배치 4. 모든 학생이 앉을 때 까지, 1-3 반복

이를 구현하면 아래와 같다.

전체 코드

N, order, prefer, board = 0, [], {}, []
dx, dy = [[0, 0, 1, -1], [1, -1, 0, 0]]

def get_candidate(board, student):
    global N, prefer, dx, dy   

    seats = []
    for i in range(N):
        for j in range(N):
            vacn_count = 0
            pref_count = 0
            if board[i][j] == 0: # 빈자리 일때만
                for _ in range(4): # 4 방향 탐색
                    nx, ny = i + dx[_], j + dy[_]
                    if 0 <= nx < N and 0 <= ny < N: # 격자 안에서만 탐색
                        if board[nx][ny] == 0: vacn_count += 1 # 0이면 빈공간
                        if board[nx][ny] in prefer[student]: pref_count += 1 # 좋아하는 학생?

                seats.append((-pref_count, -vacn_count, i, j))

    return sorted(seats)

def debug(board):
    for item in board:
        print(item)

def solution():
    global N, order, prefer, board, dx, dy
    answer = 0
    score_dict = {0: 0, 1: 1, 2: 10, 3: 100, 4: 1000}

    N = int(input())

    for _ in range(N*N):
        infos = list(map(int, input().split()))
        prefer[infos[0]] = infos[1:]
        order.append(infos[0])

    board = [[0]*N for _ in range(N)]
    # 첫번째 학생은 무조건 (1, 1)위치에 앉게됨 (비어있는 칸수가 4개인 자리중 행,열이 가장 작은 곳)
    board[1][1] = order[0]

    # 1. 학생들을 차례대로 앉히기
    for i in order[1:]:
        # 각 자리에 대한 (좋아하는 학생 수, 비어있는 칸수, 행번호, 열번호) 정보 저장
        candidates = get_candidate(board, i)

        # 학생배치
        x, y = candidates[0][2], candidates[0][3]

        # print(f'배치완료! {i}: ({x}, {y})')
        # print(candidates)
        # debug(board)
        # print('-'* 100)

        board[x][y] = i

    # debug(board)

    # 2. 만족도 점수 계산하기
    for i in range(N):
        for j in range(N):
            student = board[i][j]
            pref_count = 0
            for _ in range(4):
                nx, ny = i + dx[_], j + dy[_]
                if 0 <= nx < N and 0 <= ny < N: # 격자 안에서만 탐색
                    if board[nx][ny] in prefer[student]:
                        pref_count += 1
            answer += (score_dict[pref_count])

    return answer

if __name__ == "__main__":
    answer = solution()
    print(answer)

https://www.youtube.com/watch?v=XepXtl9YKwc

1. 의미

• "Maximum likelihood를 찾았다" ?
  • 관측치에 대한 우도를 최대화 하는 평균 or 표준편차를 찾은것
• 데이터의 분포를 fit하기 위한 최적의 방법(분포)를 찾는 것

2. 예시

• Goal: 쥐의 몸무게들을 잘 표현하는 분포 찾기

• 어떤 분포가 가장 적합한지 탐색

  • 가장 간단한 정규분포로 가정

  • 평균 활용

    • 원: 쥐의 몸무게 데이터, 그래프: 가정할 분포

    • 

    • 1번, 3번 분포의 경우

      • 평균과 거리가 먼 오른쪽/왼쪽 데이터들의 likelihood는 낮게 평가됨
      • 

    • 2번 분포의 경우

      • 가정한 분포의 평균과 데이터의 평균이 일치
      • likelihood가 높게 평가됨
      • 

  • 표준편차 활용

    • 표준편차가 커질수록 분포가 퍼짐
    • 평균과 동일하게 표준편차에 따라 likelihood값이 달라짐
    • likelihood가 최대가 되는 표준편차를 선택
    • 

3. 딥러닝과의 관계

• 모델의 가중치 $\theta = (W^1,...,W^L)$
• 소프트맥스 벡터=카테고리분포의 모수 $(p_1,...,p_K)$ 를 모델링
• 정답 레이블 $y=(y_1,...,y_K)$ (원핫 인코딩)을 이용, 소프트맥스 벡터의 로그가능도를 최적화
• $\hat{\theta_{MLE}}=argmax_{\theta}({1 \over n} \sum_{i=1}^n \sum_{k=1}^K y_{i,k} log(MLP_\theta (x_i)_k))$
• 소프트맥스 벡터의 likelihood를 최적화
• Log likelihood를 사용하는 이유
  • 계산의 편의성
  • 추정한 분포와 데이터의 거리의 곱으로 가능도를 표현하기 때문에, 그 값의 크기를 줄일 수 있음

먼저 BertEncoder의 정의 부분을 살펴보면 config.num_hidden_layers에 정해진 만큼 BertLayer를 반복문으로 생성하는 것을 볼 수 있습니다. 즉 N개의 transformer 구조가 저 코드로 인해 생성되는 것입니다.

이제 부터는 저 N개의 층 중 하나인 BertLayer 속을 들여다 보겠습니다.

BertLayer는 크게 3개의 모듈로 구성되어있습니다.

• BertAttention
• BertIntermediate
• BertOutput

Transformer의 대표적인 그림으로 살펴보자면, 모듈들은 그림의 조각 부분을 각각 담당하고 있습니다.

BertAttention 모듈은 또 Multi-Head Attention을 계산해주는 모듈과 Add & Norm을 계산해주는 모듈로 나누어져 있습니다. 가장 핵심인 Attention 계산은 이 Multi-Head Attention 모듈 안에서 이루어집니다. 만약 Attention mechanism을 바꾸고 싶다면, 이 모듈을 불러와 수정을 하면 됩니다.

BertIntermediate 모듈은 그림에서 Feed Foward 부분을 담당하고 있습니다. 그래서 정의 부분을 살펴보면 간단하게 Linear layer 한개가 선언 되어있습니다.

def __init__(self, config):
    super().__init__()
    self.dense = nn.Linear(config.hidden_size, config.intermediate_size)
    if isinstance(config.hidden_act, str):
        self.intermediate_act_fn = ACT2FN[config.hidden_act]

ACT2FN은 active function을 의미합니다. 다음과 같이 config 파일에서 간단하게 키워드를 수정하는 것으로 다양한 active function을 사용할 수 있게 구현이 되어있습니다.

ACT2FN = {
    "gelu": GELUActivation(),
    "gelu_10": ClippedGELUActivation(-10, 10),
    "gelu_fast": FastGELUActivation(),
    "gelu_new": NewGELUActivation(),
    "gelu_python": GELUActivation(use_gelu_python=True),
    "linear": LinearActivation(),
    "mish": MishActivation(),
    "quick_gelu": QuickGELUActivation(),
    "relu": nn.ReLU(),
    "sigmoid": nn.Sigmoid(),
    "silu": SiLUActivation(),
    "swish": SiLUActivation(),
    "tanh": nn.Tanh(),
}

마지막으로 BertOuput은 Add & Norm 부분을 담당합니다. Feed Forward를 거쳐 오는 hidden_state와 residual 구조를 통해 넘어오는 input_tensor를 가지고, 다음 forward 함수와 같이 적용이되어 hidden states vector를 생산합니다.

def forward(self, hidden_states: torch.Tensor, input_tensor: torch.Tensor) -> torch.Tensor:
    hidden_states = self.dense(hidden_states)
    hidden_states = self.dropout(hidden_states)
    hidden_states = self.LayerNorm(hidden_states + input_tensor)
    return hidden_states

이과정을 N번 반복해 최종적으로 hidden states vector를 반환하게 됩니다.

요약: A음식과 B음식의 맛의 차이가 최소가 되도록 재료를 배분, 맛의 차이 최소값 구하기

1. 재료 고르기 (조합)

우선 음식 재료를 정하기 위해 N개의 재료 중 N/2개의 재료를 고르기 위한 알고리즘이 필요하다. 생각해보면 음식의 순서는 상관 없기 때문에 조합(combination)을 사용해야한다. iterationtools를 사용하면 간단하지만, 아무래도 이런 라이브러리는 활용할 수 없을 수도 있기 때문에 직접 조합을 생성하는 코드를 작성해 보았다.

def select(info, selected, N, r, idx, next):
    global min_val
    # 선택을 다 했으면
    if idx == r:
        nums = selected[:r]
        val = score(info, nums, N)
        min_val = min(min_val, val)
        return

    if next >= N: return

    selected[idx] = next
    # 현재 재료(next) 선택
    select(info, selected, N, r, idx + 1, next + 1)
    # 현재 재료(next) 값 미선택
    select(info, selected, N, r, idx, next + 1)

• info: 음식 시너지 정보가 담긴 배열
• selected: 선택된 음식
• N: 총 음식 재료 개수
• r: 선택해야할 음식 재료 개수
• idx: 고를 음식 순번
• next: 음식 재료 번호

위와 같은 파라미터들을 활용한다. 재귀를 이용해서 하나씩 선택을 해나아가는 알고리즘이다.

if idx == r 부분은 r개를 모두 선택했을 때, 이후 프로세스를 처리한다. 만약 아직 r개를 다 고르지 못했다면, 다음으로 넘어온다. 그리고 next가 재료의 번호 이기 때문에 N을 넘으면 더 이상 진행하지 않는다.

모든 종료조건을 통과했으면, selected[idx] = next 즉, 고를 순번(idx)에 음식 재료 번호(next)를 할당한다.

그리고 이 선택을 유지할려면 다음 순번을 고르기 위해 idx + 1, next + 1를 해주고, 해당 재료를 선택하지 않는다면 고르는 순번 증가 없이 재료만 다음 재료로 설정해준다. 그러면 자연스럽게 selected[idx] = next + 1이 되면서 해당 순번에 다음 재료가 선택이된다.

다시 돌아와서 r개를 모두 선택했을 때, 골라진 r개를 이용해 각 음식의 점수를 계산한다. 선택된 재료들(A의 음식재료)과 선택되지 못한 재료들(B의 음식재료)을 나누고, 반복문을 활용해 각 음식의 점수를 계산해준다. 두 음식 점수 차이에 절대값을 적용해 반환해준다.

def score(info, selected, N):
    A = 0
    B = 0

    not_selected = [i for i in range(N) if i not in selected]
    for i in range(N):
        if i in selected:
            for j in selected:
                A += info[i][j]
        else:
            for j in not_selected:
                B += info[i][j]
    # print(f'A: {selected}, B: {not_selected}')            
    # print(f'A: {A}, B: {B}')
    return abs(A-B)

점수 계산 후 해당 조합에서 min_val = min(min_val, val)을 이용해, global한 최소값을 업데이트 해준다.

즉, 모든 조합에 대해 점수를 계산해보고, 최소값을 업데이트 하게됨으로 두 음식의 점수 차이의 최소값을 구할 수 있게 된다.

전체코드

def score(info, selected, N):
    A = 0
    B = 0

    not_selected = [i for i in range(N) if i not in selected]
    for i in range(N):
        if i in selected:
            for j in selected:
                A += info[i][j]
        else:
            for j in not_selected:
                B += info[i][j]
    # print(f'A: {selected}, B: {not_selected}')            
    # print(f'A: {A}, B: {B}')
    return abs(A-B)


def select(info, selected, N, r, idx, next):
    global min_val
    # 선택을 다 했으면
    if idx == r:
        nums = selected[:r]
        val = score(info, nums, N)
        min_val = min(min_val, val)
        return

    if next >= N: return

    selected[idx] = next
    # 현재 재료(next) 선택
    select(info, selected, N, r, idx + 1, next + 1)
    # 현재 재료(next) 값 미선택
    select(info, selected, N, r, idx, next + 1)


T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # 재료개수 입력
    N = int(input())

    # 시너지 정보 입력
    info = [list(map(int, input().split())) for _ in range(N)]

    min_val = 999999999
    selected = [0] * N
    select(info, selected, N, N//2, 0, 0)
    print(f'#{test_case} {min_val}')

요약: 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.

간단하게 규칙에 맞추어 순차적으로 감독관을 배치하면 풀수있는 문제입니다.

우선 시험장마다 총감독관은 1명 필수로 있으므로, answer +=1을 적용해준다.

다음으로, 총감독관이 감시할 수 있는 응시자 수(B)가 시험장에 있는 학생의 수(A)보다 작을 경우, 그 차이만큼 학생을 감독할 수 있는 부감독관(C)을 배치해야한다.

따라서 (A-B) % C의 값에 따라 부감독관을 배치한다. 만약 남은 학생수가 부감독관이 감독할 수 있는 학생수의 약수이면, 몫만큼 부감독관을 배치하면 된다.

딱 나누어 떨어지지 않는 다면, 부감독관을 몫+1만큼 배치해야한다.

이를 구현하면 아래와 같다.

전체 코드

def solution():
    N = int(input())
    students = list(map(int, input().split()))
    B, C = map(int, input().split())

    answer = 0
    for A in students:
        answer += 1
        if A > B:
            if (A - B) % C == 0: answer += (A - B) // C
            else: answer += (((A - B) // C) + 1)

    return answer

def main():
    answer = solution()
    print(answer)

if __name__ == '__main__':
    main()

요약: 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

0. 입력 받기

   customers = []
   for _ in range(N):
    customers.append(list(map(int, input().split())))

customers라는 배열을 선언하고, [고객상담에 걸리는 일수, 얻을 수 있는 보상] 정보를 저장합니다.

1. dfs를 활용한 완전 탐색 방법

고객 상담을 할지 않할지 분기를 이용해 재귀적으로 풀어보았습니다.

if idx >= len(customers):
    global_max = max(sum, global_max)
    return

종료조건은 다음과 같습니다. 매일같이 받을 수 있는 고객이 있기 때문에, 고객의 길이는 퇴사하려는 날짜와 동일합니다. 따라서, 현재 날짜(idx)가 퇴사일(len(customers))을 넘어간다면 현재 날짜의 고객은 선택할 수 없습니다. 즉, 현재 case의 pay(sum)와 지금까지 max값(global_max)을 비교해 갱신해 줍니다.

# 고객 상담
if idx + customers[idx][0] <= N:
    dfs_choose_schadule(N, customers, idx + customers[idx][0], sum + customers[idx][1])
# 고객 상담 x
dfs_choose_schadule(N, customers, idx + 1, sum)

만약 상담이 가능하다면, 그 고객을 상담할 것인지 아닌지로 분기를 나누어줍니다. 고객을 상담한다면, 현재일에서 해당 고객을 상담하는데 걸리는 일 수가 퇴사일을 넘으면 안됩니다. 조건문을 통해, 퇴사일을 넘지 않을 때만 상담하는 분기로 넘어 갑니다. 그렇지 못한경우에는 고객을 상담하지 않고 넘어 갑니다.

재귀문이 끝난 경우 모든 경우의 수를 탐색해 가장 높게 받을 수 있는 pay가 global_max에 저장됩니다.

2. Dp를 활용한 탐색 방법

Dynamic programming을 활용한 경우 다음과 같이 풀이가 가능합니다.

# 해당 일자(index)에 최대로 받을 수 있는 금액
dp = [0] * (N + 1)

우선 Dp 배열을 위와 같이 정의합니다. (처음엔 모두 0) 그리고 max_money라는 변수를 활용해 다음과 같이 풀이가 가능합니다.

• Dp[1]은 아직일을 하지 않았기 때문에 수입이 없어 0입니다. 그리고 만약 일을 수행한다면 3일 후인 Dp[1+3]에 10이라는 보상을 얻게 됩니다.
• Dp[2]도 마찬가지로 얻는 수입은 없습니다. 그리고 해당 일을 수행했을 때 5일 후인 Dp[2+5]에 20이라는 보수를 얻습니다.
• Dp[3]도 마찬가지 수입은 0입니다. 그리고 일을 하게되면 1일 후에 10이라는 보상을 얻습니다.
• Dp[4]는 Dp[1]에서 일을 수행했기 때문에 최대로 얻을 수 있는 보상은 10입니다. 따라서 현재까지 가장 많이 얻을 수 있는 수입이 10임으로, max_money는 10이 됩니다. 그리고 일을 수행했다면, 1일 후인 Dp[4+1]에 30(현재최대보상 10 + 일한 보수 20)이라는 보상을 업을 수 있습니다.
• Dp[5]는 현재 최대 30의 보수를 얻을 수 있습니다. 동일하게 max_money는 업데이트됩니다. 그리고 일을 수행하면 Dp[5+2]에 30 + 15로 45라는 보수를 얻을 수 있습니다.
• Dp[6]에서는 해당일을 수행하는 것은 불가능합니다. Dp[6]은 0이지만, 이전 일수 까지 최대값이 30이었기 때문에 6일차도 누적 30이라는 최대의 보수를 획득할 수 있습니다. 따라서 Dp[6] = 30이 됩니다.
• Dp[7]에서는 45라는 보수를 얻을 수 있습니다. 따라서 max_money가 45로 업데이트됩니다. 그리고 해당일차의 일은 수행할 수 없습니다.

결과적으로 45가 최대로 얻을 수 있는 보수가 됩니다.

이것을 구현하면 다음과 같습니다.

 max_money = 0
 for idx in range(N + 1):
     dp[idx] = max(max_money, dp[idx])
    # idx번째 업무 + 걸리는 일수
    next = idx + customers[idx][0]
    if (next < N + 1): # 퇴사일을 넘어가지 않으면  
        dp[next] = max(dp[next], customers[idx][1] + dp[idx])
    max_money = max(max_money, dp[idx])

전체 코드는 다음과 같습니다. chatGPT를 이용해 최적화도 한번 해보았습니다.

global_max = 0

def dfs_choose_schadule(N, customers, idx, sum):
    global global_max

    if idx >= len(customers):
        global_max = max(sum, global_max)
        return

    # 고객 상담
    if idx + customers[idx][0] <= N:
        dfs_choose_schadule(N, customers, idx + customers[idx][0], sum + customers[idx][1])
    # 고객 상담 x
    dfs_choose_schadule(N, customers, idx + 1, sum)

def dp_choose_schedule(dp, N, customers):
    max_money = 0
    for idx in range(N + 1):
        #
        dp[idx] = max(max_money, dp[idx])

        # idx번째 업무 + 걸리는 일수
        next = idx + customers[idx][0]
        if (next < N + 1): # 퇴사일을 넘어가지 않으면  
            dp[next] = max(dp[next], customers[idx][1] + dp[idx])
        max_money = max(max_money, dp[idx])    
    return max_money

# chatGPT 최적화
def caht_dp_choose_schedule(customers):
    dp = [0] * (len(customers))
    max_money = 0
    for idx, (duration, reward) in enumerate(customers):
        max_money = max(max_money, dp[idx])
        next = idx + duration
        if next < len(customers):
            dp[next] = max(dp[next], reward + max_money)
    return max_money

def solution():
    global global_max
    N = int(input())

    customers = []
    for _ in range(N):
        customers.append(list(map(int, input().split())))

    dfs_choose_schadule(N, customers, 0, 0)

    customers.append([0, 0])
    # 해당 일자(index)에 최대로 받을 수 있는 금액
    dp = [0] * (N + 20)
    max_money = dp_choose_schedule(dp, N, customers)

    chat_max_money = caht_dp_choose_schedule(customers)

    return global_max, max_money, chat_max_money

if __name__ == "__main__":
    answer = solution()
    print(answer)

하지만 기본 구조를 가지고 있는 것이기 때문에, 내가 직면한 태스크를 보다 잘 수행하기 위해서는 내부구조를 잘 알고 수정할 수 있어야 한다. 단순히 "from_pretrained("모델명")" 으로 불러다가만 쓰기에는 태스크의 성능을 끌어올리기 매우매우 어려울 수 있다.

자연어 처리 태스크에는 여러가지가 있지만, Huggingface는 대부분 모델들이 유사한 구조로 구현이 되어있기 때문에 하나의 모델만 잘 분석해봐도 다른 모델의 구조를 파악하는 것이 쉬워진다.

그래서 문장 분류 태스크를 수행하기 위해 사용하는 BertForSequenceClassification 클래스를 한번 뜯어보려고 한다.

모델구조(BertEmbedding) 살펴보기

아래 그림은 BertForSequenceClassification을 구조화해 둔것이다.

그림을 살펴보면 가장 윗단에서 BertModel과 Classifier로 나뉘게 된다. BertModel이 Transformer layer가 여러겹으로 쌓여있는 본체이다. Classifier는 태스크에 따라 달라질 수 있는 task-specific한 부분이라고 생각하면 된다.

BertModel을 조금더 살펴보면, BertEmbedding과 BertEncoder 부분으로 나누어진다. BertEmbedding은 문장을 입력으로 받아 다음 3개의 임베딩 값을 만들고, 더해서 반환해주는 역할을 한다.

• token embedding (각 토큰들의 임베딩)
• segment embedding (문장이 2개일 경우, 첫번째 문장은 0, 두번째 문장으 1)
• position embedding (토큰의 위치에 따른 임베딩)

실제로 구현부를 살펴보면, 3개의 임베딩 레이어를 가지고 있는 것을 볼 수 있다. 그리고 forward 부분에서 3개의 임베딩 벡터를 더해서 반환해주는 것도 확인 할 수 있다.

self.word_embeddings = nn.Embedding(config.vocab_size, config.hidden_size, padding_idx=config.pad_token_id)
self.position_embeddings = nn.Embedding(config.max_position_embeddings, config.hidden_size)
self.token_type_embeddings = nn.Embedding(config.type_vocab_size, config.hidden_size)

# ...생략... #

embeddings = inputs_embeds + token_type_embeddings
if self.position_embedding_type == "absolute":
    position_embeddings = self.position_embeddings(position_ids)
    embeddings += position_embeddings

수정 및 활용해보기

이제 BertEmbedding의 구조를 파악했으니, 수정도 할 수 있다. 아래처럼 새로운 임베딩 레이어를 정의하는 것으로 쉽게 레이어를 추가할 수 있다.

self.new_embeddings = nn.Embedding(#유니크값 개수#, #임베딩벡터 차원크기#, padding_idx=config.pad_token_id)

forward에서도 아래와 같이 기존 임베딩 벡터에 더해주는 방식으로 활용할 수도 있다. 물론 더해주지 않고 평균을 낼수도 있고, 활용방법은 한번 고민해보면 좋을 것 같다.

new_embeddings = self.new_embeddings(new_input)
embeddings = inputs_embeds + token_type_embeddings + new_embeddings
if self.position_embedding_type == "absolute":
    position_embeddings = self.position_embeddings(position_ids)
    embeddings += position_embeddings

하나의 예시로서, Relation Extraction(RE)이라는 태스크가 있다. 문장이 주어지고, 문장안에서 두개의 엔티티가 주어졌을 때, 두 엔티티 사이의 관계를 예측하는 태스크이다.

• 손흥민의 아버지는 손웅정이다.
• 손흥민 - 손웅정 : 부모관계

RE 데이터셋의 경우 손흥민, 손웅정에게 "사람"이라는 타입이 주어진 데이터셋이 있다고 했을때, 타입에 대한 임베딩 레이어를 만들어 "손흥민" 토큰과 "손웅정" 토큰에 "사람"이라는 임베딩 벡터 값을 더해주어 정보를 추가해줄 수도 있다. (실제로 RE 태스크 논문들에서 많이 활용하고 있다.)

이런식으로 문장을 가지고만 판단을 하던 언어모델에 추가적인 정보를 주는 방식으로 Embedding layer를 수정하고 학습시키는 것이 가능하다.

다음에는 본체인 BertEncoder의 구조를 살펴보자!