import sys
def backTracking(idx):
if len(case) == 6:
for i in range(6):
print(case[i],end=' ')
print()
return
for i in range(idx,array[0]+1):
if len(case) > 0:
if case[-1] >= array[i]:
continue
case.append(array[i])
backTracking(idx+1)
case.pop()
return
while True:
array = list(map(int,sys.stdin.readline().rstrip().split(' ')))
if not array[0]:
break
case = []
backTracking(1)
print()
풀이 설명:
풀이에 핵심이 되는 backTracking 함수를 설명하고 가겠습니다.
def backTracking(idx):
if len(case) == 6:
for i in range(6):
print(case[i],end=' ')
print()
return
for i in range(idx,array[0]+1):
if len(case) > 0:
if case[-1] >= array[i]:
continue
case.append(array[i])
backTracking(idx+1)
case.pop()
return
문제의 조건은 다음과 같습니다.
1) 6개의 수를 뽑아라
2) 사전 순으로 출력하라
if len(case) == 6:
for i in range(6):
print(case[i],end=' ')
print()
return
1번 조건을 만족시키기 위해, 출력할 value들을 담은 배열의 길이가 6일 경우 출력하도록 세팅하였습니다.
for i in range(idx,array[0]+1):
if len(case) > 0:
if case[-1] >= array[i]:
continue
case.append(array[i])
backTracking(idx+1)
case.pop()
return
backTracking은 다음과 같이 구성하였습니다.
먼저 2번 조건을 만족 시켜주기 위해, 뽑은 숫자를 저장하는 case 배열에 역순으로 수가 담기지 못하도록 조건문을 설정해주었습니다.
이후, 주어진 수열의 값을 백트래킹 기법을 통해 탐색하도록 하여 모든 경우의 수를 출력할 수 있도록 하였습니다.
문제: N x N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제.
풀이 방법: 백 트래킹
풀이 코드:
n = int(input())
board = [0] * n
visited = [0]*n
count = 0
def checkAvailable(col):
for i in range(col):
if abs(board[col] - board[i]) == col - i:
return False
return True
def searchGraph(col):
global count
if col == n:
count += 1
return
for i in range(n):
if col == 0 and n % 2 == 0 and i == n/2: # 보드가 짝수 size 일 경우, 대칭이기 때문에 *2 연산으로 연산 횟수 줄임
return
if visited[i]:
continue
board[col] = i
if checkAvailable(col):
visited[i] = True
searchGraph(col+1)
visited[i] = False
searchGraph(0)
if n % 2 == 0:
print(count*2)
else:
print(count)
풀이설명:
board = [0] * n
visited = [0] * n
board에는 각 행에 퀸이 몇번째 열에 있는지 여부를 저장하는 배열이고, visited는 각 열에 퀸이 존재하는지 여부를 저장하는 배열입니다.
def checkAvailable(col):
for i in range(col):
if abs(board[col] - board[i]) == col - i:
return False
return True
checkAvailable은 퀸이 놓여질 수 있는지 여부를 판단하는 함수 입니다.
예를들어, (0 , 0)과 (1 , 1)은 서로 대각선에 위치하는 점 입니다. (4 , 5)와 (6 , 8)도 서로 대각선의 위치에 존재하는 점 입니다.
대각선에 위치하는 점들 끼리는 행의 값 차이와 열의 값 차이가 서로 같습니다.
따라서, 다음 조건을 통해 대각선 상에 위치한다면 False를 return 하도록 구성하였습니다.
def searchGraph(col):
global count
if col == n:
count += 1
return
for i in range(n):
if col == 0 and n % 2 == 0 and i == n/2: # 보드가 짝수 size 일 경우, 대칭이기 때문에 *2 연산으로 연산 횟수 줄임
return
if visited[i]:
continue
board[col] = i
if checkAvailable(col):
visited[i] = True
searchGraph(col+1)
visited[i] = False
searchGraph 함수는 최종적으로 체스 보드에 퀸이 들어갈 수 있는 경우의 수를 탐색하는 함수 입니다.
한 행에 1개의 퀸만 넣는다고 하였을 때, 퀸이 체스 보드에 들어갈 수 있는 위치는 다음 조건을 만족하여야 합니다.
1. 앞선 행의 대각선 위치에 퀸이 존재하지 않을 것
2. 같은 열에 퀸이 존재하지 않을 것
visited 배열을 통애 같은 열 안에 퀸이 존재하는지 확인하고, 같은 열에 퀸이 존재하지 않을 경우에 대각선에 퀸이 존재하는지 확인합니다.
즉, 두 조건을 만족하면 visited에 해당 열에 퀸이 존재한다고 표시하고(True) 재귀를 통해 다음 행에 대한 searchGraph 함수를 호출합니다.
함수에 들어오는 행의 값이 n일 경우, 0~ n-1번째 행에 퀸이 채워졌다는 의미이므로 1개를 카운트 해줍니다.
추가적으로 시간을 줄이기 위해, 짝수 size의 체스판에서는 경우의 수가 좌우 대칭을 이루기 때문에 절반까지만 세고 x2를 해주는 방식을 사용하였습니다.
임의의 점으로 부터 가장 먼 노드를 2번 구해 지름을 구한다는 발상에 너무 감탄했던 문제입니다.
문제: 트리가 주어졌을 때, 트리의 지름을 구하는 문제입니다.
풀이 방법: 다잌스트라
풀이코드:
import random
import sys
import heapq
n = int(input())
graph = [[] for _ in range(n+1)]
dist = [1E9] * (n+1)
for i in range(1,n+1):
line = list(map(int,sys.stdin.readline().rstrip().split()))
nowNode = line[0]
for j in range(1,len(line)-1,2):
graph[nowNode].append((line[j+1], line[j])) #cost, nextNode
def dijkstra(node):
q = [(0,node)]
while q:
startCost, startNode = heapq.heappop(q)
for nextCost,nextNode in graph[startNode]:
distance = dist[startNode] + nextCost
if dist[nextNode] > distance:
dist[nextNode] = distance
heapq.heappush(q,(distance,nextNode))
#임의의 점으로 부터 제일 먼 노드 X 구하기
startpos = random.randint(1,n)
dist[startpos] = 0
dijkstra(startpos)
index = dist.index(max(dist[1:]))
#X로부터 제일 먼 노드 Y 구하기
dist = [1E9] * (n+1)
dist[index] = 0
dijkstra(index)
#X-Y의 거리가 지름이 된다
print(max(dist[1:]))
풀이 설명:
먼저 입력 값을 보면,
1 3 2 -1
과 같이 입력이 주어질 경우, 1에서 3까지 가는 비용이 2가 된다는 의미이고
3 1 2 4 3 -1
과 같이 입력이 주어지면, 3에서 1까지 가는 비용이 2 그리고 3에서 4까지 가는 비용이 3이라는 의미입니다.
for i in range(1,n+1):
line = list(map(int,sys.stdin.readline().rstrip().split()))
nowNode = line[0]
for j in range(1,len(line)-1,2):
graph[nowNode].append((line[j+1], line[j])) #cost, nextNode
방향성이 없고 한줄에 한 노드로 부터 갈 수 있는 모든 노드의 정보가 주어지므로 다음과 같이 입력을 받아주었습니다.
def dijkstra(node):
q = [(0,node)]
while q:
startCost, startNode = heapq.heappop(q)
for nextCost,nextNode in graph[startNode]:
distance = dist[startNode] + nextCost
if dist[nextNode] > distance:
dist[nextNode] = distance
heapq.heappush(q,(distance,nextNode))
다음은 가장 거리가 먼 노드를 구하기 위해 다잌스트라 함수를 구현했습니다.
#임의의 점으로 부터 제일 먼 노드 X 구하기
startpos = random.randint(1,n)
dist[startpos] = 0
dijkstra(startpos)
index = dist.index(max(dist[1:]))
#X로부터 제일 먼 노드 Y 구하기
dist = [1E9] * (n+1)
dist[index] = 0
dijkstra(index)
#X-Y의 거리가 지름이 된다
print(max(dist[1:]))
문제: A, B가 주어졌을 때, 2를 곱하거나 수의 가장 오른쪽에 1을 붙이는 연산을 통해 A를 B로 바꾸는데 필요한 연산 횟수를 출력하는 문제
풀이 방법: top- down , bfs
1번 풀이코드:
<top-down>
import sys
a,b = map(int,sys.stdin.readline().rstrip().split())
cnt = 0
pause = 0
while b != a and b >= a:
cnt += 1
if b % 10 == 1:
b //= 10
elif b % 2 == 0:
b //= 2
else:
pause = 1
break
if not pause and a==b:
print(cnt+1)
else:
print(-1)
풀이 설명:
결과 값이 주어지므로, top - down 방식으로 구현하는 방법으로 코드를 짜보았습니다.
수의 오른쪽에 1을 붙이는 연산은 반대로 수를 10으로 나눴을 때 나머지가 1이라는 뜻입니다.
*2의 연산은 반대로 나누기 2 입니다.
따라서 다음과 같이 구현하였습니다.
while문의 종료조건은 b(나눠지는 수)가 a 같거나 크면서 같지 않을 때 연산이 진행되도록 하였습니다.
if b % 10 == 1:
b //= 10
elif b % 2 == 0:
b //= 2
else:
pause = 1
break
if문과 elif 문의 조건에 부합하지 못하는 경우는 구할 수 없는 수 이므로, pause 값을 1로 설정해주고 반복문을 종료해줍니다.
if not pause and a==b:
print(cnt+1)
else:
print(-1)
pause에 아무런 값이 설정되지 않고 a 가 b와 동일할 경우, 연산 횟수를 출력해줍니다.
2번 풀이코드: bottom-up 방식으로 bfs 입니다.
import sys
from collections import deque
a, b = map(int,sys.stdin.readline().rstrip().split())
deq = deque([(a,1)])
tot = -1
while len(deq) > 0:
val, cnt = deq.popleft()
if 2 * val <= b:
deq.append([2*val,cnt + 1])
if val*10+1 <= b:
deq.append([10*val + 1 , cnt+1])
if 2*val == b or 10*val + 1 == b:
tot = cnt + 1
print(tot)
풀이 설명:
주어진 a 부터 b를 구해 나가는 과정입니다.
if 2 * val <= b:
deq.append([2*val,cnt + 1])
if val*10+1 <= b:
deq.append([10*val + 1 , cnt+1])
위와 같이, 두가지 연산에 대하여 조건을 충족할 경우 deque에 값을 추가해줍니다.
if 2*val == b or 10*val + 1 == b:
tot = cnt + 1
연산을 하다보면, 원하는 값에 도달하는 경우가 있는데 이 경우 변수에 count 값을 저장하도록 하였고
만약 값에 도달하지 못하거나 값을 넘어가게 되면 while문의 종료조건을 통해 종료 되도록 설정하였습니다.
1번 top-down2번 bottom-up
속도는 top-down 방식이 약 2배 빠른 것으로 나왔습니다. 아마 단순 연산이기 때문에 deque를 거치는 것이 오히려 더 느린 것이 아닐까 생각합니다.
처음 보는 백트래킹 문제라, 고민고민 하다가 결국 풀지 못하고 백트래킹에 대해서 구글링해서 푼 문제입니다.
DFS와 다르게 되돌아간다는 개념이 정말 신기하게 다가왔던 문제였습니다.
문제: 두 개의 수 N,M이 주어졌을 때, 1부터 N까지 자연수 중 M개의 수로 구성할 수 있는 모든 오름차순 수열을 모두 구하는 문제입니다.
풀이 방법: 백트래킹
풀이코드:
import sys
n, m = map(int,sys.stdin.readline().rstrip().split())
lst = []
def backTracking(start):
if len(lst) == m:
print(' '.join(map(str,lst)))
return
for i in range(start,n+1):
if i not in lst:
lst.append(i)
backTracking(i+1)
lst.pop()
backTracking(1)
import sys
import math
n = int(input())
modular = 1000000007
total = 0
numerator = []
dominator = []
def getLcd(dominator:list):
dom = dominator[0]
for i in range(len(dominator)-1):
dom = math.lcm(dom,dominator[i+1])
return dom
def getFraction(numerator:list,dominator:list,dom):
sumNumerator = 0
for i in range(len(dominator)):
sumNumerator += numerator[i] * (dom//dominator[i])
return (sumNumerator,dom)
def DQ(num,x):
if x == 1:
return num
tmp = DQ(num,x//2)
if x % 2 == 1:
return tmp *tmp* num % modular
else:
return tmp * tmp % modular
for _ in range(n):
n, s = map(int,sys.stdin.readline().rstrip().split())
numerator.append(s)
dominator.append(n)
sumN, lcd = getFraction(numerator,dominator,getLcd(dominator))
total = DQ(lcd,modular-2)
print((sumN*total) % modular)
풀이 설명:
먼저 기대값을 계산하는 법에 대해서 설명을 드리겠습니다.
문제 예시인 n = 3, s = 7 일 경우, 7 * ( 3 ^ -1 ) mod 1000000007의 경우는 7 * ( 3 ^ 1000000005 ) mod 1000000007과 같습니다.
그리고 예를들어 기약 분수가 7/3 , 6/5 두개가 주어졌다면, 53/15에 대하여 연산해주면 됩니다.
표현하자면, 53 * ( 15 ^ 1000000005) mod 1000000007로요.
보시면 아시겠지만, 1000000005 제곱을 해주어야 하기 때문에 분할 정복을 활용하여 문제를 풀어주었습니다.
코드는 다음과 같이 구성하였습니다.
for _ in range(n):
n, s = map(int,sys.stdin.readline().rstrip().split())
numerator.append(s)
dominator.append(n)
분자, 분모의 값은 입력 받아 리스트에 저장해주었습니다.
def getLcd(dominator:list):
dom = dominator[0]
for i in range(len(dominator)-1):
dom = math.lcm(dom,dominator[i+1])
return dom
위 코드는 분모가 될 최소 공배수를 구하는 코드입니다.
math.lcm 함수를 통해 분모들을 비교하면서 최종적인 최소공배수를 구해주었습니다.
예를 들어 3,5,7이 있다면 (3 , 5 , 7)의 최소 공배수는 3과 5의 최소 공배수인 15와 7의 최소 공배수와 동일하기 때문에 다음과 같이 구해주었습니다.
def getFraction(numerator:list,dominator:list,dom):
sumNumerator = 0
for i in range(len(dominator)):
sumNumerator += numerator[i] * (dom//dominator[i])
return (sumNumerator,dom)
그 다음은 기약분수를 구하는 코드입니다.
7/3 의 분자를 15로 바꾸어주려면 분자에도 5를 곱하여 35/15를 만들어 주어야 합니다.
따라서 구해놓은 분모들의 최소공배수를 현재 분수의 분모로 나누어 몫을 구해준 다음
몫을 분자의 값과 곱해준 값을 모두 더해주었습니다.
(이미 분모들의 최소 공배수는 앞에서 구해주어서, 분자들의 값의 합만 구하면 주어진 분수들의 합을 구할 수 있습니다.)
그런 다음, 최종 기약 분수의 분자 분모 값을 return 해주었습니다.
def DQ(num,x):
if x == 1:
return num
tmp = DQ(num,x//2)
if x % 2 == 1:
return tmp *tmp* num % modular
else:
return tmp * tmp % modular
다음은 분할정복을 통해 값을 구하는 코드입니다.
sumN, lcd = getFraction(numerator,dominator,getLcd(dominator))
total = DQ(lcd,modular-2)
print((sumN*total) % modular)
최종적으로 값을 출력하는 부분입니다.
분수들의 값을 모두 더한 분자 분모를 구해줍니다.( sumN, lcd )
원하는 값은 lcd * (sumN ^ 1000000005) mod 1000000007 이므로,
sumN ^ 1000000005 mod 1000000007 값을 분할 정복으로 구해줍니다.
위에서 구한 값을 lcd 와 곱한 후 1000000007 로 나눈 나머지를 구해 출력해주면 됩니다.
문제: 도시 간 이동하는 버스 정보와 그 비용이 주어졌을 때, 출발 도시에서 도착 도시까지 드는 최소 비용 / 최소 비용을 갖는 경로에 있는 도시의 갯수 / 최소 비용을 갖는 경로로 방문하는 도시를 순서대로 출력하는 문제입니다.
풀이 방법: 다잌스트라 알고리즘
풀이코드:
import sys
import heapq
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
startNode, endNode, cost = map(int,sys.stdin.readline().rstrip().split())
graph[startNode].append((cost,endNode))
start, end = map(int,sys.stdin.readline().rstrip().split())
q = [(0,start)]
route = [[] for _ in range(n+1)]
distance = [1E9] * (n+1)
distance[start] = 0
while q:
cost, node = heapq.heappop(q)
if cost > distance[node]:
continue
for newCost, newNode in graph[node]:
dist = newCost + distance[node]
if dist < distance[newNode]:
distance[newNode] = dist
heapq.heappush(q,(distance[newNode],newNode)) # 위 코드 까지는 다잌스트라
route[newNode] = [node] # 방문하는 경로 저장
pos = end
minRoute = [end]
while pos != start:
minRoute.append(route[pos][0])
pos = route[pos][0]
print(distance[end])
print(len(minRoute))
for i in minRoute[::-1]:
print(i,end =' ')
풀이 설명:
for _ in range(m):
startNode, endNode, cost = map(int,sys.stdin.readline().rstrip().split())
graph[startNode].append((cost,endNode))
시작점과 도착점 정보로, 단방향성 정보가 주어집니다. 따라서 다음과 같이 그래프에 저장해주었습니다.
while q:
cost, node = heapq.heappop(q)
if cost > distance[node]:
continue
for newCost, newNode in graph[node]:
dist = newCost + distance[node]
if dist < distance[newNode]:
distance[newNode] = dist
heapq.heappush(q,(distance[newNode],newNode)) # 위 코드 까지는 다잌스트라
route[newNode] = [node] # 방문하는 경로 저장
이제 코드에서 핵심되는 부분은 다잌스트라 알고리즘을 통해 최소 비용 및 방문하는 도시를 탐색하는 부분입니다.
여기서 기존 다잌스트라 알고리즘과 다른 부분은 경로를 저장해주는 부분입니다.
route[newNode] = [node] # 방문하는 경로 저장
위 코드를 통해 최소 비용의 거리가 갱신되었을 경우 , 경로를 저장하도록 하였는데요.
값을 append로 덧붙여 주는 것이 아닌 갱신 되었을 때 해당 값만 저장하도록 하여 최소 비용에 들어가는 도시만을 저장해였습니다.
예를 들어, 출발점과 도착점을 1 -> 2, 3 -> 4 가 있다고 하였을 때,
route[ 2 ] = [ 1 ] , route[ 4 ] = [ 3 ] 과 같은 형태로 저장되게 됩니다.
도착점에 대해 시작점의 정보를 value로 가질 수 있게 저장한 것입니다.
pos = end
minRoute = [end]
while pos != start:
minRoute.append(route[pos][0])
pos = route[pos][0]
저장한 경로를 바탕으로 위 코드를 통해 최소비용을 갖는 루트의 각 도시 정보를 구했습니다.
최소 비용을 갖는 루트가 1 -> 4 - > 5 라고 하였을 때,
route[ 5 ] = [ 4 ]
route[ 4 ] = [ 1 ] 와 같이 저장이 되게 됩니다.
이를 도착점 부터 탐색하여 도착점 5를 통해 중간 도시인 4를, 중간 도시 4를 통해 시작 도시 1을 배열에 저장해줍니다.
print(distance[end])
print(len(minRoute))
for i in minRoute[::-1]:
print(i,end =' ')
마지막으로 각 정보를 출력해주는데, 거쳐간 도시의 정보는 역순으로 저장해주었으므로 역순으로 출력해주었습니다.
