성능 요약

메모리: 33992 KB, 시간: 184 ms

분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 구현(implementation), 시뮬레이션(simulation)

문제 설명

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

풀이 과정

문제를 잘못 읽은 부분이 많았어서, 그 부분들을 고치느라 문제푸는데 시간이 정말 오래 걸렸다.

먼저 BFS를 통해 현재 위치에서 먹을 수 있는 물고기가 있는 위치에서 가장 적은 시간이 걸리는 물고기들만 찾았다.

이때 heapq를 사용했다! heapq에 이동 시간, 행, 열 순으로 넣어서 문제에서 제시한 위쪽, 왼쪽 순서대로 찾도록 했다.

그리고 현재 내가 먹은 물고기의 수를 비교하면서, 크기를 늘려주었다.

코드

import sys
from collections import deque
import heapq

N = int(sys.stdin.readline())
MAP = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

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

size = 2
cnt = 0

def BFS(st, sr, sc) :
    global size, cnt
    visited = [[0 for _ in range(N)] for _ in range(N)]
    visited[sr][sc] = 1
    queue = deque()
    queue.append((st, sr, sc))
    area = []
    minT = 1e9

    while queue :
        t, r, c = queue.popleft()
        for i in range(4) :
            nt, nr, nc = t + 1, r + dr[i], c + dc[i]
            if nr < 0 or nr >= N or nc < 0 or nc >= N or visited[nr][nc] == 1 :
                continue

            if size >= MAP[nr][nc] :
                if 0 < MAP[nr][nc] < size  :
                    if nt > minT :
                        break
                    else :
                        minT = nt
                    heapq.heappush(area, (nt, nr, nc))
                else :
                    queue.append((nt, nr, nc))
                    visited[nr][nc] = 1

    if area :
        newT, newR, newC = heapq.heappop(area)
        MAP[sr][sc] = 0
        MAP[newR][newC] = 9

        cnt += 1
        if size == cnt :
            size += 1
            cnt = 0
        BFS(newT, newR, newC)
    else :
        print(st)

for i in range(N) :
    for j in range(N) :
        if MAP[i][j] == 9 :
            BFS(0, i, j)
            break
    else: 
        continue
    break

성능 요약

메모리: 39052 KB, 시간: 180 ms

분류

자료 구조(data_structures), 우선순위 큐(priority_queue)

문제 설명

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -2³¹보다 크고, 2³¹보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

코드

import heapq
import sys

input = sys.stdin.readline

N = int(input())

heap = []

for _ in range(N) :
    tmp = int(input())
    num = (abs(tmp), tmp)

    if tmp == 0 : 
        if heap :
            print(heapq.heappop(heap)[1])
        else : 
            print(0)
    else :
        heapq.heappush(heap, num)

성능 요약

메모리: 30840 KB, 시간: 328 ms

분류

플로이드–와샬(floyd_warshall), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

코드

import sys

input = sys.stdin.readline

N = int(input())

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

for k in range(N) :
    for i in range(N) :
        for j in range(N) :
            if graph[i][k] and graph[k][j] == 1 :
                graph[i][j] = 1


for i in range(N) :
    for j in range(N) :
        print(graph[i][j], end=" ")
    print()

성능 요약

메모리: 30840 KB, 시간: 68 ms

분류

다이나믹 프로그래밍(dp)

문제 설명

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

코드

import sys

N = int(sys.stdin.readline())


dp = [0] * 1001

dp[1] = 1
dp[2] = 3

for i in range(3, N + 1) :
    dp[i] = (dp[i-2] * 2 + dp[i-1]) % 10007

print(dp[N])

성능 요약

메모리: 30840 KB, 시간: 68 ms

분류

다이나믹 프로그래밍(dp), 수학(math)

문제 설명

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

풀이 과정

import sys
T = int(sys.stdin.readline())

for _ in range(T) :
    N = int(sys.stdin.readline())
    dp = [0] * 101

    dp[1] = 1
    dp[2] = 1
    dp[3] = 1
    dp[4] = 2
    dp[5] = 2
    dp[6] = 3
    dp[7] = 4
    dp[8] = 5
    dp[9] = 7
    dp[10] = 9

    for i in range(10, N + 1) :
        dp[i] = dp[i-1] + dp[i-5]


    print(dp[N])

성능 요약

메모리: 32440 KB, 시간: 88 ms

분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다.

주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까?

게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다.

플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다. 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다. 즉, 사다리를 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 크고, 뱀을 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 작아진다.

게임의 목표는 1번 칸에서 시작해서 100번 칸에 도착하는 것이다.

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

입력

첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으로 이동한다는 의미이다.

다음 M개의 줄에는 뱀의 정보를 의미하는 u, v (u > v)가 주어진다. u번 칸에 도착하면, v번 칸으로 이동한다는 의미이다.

1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다. 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다. 항상 100번 칸에 도착할 수 있는 입력만 주어진다.

출력

100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 출력한다.

코드

import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())
MAP = [i for i in range(101)]

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

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

visited = [0 for i in range(101)]

queue = deque()
queue.append((1, 0))

while queue :
    pos, cnt = queue.popleft()
    for i in range(pos + 1, pos + 7) :
        nPos = MAP[i]
        if nPos >= 100 :
            print(cnt + 1)
            exit()
        if visited[i] == 0 :
            queue.append((nPos, cnt + 1))
            visited[i] = 1

성능 요약

메모리: 41532 KB, 시간: 316 ms

분류

덱(deque), 파싱(parsing), 구현(implementation), 문자열(string), 자료 구조(data_structures)

문제 설명

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x₁,...,x_n]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ x_i ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

코드

import sys
from collections import deque

input = sys.stdin.readline

T = int(input())

def R(arr) :
    result = deque()
    for i in range(len(arr) - 1, -1, -1) :
        result.append(arr[i])
    return result

for _ in range(T) :
    P = input().rstrip()
    N = int(input())
    inputX = input().rstrip()

    X = deque(inputX[1:-1].split(','))
    if inputX == "[]" :
        X = deque()

    cntD = 0
    cntR = 0
    for p in P :
        if p == 'D' :
            cntD += 1
        elif p == 'R' :
            cntR += 1

    if cntD > len(X) :
        print("error")
        continue

    isReverse = False
    for p in P :
        if p == 'R' :
            if isReverse :
                isReverse = False
            else :
                isReverse = True
        elif p == 'D' :
            if isReverse : 
                X.pop()
            else :         
                X.popleft()

    if isReverse :
        X = R(X)

    print(f'[{",".join(X)}]')

성능 요약

메모리: 32796 KB, 시간: 300 ms

분류

문자열(string)

문제 설명

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 P_N이라고 한다.

• P₁ IOI
• P₂ IOIOI
• P₃ IOIOIOI
• P_N IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 P_N이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력

S에 P_N이 몇 군데 포함되어 있는지 출력한다.

풀이 과정

import sys

input = sys.stdin.readline

N = int(input())
M = int(input())

S = input().rstrip()

Pn = "IO" * N + "I"

cnt = 0
answer = 0
i = 0

while i < (M - 1) :
    if S[i : i+3] == 'IOI' :
        cnt += 1
        i += 2
        if cnt == N :
            cnt -= 1
            answer += 1

    else :
        i += 1
        cnt = 0

print(answer)

성능 요약

메모리: 32476 KB, 시간: 92 ms

분류

너비 우선 탐색(bfs), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

코드

import sys
from collections import deque

N = int(sys.stdin.readline())

Map = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(N)]
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

def BFS(sr, sc) :
    queue = deque()    
    queue.append((sr, sc))
    houseCnt = 1
    while queue :
        r, c = queue.popleft()
        for i in range(4) :
            nr, nc = r + dr[i], c + dc[i]
            if 0 <= nr < N and 0 <= nc < N :
                if Map[nr][nc] == 1 and visited[nr][nc] == 0 :
                    queue.append((nr, nc))
                    visited[nr][nc] = 1
                    houseCnt += 1
    return houseCnt

visited = [[0 for _ in range(N)] for _ in range(N)]

danjiCnt = 0
houseCnt = []
for i in range(N) :
    for j in range(N) :
        if Map[i][j] == 1 and visited[i][j] == 0 :
            visited[i][j] = 1
            danjiCnt += 1
            houseCnt.append(BFS(i, j))

print(danjiCnt)
houseCnt.sort()
for cnt in houseCnt :
    print(cnt)

• 외주 레이아웃 마무리 작업
• 1992_쿼드트리
• 10026_적록색약
• 14500_테트로노미노
• kt ds 자소서 작성

하루 회고

나에게 주는 점수

B+

성능 요약

메모리: 116944 KB, 시간: 320 ms

분류

브루트포스 알고리즘(bruteforcing), 구현(implementation)

문제 설명

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

코드

import sys
input = sys.stdin.readline
N, M = map(int, input().split())

paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

cases = [[(0, 0), (0, 1), (1, 0), (1, 1)], 
         [(0, 0), (0, 1), (0, 2), (0, 3)], 
         [(0, 0), (1, 0), (2, 0), (3, 0)], 
         [(0, 0), (1, 0), (1, 1), (2, 1)],
         [(0, 1), (0, 2), (1, 0), (1, 1)],
         [(0, 1), (1, 0), (1, 1), (2, 0)],
         [(0, 0), (0, 1), (1, 1), (1, 2)],
         [(0, 0), (0, 1), (0, 2), (1, 1)],
         [(0, 1), (1, 0), (1, 1), (2, 1)],
         [(0, 1), (1, 0), (1, 1), (1, 2)],
         [(0, 0), (1, 0), (1, 1), (2, 0)],
         [(0, 0), (1, 0), (2, 0), (2, 1)],
         [(0, 0), (0, 1), (0, 2), (1, 0)],
         [(0, 0), (0, 1), (1, 1), (2, 1)],
         [(0, 2), (1, 0), (1, 1), (1, 2)],
         [(0, 1), (1, 1), (2, 0), (2, 1)],
         [(0, 0), (1, 0), (1, 1), (1, 2)],
         [(0, 0), (0, 1), (1, 0), (2, 0)],
         [(0, 0), (0, 1), (0, 2), (1, 2)]
        ]

answer = 0

for r in range(N) :
    for c in range(M) :
        for case in cases :
            value = 0 # 더한 값
            for pos in case :
                nr, nc = r + pos[0], c + pos[1]
                if 0 <= nr < N and 0 <= nc < M :
                    value += paper[nr][nc]
                else :
                    value = 0
                    break
            answer = max(answer, value)

print(answer)

성능 요약

메모리: 33184 KB, 시간: 120 ms

분류

너비 우선 탐색(bfs), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

코드

import sys
from collections import deque
sys.setrecursionlimit(6000)

input = sys.stdin.readline

N = int(input())
normal_picture = []
weird_picture = []

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

for _ in range(N) :
    tmp = []
    tmp2 = []
    for color in input().rstrip() :
        tmp.append(color)
        if color == 'G' :
            tmp2.append('R')
        else :
            tmp2.append(color)
    normal_picture.append(tmp)
    weird_picture.append(tmp2)

def dfs(r, c, picture) :
    global flag
    for i in range(4) :
        nr, nc = r + dr[i], c + dc[i]
        if 0 <= nr < N and 0 <= nc < N :
            if visited[nr][nc] == 0 and picture[r][c] == picture[nr][nc] :
                visited[nr][nc] = flag
                dfs(nr, nc, picture)

flag = 1
visited = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N) :
    for j in range(N) :
        if visited[i][j] == 0 :
            dfs(i, j, normal_picture)
            flag += 1
print(flag - 1, end=" ")

flag = 1
visited = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N) :
    for j in range(N) :
        if visited[i][j] == 0 :
            dfs(i, j, weird_picture)
            flag += 1
print(flag - 1)

성능 요약

메모리: 30840 KB, 시간: 72 ms

분류

분할 정복(divide_and_conquer), 재귀(recursion)

문제 설명

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

영상을 압축한 결과를 출력한다.

코드

import sys
N = int(sys.stdin.readline())

video = []

for _ in range (N) :
    tmp = []
    for num in sys.stdin.readline().rstrip() :
        tmp.append(int(num))
    video.append(tmp)

answer = ""

def recursion(sr, sc, n) :
    global answer
    startNum = video[sr][sc]
    half = n // 2

    for r in range(sr, sr + n) :
        for c in range(sc, sc + n) :
            if startNum != video[r][c] :
                answer += "("
                recursion(sr, sc, half)
                recursion(sr, sc + half, half)
                recursion(sr + half, sc, half)
                recursion(sr + half, sc + half, half)
                answer += ")"
                return
    answer += str(startNum)

recursion(0, 0, N)
print(answer)

성능 요약

메모리: 219264 KB, 시간: 9432 ms

분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d₁, d₂, d₃, d₄라고 하자(즉 n = ((d₁ × 10 + d₂) × 10 + d₃) × 10 + d₄라고 하자)

1. D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
2. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
3. L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d₂, d₃, d₄, d₁이 된다.
4. R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d₄, d₁, d₂, d₃이 된다.

위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.

여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.

1234 →_L 2341 →_L 3412
1234 →_R 4123 →_R 3412

따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.

n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

입력

프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

출력

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.

코드

import sys
from collections import deque

N = int(sys.stdin.readline())

def D(n) :
    return n * 2 if n * 2 < 9999 else (n * 2) % 10000

def S(n) :
    return n - 1 if n > 0 else 9999

def L(n) :
    return (n % 1000) * 10 + (n // 1000)

def R(n) :
    return (n % 10) * 1000 + (n // 10)


def BFS(A, B) :
    queue = deque()
    queue.append((A, ''))
    visited = set()
    while queue :
        a, command = queue.popleft()
        Da, Sa, La, Ra = D(a), S(a), L(a), R(a)
        if a == B :
            print(command)
            return
        if Da not in visited :
            visited.add(Da)
            queue.append((Da, command + 'D'))
        if Sa not in visited :
            visited.add(Sa)
            queue.append((Sa, command + 'S'))
        if La not in visited :
            visited.add(La)
            queue.append((La, command + 'L'))
        if Ra not in visited :
            visited.add(Ra)
            queue.append((Ra, command + 'R'))

for _ in range(N) :
    A, B = map(int, sys.stdin.readline().split())
    BFS(A, B)

성능 요약

메모리: 30840 KB, 시간: 68 ms

분류

다이나믹 프로그래밍(dp)

문제 설명

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

코드

import sys

N = int(sys.stdin.readline())

dp = [0 for _ in range(N)]

stairs = [0 for _ in range(N)]
for i in range(N) :
    stairs[i] = int(sys.stdin.readline())

for i in range(N) :
    if i == 0 :
        dp[i] = stairs[i]
    elif i == 1 :
        dp[i] = dp[i-1] + stairs[i]
    elif i == 2 :
        dp[i] = max(stairs[i-1] + stairs[i], stairs[i-2] + stairs[i])
    else :
        dp[i] = max(dp[i-2] + stairs[i], dp[i-3] + stairs[i-1] + stairs[i])

print(dp[N-1])

성능 요약

메모리: 30840 KB, 시간: 1400 ms

분류

브루트포스 알고리즘(bruteforcing)

문제 설명

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

코드

import sys
input = sys.stdin.readline

N = int(input())

# 어차피 100에서 시작이므로
if N == "100" :
    print(0)
    exit()

M = int(input())

# 고장난 버튼을 빼기 위해 set과 차집합 이용
nums = {str(i) for i in range(10)}
breaks = set(input().split())
nums -= breaks

answer = abs(N - 100)

for num in range(1000000):
    num = str(num)

    flag = True
    for n in num:
        if n not in nums:
            flag = False
            break

    if flag : 
        answer = min(answer, abs(int(num) - N) + len(num))


print(answer)

성능 요약

메모리: 120148 KB, 시간: 204 ms

분류

너비 우선 탐색(bfs), 플로이드–와샬(floyd_warshall), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.

4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. 사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다.

출력

첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

코드

import sys

input = sys.stdin.readline

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

graph = [[1e9 for _ in range(N)] for _ in range(N)]

for _ in range(M) :
    A, B = map(int, input().split())
    graph[A-1][B-1] = 1
    graph[B-1][A-1] = 1

for k in range(N) :
    for i in range(N) :
        for j in range(N) :
            if graph[i][k] + graph[k][j] < graph[i][j] :
                graph[i][j] = graph[i][k] + graph[k][j]

for i in range(N) :
    graph[i][i] = 0


minKevinBaker = 1e9
answer = 0

for i in range(N) :
    tmp = sum(graph[i])
    if minKevinBaker > tmp :
        minKevinBaker = tmp
        answer = i + 1

print(answer)

성능 요약

메모리: 175560 KB, 시간: 1336 ms

분류

분할 정복(divide_and_conquer), 재귀(recursion)

문제 설명

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 3⁷, N은 3^k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

풀이 과정

import sys

N = int(sys.stdin.readline())

answers = {-1: 0, 0: 0, 1:0}
papers = []

for _ in range(N) :
    tmp = list(map(int, sys.stdin.readline().split()))
    papers.append(tmp)

def recursion(sr, sc, n) :
    if n < 1 :
        return

    startNum = papers[sr][sc]
    cutNum = n // 3

    for r in range(sr, sr + n) :
        for c in range(sc, sc + n) :
            if papers[r][c] != startNum :
                recursion(sr, sc, cutNum)
                recursion(sr + cutNum, sc, cutNum)
                recursion(sr + cutNum * 2, sc, cutNum)

                recursion(sr, sc + cutNum, cutNum)
                recursion(sr + cutNum, sc + cutNum, cutNum)
                recursion(sr + cutNum * 2, sc + cutNum, cutNum)

                recursion(sr, sc + cutNum * 2, cutNum)
                recursion(sr + cutNum, sc + cutNum * 2, cutNum)
                recursion(sr + cutNum * 2, sc + cutNum * 2, cutNum)
                return
    answers[startNum] += 1


recursion(0, 0, N)

for answer in answers.values() :
    print(answer)

• 아침 8시 헬스
• 오늘도 하루 종일 외주 제작...
• 1107_리모컨 풀었음
• 영어 화상회화 수업
• 알고리즘 스터디 진행
• kt ds 자소서 초안 작성

하루 회고

외주 강도가 생각보다 너무 세서 다른 공부를 아예 못 하고 있는 것 같다.. 심지어 자소서까지 작성해야해서 시간이 남아나지가 않는 것 같다. 다음주면 정보처리기사랑 중간고사까지 겹치는데 다 소화할 수 있을 지가 무섭다....

그래도 매일매일 열심히 산다는 생각에 뿌듯하다..

외주하면서 많은 트러블 슈팅을 경험하고 있는데, 이를 노션에 계속 기록하고 있따. 외주가 끝나면 쭉 정리해서 업로드해야지

나에게 주는 점수

B+