No. 10971
1. Problem
2. My Solution
- 첫 번째 방법
- itertools 모듈 permutations 함수 사용
- 10! = 3628804 개의 순열 = 473 MB -> 메모리초과
from itertools import permutations
import sys
import math
n = int(sys.stdin.readline())
city = []
res = []
for _ in range(n):
city.append(list(map(int,sys.stdin.readline().rstrip().split())))
routes = [i+(i[0],) for i in list(permutations(range(n),n))]
for route in routes:
sum = 0
for i in range(n):
if city[route[i]][route[i+1]] == 0:
sum += math.inf
break
sum += city[route[i]][route[i+1]]
res.append(sum)
print(min(res))- 두 번째 방법
- 3628804 개의 순열을 모두 생성하지 않고 순열 생성 코드를 직접 구현하여 백트래킹 기법 적용
- Python3 시간초과, PyPy3 통과 (0.128MB, 1160ms)
import sys
import math
def sum(route):
global res
temp = 0
for i in range(n-1):
temp += city[route[i]][route[i+1]]
temp += city[route[-1]][route[0]]
res = min(res, temp)
def permutation(level):
if level >= n:
if city[arr[-1]][arr[0]] != 0:
sum(arr)
else:
for i in range(n):
if visited[i] == True:
continue
elif level > 0 and city[arr[level-1]][i] == 0: # out of index 방지를 위해 level > 0 을 and 연산자 왼쪽에 배치
continue
else:
visited[i] = True
arr[level] = i
permutation(level+1)
visited[i] = False
n = int(sys.stdin.readline())
city = []
res = math.inf
visited = [False] * n
arr = [0] * n
for _ in range(n):
city.append(list(map(int,sys.stdin.readline().rstrip().split())))
permutation(0)
print(res)- 세 번째 방법
- 445MB 메모리를 사용하지만 통과됨..?
- 그냥 코드를 수행하면 시간초과지만 함수로 모든 코드를 수행하면 통과
from itertools import permutations
import sys
import math
def solution():
n = int(sys.stdin.readline())
city = []
res = math.inf
for _ in range(n):
city.append(list(map(int,sys.stdin.readline().rstrip().split())))
routes = list(permutations(range(n)))
for route in routes:
if city[route[-1]][route[0]] == 0:
continue
sum = 0
flag = False
for i in range(n-1):
if city[route[i]][route[i+1]] == 0 or sum >= res:
sum += math.inf
flag = True
break
sum += city[route[i]][route[i+1]]
if flag:
continue
sum += city[route[-1]][route[0]]
res = min(res,sum)
print(res)
solution() - 외판원 순회 전용 풀이방법과 DFS를 이용한 해결 방법은 추후 풀어볼 예정
3. Learned
- 함수내에서 수행하면 속도가 더 빠름 (스택오버플로우)
- 메모리의 사용량을 확인하고 싶을 때는 tracemalloc 모듈 사용(파이썬 문서)
- 함수내에서 사용되고 해당 scope 를 벗어나면 없어지거나 찌꺼기 메모리만 남음
- 코드를 제출하기전에 time 모듈로 시간 체크하고, tracemalloc 모듈로 메모리 체크하는 습관 들이기
No. 13023
1. Problem
2. My Solution
- DFS 알고리즘을 이용하여 문제 해결
- A -> B -> C -> D -> E 처럼 5명이 쭉 알고있다면 (깊이가 5라면) 1출력 아니면 0 출력
- 깊이가 5인 순간 바로 1을 출력하고 exit()
- 모든 사람을 기준으로 해당 관계가 존재하는지 판단하기 위해서 매번 visited 를 초기화 시킴
import sys
sys.setrecursionlimit(10**8)
def dfs(v,level, visited):
visited[v] = True
level += 1
if level >= 5:
print(1)
exit()
for u in range(n):
if u in friendship[v] and visited[u] != True:
dfs(u,level, visited)
n, link = map(int,sys.stdin.readline().rstrip().split())
friendship = [[] for _ in range(n)]
visited = [False] * n
for _ in range(link):
a,b = map(int,sys.stdin.readline().rstrip().split())
friendship[a].append(b)
friendship[b].append(a)
for i in range(n):
visited_copy = visited.copy()
dfs(i,0,visited_copy)
print(0)
3. Others' Solutions
-
위에 코드는 아래에서 빨간색 경로로 가게되면 깊이가 5가되지 않아서 다시 돌아간뒤 파란색 경로로 탐색해야 되지만 빨간색 경로 때 True 로 설정했기 때문에 파란색 경로로 수행될 수 없음 따라서 다시 False로 초기화하는 작업이 필요함
-
for 문에서 dfs(i,0) 을 수행한 뒤에 해당 노드가 탐색되도록 하기 위해서 vistited[i] = False 수행
import sys
def dfs(v,level):
visited[v] = True
level += 1
if level >= 5:
print(1)
sys.exit()
for u in friendship[v]:
if visited[u] == False:
dfs(u,level)
visited[u] = False
n, m = map(int,sys.stdin.readline().rstrip().split())
friendship = [[] for _ in range(n)]
visited = [False] * n
for _ in range(m):
a,b = map(int,sys.stdin.readline().rstrip().split())
friendship[a].append(b)
friendship[b].append(a)
for i in range(n):
dfs(i,0)
visited[i] = False
print(0)
3. Learned
- PyPy3 에서 setrecursionlimit() 이 적용되긴 하지만 이에따른 메모리가 생겨남. 메모리 제한이 512MB 일때 setrecursionlimit(10**5) 까지만 수행되고 6부터는 메모리초과
- BFS 알고리즘은 적용할 수 없음. B에서 시작한다고 가정했을 때 빨간색 경로는 DFS로 깊이 5에 도달할 수 있지만 BFS 는 깊이 3까지만 가게됨
No. 14391
1. Problem
2. Others' Solution
- 비트마스크 알고리즘을 이용하여 문제 해결
- n*m 개 bit 만큼 이진수 정수를 표현할 수 있음
- 여기서는 포함 여부가 아닌 (모두 다 포함됨) 0 이면 가로, 1 이면 세로로 판단
- k = i * m + j ( i 마다 행이 바뀌고 j 마다 열이 바뀜 )
- 참고 블로그
import sys
n, m = map(int,sys.stdin.readline().rstrip().split())
paper = []
res = 0
for _ in range(n):
paper.append(list(map(int,list(sys.stdin.readline().rstrip()))))
for bit in range(1 << n*m):
sum = 0
# 가로 찾기
for i in range(n):
temp = 0
for j in range(m):
k = i * m + j
if bit & (1 << k) == 0: # 가로라면
temp = temp * 10 + paper[i][j] # 숫자 뒤에 붙이기 위해 원래 존재하는 수에 *10 한뒤 덧셈
else: # 세로라면
sum += temp
temp = 0
sum += temp
# 세로 찾기
for j in range(m):
temp = 0
for i in range(n):
k = i * m + j
if bit & (1 << k) != 0: # == 1 하면 버그발생
temp = temp * 10 + paper[i][j]
else:
sum += temp
temp = 0
sum += temp
res = max(res, sum)
print(res)
3. Learned
- 비트마스크에서 해당 원소가 모두 포함되는 경우에는 0과 1로 다른 정보를 표현할 수 있음
- n 개의 bit로 표현할 수 있는 최댓값은 2^n -1
(n 개의 bit로 표현할 수 있는 최댓값은 n개 모두 1인경우이고 가중치는 0부터 시작하기 때문에 최대 가중치는 n-1 임. 따라서 2진수의 n 가중치 bit가 1이고 나머지가 0인 이진수에서 -1을 하면 n-1 가중치부터 0까지 모두 1인 bit가 만들어짐)
No. 9012
1. Problem
2. My Solution
- 첫 번째 방법
import sys
def solution():
test_n = int(sys.stdin.readline())
for _ in range(test_n):
stack = []
flag = False
for i in (list(sys.stdin.readline().rstrip())):
if i == '(':
stack.append(i)
elif stack:
stack.pop()
else:
flag = True
if stack or flag == True: # ')' 먼저 나온경우 또는 스택에 '(' 가 남아있는 경우
print("NO")
else:
print("YES")
solution()- 두 번째 방법
import sys
def solution():
stack = []
for i in (list(sys.stdin.readline().rstrip())):
if i == '(':
stack.append(i)
elif stack:
stack.pop()
else:
print("NO")
return
if stack:
print("NO")
else:
print("YES")
test_n = int(sys.stdin.readline())
for _ in range(test_n):
solution()