곽의 개발 blog

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

코드

import sys
import copy
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]

def bfs_game():
    game_matrix = copy.deepcopy(matrix)
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    q = deque()
    for i in range(n):
        for j in range(m):
            if game_matrix[i][j] == 2:
                q.append((j, i))
   
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n and game_matrix[ny][nx] == 0:
                game_matrix[ny][nx] = 2
                q.append((nx, ny))
    
    global maxCnt
    cnt = 0

    for i in range(n):
        cnt += game_matrix[i].count(0)
    
    maxCnt = max(maxCnt, cnt)

def make_wall(cnt):
    if cnt == 3:
        bfs_game()
        return 
    
    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 0:
                matrix[i][j] = 1
                make_wall(cnt+1)
                matrix[i][j] = 0


maxCnt = 0
make_wall(0)
print(maxCnt)

bfs로 바이러스가 퍼지는 함수를 구현하고, 안전 영역 최댓값 구하는 건 쉬웠는데,

처음부터 어렵게 생각해서 벽을 세우는 알고리즘을 고민하는 데 시간을 많이 썼다.

무조건 3개의 벽을 세워야 했기 때문에 모든 경우의 수를 찾아보는 수 밖에 없었다.

하지만, 이때 효율적으로 탐색하기 위해 백트랙킹 방법을 사용하였다.

#벽을 세우는 함수 (재귀 + 백트래킹)
def make_wall(cnt):
    # 3-1. 베이스 케이스: 벽 3개를 모두 세웠다면
    if cnt == 3:
        bfs_game() # 바이러스 확산 시뮬레이션 실행
        return # 재귀 호출 종료

    # 3-2. 재귀 단계: 벽을 세울 위치 탐색
    # 연구소의 모든 칸을 순회
    for i in range(n):
        for j in range(m):
            # 현재 칸이 빈 칸(0)이라면 벽을 세울 수 있음
            if matrix[i][j] == 0:
                # 벽 세우기 시도
                matrix[i][j] = 1 # 현재 칸에 벽(1)을 임시로 세움
                # 다음 벽을 세우기 위해 재귀 호출 (cnt + 1)
                make_wall(cnt + 1)
                # 백트래킹: 재귀 호출이 끝난 후, 세웠던 벽을 다시 빈 칸(0)으로 되돌림
                # 이렇게 해야 다음 반복문에서 다른 위치에 벽을 세우는 경우를 탐색할 수 있음
                matrix[i][j] = 0

make_wall(cnt + 1) 호출이 끝나고 돌아오면, matrix[i][j] = 0을 통해 방금 세웠던 임시 벽을 다시 제거한다.

백트래킹을 해야만, 현재 위치 (i, j)에 벽을 세우는 경우를 모두 탐색한 후, 이 벽을 제거하고 다음 빈 칸에 벽을 세우는 경우를 시도할 수 있다. 이 과정을 통해 모든 가능한 "빈 칸 3개 선택" 조합을 탐색하게 된다.

우선순위 큐 문제가 너무 오랜만이라 기억이 잘 안 나서 개념정리도 같이 했다.

힙(Heap) 이란?

• 완전 이진 트리 형태로 되어 있는 자료구조.
• 각 노드의 값이 자식 노드보다 작거나 같다 → 최소 힙
• 각 노드의 값이 자식 노드보다 크거나 같다 → 최대 힙

파이썬에서 힙 자료구조를 사용할 수 있게 해주는 표준 라이브러리가 heapq이다.

heapq는 우선순위 큐를 구현할 때 주로 사용되며, 이진 최소 힙을 기본으로 한다.

heapq는 기본적으로 최소 힙(min-heap)

작은 값이 먼저 나오므로 우선순위가 낮은 수 (작은 수)가 먼저 처리됨

어떻게 최대 힙 ?

우선순위를 반대로 만들고 싶으면 값에 음수(-)를 붙이면 됨.

음수로 넣고, 꺼낼 때 다시 음수 부호를 제거하면 최대 힙처럼 사용 가능

✅ heapq.heappop()의 동작 원리

파이썬의 heapq 모듈은 최소 힙(min-heap) 기반
힙의 시간 복잡도 특성 때문에 heappop() 함수는 힙에서 가장 작은 원소 하나만 꺼냄

• 삽입 (heappush) : O(log n)
• 꺼내기 (heappop) : O(log n)

여러개를 pop하려면 조건 걸어서 처리

while pq and abs(pq[0][1]) == 3:
    _, val = heapq.heappop(pq)
    print(val)

+ 튜플의 값 순서대로 정렬 조건

코드

# 우선순위 큐 
import heapq
import sys
input = sys.stdin.readline

def max_fullness(t, a, b):
    visited = [[False] * 2 for _ in range(t+1)] #[fullness][물 마셨는 지]
    pq = [( -0, 0, 0)] # (-fullness, fullness, drank_water)

    max_full = 0

    while pq:
        neg_f, f, water = heapq.heappop(pq)
        visited[f][water] = True
        max_full = max(max_full, f)

        # orange
        if f + a <= t and not visited[f+a][water]:
            heapq.heappush(pq, (-(f + a), f+a, water))
        # lemon
        if f + b <= t and not visited[f+b][water]:
            heapq.heappush(pq, (-(f + b), f+b, water))
        
        if water == 0:
            new_f = f // 2
            if not visited[new_f][1]:
                heapq.heappush(pq, (-new_f, new_f, 1))

    return max_full

t, a, b = map(int, input().split())
print(max_fullness(t, a, b))

처음에 기본 최소 힙으로 구현했을 때 시간 초과가 떴다.

하지만 이 문제는 "최대 포만감을 얻는 것"이 목적이기 때문에,
우선순위를 큰 포만감부터 처리해야 탐색 횟수를 줄일 수 있다.

따라서 앞에 포만감의 음수값을 추가해줬고, 정답 처리가 떴다.

코드

처음에 두번째 시간 초과 코드를 거의 1분만에 짜고 냈다가 시간초과가 떴다.

이렇게 쉬울 리가 없자나.....ㅜ

곧 시간복잡도, 공간복잡도를 고려해면서 풀 수 있는 실력이 되겠지..?

정답 코드 ( DP 사용)

import sys
input = sys.stdin.readline

n = int(input())

dp = [[0] * 10 for _ in range(n+1)]

for j in range(10):
    dp[1][j] = 1

for i in range(2, n+1):
    for j in range(10):
        dp[i][j] = sum(dp[i-1][k] for k in range(j+1))

result = sum(dp[n][j] for j in range(10))
print(result % 10007)

dp[i][j] 테이블을 사용한다. i는 자릿수, j는 자릿수의 끝값을 나타낸다.

즉 dp[2][3] 이라면 (03, 13, 23)이 해당되기 때문에 3이된다.

생각해보면 dp[2][3]은 dp[1][3보다 같거나 작은 모든 수] 값들 뒤에 3만 붙인 것과 같다.

그렇다면, 점화식은 아래와 같다.

dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j] 

점화식을 이용해 테이블을 채우고, 마지막 자릿수에서 가능한 모든 값을 더하여 결과를 출력하면 result값이 나오고,

최종적으로 result값을 10007로 나눈 나머지를 출력하면 정답이 된다.

누적합을 사용하면 합을 계산하는 시간이 O(1)이 되고, dp 배열을 계산하는 시간은 O(n*10)이다.

따라서 전체 시간 복잡도는 O(n*10) 즉 O(n)이 된다.

시간 초과 코드 (단순 비교 방식)

import sys
input = sys.stdin.readline

n = int(input())

def func(n):
    n = str(n)
    for i in range(1, len(n)):
        if n[i-1] > n[i]:
            return False
    return True

if n == 1:
    print(10)
else:
    cnt = 0
    for i in range(10**n):
        if func(i):
            cnt += 1
    print(cnt)

이 코드는 그냥 오름차순 조건을 만족하는 지 모든 숫자를 체크하는 방식이다.

위 코드에서 func(i)의 시간 복잡도는 O(n의 자릿수)이다.

결국 i가 0부터 10^n -1까지 즉 10^n 번 func(i)를 반복하기 때문에

전체 시간 복잡도는 O(10^n * n)이다.

• 첫 번째 코드는 DP를 사용하여 시간 복잡도를 최적화할 수 있으며, 자릿수가 커지더라도 비교적 효율적으로 증가하는 수의 개수를 계산할 수 있다.
• 두 번째 코드는 단순 비교 방식으로, 자릿수가 커질수록 시간이 급격히 증가하여 시간 초과가 발생할 수 있다.

오랜만에 DP 문제 푸는 거라, DP 개념정리도 다시 한번 적어두려고 한다.

DP ( Dynamic Programming)

동적 계획법은 문제를 더 작은 부분 문제로 나누어 풀고, 각 부분 문제의 결과를 저장해두고 이를 재사용하는 방법이다.

이미 계산된 결과를 저장하여 반복 계산을 피할 수 있으며, 주어진 문제를 풀기 위한 최적의 해를 찾을 수 있다.

중복 계산을 방지하기 때문에 시간 복잡도가 크게 줄어든다.

문제

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

 

국민대학교에서는 매 학기 시작 전 종합정보시스템에서 수강신청을 한다. 매 수강신청마다 아주 많은 학생들이 몰려 서버에 많은 부하가 가기 때문에, 국민대학교에서는 수강신청 부하 관리 시스템을 도입하기로 결정하였다. 새로운 관리 시스템은 다음과 같은 방식으로 동작한다.

1. 수강신청 버튼이 활성화 된 후, 수강신청 버튼을 조금이라도 빨리 누른 학생이 대기목록에 먼저 들어간다.
2. 이미 대기열에 들어가 있는 상태에서 다시 수강신청 버튼을 누를 경우 대기목록의 맨 뒤로 밀려난다.
3. 잠시 후 수강신청 버튼이 비활성화 되면, 대기목록에서 가장 앞에 있는 학생부터 자동으로 수강신청이 완료되며, 수강 가능 인원이 꽉 찰 경우 나머지 대기목록은 무시하고 수강신청을 종료한다.

위의 표는 최대 수강 가능 인원이 3명인 알고리즘 수업에 대해 6명의 학생이 수강신청을 진행한 모습이다. 버튼이 비활성화 된 후, 먼저 규칙 1을 적용하여 클릭을 2번 이상 한 학생의 중복된 대기목록을 삭제한다. 중복된 목록을 제거한 후, 맨 앞에서부터 최대 수강 가능 인원인 3명을 선정한다. 표의 맨 오른쪽에는 그 최종결과를 나타낸 모습이다. 이와 같은 방법을 이용하여 최종적으로 수강신청에 성공한 인원을 출력하는 프로그램을 작성하시오.

import sys
from collections import OrderedDict

input = sys.stdin.readline

k, l = map(int, input().split())
students = [input().strip() for _ in range(l)]

student_dict = OrderedDict()

for student in students:
    if student in student_dict:
        del student_dict[student]
    student_dict[student] = True

success = list(student_dict.keys())

for student in success[:min(k, len(success))]:
    print(student)

중복 신청한 경우에는 가장 마지막에 신청한 기록만 남아야 하는데 어떤 자료구조를 써야할 지 고민했다.

set은 중복 제거 처리가 되지만 순서 유지가 안되기 때문에 딕셔너리로 구현했다.

찾아보니 순서를 고려하면서 중복을 제거할 수 있는 모듈이 있었다. 고게 바로 OrderedDict !!

근데 사실 Python3.7 이상부터는 dict를 사용해도 순서가 유지되기 때문에 일반적인 상황에서는

dict를 사용하는 게 나을 것 같고, 순서를 조작하거나 추가 기능을 구현하고 싶을 때 사용하면 좋을 것 같다.

처음에는 오잉..? 쉬운 것 같은데..? 하고 풀다가 틀렸습니다가 떠서 고생햇다..

-> 학번이 0부터 시작할 수 있으니 int가 아닌 str으로 받아야 함 !

-> 성공한 인원이 k보다 작을 수 있으니 k번 출력으로 하면 안됨 !

코드

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
year = 0

def dfs(y, x):
    stack = [(y, x)]
    visited[y][x] = True
    while stack:
        cy, cx = stack.pop()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= ny < n and 0 <= nx < m and matrix[ny][nx] > 0 and not visited[ny][nx]:
                visited[ny][nx] = True
                stack.append((ny, nx))

def split():
    global visited
    visited = [[False] * m for _ in range(n)]
    cnt = 0
    for i in range(n):
        for j in range(m):
            if matrix[i][j] > 0 and not visited[i][j]:
                visited[i][j] = True
                dfs(i, j)
                cnt += 1
    return cnt

while True:
    if split() >= 2:
        print(year)
        break
    if not any(matrix[i][j] > 0 for i in range(n) for j in range(m)):
        print(0)
        break

    ice_cnt = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if matrix[i][j] > 0:
                cnt = 0
                for k in range(4):
                    ny = i + dy[k]
                    nx = j + dx[k]
                    if 0 <= nx < m and 0 <= ny < n and matrix[ny][nx] == 0:
                        cnt += 1
                ice_cnt[i][j] = cnt
    for i in range(n):
        for j in range(m):
            matrix[i][j] = max(0, matrix[i][j] - ice_cnt[i][j])
        
    year += 1

이번 주 내내 풀었던 그래프 탐색 문제 중 가장 복잡?했던 ..!

레벨도 높았움.. 골드4였나...?

1. DFS(깊이 우선 탐색)로 빙산 덩어리 찾기

• 빙산이 몇 개의 덩어리로 이루어졌는지 확인하기 위해 DFS를 사용하여 탐색한다.
• DFS를 통해 연결된 빙산을 방문 처리하면서 개수를 세는 방식으로 덩어리 수를 구할 수 있다.
• DFS는 스택을 이용해서 구현한다.

2. 빙산이 녹는 과정 (시뮬레이션)

• 각 빙산은 주변의 바닷물(0의 개수) 만큼 녹는다.
• 매년 반복적으로 녹이는 연산이 필요하며, 한 번의 루프에서 모든 빙산을 녹인 후 업데이트해야 한다.
• 녹이기 전에 빙산이 녹을 양을 따로 저장한 뒤, 한 번에 반영해야 데이터가 오염되지 않는다.

3. 모든 빙산이 녹으면 종료 (0 출력)

• 모든 빙산이 녹았는데(모든 값이 0일때) 덩어리가 2개 이상이 되지 않으면, 0을 출력해야 한다.

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

코드

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
matrix = [list(map(int, input().strip())) for _ in range(n)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
distance = [[-1] * m for _ in range(n)] #최단 거리 저장 배열, 방문하지 않으면 -1 -> visited 따로 필요없음

q = deque([(0, 0)]) # 시작점
distance[0][0] = 1

while q:
    y, x = q.popleft()

    if y == n - 1 and x == m - 1:
        print(distance[y][x])
        break

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if 0 <= ny < n and 0 <= nx < m and matrix[ny][nx] == 1 and distance[ny][nx] == -1:
                q.append((ny, nx))
                distance[ny][nx] = distance[y][x] + 1  # 최단 거리 갱신

- list(map(int, input().split())) 으로 해놓고 계속 에러가 나서 머지.. 하다가 멍총한 짓 한 걸 깨달았다. strip()이다 !!!!

- BFS를 사용하면 최단 거리가 보장된다. 한 번 방문한 곳은 더 짧은 거리로 갱신되지 않으므로, 도착 지점에 처음 도달하면 그것이 최단 거리임 !

- visited 리스트를 따로 쓰지 않고, distance 배열에서 -1인지 확인하도록