한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.
한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.
문제 해결 방법
파이썬의 조합으로도 풀 수 있었지만, 백트래킹으로 문제를 풀었다.
number리스트의 원소별로 학생의 번호를 달았다. 왜냐하면 문제 제한 사항에 서로 다른 학생의 정수 번호가 같을 수 있다는 문구때문이다. 예를들어 number리스트에 학생 10명이 있다고 가정했을때, 5명의 정수 번호가 0이면 학생 번호로 구분해야한다.
number리스트를 방문 여부를 체크하면서 조건에 맞게 재귀 호출을 한 경우 카운트를 매기며, 총 카운트가 3이되면, 더이상 재귀 호출을 하지 않게끔 했다.
카운트가 3이 됐을때, 문제의 조건(삼총사의 정수 번호 합이 0인 경우)에도 부합하면 totalResult에 삼총사를 추가한다.
최종적으로 totalResult가 만들어졌으면, 중복된 요소들을 삭제하기 위해 요소들을 tuple형태로 바꾸어 주고, 리스트를 최종적으로 set() 으로 변경하기 좋은 상태를 만든다.
준비가 되었으면 set()으로 변경해주면 중복 요소 처리를 할 수 있다.
정리된 집합의 원소 수를 세면 그것이 정답이다.
코드 구현
dfs를 통해 구현한 코드
# 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사
def solution(number):
answer = 0
newL = []
for idx, i in enumerate(number):
newL.append([idx, i])
totalResult = []
def dfs(cnt, visited, summ, result, totalResult):
for idx, i in enumerate(newL):
if visited[idx] == False:
cnt += 1
summ += i[1]
visited[idx] = True
result.append(i)
if cnt == 3 and summ == 0:
totalResult.append(result[:])
if cnt < 3:
dfs(cnt, visited, summ, result, totalResult)
visited[idx] = False
cnt -= 1
summ -= i[1]
result.pop()
for idx, i in enumerate(newL):
summ, cnt = 0, 0
result = []
visited = [False] * len(newL)
visited[idx] = True
cnt+=1
summ+=i[1]
result.append(i)
dfs(cnt, visited, summ, result, totalResult)
newS = set()
tmpL = []
for i in totalResult:
tmpL = sorted(i, key = lambda x:x[0])
tuple_arr = [tuple(i) for i in tmpL]
newS.add(tuple(tuple_arr))
answer = len(newS)
return answer
시간/공간 복잡도
최악의 경우 O(N!)
최적화 및 개선
재귀 함수 호출시 불필요한 매개변수를 삭제함
어려웠던 점
이번 문제는 진짜 어려웠다.
특히 백트래킹을 구현할 때 계속 시간초과가 났다. 분명히 코드는 제대로 작성한것 같다고 생각했다.
코드를 분석해보니, 문제 조건과 카운트 수가 맞아서 totalResult에 삼총사를 추가하고나서 다음 절차를 진행할 때, totalResult내부의 값이 자꾸 바뀌는 문제가 발생했다. 알아보니 리스트를 새로 만들어주지 않고 계속 똑같은 리스트가 뒤에 절차를 진행할 때도 재활용된다는 문제였다. 이를 위해서 리스트 슬라이싱을 통해 새로운 리스트를 만드는 식으로 코드를 변경했더니 문제가 해결됐다.
이 이후에는 자꾸 대부분의 테스트케이스에서 시간 초과가 났다.
진짜 분명 코드는 제대로 작성한 것 같다고 생각했다.
그런데 아뿔싸 설마,,?
재귀 호출을 할때, 카운트 제한(3)을 조건문으로 걸어주지 않아서 시간 초과가 나는건가?
맞았다. 이때문에 불필요한 재귀 호출을 마구마구마구 하기 때문에 시간 초과가 났었다.
해당 조건을 추가해주고 나니 더이상 시간 초과가 나지 않았다.
그리고 리스트 원소를 중복제거 하기 위해서 집합자료형으로 바꾸는 과정에서 애를 먹었다.
그냥 일반 리스트면 몰라도 이중 리스트는 쉽지 않았다!!! 내부의 내부의 리스트를 튜플로 변경시켜주고, 그것들을 감싸고있는 껍데기도 튜플로 변경시켜줘야 한다. 그러면 Hashable 자료형인 튜플로 변경할 수 있게된다..!!!!!!
lv1짜리 문제지만, 내가 알고있는 파이썬 문법에 구멍이 있다는 것을 크게 깨달았다. 이대로 정진!!!!!!!
XX게임에는 피로도 시스템(0이상의 정수로 표현합니다)이 있으며,일정 피로도를 사용해서 던전을 탐험할 수 있습니다.이때,각 던전마다 탐험을 시작하기 위해 필요한"최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는"소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다.예를 들어"최소 필요 피로도"가80, "소모 피로도"가20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는80이상 이어야 하며,던전을 탐험한 후에는 피로도20이 소모됩니다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데,한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다.유저의 현재 피로도k와 각 던전별"최소 필요 피로도", "소모 피로도"가 담긴2차원 배열dungeons가 매개변수로 주어질 때,유저가 탐험할수 있는 최대 던전 수를return하도록solution함수를 완성해주세요.
제한사항
k는1이상5,000이하인 자연수입니다.
dungeons의 세로(행)길이(즉,던전의 개수)는1이상8이하입니다.
dungeons의 가로(열)길이는2입니다.
dungeons의 각 행은 각 던전의["최소 필요 피로도", "소모 피로도"]입니다.
"최소 필요 피로도"는 항상"소모 피로도"보다 크거나 같습니다.
"최소 필요 피로도"와"소모 피로도"는1이상1,000이하인 자연수입니다.
서로 다른 던전의["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.
입출력 예
kdungeonsresult
80[[80,20],[50,40],[30,10]]3
입출력 예 설명
현재 피로도는80입니다.
만약,첫 번째→두 번째→세 번째 던전 순서로 탐험한다면
현재 피로도는80이며,첫 번째 던전을 돌기위해 필요한"최소 필요 피로도"또한80이므로,첫 번째 던전을 탐험할 수 있습니다.첫 번째 던전의"소모 피로도"는20이므로,던전을 탐험한 후 남은 피로도는60입니다.
남은 피로도는60이며,두 번째 던전을 돌기위해 필요한"최소 필요 피로도"는50이므로,두 번째 던전을 탐험할 수 있습니다.두 번째 던전의"소모 피로도"는40이므로,던전을 탐험한 후 남은 피로도는20입니다.
남은 피로도는20이며,세 번째 던전을 돌기위해 필요한"최소 필요 피로도"는30입니다.따라서 세 번째 던전은 탐험할 수 없습니다.
만약,첫 번째→세 번째→두 번째 던전 순서로 탐험한다면
현재 피로도는80이며,첫 번째 던전을 돌기위해 필요한"최소 필요 피로도"또한80이므로,첫 번째 던전을 탐험할 수 있습니다.첫 번째 던전의"소모 피로도"는20이므로,던전을 탐험한 후 남은 피로도는60입니다.
남은 피로도는60이며,세 번째 던전을 돌기위해 필요한"최소 필요 피로도"는30이므로,세 번째 던전을 탐험할 수 있습니다.세 번째 던전의"소모 피로도"는10이므로,던전을 탐험한 후 남은 피로도는50입니다.
남은 피로도는50이며,두 번째 던전을 돌기위해 필요한"최소 필요 피로도"는50이므로,두 번째 던전을 탐험할 수 있습니다.두 번째 던전의"소모 피로도"는40이므로,던전을 탐험한 후 남은 피로도는10입니다.
따라서 이 경우 세 던전을 모두 탐험할 수 있으며,유저가 탐험할 수 있는 최대 던전 수는3입니다.
문제 해결 방법
1. dungeons에서 모두 나올 수 있는 순서에 대해 경우의 수를 순열로 뽑는다.
2. 리스트를 하나 만들고, 순열로 뽑은 모든 경우의 수에 대해서 조건을 따져가면서 던전에 방문한 횟수를 카운트 하여 최종적으로 카운트 한 수를 해당 리스트에 추가한다.
2-1. 위에서 말한 조건으로 각 던전의 최소 필요 피로도가 k와 같거나 커야지 던전에 방문할 수 있으니 해당하는 조건을 체크한다.
from itertools import permutations
def solution(k, dungeons):
answer = -1
cpk=k
cases = list(permutations(dungeons, len(dungeons)))
checkList=[]
for i in range(len(cases)):
cpK=k
checkcheck = 0
for j in range(len(cases[i])):
if cpK >= cases[i][j][0]:
cpK = cpK - cases[i][j][1]
checkcheck += 1
else:
pass
if j == len(cases[i])-1:
checkList.append(checkcheck)
answer = max(checkList)
return answer
주석 포함 코드
from itertools import permutations
def solution(k, dungeons):
answer = -1
#print('k', k, 'dungeons', dungeons)
# 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"
# 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"
#최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됨
#하루에 한 번씩 탐험할 수 있는 던전이 여러개
# 1. dungeons는 [0]기준 MAX를 뽑는다.
# 2. dungeons의 순열을 뽑는다.
cpk=k
cases = list(permutations(dungeons, len(dungeons)))
#print(cases)
checkList=[]
#print("")
for i in range(len(cases)):
#maxx = cases[i][0][0]
cpK=k
#print("1 cpK", cpK)
checkcheck = 0
#print('i', i, cases[i])
for j in range(len(cases[i])):
#print('j', j, cases[i][j])
if cpK >= cases[i][j][0]:
cpK = cpK - cases[i][j][1]
#print('cpK', cpK)
checkcheck += 1
else:
pass
if j == len(cases[i])-1:
checkList.append(checkcheck)
#print("")
#print("")
#print(checkList)
answer= max(checkList)
return answer
dfs를 통해 구현한 현재 코드
def solution(k, dungeons):
answer = []
# k - 현재 피로도, 하루 한번 탐험가능한 던전 dungeons
# 유저가 탐험할 수 있는 최대 던전 수
cnt = len(dungeons)
visited = [False] * cnt
def check2(k, iz, io):
if k >= iz:
return k - io
else:
return None
def check(k, cnt, visited):
answer.append(cnt)
for idx, i in enumerate(dungeons):
cs, sm = i
if check2(k, cs, sm) and visited[idx] == False:
kk = check2(k, cs, sm)
visited[idx] = True
check(kk, cnt + 1, visited)
visited[idx] = False
# 예를들어서 1, 2, 3, 4, 5 가 있는데 조건 때문에 1, 2, 3까지 방문을 마치고 기록을 했다. 근데 이제 1, 2까지 온 상태에서 3을 빼고 나머지 4, 5와도 조합을 했을때 조건이 맞을 수 있기 때문에 3에 대한 방문을 false처리하고 나머지를 탐색해봐야해서
# visited[idx] = False 코드가 필요한 것임.
for idx, i in enumerate(dungeons):
visited = [False] * len(dungeons)
cs, sm = i
if check2(k, cs, sm):
valueK = check2(k, cs, sm)
visited[idx] = True
check(valueK, 1, visited)
print(answer)
answer = max(answer)
return answer
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
문제 해결 방법
triangle을 순회할때, n번째 리스트의 각 원소를 기준으로 n-1번째 리스트에서 자신이 거쳐올 수 있었던 원소 후보 중에서 큰 값을 자신과 더해나가면 된다.
코드 구현
def solution(triangle):
answer = 0
for idx, i in enumerate(triangle):
if idx == 0:
continue
for cnt, j in enumerate(i):
if cnt == 0:
i[cnt] = triangle[idx-1][cnt] + i[cnt]
elif cnt == len(i)-1:
i[cnt] = triangle[idx-1][cnt-1] + i[cnt]
else:
if triangle[idx-1][cnt-1] > triangle[idx-1][cnt]:
i[cnt] = triangle[idx-1][cnt-1] + i[cnt]
else:
i[cnt] = triangle[idx-1][cnt] + i[cnt]
if len(triangle)-1 == idx:
answer = max(triangle[idx])
return answer
다음 그림과 같이 지뢰가 있는 지역과 지뢰에 인접한 위, 아래, 좌, 우 대각선 칸을 모두 위험지역으로 분류합니다.
지뢰는 2차원 배열 board에 1로 표시되어 있고 board에는 지뢰가 매설 된 지역 1과, 지뢰가 없는 지역 0만 존재합니다.
지뢰가 매설된 지역의 지도 board가 매개변수로 주어질 때, 안전한 지역의 칸 수를 return하도록 solution 함수를 완성해주세요.
문제 해결 방법
폭탄 주변에 지뢰와 인접한 지역을 판단할 좌표를 미리 만들어두고, 지도를 탐색할 때, 폭탄이 발견되는 경우, 주변을 지뢰 인접 지역으로 표시하면된다.
코드 구현
def solution(board):
answer = 0
dx = [0, 0, -1, 1, -1, 1, -1, 1]
dy = [1, -1, 0, 0, 1, 1, -1, -1]
m = len(board)
for idx, i in enumerate(board):
for idx2, j in enumerate(i):
if j == 1:
# 상, 하, 좌, 우, 대각선 4개 다 -1칠하기
for k in range(8):
nx = idx+dx[k]
ny = idx2+dy[k]
if nx<0 or ny<0 or nx>=m or ny>=m:
continue
if board[nx][ny]==1:
continue
elif board[nx][ny]==-1:
continue
elif board[nx][ny]==0:
board[nx][ny]=-1
for i in board:
for j in i:
if j == 0:
answer+=1
return answer
하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.
한 번에 하나의 원판만 옮길 수 있습니다.
큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.
1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.
문제 해결 방법
재귀 함수를 이용하여 문제를 해결하면 된다.
n개의 원판을 x에서 y로 움직여야 하는 경우, 로직은 다음과 같다.
1. n-1개의 원판을 x번 기둥에서 6-x-y번 기둥으로 옮긴다. (n이 1이 될 때까지, n이 1이 되는 경우 x번기둥에서 y번 기둥으로 바로 옮겨준다. )
2. n번째 원판을 x번 기둥에서 y번 기둥으로 옮긴다.
3. n-1개의 원판을 6-x-y번 기둥에서 3번 기둥으로 옮긴다. (n이 1이 될 때까지)
(n이 1이 될 때까지, n이 1이 되는 경우 x번기둥에서 y번 기둥으로 바로 옮겨준다. )
n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.
송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.
문제 해결 방법
그래프로 구현하고 dfs로 송전탑의 개수를 세아렸다.
코드 구현
def dfs(newGraph, visited, node):
visited[node] = True
cnt=1
for injeop in newGraph[node]:
if visited[injeop] == False:
cnt += dfs(newGraph, visited, injeop)
return cnt
def solution(n, wires):
answer = -1
# 그래프 생성
graph = [[] for _ in range(n+1)]
for v1, v2 in wires:
graph[v1].append(v2)
graph[v2].append(v1)
Totalcntlist = []
for i in range(1, n+1):
for value in graph[i]:
# print('어디보자---^^^')
# print('graph[', i, ']: ', graph[i], 'value: ',value)
idxOne = graph[value].index(i)
graph[value].remove(i)
idxTwo = graph[i].index(value)
graph[i].remove(value)
cntlist=[]
visited = [False] * (n+1)
for j in range(1, n+1):
if visited[j] == False:
cnt = dfs(graph, visited, j)
cntlist.append(cnt)
# print(cntlist)
sum = abs(cntlist[0]-cntlist[1])
Totalcntlist.append(sum)
# graph[value].append(i) # 문제의 코드
# graph[i].append(value)
# print('graph[', i, ']: ', graph[i])
# print('결과보자 ---vvv')
graph[value].insert(idxOne, i)
graph[i].insert(idxTwo, value)
answer = min(Totalcntlist)
return answer
def solution(N, road, K):
answer = 0
distances = [float("inf")] * (N+1)
distances[0] = 0 # 0과 1은 사용하지 않음
distances[1] = 0
for i in range(N-1):
for i in range(1, N+1):
for nodeSet in road:
fromm, to, weight = nodeSet
if fromm == i:
distance = distances[i] + weight
if distance < distances[to]:
distances[to] = distance
to, fromm, weight = nodeSet
if fromm == i:
distance = distances[i] + weight
if distance < distances[to]:
distances[to] = distance
# N개의 마을 중에서 K시간 이하로 배달이 가능한 마을에서만 주문을 받으려고함
# 1번 마을에 있는 음식점이 음식 주문을 받을 수 있는 마을의 개수를 return
# a, b = 마을의 번호 c = 도로를 지나는데 걸리는 시간
# 그래프 만들기
answer +=1
for i in distances:
if i <= K and i>0:
answer+=1
return answer
시간/공간 복잡도
O((N+E)N)
최적화 및 개선
하지않음...
어려웠던 점
양방향 이동이라는 점을 잘 새겨봤어야 했다. 코드를 짜다보니 나도 모르게 단방향으로 코드를 작성했다.
다익스트라 알고리즘은 n-1번 반복해야 하는 것을 잘 기억해야겠다.
처음에 코드 작성후, 채점하니 40점이 나왔는데 혹시나 해서 최단거리 구하는 코드를 한번더 복사 붙여넣기 한 후 채점하니 50점이 나왔다. 그 후 힌트를 얻기위해 책을 한번더 보고, 그 후 한번 더 복사 붙여넣기 하니 80점이 나왔는데 그때 깨달았다..
네트워크란컴퓨터상호간에정보를교환할수있도록연결된형태를의미합니다. 예를들어, 컴퓨터 A와컴퓨터 B가직접적으로연결되어있고, 컴퓨터 B와컴퓨터 C가직접적으로연결되어있을때컴퓨터 A와컴퓨터 C도간접적으로연결되어정보를교환할수있습니다. 따라서컴퓨터 A, B, C는모두같은네트워크상에있다고할수있습니다.
컴퓨터의개수 n, 연결에대한정보가담긴 2차원배열 computers가매개변수로주어질때, 네트워크의개수를 return 하도록 solution 함수를작성하시오.
문제 해결 방법
이런 문제는 최적의 해 보다는 모든 요소를 탐색하는 것이 목적이다.
모든 요소를 탐색하기 위해 DFS가 좋다.
computers를 그래프로 표현한 후, 방문 테이블을 만들고, 방문 테이블을 통해 그래프를 DFS로 몇번 탐색 했는지를 출력하면 된다.
def dfs(computers, visited, node):
visited[node] = True
for idx, connected in enumerate(computers[node]):
if connected and not visited[idx]:
dfs(computers, visited, idx)
def solution(n, computers):
answer = 0
visited = [False] * n
for i in range(n):
if not visited[i]:
dfs(computers, visited, i)
answer += 1
return answer
def dfs(computers, visited, node):
# 조회를 하면 해당 노드에 대해 방문처리를 해준다.
# 해당 노드를 통해 computers에 딸린 다른 노드들을 반복문을 통해 조회하고,
# 연결 여부와 방문 여부를 확인한다.
# 연결된 것을 통해 깊이 우선 탐색을 계속 해나간다.
visited[node] = True
for index, connected in enumerate(computers[node]):
if connected and visited[index] == False:
dfs(computers, visited, index)
def solution(n, computers):
answer = 0
# 방문여부를 담는 크기 n만큼의 배열
visited = [False] * n
for i in range(n):
if visited[i] == False:
dfs(computers, visited, i)
answer+=1
# 반복문을 통해 노드를 0~n까지 순회하며 깊이 우선 탐색을 한다.
# 깊이 우선 탐색 dfs에는 computers라는 그래프와, visited, 그리고 노드를 보내준다.
# 깊이 우선 탐색이 끝나면 answer +1 을 해준다.
return answer
