✅ 문제 풀이 - BOJ 자료구조
🎈 1717 집합의 표현
첫 줄에 n, m이 주어지고 m은 입력으로 주어지는 연산의 개수를 의미한다. 합집합은 0 a b로 입력이 주어지고 이는 a가 포함된 집합과 b가 포함된 집합을 합친다는 의미이다.
두 원소가 같은 집합에 포함되어 있는지 확인하는 연산은 1 a b로 주어지고 a와 b가 같은 집합에 포함되었으면 yes를 아니면 no를 출력하는 문제
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
parent = [i for i in range(n+1)]
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
a = find(a)
b = find(b)
if a < b:
parent[b] = a
else:
parent[a] = b
for i in range(m):
value, a, b = map(int, input().split())
if value == 0:
union(a, b)
else:
if find(a) == find(b):
print('yes')
else:
print('no')< 풀이 과정 >
주어진 m개의 연산에 0의 개수만큼 집합을 생성해야 하는데 같은 집합인지 여부를 판단해주기 위해 union - find 알고리즘을 사용하였다.
- find 함수로 주어진 x의 부모 노드를 찾아주고
- union 함수로 주어진 a, b를 한 집합으로 합쳐준다.
- for문으로 m줄 만큼 value, a, b를 입력받아 value가 0이면 union함수, 1이면 find로 동일 집합 여부 확인
🎈 2493 탑
n개의 탑이 주어지고 각 탑을 기준으로 왼쪽에 있는 현재 탑보다 크다면 해당 탑이 몇번째 탑인지 출력하는 문제
import sys
input = sys.stdin.readline
n = int(input())
tower = list(map(int, input().split()))
stack = []
answer = []
for i in range(n):
while stack:
if stack[-1][1] > tower[i]:
answer.append(stack[-1][0] + 1)
break
else:
stack.pop()
if not stack:
answer.append(0)
stack.append((i, tower[i]))
print(*answer)< 풀이 과정 >
주어진 n의 범위가 1 이상 500,000 이하이므로, 2중 for문은 사용하게 되면 시간 복잡도를 해결하지 못해 stack으로 구현하였다.
stack과 answer를 빈 리스트로 만들어주고 for문으로 타워의 인덱스를 돌며 stack에 타워인덱스, 타워 높이를 append해준다.
while 문으로 스택이 비어있지 않으면 타워 기준 왼쪽이 더 높으면 answer에 타워 인덱스 + 1을 넣어준다. 아닌 경우 stack 원소를 pop한다.
만일 stack이 비어있지 않으면 answer에 0을 넣어준다.
✅ 문제 풀이 - BOJ DP
🎈 2096 내려가기
첫 줄에 N이 주어지고 N줄에 0 이상 9 이하 숫자가 세개씩 적혀있다. 즉 NX3 크기의 그래프에서 맨 윗줄에서 시작해 아래 줄로 내려가면서 값을 더해줄 때 맨 아래줄의 최대값과 최소값을 구하는 문제. 이때 내려가는 조건은 다음 2가지이다.
- 바로 아래 수로 넘어가기 or 아래 수와 붙어있는 수로만 이동이 가능하다.
import sys
input = sys.stdin.readline
n = int(input())
graph = list(map(int, input().split()))
max_dp = graph
min_dp = graph
for _ in range(n-1):
a, b, c = map(int, input().split())
max_dp = [a + max(max_dp[0], max_dp[1]), b + max(max_dp), c + max(max_dp[1], max_dp[2])]
min_dp = [a + min(min_dp[0], min_dp[1]), b + min(min_dp), c + min(min_dp[1], min_dp[2])]
print(max(max_dp), min(min_dp))< 풀이 과정 >
주어진 graph를 타고 내려가서 가장 아래 줄의 최대값을 찾기 위한 그래프 max_dp와 최소값을 찾기 위한 그래프 min_dp를 2차원으로 미리 만들고 시작하면 메모리 초과가 발생하는 문제.
따라서 주어진 초기값만 저장하기 위해 graph로 첫 행만 입력받고 max_dp와 min_dp를 graph로 저장을 한다.
이후 for문으로 나머지 행 길이 n-1만큼 돌며 a, b, c 3개의 값을 입력받아 max_dp와 min_dp를 주어진 조건에 맞게 update하면 해결된다.
🎈 17070 파이프 옮기기 1 (💡추후 다시 풀기)
새 집의 크기는 nXn의 격자판으로 나타낼 수 있고 r은 행 번호, c는 열 번호를 뜻하고 파이프는 2칸을 차지한다. 파이프는 항상 빈 칸만을 차지해야 하며 파이프를 밀 수 있는 방향은 →, ↘, ↓ 로 3가지이다. 가장 첫 파이프는 (1,1), (1,2)를 차지하고 있을 때 파이프의 한 쪽 끝을 n,n으로 이동시키는 방법의 개수를 구하는 문제
주어진 그래프에서 빈 칸은 0, 벽은 1로 주어지고 가능한 방법의 개수가 없으면 0을 출력한다.
추가로 다음과 같은 경우에만 파이프를 밀 수 있다.
- → : →, ↘
- ↓ : ↓, ↘
- ↘ : →, ↓, ↘
import sys
input = sys.stdin.readline
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
answer = 0
def solution(i, j, direction):
global answer
# 도착 여부
if i == n-1 and j == n-1:
answer += 1
return answer
# 현재 파이프 상태 가로
if direction == 0 or direction == 2:
if j+1 < n and graph[i][j+1] == 0:
solution(i, j+1, 0)
# 현재 파이프 상태 세로
if direction == 1 or direction == 2:
if i+1 < n and graph[i+1][j] == 0:
solution(i+1, j, 1)
# 파이프 상태 대각선
if i+1 < n and j+1 < n:
if graph[i+1][j] == 0 and graph[i][j+1] == 0 and graph[i+1][j+1] == 0:
solution(i+1, j+1, 2)
if graph[n-1][n-1] == 1:
print(0)
else:
solution(0, 1, 0)
print(answer)< 풀이 과정 >
bfs로는 도저히 시간초과를 벗어날 수 없고, dfs 재귀를 이용하여 해결한 풀이 (pypy)
문제 해결 방법은 DP이지만 DP로는 대각선을 어떤 방식으로 표현해야 해결할 지 모르겠어서 dfs를 활용하였다.
- pipe함수를 생성해 i(열), j(행), direction(가로, 세로, 대각선)의 변수를 입력하여 구현하였다.
최종적으로 i와 j가 도착지에 위치하면 answer 에 경로를 1씩 더해주고 리턴한다.
그 과정에서 가로, 세로, 대각선으로 각각 이동할 수 있는 경우를 if문으로 지정해준다. 가로, 세로로 파이프를 연결할 수 있는 경우 다음 위치를 solution함수로 재귀해주고 대각선의 경우 범위는 물론 왼쪽, 위쪽, 아래 대각선의 graph값이 0 이어야 파이프를 연결할 수 있으므로 이를 반영하였다.
최종적으로 현재 파이프의 끝점이 (1,2)이므로 pipe(0, 1, 0)을 넣어 answer를 리턴한다.
