N = int(input())
def makePrimeNumber(num,idx):
if idx == N:
result.append(num)
else:
for last_num in range(1,10,2):
new_num = num*10 + last_num
if isPrime(new_num):
makePrimeNumber(new_num,idx+1)
def isPrime(num):
if num in prime_numbers:
return True
for i in range(2,int(num**0.5)+1):
if num%i == 0:
return False
prime_numbers.add(num)
return True
prime_numbers = set([2,3,5,7])
result = []
for num in [2,3,5,7]:
makePrimeNumber(num,1)
result.sort()
for row in result:
print(row)
이 문제는 처음에 모든 N자리의 숫자를 primnumber 인지를 구했더니 메모리초과가 났던 문제이다.
이 문제를 푸는 방법은 다음과 같다.
이 문제를 보면 우리는 제일 왼쪽부터 한자리숫자씩 늘리면서 모든 경우에 소수인 것을 구하는 것이다.
그러면 우리가 한자리숫자에서 소수인 것은 2,3,5,7 임을 알 수 있다.
그러면 제일 왼쪽은 무조건 2,3,5,7로 시작되게 해준다.
그리고 N자리를 dfs로 구해주면 된다.
현재 num에 10을 곱하고 끝자리를 바꿔가면서 그 값이 소수인지 판별해주면 된다.
그리고 우리는 한자리숫자를 제외한 두자리숫자부터는 끝 숫자부분이 홀수여야지만 소수가 될 가능성임을 알 수 있다.
그러므로 끝자리는 홀수들만 들어가게 해준다.
소수를 판별하는 방법은 이 수의 제곱근까지의 숫자까지 나눠가면서 나눠지는 경우가 있는지 확인해주면 된다.
import sys
def find_parents(X):
if X == make_set[X]:
return X
make_set[X] = find_parents(make_set[X])
return make_set[X]
def union(x,y):
X = find_parents(x)
Y = find_parents(y)
if X !=Y:
if ranks[X]< ranks[Y]:
X,Y = Y,X
make_set[Y] = X
if ranks[X] == ranks[Y]:
ranks[X] += 1
return True
return False
def input():
return sys.stdin.readline().rstrip()
N,M = map(int,input().split())
dire = {
"U": [-1,0],
"L": [0,-1],
"R" : [0, 1],
'D': [1,0]
}
arr = [list(input()) for _ in range(N)]
make_set = [i for i in range(N*M)]
ranks = [1 for _ in range(N*M)]
for x in range(N):
for y in range(M):
point = x*M+y
dx,dy = dire[arr[x][y]]
next_point = (x+dx)*M+y+dy
union(point,next_point)
result = 0
for x in range(N):
for y in range(M):
point = x*M+y
if point == find_parents(point):
result += 1
print(result)
이 문제는 union find를 통해 집합이 몇개가 되는지 확인하면 된다.
그 방법은 현재 노드와 부모노드가 동일한 개수를 세주면 된다.
import sys
def input():
return sys.stdin.readline().rstrip()
N,M = map(int,input().split())
dire = {
"U": [-1,0],
"L": [0,-1],
"R" : [0, 1],
'D': [1,0]
}
arr = [list(input()) for _ in range(N)]
visited = [[-1 for _ in range(M)] for _ in range(N)]
result = 0
for x in range(N):
for y in range(M):
if visited[x][y] != -1:
continue
point = x*M+y
nx,ny = x,y
while visited[nx][ny] == -1:
visited[nx][ny] = point
dx,dy = dire[arr[nx][ny]]
nx = nx + dx
ny = ny + dy
if visited[nx][ny] == point:
result += 1
print(result)
다르게 푸는 방식은 visited를 만들어놓고 같은 point가 되는 지점에 돌아왔을때 result + 1 해주는 것이다.
안전지대가 된다는 것은 한 지점에서 출발했다가 원래지점으로 돌아온다는것을 뜻하므로, 그 조건을 만족하는 개수를 세주면 된다.
import sys
sys.setrecursionlimit(10000)
def input():
return sys.stdin.readline().rstrip()
def cycle_check(node,parent):
if visited[node]:
return node
else:
visited[node] = True
for next_node in graph[node]:
if next_node == parent:continue
return_node = cycle_check(next_node,node)
if return_node > 0:
cycle_check_node[node] = True
if return_node == node:
return 0
else:
return return_node
cycle_check_node[node] = False
return 0
def dfs(start):
stack = [(start,0,0)]
visited = [True for _ in range(N+1)]
while stack:
node,parent,dis = stack.pop()
if cycle_check_node[node]:
distance[start] = dis
return
visited[node] = False
for next_node in graph[node]:
if next_node == parent:continue
if visited[next_node]:
stack.append((next_node,node,dis+1))
N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N):
x,y = map(int,input().split())
graph[x].append(y)
graph[y].append(x)
visited = [False for _ in range(N+1)]
cycle_check_node = [False for _ in range(N+1)]
distance = [0 for _ in range(N+1)]
cycle_check(1,0)
for k in range(1,N+1):
if not cycle_check_node[k]:
dfs(k)
print(*distance[1:])
처음 풀이는 생각나는대로 풀었다. 먼저 2가지 함수로 나눠서 했다.
처음은 cycle을 체크하는 함수이다. 어느 노드에서든지 시작을 해서, 한번 방문을 했던 노드가 나올때까지
부모노드를 제외한 자식노드를 탐색해간다. 그러다보면 cycle의 시작지점을 방문하게 되는데 이때,
우리는 해당 node의 번호를 리턴해준다. 그러면 우리는 return 된 값이 0보다 크면
이 노드는 사이클에 포함된 노드임을 알 수 있다. 그러므로 return이 된 값이 0보다 크면 cycle임을 체크해주고,
시작지점에 도착하면, return 된 node와 값이 같으므로, 그걸로 판별뒤, 그 뒤에는 0을 반환해주면 된다.
그러면 우리는 0이 반환이 되면, 해당 노드는 사이클이 아닌것을 알게 된다.
이렇게 cycle을 체크한 뒤에
dfs를 돌려 cycle을 최초로 만나는 지점까지의 거리를 구해서 저장해주면 된다.
import sys
sys.setrecursionlimit(10000)
def input():
return sys.stdin.readline().rstrip()
def cycle_check(node,parent):
if visited[node]:
return node
else:
visited[node] = True
for next_node in graph[node]:
if next_node == parent:continue
return_node = cycle_check(next_node,node)
if return_node > 0:
cycle_check_node[node] = True
distance[node] = 0
if return_node == node:
return 0
else:
return return_node
cycle_check_node[node] = False
return 0
def dfs(start,parent):
if distance[start] != INF:
return distance[start]
for next_node in graph[start]:
if next_node == parent:continue
distance[start] = min(dfs(next_node,start)+1,distance[start])
return distance[start]
N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N):
x,y = map(int,input().split())
graph[x].append(y)
graph[y].append(x)
visited = [False for _ in range(N+1)]
cycle_check_node = [False for _ in range(N+1)]
INF = float('inf')
distance = [INF for _ in range(N+1)]
cycle_check(1,0)
for k in range(1,N+1):
if not cycle_check_node[k] and distance[k] == INF:
dfs(k,0)
print(*distance[1:])
이 방식은 좀 더 깔끔한 코드이다. 모든 노드들을 dfs를 각각돌리는것이 아닌. cycle인 부분에서부터 1씩 거리를 늘리면서 하나씩 해주는 방식이다.
import sys
sys.setrecursionlimit(10000)
def input():
return sys.stdin.readline().rstrip()
def LCS(X,Y):
if depth[X] != depth[Y]:
if depth[X]>depth[Y]:
X,Y = Y,X
for i in range(MAX_NODE-1,-1,-1):
if (depth[Y]-depth[X] >= (1<<i)):
Y = parents[Y][i]
if X == Y:
return X
if (Y != X):
for i in range(MAX_NODE-1,-1,-1):
if parents[X][i] != parents[Y][i]:
X = parents[X][i]
Y = parents[Y][i]
return parents[X][0]
def tree_make(idx,cur_node,node_cnt,parent_idx):
if idx == len(binary_list):
return
if binary_list[idx] == 0:
node_cnt += 1
cur_node = node_cnt
binary_search[idx+1] = cur_node
tree[cur_node].visited.append(idx+1)
tree[cur_node].parent = parent_idx
depth[cur_node] = depth[parent_idx] + 1
parents[cur_node][0] = parent_idx
if cur_node != 1:
parent_node = tree[cur_node].parent
if tree[parent_node].left == None:
tree[parent_node].left = cur_node
else:
tree[parent_node].right = cur_node
tree_make(idx+1,cur_node,node_cnt,cur_node)
else:
binary_search[idx+1] = cur_node
tree[cur_node].visited.append(idx+1)
cur_node = tree[cur_node].parent
tree_make(idx+1,cur_node,node_cnt,cur_node)
class Node():
def __init__(self,data):
self.data = data
self.left = None
self.right = None
self.parent = None
self.visited = []
N = int(input())
binary_list = list(map(int,list(input())))
i,j = map(int,input().split())
tree = [Node(i) for i in range(N+1)]
MAX_NODE = 15
binary_search = [0 for _ in range(len(binary_list)+1)]
depth = [0 for _ in range(N+1)]
parents = [[0 for _ in range(MAX_NODE)] for _ in range(N+1)]
tree_make(0,0,0,0)
for par_idx in range(1,MAX_NODE):
for k in range(1,N+1):
parents[k][par_idx] = parents[parents[k][par_idx-1]][par_idx-1]
X,Y = binary_search[i],binary_search[j]
result_node = LCS(X,Y)
print(*tree[result_node].visited)
import sys
input = sys.stdin.readline
def dfs(node):
global result
if not len(graph[node]):
ball_cnt_list[parent_list[node]] += (ball_cnt_list[node] -1)
result += abs(ball_cnt_list[node] - 1)
else:
for next_node in graph[node]:
dfs(next_node)
if parent_list[node] != -1:
ball_cnt_list[parent_list[node]] += ball_cnt_list[node] - 1
result += abs(ball_cnt_list[node] - 1)
while True:
N = int(input())
if N == 0:
break
graph = [[] for _ in range(N+1)]
parent_list = [-1 for _ in range(N+1)]
ball_cnt_list = [0 for _ in range(N+1)]
indegree = [0 for _ in range(N+1)]
for _ in range(N):
node_num,ball_cnt,*arg = map(int,input().split())
if arg[0]>0:
for child_node in arg[1:]:
graph[node_num].append(child_node)
parent_list[child_node] = node_num
indegree[child_node] += 1
ball_cnt_list[node_num] = ball_cnt
result = 0
for k in range(1,N+1):
if indegree[k] == 0:
dfs(k)
print(result)
이 문제를 해결하는데 어려움을 겪었다.
이 문제를 해결하는 방식은 가장 끝 리프노드부터 1씩 무조건 맞춰주는 것이다.
그리고 그때의 절대값들을 전부 더해주는 방식을 해주면 된다.
현재 노드에서 1와의 차이를 부모노드로 옮겨주고,
그때 차이의 절대값을 결과에 계속 더해주면 된다.
# dotorya님 풀이
import sys
input = sys.stdin.readline
def dfs(node):
global result
cnt = ball_cnt_list[node] -1
for next_node in graph[node]:
cnt += dfs(next_node)
result += abs(cnt)
return cnt
while True:
N = int(input())
if N == 0:
break
graph = [[] for _ in range(N+1)]
ball_cnt_list = [0 for _ in range(N+1)]
indegree = [0 for _ in range(N+1)]
for _ in range(N):
node_num,ball_cnt,*arg = map(int,input().split())
if arg[0]>0:
for child_node in arg[1:]:
graph[node_num].append(child_node)
indegree[child_node] += 1
ball_cnt_list[node_num] = ball_cnt
result = 0
for k in range(1,N+1):
if indegree[k] == 0:
dfs(k)
print(result)
두 번째 풀이는 dotorya님 풀이를 복기한 것이다.
끝노드부터 하는 것은 동일하다.
그리고 현재의 격차를 상위노드로 전달해주고, 결과에는 그 절대값을 계속 누적해서 더해주면 되는 것이다.
import sys
sys.setrecursionlimit(100000)
def dfs(x,y):
if visited[x][y]:
return INF
elif dp[x][y] >0:
return dp[x][y]
else:
visited[x][y] = True
for i in range(4):
nx = x + dx[i]*int(arr[x][y])
ny = y + dy[i]*int(arr[x][y])
if 0<=nx<N and 0<=ny<M and arr[nx][ny].isdigit():
dp[x][y] = max(dp[x][y],dfs(nx,ny) + 1)
if dp[x][y] == INF:
return INF
visited[x][y] = False
return dp[x][y]
dx = [-1,1,0,0]
dy = [0,0,1,-1]
N,M = map(int,input().split())
INF = float('inf')
arr = [list(input()) for _ in range(N)]
visited = [[False for _ in range(M)] for _ in range(N)]
dp = [[0 for _ in range(M)] for _ in range(N)]
result = dfs(0,0)
if result == INF:
print(-1)
else:
print(result+1)
DP와 DFS를 활용한 문제 였다. 이 와 비슷한 문제를 풀어본 경험이 있었기 때문에 수월하게 풀 수 있었다.
여기서 문제에서 동전을 무한번 움직일때 -1을 출력한다는 것은 한번 방문을 했던 곳을 재귀 중에 방문을 하면, 들렸던
장소에서 현재까지 오는 것이기때문에, 무한번 반복할 수 있다는 생각으로 만들어줬다.
그리고 입력과 똑같은 크기의 DP를 만들어서 해당 값이 초기값인 0이 아닌 다른 값이 있는 것은 해당 위치에서
탐색을 끝낸 것이기 때문에 초기값이 아닐때에는 바로 넘겨주는 것을 구현을 했다.
기본적이 풀이 방식은 다음과 같다.
왼쪽 위에서부터 탐색을 하면서, DFS를 처음 들어갈때 방문을 한곳인지 아닌지를 체크한다. 방문을 안한 곳이면,
방문을 체크해주고, 현재 위치에서 동서남북으로, 움직임이 가능한 경우를 탐색한다.
그리고 가능할때 그 방향으로 DFS를 하면서 한번 움직인 것이기 때문에 + 1을 해준다.
이렇게 재귀를 하면서 현재의 DP값과 최대값을 비교해서 저장을 해준다.
그리고 이 4방향을 다 둘러본것은 전부 탐색을 한 것이기 때문에 방문을 초기화 해준다.
그리고 현재 DP 값을 돌려주면 된다.
이렇듯 방문을 체크하는 리스트와 현재 위치에서의 최대값을 저장해주는 DP를 활용해서 풀 수 있는 문제였다.