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

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

풀이 과정

1. 입력된 뉴런 a와 b가 같은 집합 내에 속해있는지 검사한다.
   1. 같은 집합 내에 속해있지 않다면 Union
   2. 같은 집합 내에 속해있다면 해당 뉴런은 끊어내야 하는 뉴런이므로 연산 횟수를 하나 증가시킨다.
2. 모든 뉴런들에 대해 같은 집합에 속해있는지 검사한다.
   1. 다른 집합에 속해있다면, 두 집합을 Union 해주고 연산 횟수를 하나 증가시킨다.
3. 연산 횟수를 출력시켜준다.

소스 코드

import sys

sys.setrecursionlimit(10**6)

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

parent = [i for i in range(N+1)]

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
        
    return parent[a]

def union(parent, a, b):
    p1 = find(parent, a)
    p2 = find(parent, b)
    if p1 != p2:
        parent[p1] = p2

answer = 0

for _ in range(M):
    a, b = map(int, input().split())
    if find(parent, a) != find(parent, b):
        union(parent, a, b)
    else:
        answer += 1

parent_node = find(parent, 1)
idx = 1
for i in range(2, N+1):
    if find(parent, i) != parent_node:
        union(parent, i, idx)
        parent_node = find(parent, i)
        idx = i
        answer += 1

print(answer)

https://programmers.co.kr/learn/courses/30/lessons/12971

풀이 과정

1. 원형으로 연결되어 있으므로 첫번째 스티커를 선택하는지 선택하지 않는지에 따라 달라진다.
   1. 첫번째 스티커를 선택하는 경우, 마지막 스티커는 선택하지 않아야 함
   2. 첫번째 스티커를 선택하지 않는 경우, 마지막 스티커를 선택할 수도 있음
2. 첫번째를 선택하거나 선택하지 않은 각각의 경우에 따라 dp테이블을 구성해 준다.
3. 점화식은 다음과 같다.
   1. DP[i][0] = max(DP[i-1][0], DP[i-1][1])
   2. DP[i][1] = DP[i-1][0] + i번째 스티커
4. 첫번째 스티커를 선택한 경우는 마지막 스티커를 선택할 수 없으므로 DP[n-2]에서의 최댓값을, 첫번째 스티커를 선택하지 않은 경우는 마지막 스티커를 선택 가능하므로 DP[n-1]에서의 최댓값을 구해주면 된다.

소스 코드

def solution(sticker):
    answer = 0
    dp = [[0] * 2 for _ in range(len(sticker))]
    
    if len(sticker) == 1:
        return sticker[0]
    
    # 첫번째 선택
    dp[0][0], dp[0][1] = 0, sticker[0]
    dp[1][0], dp[1][1] = sticker[0], 0
    for i in range(2, len(sticker)):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        dp[i][1] = dp[i-1][0] + sticker[i]
    answer = max(answer, max(dp[len(sticker)-2]))
    
    # 첫번째 선택하지 않은 경우
    dp[0][0], dp[0][1] = 0, 0
    dp[1][0], dp[1][1] = 0, sticker[1]
    for i in range(2, len(sticker)):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        dp[i][1] = dp[i-1][0] + sticker[i]
    answer = max(answer, max(dp[len(sticker)-1]))
    
    return answer

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

풀이 과정

1. Tree를 먼저 중위순회 해보고 마지막에 방문하는 정점이 어디인지 파악한다.
2. 전체 간선의 개수의 두배에서 마지막에 방문하는 정점을 방문하기 위해 지나온 간선의 개수를 빼주어서 출력

소스 코드

import sys

sys.setrecursionlimit(10**6)

input = lambda: sys.stdin.readline().rstrip()
left = dict()
right = dict()

N = int(input())
parent = [0] * (N+1)
node_count = 0
for _ in range(N):
    a, b, c = map(int, input().split())
    left[a] = b
    right[a] = c

    if b != -1:
        parent[b] = a
        node_count += 1
    if c != -1:
        parent[c] = a
        node_count += 1

# 마지막 노드 구하는 파트
last_node = 0
def traverse(node):
    global last_node
    if node == -1:
        return
    traverse(left[node])
    last_node = node
    traverse(right[node])

traverse(1)
edge_count = node_count * 2
movement = 0
# 마지막 노드까지 이동 경로의 거리 구함
while last_node != 1:
    movement += 1
    last_node = parent[last_node]
print(edge_count - movement)

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

풀이 과정

1. 경우의 수가 너무 많아질 수 있으므로 탐색으로 구하는 문제는 아닌것 같아 DP로 풀이
2. DP로 풀이하기 위해 점화식을 도출한다.
   1. DP[i][j][0] = sum(DP[v][j-1][1] , 0<= v < i)
   2. DP[i][j][1] = sum(DP[v][j-1][0] , 0<= v < i)
   3. 여기서, DP[i][j][k]에서 i가 의미하는것은 현재 위치, j가 의미하는것은 현재 문자열이 두루마리의 몇번째에 적힌 문자열인지, k가 의미하는 것은 0일땐 악마의 돌다리, 1일땐 천사의 돌다리이다.
3. 점화식을 이용하여 전체 경우의 수를 구한 전체 DP테이블에서 두루마리의 마지막 문자까지 간 경우의 수들만 더해주면 된다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
target = input()
s1 = input()
s2 = input()

dp = [[[0] * 2 for _ in range(len(target))] for _ in range(len(s1))]

for i in range(len(s1)):
    if s1[i] == target[0]:
        dp[i][0][0] = 1
    if s2[i] == target[0]:
        dp[i][0][1] = 1

for i in range(len(s1)):
    for j in range(1, len(target)):
        if s1[i] == target[j]:
            for k in range(i):
                dp[i][j][0] += dp[k][j-1][1]

        if s2[i] == target[j]:
            for k in range(i):
                dp[i][j][1] += dp[k][j-1][0]

answer = 0
for i in range(len(s1)):
    answer += (dp[i][len(target)-1][0] + dp[i][len(target)-1][1])

print(answer)

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

풀이 과정

1. 전체적인 점화식은 다음과 같다. 
   • dp[i][j] = dp[i-1][j] + dp[i-2][j-1]
   • dp[i][j]는 j번 칠했을 때 i번 위치에서의 경우의 수이다.
   • 설명하자면, dp[i-1][j]->dp[i][j]는 i에서 칠하지 않는 경우의 수이고 dp[i-2][j-1]은 i에서 칠하는 경우의 수이다.
2. DP를 두번 진행한다. 한번은 맨 첫번째 색상환을 칠하는 경우, 다른 한번은 첫번째 색상환을 칠하지 않는 경우이다. 이 때 주의해야 할 점은 첫번째 색상환을 칠하는 여부에 따라 dp 테이블 초기화 방식이 다르다는 점이다. 이 점 때문에 시간 많이 잡아먹음..ㅋㅋ
3. 맨 첫번째 색상환을 칠하는 경우에는 마지막 색상환을 칠해선 안되므로 dp[N-1][K]
4. 맨 첫번째 색상환을 칠하지 않는 경우는 마지막 색상환을 칠할 수 있으므로 dp[N][K]
5. 두 합을 구해서 출력시켜준다.

소스 코드

import sys

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

N = int(input())
K = int(input())

answer = 0
selected = True

div = 1000000003
for i in range(2):
    dp = [[0] * (K+1) for _ in range(N+1)]
    for i in range(1, N+1):
        if not selected:
            dp[i][1] = i-1
            dp[i][0] = 1
        else:
            dp[i][1] = 1
            dp[i][0] = 0

    for i in range(2, N+1):
        for j in range(2, K+1):
            dp[i][j] += dp[i-1][j]
            if i >= 2 and j >= 1:
                dp[i][j] += dp[i-2][j-1]

            dp[i][j] %= div

    if selected:
        answer += dp[N-1][K]
    else:
        answer += dp[N][K]
        
    answer %= div
    selected = not selected
    
print(answer)

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

그냥 풀기 너무 어려워서 백준 내 질문게시판을 참조함..

풀이 과정

1. 출구가 한곳이 아니므로 전체 테두리를 .으로 감싸서 외부에서 시작할 때는 [0, 0]에서 시작할 수 있도록 한다.
2. 총 3번의 BFS를 진행하여야 한다.
   1. 1번 죄수 기준으로 BFS를 진행하여 전체 지점에서 부숴야 하는 최소 벽 개수를 구한다.
   2. 2번 죄수 기준으로 BFS를 진행하여 전체 지점에서 부숴야 하는 최소 벽 개수를 구한다.
   3. 외부 조력자 기준([0, 0])으로 BFS를 진행하여 전체 지점에서 부숴야 하는 최소 벽 개수를 구한다.
3. 전체 좌표에 대해서, 1번 죄수가 부숴야하는 벽, 2번 죄수가 부숴야하는 벽, 외부 조력자가 부숴야 하는 벽의 수를 모두 합한 값이 최소일 때의 값을 출력한다.
   • 단, 이 때 현 좌표가 벽인 경우는 1~3번이 모두 부수므로 2를 빼준다.

소스 코드

import sys
from collections import deque as Deque

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

def bfs(matrix, x, y):
    new_matrix = [[int(10e9)] * len(matrix[0]) for _ in range(len(matrix))]
    deque = Deque([[x, y]])
    dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]
    R, C = len(matrix), len(matrix[0])
    visited = [[False] * C for _ in range(R)]
    visited[x][y] = True
    new_matrix[x][y] = 0
    while deque:
        cx, cy = deque.popleft()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx and nx < R and 0 <= ny and ny < C:
                if not visited[nx][ny] and matrix[nx][ny] == '.':
                    new_matrix[nx][ny] = new_matrix[cx][cy]
                    deque.appendleft([nx, ny])
                elif not visited[nx][ny] and matrix[nx][ny] == '#':
                    new_matrix[nx][ny] = new_matrix[cx][cy]+1
                    deque.append([nx, ny])
                visited[nx][ny] = True
    return new_matrix

for _ in range(T):
    h, w = map(int, input().split())
    matrix = [list('.'+input()+'.') for _ in range(h)]
    matrix = [['.'] * (w+2)] + matrix + [['.'] * (w+2)]
    player = []
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == '$':
                player.append([i, j])
                matrix[i][j] = '.'
                
    playerA, playerB = player[0], player[1]
    matrix1 = bfs(matrix, 0, 0)
    matrix2 = bfs(matrix, playerA[0], playerA[1])
    matrix3 = bfs(matrix, playerB[0], playerB[1])

    answer = int(10e9)
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == '*':
                continue
            sumation = matrix1[i][j] + matrix2[i][j] + matrix3[i][j]
            if matrix[i][j] == '#':
                answer = min(answer, sumation-2)
            else:
                answer = min(answer, sumation)

    print(answer)

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

풀이 과정

1. 2차원 DP 테이블을 구성한다.
   1. DP[i][0]: i번째 스티커를 붙이지 않았을 때 최대 점수
   2. DP[i][1]: i번째 스티커를 윗줄에 붙였을 때 최대 점수
   3. DP[i][2]: i번째 스티커를 아랫줄에 붙였을 때 최대 점수
2. 점화식을 구해준다.
   1. 예시로 DP[i][0]의 경우는 i번째 스티커를 붙이지 않을 때의 경우이므로 DP[i-1][0], DP[i-1][1], DP[i-1][2]중 최댓값과 같다.
   2. DP[i][1]이나 DP[i][2]를 구할 때는, 현재 스티커의 점수를 더해서 저장해주어야 한다.
3. 테이블을 모두 구성하면 DP 테이블의 맨 마지막 행의 최댓값을 구해서 출력시켜준다.

소스 코드 

import sys

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

for _ in range(T):
    N = int(input())
    scoreA = list(map(int, input().split()))
    scoreB = list(map(int, input().split()))
    DP = [[0] * 3 for _ in range(N)]
    DP[0][0], DP[0][1], DP[0][2] = 0, scoreA[0], scoreB[0]
    for i in range(1, N):
        DP[i][0] = max(DP[i-1][0], DP[i-1][1], DP[i-1][2])
        DP[i][1] = max(DP[i-1][0], DP[i-1][2]) + scoreA[i]
        DP[i][2] = max(DP[i-1][0], DP[i-1][1]) + scoreB[i]

    print(max(DP[N-1]))

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

풀이 과정

1. BFS 알고리즘을 사용하여 크기가 가장 큰 블록 그룹을 찾는다.
   1. 이 때, 크기가 같은 경우 무지개 블록의 수를 비교하여서 갱신시킨다.
   2. 기준 블록을 왼쪽 위에서 오른쪽 아래 순서로 골라서 블록 그룹을 찾으므로 현재 고른 블록이 기준 블록의 행이 가장 크고 열이 가장 큰 것이다. 따라서 크기가 같고 무지개 블록의 수도 같은 경우는 갱신시켜 주어야 한다.
2. (1)에서 구한 블록 그룹을 모두 제거한다. 이 때 점수도 같이 구해준다.
   • 제거 표시는 -2로 표시하고, 점수는 블록 그룹 내 블록의 수 제곱을 해준다.
3. 중력 기능을 구현한다.
   • 가장 아래 행에서부터 시작해서 하나하나의 요소들을 아래에 -2가 나타나지 않을때까지 당겨준다.
4. 회전 기능을 구현한다.
   • matrix[i][j] = matrix[j][len(matrix[0])-1-i]
5. 구현 순서에 맞추어서 전체 기능을 조합한다. 이 때, 최대 블록 그룹을 구했을 때, 그룹이 없거나 그룹 내 블록의 수가 1개인 경우에 게임을 종료시킨다.

소스 코드

import sys
from collections import deque
import copy


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

def bfs(matrix, startX, startY):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    queue = deque([[startX, startY]])
    block_color = matrix[startX][startY]
    matrix[startX][startY] = -1
    block_count = 1
    rainbow = []
    block = [[startX, startY]]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < N and 0 <= ny and ny < N:
                if matrix[nx][ny] == block_color or matrix[nx][ny] == 0:
                    queue.append([nx, ny])
                    block.append([nx, ny])
                    block_count += 1
                    if matrix[nx][ny] == 0:
                        rainbow.append([nx, ny])
                    matrix[nx][ny] = -1

    for nx, ny in rainbow:
        matrix[nx][ny] = 0

    return block, block_count, len(rainbow)

def find_max_block(target):
    matrix = copy.deepcopy(target)
    max_block, max_block_count, max_rainbow = None, 0, 0
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] > 0:
                block, block_count, rb_len = bfs(matrix, i, j)
                if max_block_count < block_count:
                    max_block, max_block_count, max_rainbow = block, block_count, rb_len
                elif max_block_count == block_count:
                    if max_rainbow <= rb_len:
                        max_block, max_block_count, max_rainbow = block, block_count, rb_len

    return max_block

def destroy(matrix, block):
    for x, y in block:
        matrix[x][y] = -2

def gravity(matrix):
    for i in range(len(matrix)-2, -1, -1):
        for j in range(len(matrix[0])):
            index = i
            if matrix[i][j] == -1:
                continue
            while index+1 != N and matrix[index+1][j] == -2:
                matrix[index+1][j] = matrix[index][j]
                matrix[index][j] = -2
                index += 1

def rotate(matrix):
    new_matrix = copy.deepcopy(matrix)
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            new_matrix[i][j] = matrix[j][len(matrix)-1-i]

    return new_matrix
            

score = 0

while True:
    block = find_max_block(matrix)
    if block == None:
        break
    if len(block) <= 1:
        break
    score += (len(block) ** 2)
    destroy(matrix, block)
    gravity(matrix)
    matrix = rotate(matrix)
    gravity(matrix)

print(score)

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

풀이 과정

1. 입력받은 순서대로 미네랄을 하나 없애준다. 이 때 왼쪽, 오른쪽 순으로 없애는 것에 유의
2. 각각의 미네랄을 기준으로 bfs를 진행해서 블록들을 구해준다.
   1. 이 때, 블록이 바닥에 닿지 않는다면, 해당 블록을 이동시켜주어야 하니 잠시 저장시켜 둔다.
3. 바닥에 닿지 않는 블록이 있는 경우, 바닥에 닿지 않는 블록들을 몇칸 내려야 다른 블록에 충돌하는지 벽에 닿는지 검사하고, 해당 칸수만큼 블록 내 모든 미네랄들을 내려준다.
4. 1-3번 과정을 반복한다.

소스 코드

import sys
from collections import deque
import copy

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

N = int(input())
throws = map(int, input().split())

def bfs(matrix, sx, sy):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    block = [[sx, sy]]
    queue = deque([[sx, sy]])
    matrix[sx][sy] = '.'
    down = False if sx == R-1 else True
    while queue:
        sx, sy = queue.popleft()
        for i in range(4):
            nx, ny = sx + dx[i], sy + dy[i]
            if nx >= 0 and nx < R and ny >= 0 and ny < C and \
               matrix[nx][ny] == 'x':
                down = False if nx == R-1 else down
                block.append([nx, ny])
                queue.append([nx, ny])
                matrix[nx][ny] = '.'

    return block, down
    

def movedown(matrix, block):
    for x, y in block:
        matrix[x][y] = '.'
    movement_count = 0
    # 몇칸 이동해야하는지 구함
    for i in range(1, R):
        for x, y in block:
            if x+i+1 == R or matrix[x+i+1][y] == 'x':
                movement_count = i
                break
        if movement_count != 0:
            break

    for x, y in block:
        matrix[x+movement_count][y] = 'x'
    

def check(matrix):
    target = None
    cp_matrix = copy.deepcopy(matrix)
    for i in range(len(cp_matrix)):
        for j in range(len(cp_matrix[0])):
            if cp_matrix[i][j] == 'x':
                block, down = bfs(cp_matrix, i, j)
                if down:
                    target = block
                    break
        if target:
            break

    if target:
        movedown(matrix, target)

left = True
for throw in throws:
    if left:
        for j in range(C):
            if matrix[R-throw][j] == 'x':
                matrix[R-throw][j] = '.'
                break
    else:
        for j in range(C-1, -1, -1):
            if matrix[R-throw][j] == 'x':
                matrix[R-throw][j] = '.'
                break
    check(matrix)
    left = not left

for m in matrix:
    print("".join(m))

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

풀이 과정

1. 임의의 수를 두개 고른 다음, 두 수의 합의 부호를 반전시켜 준다.
2. 반전시켜 준 값이 고른 두개의 수 위치 뒤에 있는지 확인한다.
   1. 있다면, 값이 여러개일 수 있으므로 이분 탐색을 두번 진행한다.
   2. bisect_left로 왼쪽 위치를 구해주고, bisect_right로 오른쪽 위치를 구해준 다음 두 값의 차이만큼 정답에 더해준다.
   3. bisect_left의 경우 값이 존재하는 맨 왼쪽 위치가 리턴되고, bisect_right의 경우 값이 존재하는 맨 오른쪽 위치 + 1이 존재하므로 bisect_right의 결과에서 bisect_left의 결과를 빼주면 동일한 값의 개수가 나온다.

소스 코드

import sys
from bisect import bisect_left, bisect_right

input = lambda: sys.stdin.readline().rstrip()
N = int(input())
numbers = list(map(int, input().split()))
numbers.sort()
cache = set(numbers)
answer = 0
for i in range(N):
    for j in range(i+1, N):
        target = -(numbers[i] + numbers[j])
        if target in cache:
            answer += bisect_right(numbers, target, j+1, N) - bisect_left(numbers, target, j+1, N)

print(answer)