728x90
1. 그래프 문제 풀이
1. 1388번 - 바닥 장식
import sys
N, M = map(int, sys.stdin.readline().split())
graph = [list(sys.stdin.readline().strip()) for _ in range(N)]
visited = [[0] * M for _ in range(N)]
# 같은 행에 존재하는지 확인해야하므로 열 번호 증가
def col(x, y) :
visited[x][y] = 1
stack = [(x, y)]
while stack :
curx, cury = stack.pop()
for i in range(1, M) :
ny = cury + i
if ny < M and graph[curx][ny] == '-' and visited[curx][ny] == 0 :
visited[curx][ny] = 1
stack.append((curx, ny))
else : # 단 연속적으로 존재하는 것이 아니면 같을 수 없다.
return
# 같은 열에 존재하는지 확인해야하므로 행 번호 증가
def row(x, y) :
visited[x][y] = 1
stack = [(x, y)]
while stack :
curx, cury = stack.pop()
for i in range(1, N) :
nx = curx + i
if nx < N and graph[nx][cury] == '|' and visited[nx][cury] == 0 :
visited[nx][cury] = 1
stack.append((nx, cury))
else : # 단 연속적으로 존재하는 것이 아니면 같을 수 없다.
return
count = 0
for i in range(N) :
for j in range(M) :
if visited[i][j] == 0 :
if graph[i][j] == '-' :
col(i, j)
count += 1
elif graph[i][j] == '|' :
row(i, j)
count += 1
print(count)알아보기 편하게 하기 위해 '-'의 경우와 '|' 경우를 나눠서 함수를 구현했다.
1. - 의 경우
: 같은 행에 위치하면서 연속적으로 존재해야하므로 현재 y좌표에 순서대로 더해보면서 왼쪽부터 오른쪽으로 확인
2. | 의 경우
: 같은 열에 위치하면서 연속적으로 존재햐야하므로 현재 x좌표에 순서대로 더해보면서 위쪽에서 아래쪽으로 확인
2. 2667번 - 단지번호붙이기
# 단지 번호 붙이기
import sys
from collections import deque
N = int(sys.stdin.readline())
apart = [list(sys.stdin.readline().strip()) for _ in range(N)]
result = []
visited = [[0] * N for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y) :
count = 1
queue = deque()
visited[x][y] = 1
queue.append((x, y))
while queue :
curx, cury = queue.popleft()
for i in range(4) :
nx, ny = curx + dx[i], cury + dy[i]
if 0 <= nx < N and 0 <= ny < N and apart[nx][ny] == '1' and visited[nx][ny] == 0 :
count += 1
visited[nx][ny] = 1
queue.append((nx, ny))
return count # 한 단지 내에 있는 집의 수 반환
for i in range(N) :
for j in range(N) :
if visited[i][j] == 0 and apart[i][j] == '1' :
result.append(bfs(i, j))
result.sort()
print(len(result))
for i in result :
print(i)그래프 탐색의 기본 문제
BFS를 이용하여 탐색하며 찾은 위치들을 count하도록 하여 결론 도출
3. 18405번 - 경쟁적 전염
# 경쟁적 전염
import sys
from collections import deque
N, K = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
S, X, Y = map(int, sys.stdin.readline().split())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs() :
time = 0
start = []
for i in range(N) :
for j in range(N) :
if graph[i][j] != 0 :
start.append((graph[i][j] ,i, j))
# 낮은 번호의 바이러스부터 증식한다.
start.sort() # 바이러스의 번호에 따라 정렬
queue = deque(start)
snum = queue[0][0] # 가장 낮은 번호
fnum = queue[len(queue)-1][0] # 가장 높은 번호
past = 0 # 전에 탐색한 번호
while queue :
# 큐 = 선입선출
num, curx, cury = queue.popleft()
# 전의 번호가 가장 높은 번호이고 현재 번호가 가장 낮은 번호이면
# 1초 증가
if past == fnum and num == snum :
time += 1
if time == S :
break
for i in range(4) :
nx, ny = curx + dx[i], cury + dy[i]
if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 0 :
graph[nx][ny] = num
queue.append((num, nx, ny))
past = num
bfs()
print(graph[X-1][Y-1])문제 조건 : 시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.
위의 조건을 보면 작은 번호의 바이러스를 먼저 증식시켜야 한다. 이때 큐를 이용하면 처음에만 오름차순으로 정렬해서 넣어주면 선입선출 구조이기 때문에 계속해서 순서대로 실행되기 때문에 첫 입력값을 정렬하여 넣어주었다.
하지만 문제는 언제 시간(초)를 증가시켜야 하는가인데, 바이러스 번호 중 가장 작은 것과 가장 큰 것을 저장하여 현재 번호가 가장 작은 번호이고 전에 탐색한 번호가 가장 큰 번호일 때 1초가 지났다고 생각하고 증가시켜줬다.
2. 동적 프로그래밍(Dynamic Programming)
분할 정복과 마찬가지로 부분 문제의 해를 결합해 문제를 해결
▶ Overlapping Subproblems :부분 문제를 한번만 풀어 그 해를 테이블에 저장함으로써 각 부분 문제를 풀 때 마다 다시 계산하는 일을 피하므로 부분 문제가 서로 중복될 때, 즉 부분 문제가 다시 자신의 부분 문제를 공유할 때 적용한다.
▶ Optimization Problem : 최적화 문제는 다양한 해를 가지는데 이 중 최적의 값을 찾기 원한다. 즉, 최적 부분 구조(Optimal Subtructure)를 가져 하나의 문제에 대한 최적해는 각각을 독립적으로 풀 수 있는 연관된 부분 문제들을의 최적해를 이용한다.
1. 구현 방법
1. Top-Down (하향식)
: 프로시저를 자연스럽게 재귀적으로 쓰지만 각각의 부분 문제의 결과를 보통 배열이나 해시테이블에 저장해 놓는다.
프로시저는 현재 부분 문제를 이전에 풀었는지 알아보고 풀었다면 저장되어 있는 값을 사용하고 아니면 계산을한다.
이 재귀 과정을 메모되었다(Memoization)라고 한다.
▶ 하향식 동적 프로그래밍 방법으로 피보나치 수열 의사코드
▶ 하향식 동적 프로그래밍 방법으로 피보나치 수열 구현
import sys
N = int(sys.stdin.readline())
# 하향식 동적 프로그래밍
dic = {0 : 0, 1 : 1}
def top_down_fib(n) :
if n not in dic.keys() :
dic[n] = top_down_fib(n-1) + top_down_fib(n-2)
return dic[n]
print(top_down_fib(N))
2. Bottom-Up (상향식)
: 특정 부분 문제를 푸는 것이 더 작은 부분 문제를 푸는 것에만 의존
즉, 특정 부분 문제를 풀 때는 그 해에 영향을 미치는 더 작은 부분 문제를 모두 풀어 그 해를 모두 저장해놓는다.
▶ 상향식 동적 프로그래밍 방법으로 피보나치 수열 의사코드
▶ 상향식 동적 프로그래밍 방법으로 피보나치 수열 구현
import sys
N = int(sys.stdin.readline())
# 상향식 동적 프로그래밍
def bottom_up_fib(n) :
memo = [0] * (n+1)
memo[1] = 1
for i in range(2, n+1) :
memo[i] = memo[i-1] + memo[i-2]
return memo[n]
print(bottom_up_fib(N))< 참고 >
🔗 https://ko.wikipedia.org/wiki/동적_계획법
🔗 https://hongjw1938.tistory.com/47
🔗 https://doorbw.tistory.com/53
2. DP 문제 풀이
1. 1904번 - 01타일
import sys
N = int(sys.stdin.readline())
def binary(n) :
if n < 3 :
return n
a = 1
b = 2
cnt = 2
while cnt != n :
cur = (a + b) % 15746
a, b = b ,cur
cnt += 1
return cur
print(binary(N))import sys
N = int(sys.stdin.readline())
def binary(n) :
dp = [0] * (n+1)
dp[1] = 1
if n == 1 :
return dp[1]
dp[2] = 2
for i in range(3, n+1) :
dp[i] = (dp[i-1] + dp[i-2]) % 15746
return dp[n]
print(binary(N))
첫번째 코드는 그때그때 구한 값을 변수에 저장하여 구한 것이고
두번째 코드는 리스트에 값을 저장하여 사용하는 방식이다.
훨씬 빠르고 메모리도 덜 사용하는 코드는 첫번째 코드이다.
이때 주의할 점은 인덱스 오류를 조심해야하는데 특히, dp배열을 사용하여 코드를 작성할 때,
위의 코드에서 보듯이 n = 1일 경우 dp[2]는 존재할 수 없다. 이를 위한 예외처리를 해주지 않으면 인덱스 오류가 발생한다.
실제로 dp문제를 풀때 많이 겪었던 문제였는데 오랜만에 풀어서 잊고 있었다.
주의해야겠다🥲
728x90
'KraftonJungle2기 > Today I Learned' 카테고리의 다른 글
| [TIL] 동적 프로그래밍 문제 풀이2 (0) | 2023.04.29 |
|---|---|
| [TIL] 동적 프로그래밍 문제 풀이 (0) | 2023.04.28 |
| [TIL] 위상 정렬 문제 풀이 + Computer System2 (0) | 2023.04.26 |
| [TIL] Algorithm - 위상 정렬 + 플로이드-워셜 (1) | 2023.04.25 |
| [TIL] Algorithm - 다익스트라 + 그래프 문제 풀이(BFS) (0) | 2023.04.24 |
