2025.04.01
TIL(TODAY I LEARN)
-
WEEK03 :
그래프(vertex, edge, node, arc), BFS, DFS, 위상정렬 -
퀴즈를 쳤다. 더 깊게 공부를 했어야 했을까. 화이팅하자
- 계속해서 알고리즘 문제를 풀었다.
3주차 퀴즈
1. 단일 프로세서 시스템에서 동시성 개념 설명
2. 반복문으로 DFS 구현
3. 다익스트라 실행과정 기록
4. B-tree 사용시 검색 성능이 왜 향상되는가?(시간복잡도 관점에서 설명)
5. 운영체제 관점에서의 4가지 추상화
위 5가지 질문이 퀴즈로 출제되었다.
나름 정리를 했다고 생각했는데 줄글로 논리있게 작성하는 연습을 해야겠다.
아래는 알고리즘 문제 풀이이다.
7569 - 토마토 - 골드5
문제 링크 - https://www.acmicpc.net/problem/7569
내 코드
import sys
from collections import deque
input = sys.stdin.readline
#가로,세로,높이
M,N,H = map(int,input().split())
visited = [[[-1 for _ in range(M)]for _ in range(N)] for _ in range(H)]
box = [[] for _ in range(H)]
for i in range(H):
for _ in range(N):
x = list(map(int,input().split()))
box[i].append(x)
# 상 하 좌 우 위 아래
dx = [0,0,-1,1,0,0]
dy = [-1,1,0,0,0,0]
dz = [0,0,0,0,1,-1]
#존재하는 모든 토마토부터 시작해야하니 미리 큐에 다 넣어놓기
q = deque()
for i in range(H):
for j in range(N):
for k in range(M):
if box[i][j][k] == 1:
q.append((i,j,k))
visited[i][j][k] = 0
while q:
c,b,a = q.popleft()
for i in range(6):
nx = a + dx[i]
ny = b + dy[i]
nz = c + dz[i]
if 0 <= nx < M and 0 <= ny < N and 0 <= nz < H and box[nz][ny][nx] == 0 and visited[nz][ny][nx] == -1:
q.append((nz,ny,nx))
visited[nz][ny][nx] = visited[c][b][a] + 1
box[nz][ny][nx] = 1
def check_result():
result = 0
for i in range(H):
for j in range(N):
for k in range(M):
if box[i][j][k] == 0:
result = -1
return result
result = max(result,visited[i][j][k])
return result
print(check_result())문제 분류
3055 - 탈출 - 골드4
문제 링크 - https://www.acmicpc.net/problem/3055
내 코드
import sys
from collections import deque
input = sys.stdin.readline
R,C = map(int,input().split())
maps = []
for _ in range(R):
x = input().strip()
maps.append(list(x))
# S -> D 로 탈출
# * 물, X 돌
# 매 분마다 물 채우고 비버 이동
#*에 대해서 큐에 넣고 maps 변화 우 s 이동 체크 후 다음 시간으로
# 도착할 수 없으면 KAKTUS 출력
# 상 하 좌 우
dx = [0,0,-1,1]
dy = [-1,1,0,0]
visited = [[-1 for _ in range(C)] for _ in range(R)]
def bfs(startx,starty,water):
#물 위치 넣기
wq = deque(water)
visited[startx][starty] = 0
q = deque()
#고슴도치 시작 위치 넣기
q.append((startx,starty))
while q:
# 물 확장 먼저 다 끝내고
for _ in range(len(wq)):
wx,wy = wq.popleft()
for i in range(4):
nwx = wx + dx[i]
nwy = wy + dy[i]
if 0 <= nwx < R and 0 <= nwy < C and visited[nwx][nwy] == -1 and maps[nwx][nwy] == '.':
maps[nwx][nwy] = "*"
wq.append((nwx,nwy))
# 고슴도치의 이동(BFS상 고슴도치는 여러마리 처럼 움직이니까 )
for _ in range(len(q)):
x,y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < R and 0 <= ny < C and visited[nx][ny] == -1 and maps[nx][ny] in ('.' , 'D'):
visited[nx][ny] = visited[x][y] + 1
q.append((nx,ny))
waterxy = []
for i in range(R):
for j in range(C):
if maps[i][j] == "*":
waterxy.append((i,j))
elif maps[i][j] == 'S':
gosumdochi = (i,j)
elif maps[i][j] == 'D':
destination = (i,j)
bfs(gosumdochi[0],gosumdochi[1],waterxy)
if visited[destination[0]][destination[1]] < 0:
print("KAKTUS")
else:
print(visited[destination[0]][destination[1]])문제 분류
2294 - 동전 2 - 골드5
문제 링크 - https://www.acmicpc.net/problem/2294
내 코드
import sys
sys.setrecursionlimit(10**6)
from collections import deque
input = sys.stdin.readline
n,k = map(int,input().split())
coin = set()
for _ in range(n):
coin.add(int(input().strip()))
# 백트래킹 완전탐색(시간초과)
#coins = list(coin)
#coins.sort(reverse = True)
# min_cnt = float('inf')
# def sol(sums, cnt):
# global min_cnt
# #가지치기
# if cnt >= min_cnt:
# return
# for i in coins:
# ns = sums + i
# nc = cnt + 1
# if ns > k:
# continue
# elif ns == k:
# min_cnt = min(min_cnt, nc)
# continue
# sol(ns, nc)
# sol(0,0)
# print(min_cnt)
#금액 기준으로 생각을 하자
coins = list(coin)
#k까지의 금액을 배열로
dist = [-1] * (k+1)
dist[0] = 0
q = deque()
q.append(0)
while q:
cur = q.popleft()
for c in coins:
nxt = cur + c
if nxt > k:
continue
if dist[nxt] == -1:
dist[nxt] = dist[cur] + 1
q.append(nxt)
print(dist[k])문제 분류
2637 - 장난감 조립 - 골드2
문제 링크 - https://www.acmicpc.net/problem/2637
내 코드
import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input().strip())
M = int(input().strip())
# ~1-N 중간부품 // N 완제품
indeg = [0 for _ in range(N+1)]
graph = [[] for _ in range(N+1)]
# dfs (시간초과)
# for _ in range(M):
# u,v,w = map(int,input().split())
# graph[u].append((v,w))
# indeg[v] += 1
# result = [0 for _ in range(N+1)]
# 완제품 -> 부품으로 개수를 셈셈
# def sol(N,cnt):
# for i,k in enumerate(graph[N]):
# if len(graph[k[0]]) == 0:
# result[k[0]] += k[1] * cnt
# else:
# sol(k[0],k[1] * cnt)
# sol(N,1)
# for i,k in enumerate(result):
# if k != 0:
# print(f"{i} {k}")
# 화살표 작은수에서 큰수로
#그래프/indegree 만들기기
for _ in range(M):
u,v,w = map(int,input().split())
graph[v].append((u,w))
indeg[u] += 1
basic = [] #기본부품 알아내기
q = deque()
for i in range(1,N):
if indeg[i] == 0:
q.append(i)
basic.append(i)
#기본부품의 개수 세기
#기본부품 -> 완제품으로 개수를 셈 (시간초과)
# def sol(N,c):
# sum_cnt = 0
# if len(graph[N]) == 0:
# return c
# for x in graph[N]:
# cnt = x[1]
# sum_cnt += sol(x[0],c * cnt)
# return sum_cnt
#for i in sorted(basic):
# print(f'{i} {sol2(i,1)}')
#갯수 기억을 위한 dp 테이블 ( 1~n 까지 여러가지의 개수가 필요하니까 n*n)
need = [[0 for _ in range(N+1)] for _ in range(N+1)]
#위상정렬과 동시에 need에 개수 업데이트
topo = []
while q:
idx = q.popleft()
topo.append(idx)
for i in graph[idx]:
need[i[0]][idx] += i[1]
if idx not in basic:
for j,k in enumerate(need[idx]):
if j != 0:
need[i[0]][j] += i[1] * k
indeg[i[0]] -= 1
if indeg[i[0]] == 0:
q.append(i[0])
for i in sorted(basic):
print(f'{i} {need[N][i]}')-
우여곡절이 많았다. 탑다운 바텀업. DFS
-
DP가 너무 어렵다…
문제 분류
크래프톤 정글의 3주차.. 점점 내용이 심화됨에 따라 어려워지는게 느껴진다.
분명히 한번했던 내용인데 응용만 들어가도 시간이 오래걸린다. 어렵다 어려워.
^_^