TIL 코딩공장

백준 파이썬 공부 2025.02.19
10026번 적록색약 (골드 5)

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

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

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

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

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

2. 입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.

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

4. 문제 풀이
규칙이 다른 그래프 탐색문제이다.
BFS를 이용하여 각각의 그래프 탐색 방식으로 그래프를 탐색해나가면 된다.

>>>코드

from collections import deque

def normal_BFS(y, x):
    queue = deque()
    queue.append((y, x))
    visited[y][x] = 1
    
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    while queue:
        y, x = queue.popleft()
         
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < n:
                if visited[ny][nx] == 0 and picture[y][x] == picture[ny][nx]:
                    visited[ny][nx] = 1
                    queue.append((ny, nx))

def rgblind_BFS(y, x):
    queue = deque()
    queue.append((y, x))
    visited[y][x] = 1
    
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    while queue:
        y, x = queue.popleft()
         
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < n and visited[ny][nx] == 0:
                if picture[y][x] == 'R' or picture[y][x] == 'G':
                    if picture[ny][nx] == 'R' or picture[ny][nx] == 'G':
                        visited[ny][nx] = 1
                        queue.append((ny, nx))
                elif picture[y][x] == picture[ny][nx]:
                    visited[ny][nx] = 1
                    queue.append((ny, nx))

n = int(input())
picture = []
for i in range(n):
    picture.append(input())

n_cnt = 0
visited = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if visited[i][j] == 0:
            normal_BFS(i, j)
            n_cnt += 1
            
b_cnt = 0
visited = [[0] * n for _ in range(n)]           
for i in range(n):
    for j in range(n):
        if visited[i][j] == 0:
            rgblind_BFS(i, j)
            b_cnt += 1
            
print(n_cnt, b_cnt)

5. 문제 링크
https://www.acmicpc.net/problem/10026

백준 파이썬 공부 2025.02.16
11727번 2xn 타일링 2 (실버 3)

1. 문제
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.

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

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

4. 문제 풀이
2xn 타일링 1번 문제와 동일하게 DP 문제인것 같다
규칙을 찾고 이를 이용해 점화식을 세워보자

1, 3, 5, 11, ... 인걸로 보아
점화식은 dp[i] = dp[i-1] + dp[i-2]*2 인것 같다.

>>>코드

def DP(n):
    dp = [0] * (n+1)
    
    for i in range(1, n+1):
        if i == 1:
            dp[i] = 1
        elif i == 2:
            dp[i] = 3
        else:
            dp[i] = dp[i-1] + dp[i-2]*2
        
    return dp[n]

n = int(input())
print(DP(n) % 10007)

5. 문제 링크
https://www.acmicpc.net/problem/11727

백준 파이썬 공부 2025.02.12
11726번 2xn 타일링 (실버 3)

1. 문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

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

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

4. 문제 풀이
다이나믹 프로그래밍 DP를 이용해서 풀어보자
점화식을 먼저 찾아야한다.

1 2 3 5 8 ...
인걸로 보아, 점화식은 dp[i] = dp[i-1] + dp[i-2] 인 것 같다.

알고보니 피보나치 수열이었다.

>>>코드

def DP(n):
    dp = [0] * (n+1)
    
    for i in range(1, n+1):
        if i == 1:
            dp[i] = 1
        elif i == 2:
            dp[i] = 2
        else:
            dp[i] = dp[i-1] + dp[i-2]
        
    return dp[n]

n = int(input())
print(DP(n) % 10007)

5. 문제 링크
https://www.acmicpc.net/problem/11726

백준 파이썬 공부 2025.02.09
9375번 패션왕 신해빈 (실버 3)

1. 문제
해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 
예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 
다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 
해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

2. 입력
첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.

- 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
- 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 
- 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

3. 출력
각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.

4. 문제 풀이

일단 딕셔너리로 의상종류 : [의상 이름1, 의상 이름2, ...] 형식으로 저장 한다.
특정 종류의 의상을 아예 입지 않는 것도 하나의 착장이라고 생각한 후
조합의 경우의 수를 구하면 된다.
마지막에 완전 알몸인 경우만 -1 해주면 된다. 

>>>코드

import sys

T = int(sys.stdin.readline().strip())
for _ in range(T):
    cloth = {}
    n = int(sys.stdin.readline().strip())
    for i in range(n):
        name, ctype = sys.stdin.readline().strip().split()
        if ctype not in cloth.keys():
            cloth[ctype] = [name]
        else:
            cloth[ctype].append(name)
    cnt = 1
    for value in cloth.values():
        # 알몸도 옷이라고 생각하여 +1 해준 후 모든 조합의 수를 구하면 된다.
        cnt *= (len(value)+1)
    # 완전 알몸인 경우 -1
    print(cnt-1)

5. 문제 링크
https://www.acmicpc.net/problem/9375

백준 파이썬 공부 2025.02.05
21736번 헌내기는 친구가 필요해 (실버 2)

1. 문제
2020년에 입학한 헌내기 도연이가 있다. 
도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 
드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 

도연이가 다니는 대학의 캠퍼스는 N * M 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 
예를 들어, 도연이가 (x, y)에 있다면 이동할 수 있는 곳은 (x+1, y), (x, y+1), (x-1, y), (x, y-1)이다. 
단, 캠퍼스의 밖으로 이동할 수는 없다.

불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.

2. 입력
첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 
N (1 <= N <= 600), M (1 <= M <= 600)이 주어진다.

둘째 줄부터 N개의 줄에는 캠퍼스의 정보들이 주어진다. 
O는 빈 공간, X는 벽, I는 도연이, P는 사람이다. I가 한 번만 주어짐이 보장된다.

3. 출력
첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 
단, 아무도 만나지 못한 경우 TT를 출력한다.

4. 문제 풀이
그래프 문제이다.
당연히 DFS, BFS를 사용하여 풀어야한다.

일단 BFS를 사용해서 풀어보자
>>>코드 1. BFS 사용

import sys
from collections import deque

def BFS(y, x):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    cnt = 0
    queue.append((y, x))
    visited[y][x] = 1
    
    while queue:
        y, x = queue.popleft()
        if graph[y][x] == 'P':
            cnt += 1
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < m and 0 <= ny < n:
                if visited[ny][nx] == 0 and graph[ny][nx] != 'X':
                    queue.append((ny, nx))
                    visited[ny][nx] = 1
    return cnt

n, m = map(int, sys.stdin.readline().split())
graph = []
for _ in range(n):
    graph.append(sys.stdin.readline())

flag = 0
queue = deque()
visited = [[0] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'I':
            cnt = BFS(i, j)
            flag = 1
            break
    if flag:
        break

if cnt:
    print(cnt)
else:
    print("TT")

다음으로는 DFS를 사용해서 풀어보자
DFS를 사용할 경우 recursion error가 발생하는데,
이는 파이썬에서 함수가 너무 많은 재귀호출을 할 때 발생하므로,
sys.setrecursionlimit(10**6) 로 재귀 깊이를 늘려 줘야한다.
그러나 이 방식보다는 BFS를 사용하는 것을 권장한다.

>>>코드2. DFS 사용

import sys
sys.setrecursionlimit(10**6)

def DFS(y, x, cnt):
    if graph[y][x] == 'P':
        cnt += 1
    
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0 <= nx < m and 0 <= ny < n:
            if visited[ny][nx] == 0 and graph[ny][nx] != 'X':
                visited[ny][nx] = 1
                cnt = DFS(ny, nx, cnt)
    return cnt

n, m = map(int, sys.stdin.readline().split())
graph = []
for _ in range(n):
    graph.append(sys.stdin.readline())

flag = 0
visited = [[0] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'I':
            visited[i][j] = 1
            cnt = DFS(i, j, 0)
            flag = 1
            break
    if flag:
        break

if cnt:
    print(cnt)
else:
    print("TT")

5. 문제 링크
https://www.acmicpc.net/problem/21736

백준 파이썬 공부 2025.02.01
11659번 구간 합 구하기 4 (실버 3)

1. 문제
수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 
둘째 줄에는 N개의 수가 주어진다. 
수는 1,000보다 작거나 같은 자연수이다. 
셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

3. 출력
총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

4. 제한
- 1 ≤ N ≤ 100,000
- 1 ≤ M ≤ 100,000
- 1 ≤ i ≤ j ≤ N

5. 문제 풀이
일단 단순 sum 함수를 사용하여 풀어보자
>>> 코드1. 단순 함수 사용 >> 시간초과

import sys

n, m = map(int, sys.stdin.readline().split())
num = list(map(int, sys.stdin.readline().split()))

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    print(sum(num[a-1 : b]))

흠 되긴 하나 실행시간이 너무 오래 걸려 시간초과가 걸린다..
그럼 다음 방식으로 누적합을 써보자
누적합을 이용하여 각각의 인덱스 까지의 합을 계산해서 저장해놓고
(j까지의 합) - (i-1까지의 합) 방식으로 계산해보자

>> 코드 2. 누적 합 계산

import sys
n, m = map(int, sys.stdin.readline().split())
num = list(map(int, sys.stdin.readline().split()))

dp = [0] * (n+1)
for i in range(1, n+1):
    dp[i] = dp[i-1] + num[i-1]

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    print(dp[b] - dp[a-1])

저장 공간과 실행 시간은 확실히 별개라는걸 다시한번 느끼게 된다.

6. 문제 링크
https://www.acmicpc.net/problem/11659

백준 파이썬 공부 2025.01.30
9461번 파도반 수열 (실버 2)

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

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

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

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

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

4. 문제 풀이
규칙 찾기
1 1 1 2 2 3 4 5 7 9 12 16
초반 1 1 1 2 2 를 제외하면 삼각형의 각도가 60도 이기 때문에 점화식은
P(n) = P(n-1) + P(n-5) 이 된다.

>> 시도 1. 재귀함수 사용 >> 시간초과

def P(n):
    if n == 1 or n == 2 or n == 3:
        return 1
    elif n == 4 or n == 5:
        return 2
    else:
        return P(n-1) + P(n-5)
    
for _ in range(int(input())):
    n  = int(input())
    print(P(n))

재귀함수를 사용하였더니 시간초과가 나온다.
DP를 사용해서 해결해봐야겠다.

재귀와 DP가 무엇이 다른지 보자면,
재귀: 하위 함수에 계산 하청 주문(?) 넣기 
>> 같은 계산을 두번 이상 할 가능성 있음

DP: 맨 바닥부터 차근차근 올라가며 계산하기 
>> 하위의 값을 저장해 놓기에 계산을 한번만 시행함

>> 시도 2. DP 사용

def pado(n):
    dp = [0] * (n + 1)
    # 초기값 설정
    dp[1:6] = [1, 1, 1, 2, 2]  # P(1)~P(5)까지 미리 할당
    for i in range(6, n + 1):
        dp[i] = dp[i - 1] + dp[i - 5]  # 점화식

    return dp[n]
    
for _ in range(int(input())):
    n  = int(input())
    print(pado(n))

5. 문제 링크
https://www.acmicpc.net/problem/9461

백준 파이썬 공부 2025.01.25
11724번 연결 요소의 개수 (실버 2)

1. 문제
방향 없는 그래프가 주어졌을 때, 
연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. 
(1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 
둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. 
(1 ≤ u, v ≤ N, u ≠ v) 
같은 간선은 한 번만 주어진다.

3. 출력
첫째 줄에 연결 요소의 개수를 출력한다.

4. 문제 풀이
연결 요소가 무엇이냐?
그냥 단순히 생각해서 서로 연결된 하나의 그래프가 하나의 연결요소이다.
그래프의 개수라고도 볼 수 있겠다.

>>>코드1. DFS 사용

import sys

def DFS(x):
    visited[x] = 1
    
    for i in range(1, n+1):
        if graph[x][i] == 1 and visited[i] == 0:
            DFS(i)

n, m = map(int, sys.stdin.readline().split())
graph = [[0] * (n+1) for _ in range(n+1)]
visited = [0] * (n+1)
cnt = 0

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a][b] = 1
    graph[b][a] = 1

for i in range(1, n+1):
    if visited[i] == 0:
        DFS(i)
        cnt += 1
        
print(cnt)

양방향 루트 이므로 그냥 0과 1로 이루어진 그래프를 하나 만들어서, DFS 탐색하였다.
처음에 cnt를 n으로 선언하고 하나씩 뺴는 방식으로 하려 했으나,
전역변수 문제가 터져서, 코드를 새로 짰다.
문제를 푸는 과정에서 알아낸 것은

# 함수 안에서의 값의 변경 >> 전역변수
- 리스트의 경우 함수 내에서 내부 값을 변경하는데에, 
해당 리스트를 호출하거나 전역변수 선언을 하지 않아도 된다.
- 그러나 리스트 전체의 구조를 새로 선언하는 경우, 전역변수 선언을 하지 않으면,
그냥 해당 함수 내의 새로운 지역변수로 인식된다.

- 일반 자료형 변수의 경우, 함수 내에서 값을 변경하려면 전역변수 선언을 해야한다.
- 또는 그냥 길이가 1인 리스트를 선언하여 내부에서 값을 변경하는 방법도 존재한다.

>>> 코드 2. BFS 사용

import sys
from collections import deque

def BFS(idx):
    queue.append(idx)
    visited[idx] = 1
    
    while queue:
        x = queue.popleft()
        
        for i in range(1, n+1):
            if graph[x][i] == 1 and visited[i] == 0:
                queue.append(i)
                visited[i] = 1

n, m = map(int, sys.stdin.readline().split())
graph = [[0] * (n+1) for _ in range(n+1)]
visited = [0] * (n+1)
queue = deque()
cnt = 0

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a][b] = 1
    graph[b][a] = 1

for i in range(1, n+1):
    if visited[i] == 0:
        BFS(i)
        cnt += 1
        
print(cnt)

5. 문제 해설
https://www.acmicpc.net/problem/11724