그냥 코딩하는 사람의 블로그

https://www.acmicpc.net/problem/17073

풀이 과정

1. 전반적인 과정은 BFS로 진행
   1. 루트 노드(1)부터 시작한다.
   2. 현재 노드에서 연결된 자식 노드 수만큼 물을 나누어서 배분시켜 준다.
   3. 나누어준 자식 노드로 이동하여서 다음 자식노드에게 물을 나누어준다.
   4. 2-3 과정을 반복한다.
2. 이 때, 자식노드가 존재하여 자식노드에게 물을 나누어준 경우에는 비교를 위해 값을 0으로 설정한다. 소숫점 비교는 잘 되지 않음.
3. BFS가 종료되면, 물의 양의 합계 / 물의 양이 0이 아닌 노드의 갯수 를 출력시켜 준다.

소스 코드

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()
N, W = map(int, input().split())
t = [[] for _ in range(N+1)]
v = [0] * (N+1)
v[1] = W

for _ in range(N-1):
    a, b = map(int, input().split())
    t[a].append(b)
    t[b].append(a)

visited = set()
visited.add(1)
queue = deque([1])

while queue:
    node = queue.popleft()
    count = 0
    for nx in t[node]:
        if nx not in visited:
            count += 1

    if count == 0:
        continue

    each_value = v[node] / count
    for nx in t[node]:
        if nx not in visited:
            v[nx] = each_value
            visited.add(nx)
            queue.append(nx)
    v[node] = 0

count = 0
for i in range(1, N+1):
    if v[i] != 0:
        count += 1

print(sum(v) / count)

https://www.acmicpc.net/problem/2250

풀이 과정

1. 루트 노드가 무조건 1번인건 아니기 때문에 루트 노드의 번호를 구한다.
   1. 1번부터 N번까지 노드를 Set에 저장시켜 둔 다음, 입력되는 노드의 오른쪽 자식이거나 왼쪽 자식인 경우, Set에서 빼준다.
   2. Set에 노드가 한개 남게 되면, 그게 루트 노드이다. 
2. 각각의 노드가 위치하는 열을 구한다. 
   
   1. 그 전에, 각각의 노드의 자식 노드 수를 구해준다.
   2. 현재 노드의 위치는 범위가 (left, right)일 때, left + 왼쪽 자식 노드 수 + 1이라고 볼 수 있다.
   3. 현재 노드의 위치를 구해준 다음, 왼쪽 자식 노드에 대해서는 (left, 현재 노드의 위치 - 1), 오른쪽 자식 노드에 대해서는 (현재 노드의 위치+1, right) 범위만큼 recursion으로 진행한다.
3. 열을 구해준다면, 이제 루트 노드에서 시작해서 BFS를 진행한다.
   1. 각각의 레벨에 열 정보들을 모두 저장시켜 둔다.
4. 저장해둔 레벨별 열 정보들을 오름차순으로 정렬시켜 준다.
   1. 맨 마지막 인덱스가 최댓값, 맨 앞 인덱스가 최솟값이므로 최댓값 - 최솟값을 구해준다.
   2. 최댓값-최솟값이 현재 정답보다 크다면, 현재 정답과 인덱스를 저장시켜 둔다.

소스 코드

import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()
N = int(input())
left_child = [-1] * (N+1)
right_child = [-1] * (N+1)
p = set([i for i in range(1, N+1)])

for i in range(N):
    a, b, c = map(int, input().split())
    left_child[a] = b
    right_child[a] = c
    if b in p:
        p.remove(b)
    if c in p:
        p.remove(c)

root_node = list(p)[0]
child_count = [-1] * (N+1)
pos = [0] * (N+1)

def get_chk_child(p):
    count = 0
    if left_child[p] != -1:
        count += get_chk_child(left_child[p])
    if right_child[p] != -1:
        count += get_chk_child(right_child[p])
    child_count[p] = count + 1
    return count + 1

def allow_number(p, left, right):
    pos[p] = left

    if left == right:
        pos[p] = left
        return
    
    if left_child[p] != -1:
        pos[p] = left+child_count[left_child[p]]

    if left_child[p] != -1:
        allow_number(left_child[p], left, pos[p]-1)

    if right_child[p] != -1:
        allow_number(right_child[p], pos[p]+1, right)

get_chk_child(root_node)
allow_number(root_node, 1, N)
step = [[] for _ in range(10001)]
queue = deque([[root_node, 0]])
while queue:
    nx, s = queue.popleft()
    step[s].append(pos[nx])
    if left_child[nx] != -1:
        queue.append([left_child[nx], s+1])
    if right_child[nx] != -1:
        queue.append([right_child[nx], s+1])

level = 1
answer = 1
for i in range(10001):
    step[i].sort()
    if len(step[i]) > 1:
        if answer < step[i][-1] - step[i][0] + 1:
            answer = step[i][-1] - step[i][0] + 1
            level = i+1

print(level, answer)

https://www.acmicpc.net/problem/16397

풀이 과정

1. 초기 현재 값과 단계를 큐에 넣은 다음, BFS를 진행한다.
   1. 다음 단계의 값에 일단 i+1을 넣어준다. -> 버튼 A
   2. 버튼 B를 구현할 때, 현재 단계의 값이 0이거나 입력받은 값을 2배한 값이 99999보다 크다면 버튼 B를 누를 수 없는 것이므로 버튼 A를 누른 결과만 진행한다.
   3. 아니라면, 2를 곱한 값의 가장 앞자리의 숫자를 하나 줄여주어야 하므로 1 * 10^(전체 자릿수-1)를 빼준다.
      • 예를 들면, 4자리라면 1000을 빼준다. 
2. 큐가 비게 되거나, 단계가 T를 넘어가게 되면 "ANG"를 출력해 주고, 목표한 값에 도달한다면 현재 단계를 출력시켜 준다.

소스 코드

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()

N, T, G = map(int, input().split())
queue = deque()
queue.append([N, 0])

def get_next_number(i):
    temp = i * 2
    if i == 0 or temp > 99999:
        return [i+1]
    index = 1
    while temp//10 != 0:
        temp //= 10
        index *= 10
    
    return [i+1, i * 2 - index]

visited = set()
visited.add(N)

while queue:
    target, step = queue.popleft()
    if step == T+1:
        print("ANG")
        break
    if target == G:
        print(step)
        break
    for nx in get_next_number(target):
        if nx not in visited:
            queue.append([nx, step+1])
            visited.add(nx)
else:
    print("ANG")

https://www.acmicpc.net/problem/2872

풀이 과정

1. 맨 오른쪽에서부터 왼쪽으로 진행하면서 N을 찾는다.
2. N이 아니라면 옮겨야 되는 값이므로 횟수를 하나 증가시킨다.
3. N이라면 찾아야 하는 값을 N-1로 줄여서 현재 위치에서부터 찾는다.
4. 2-3을 맨 왼쪽까지 반복한다.

- 위 과정을 반복하면 찾아야 하는 값 기준으로 왼쪽에서 보았을 때 증가하는 수열이 나온다.(맨 마지막 값이 N)

- 또한, 옮겨야 되는 값들은 큰것부터 작은것 순으로 맞추어서 앞에 넣어주기만 하면 되기 때문에 결국 (2)에서 구한 횟수를 그대로 리턴해주면 된다. 

- 생각보다 잘 안풀리는 문제였음

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
N = int(input())
books = [int(input()) for _ in range(N)]

find_target = N
answer = 0
for i in range(N-1, -1, -1):
    if books[i] != find_target:
        answer += 1
    else:
        find_target -= 1

print(answer)

https://www.acmicpc.net/problem/10812

풀이 과정

1. 파이썬의 슬라이싱 기능을 이용하면 쉽게 풀 수 있는 문제이다.
2. 리스트에 1~10까지 원소를 넣어둔 다음 입력받은 바구니 순서에 맞추어서 슬라이싱 해준다.
   • i, j, k가 입력되면 ~i, j~k까지, i~k까지, j~에 맞추어서 슬라이싱 해준다.
3. 최종 슬라이싱 된 리스트를 출력시켜 준다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
buckets = [i for i in range(1, N+1)]

for _ in range(M):
    i, j, k = map(int, input().split())
    i, j, k = i-1, j-1, k-1
    buckets = buckets[:i] + buckets[k:j+1] + buckets[i:k] + buckets[j+1:]
    
print(*buckets)

https://www.acmicpc.net/problem/3055

풀이 과정

1. 고슴도치와 물의 위치를 저장해 둔다.
2. 단계를 두개로 나누어서 진행한다. 고슴도치가 다음 시간에 물이 찰 예정인 칸으로는 이동할 수 없으므로, 물을 먼저 확산시킨 다음 고슴도치를 이동하는 단계를 거친다.
   1. 물이 퍼지는 단계
   2. 고슴도치가 이동하는 단계
3. BFS 코드를 작성하는데, 고슴도치가 이동하는 횟수를 저장하고, 횟수가 변경될때마다 물을 한번씩 확산시키는 과정을 거친다. 이 때, 물을 확산시키고 나서 확산시킨 위치는 따로 가지고 있어야 다음에 물을 확산시킬 때 위치를 찾을필요 없이 바로 확산시킬 수 있다.
4. 고슴도치가 비버의 굴에 도착하게 되면, 이동시킨 횟수를 출력시켜준다. 도착하지 못하게 되면(큐가 비게되면) KAKTUS를 출력시켜 준다.

소스 코드

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()
R, C = map(int, input().split())
matrix = [list(input()) for _ in range(R)]

water_pos = deque()
visited_biber = set()
biber = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

for i in range(R):
    for j in range(C):
        if matrix[i][j] == '*':
            water_pos.append([i, j])
        if matrix[i][j] == 'S':
            visited_biber.add((i, j))
            biber.append([i, j, 0])
            
def flood():
    global R, C, water_pos
    next_deque = deque()
    while water_pos:
        x, y = water_pos.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < R and 0 <= ny and ny < C and \
               matrix[nx][ny] not in ['X', 'D', '*']:
                next_deque.append([nx, ny])
                matrix[nx][ny] = '*'
    water_pos = next_deque

step = -1
while biber:
    x, y, current_step = biber.popleft()
    if matrix[x][y] == '*':
        continue
    if matrix[x][y] == 'D':
        print(current_step)
        break
    
    if current_step != step:
        step = current_step
        flood()

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx and nx < R and 0 <= ny and ny < C:
            if matrix[nx][ny] != '*' and matrix[nx][ny] != 'X' and \
               (nx, ny) not in visited_biber:
                visited_biber.add((nx, ny))
                biber.append([nx, ny, current_step+1])
else:
    print('KAKTUS')

https://www.acmicpc.net/problem/1449

풀이 과정

그냥 풀게 되면 소수점 처리가 조금 난해하므로, 10을 곱해주어 정수로 풀이하는게 더 좋음.

1. 파이프를 오름차순으로 정렬한다.
2. 맨 왼쪽 파이프부터 순차적으로 파이프에 테이프를 붙인다.
   1. 현재 파이프 위치 - 5~ 현재 파이프 위치 + 5에 테이프가 붙어져있는지 확인
      • 확인할 때, set에 해당 위치가 있는지 확인하는 방식으로 진행
   2. 전체가 붙어져있다면 다음 파이프 위치로 넘어간다.
   3. 전체가 붙여져있지 않다면 안붙여진 부분중 가장 왼쪽 위치에다가 테이프를 붙여주어야 한다.
      • 테이프를 붙여줄 때, 붙이는 위치~붙이는 위치 + 10 * L를 Set에 넣어준다.
      • 테이프를 붙인 다음, 테이프 카운트를 하나 늘려준다.
3. 붙인 테이프 개수를 출력한다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
N, L = map(int, input().split())

water = list(map(lambda x:int(x)*10, input().split()))
water.sort()
tape = set()
tape_count = 0
for pos in water:
    start = 0
    for i in range(-5, 6):
        if pos+i not in tape:
            start = pos+i
            break
    else:
        continue

    for p in range(start, start+(10*L)+1):
        tape.add(p)
    tape_count += 1

print(tape_count)

https://www.acmicpc.net/problem/7662

풀이 과정

1. 최소히프, 최대히프를 만들어 두고, 실제 데이터 개수를 체크할 딕셔너리를 하나 만들어 둔다.
2. 데이터 삽입
   1. 데이터를 최소히프, 최대히프에 모두 삽입
   2. 딕셔너리 내 해당 데이터 개수를 1개 증가시켜 준다.
3. 데이터 삭제
   1. 최소값을 뽑아야 하면 최소히프에서 빼준다.
   2. 최댓값을 뽑아야 하면 최대히프에서 빼준다.
   3. 단, (1), (2) 과정에서 뽑은 데이터에 대응되는 데이터 개수가 0개인 경우에는 이미 다른 히프에서 빼준 것이므로, 다시 빼주어야 한다.
4. 마지막에 큐가 비어있다면 Empty를, 비어있지 않다면 최댓값, 최솟값을 출력한다.
   
   1. 각각 최대히프, 최소히프에서 빼주고, 만약 빼줄 데이터가 없는 경우에는 Empty를 출력시켜주면 된다.

소스 코드

import heapq
import sys
from collections import defaultdict

input = lambda: sys.stdin.readline().rstrip()

T = int(input())
for _ in range(T): 
    min_heap = []
    max_heap = []
    element_dict = defaultdict(lambda: 0)
    K = int(input())
    for __ in range(K):
        cmd, data = input().split()
        data = int(data)
        if cmd == 'I':
            heapq.heappush(min_heap, data)
            heapq.heappush(max_heap, -data)
            element_dict[data] += 1
        if cmd == 'D':
            if data == -1:
                while min_heap:
                    r = heapq.heappop(min_heap)
                    if element_dict[r] > 0:
                        element_dict[r] -= 1
                        break
            else:
                while max_heap:
                    r = heapq.heappop(max_heap)
                    r = -r
                    if element_dict[r] > 0:
                        element_dict[r] -= 1
                        break
    min_value = None
    max_value = None
    while min_heap:
        r = heapq.heappop(min_heap)
        if element_dict[r] > 0:
            min_value = r
            break
            
    while max_heap:
        r = heapq.heappop(max_heap)
        r = -r
        if element_dict[r] > 0:
            max_value = r
            break
    if min_value == None:
        print('EMPTY')
    else:
        print(max_value, min_value)

https://www.acmicpc.net/problem/1202

풀이 과정

1. 그냥 진행하면 가방도 최대 30만개고, 보석도 최대 30만개이므로 시간초과가 나타나므로 최대 히프로 풀이한다.
2. 우선 보석을 무게 순으로 최소 히프에 넣어주고, 가방은 오름차순으로 정렬시켜 준다.
3. 가장 가벼운 가방에서부터 순차적으로 루프를 돈다.
   1. 현재 가방에 넣을 수 있는 보석들을 최소 히프에서 하나씩 꺼내면서 보석의 가격 순으로 최대 히프에 넣어준다.
   2. 넣어주는 작업이 끝나면, 최대 히프에서 값을 하나 꺼내서 더해준다. 가벼운 가방에서 무거운 가방 순서로 진행하므로 다음 가방에는 무조건 넣을 수 있는 보석이기 때문에 무게는 같이 저장할 필요가 없음. 최대 히프에서 꺼낸 값이 현재 가방에 넣어줄 보석의 가격이다.
4. 보석 가격의 합을 출력시켜 준다.

소스 코드

import sys
import heapq

input = lambda: sys.stdin.readline().rstrip()
N, K = map(int, input().split())
jewel = []

for _ in range(N):
    M, V = map(int, input().split())
    heapq.heappush(jewel, [M, V])

backpack = [int(input()) for _ in range(K)]
backpack.sort()

jewel_value_heap = []
answer = 0
for b in backpack:
    # 현재 가방에서 가능한 보석 값들 최대 히프에 넣어줌
    while jewel and jewel[0][0] <= b:
        heapq.heappush(jewel_value_heap, -heapq.heappop(jewel)[1])

    # 최대 히프에서 값 하나 꺼내서 더해줌(현재 가방에 들어갈 보석)
    if jewel_value_heap:
        answer -= (heapq.heappop(jewel_value_heap))

print(answer)

https://www.acmicpc.net/problem/3085

풀이 과정

1. 왼쪽 위에서 오른쪽 아래로 진행하면서 오른쪽으로 인접한 사탕, 아래로 인접한 사탕을 바꿔본 다음 가장 긴 연속 부분을 구한다. 구한 다음에는 다시 한번 더 바꿔서 원래 위치로 맞추어 준다.
2. 가장 긴 연속 부분을 구할 때는, 행별, 열별로 따로 i번째 요소와 i-1번째 요소가 같다면 개수를 1 증가시키고, 같지 않다면 개수를 1로 설정한다. 또한 개수를 변경할 때마다 최대 길이를 갱신시켜 준다.
3. (1)-(2)의 결괏값중 최댓값을 구해서 출력시켜 준다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
n = int(input())

board = [list(input()) for _ in range(n)]

def get_max_candy(board):
    value = 0
    for i in range(n):
        row_v = 1
        col_v = 1
        for j in range(1, n):
            if board[i][j] == board[i][j-1]:
                row_v += 1
            else:
                row_v = 1

            if board[j][i] == board[j-1][i]:
                col_v += 1
            else:
                col_v = 1
            
            value = max(value, row_v, col_v)

    return value


answer = 0
for i in range(n):
    for j in range(n):
        if i+1 < n:
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
            answer = max(answer, get_max_candy(board))
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
        if j+1 < n:
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
            answer = max(answer, get_max_candy(board))
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]

print(answer)