게임 맵 최단거리
1. Problem
2. My Solution
- BFS 알고리즘 사용
from collections import deque
def bfs(x,y,depth,maps):
n = len(maps)
m = len(maps[0])
move = [(-1,0),(1,0),(0,-1),(0,1)]
queue = deque()
queue.append((x,y,depth))
maps[x][y] = 0
while (queue):
x,y,depth = queue.popleft()
if x == n-1 and y == m-1:
return depth
for dx, dy in move:
nx = x + dx
ny = y + dy
if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1:
queue.append((nx,ny,depth+1))
maps[nx][ny] = 0
return -1
def solution(maps):
return bfs(0,0,1,maps)행렬 테두리 회전하기
1. Problem
2. My Solution
- 테두리 부분을 하나의 list 로 쫙 펼친다고 생각 (펼치는 순서는 상,우,하,좌)
- 펼칠 경우 원래의 테두리 좌표를 기억하기 위해 (x,y) 값을 갖는
target_loc - 회전하기 전의 테두리의 값과 회전한 후의 테두리의 값을 갖는
target_val target_loc의 좌표 공간에 순서대로 회전시킨target_val값을 삽입target_val에서 가장 작은 값을 answer 에 삽입하면 됨- 모서리 부분이 겹치므로 상,우,하,좌 순서로 좌표를 매핑할 때 끝 부분은 생략
from collections import deque
def rotate_and_find(x1,y1,x2,y2,arr):
target_loc = []
target_val = deque()
# 상
for y in range(y1,y2):
target_loc.append((x1,y))
target_val.append(arr[x1][y])
# 우
for x in range(x1, x2):
target_loc.append((x,y2))
target_val.append(arr[x][y2])
# 하
for y in range(y2, y1, -1):
target_loc.append((x2,y))
target_val.append(arr[x2][y])
# 좌
for x in range(x2, x1, -1):
target_loc.append((x,y1))
target_val.append(arr[x][y1])
# rotate
target_val.appendleft(target_val.pop())
# find_min
min_val = min(target_val)
# rotate_apply
for x,y in target_loc:
arr[x][y] = target_val.popleft()
return min_val
def solution(rows, columns, queries):
answer = []
arr = [[0] * (columns+1) for _ in range(rows+1)]
# 행렬에 숫자 지정
for i in range(1,rows+1):
for j in range(1,columns+1):
arr[i][j] = ((i-1) * columns + j)
for x1,y1,x2,y2 in queries:
answer.append(rotate_and_find(x1,y1,x2,y2,arr))
return answer빛의 경로 사이클
1. Problem
2. My Solution
- 격자 모임을 행렬(2차원 리스트)로 다룬다
- 모든 격자에서 상하좌우 빛을 쏴본다 (0,1,2,3 을 이용해서 방향을 매핑한다)
- R, L 격자일 때 움직일 좌표를 어떻게 뽑아낼 것인가 ? -> 하드코딩 ?
- 경로를 어떻게 저장할 것인가 ? -> (x,y,방향) ?
- 경로가 이미 존재하는 지 어떻게 판단할 것인가 ?
위와 같이 문제 해결에 필요한 로직을 뽑아냈지만 3,4,5 구현하는 방법을 생각해내지 못했음
3. Others' Solutions
-
1,2,4,5 번 해결
- 3차원visited[x][y][나가는 방향]을 이용하여 해당 격자에서 특정 방향으로 빛을 쏴보고(2번), 또한 나간적이 있는지 판단한다. 만약 빛이 나가야되는 방향으로 이미 나간적이 있다면 (3차원 값이 True) 빛을 쏜 격자로 다시 돌아왔다는 의미이고 동시에 싸이클이 형성되었다는 의미이므로 이동 횟수를 return 하면됨(4번 필요없음). 또한 빛을 쏴야되는 방향값이 True 라면 해당 싸이클은 이미 count 되었으므로 pass 하면됨(5번) -
3 번 해결
- 빛의 방향을 시계방향[↑,→,↓,←][(-1,0),(0,1),(1,0),(0,-1)]으로 매핑하게끔 설정하고 들어오는 방향에 +1 하면 오른쪽으로 방향을 틀고, -1 하면 왼쪽으로 방향을 틀게끔 구현할 수 있음
if grid[x][y] == 'R':
d = (d+1) % 4
if grid[x][y] == 'L':
d = (d-1) % 4- 재귀방법
import sys
sys.setrecursionlimit(10**8)
move = [(-1,0),(0,1),(1,0),(0,-1)]
def light(x,y,d,grid,cnt):
dx, dy = move[d]
nx = (x + dx) % n
ny = (y + dy) % m
if grid[nx][ny] == 'R':
d = (d+1) % 4
if grid[nx][ny] == 'L':
d = (d-1) % 4
if visited[nx][ny][d] == True:
return cnt
else:
visited[nx][ny][d] = True
return light(nx,ny,d,grid,cnt+1)
def solution(grid):
global n,m, visited
answer = []
n = len(grid)
m = len(grid[0])
visited = [[[False] * 4 for _ in range(m)] for _ in range(n)]
for x in range(n):
for y in range(m):
for d in range(4):
if visited[x][y][d] == False:
answer.append(light(x,y,d,grid,0))
answer.sort()
return answer- while 루프 방법
move = [(-1,0),(0,1),(1,0),(0,-1)]
def light(x,y,d,grid):
cnt = 0
while (True):
dx, dy = move[d]
x = (x + dx) % n
y = (y + dy) % m
if grid[x][y] == 'R':
d = (d+1) % 4
if grid[x][y] == 'L':
d = (d-1) % 4
if visited[x][y][d] == True:
return cnt
else:
visited[x][y][d] = True
cnt += 1
def solution(grid):
global n,m, visited
answer = []
n = len(grid)
m = len(grid[0])
visited = [[[False] * 4 for _ in range(m)] for _ in range(n)]
for x in range(n):
for y in range(m):
for d in range(4):
if visited[x][y][d] == False:
answer.append(light(x,y,d,grid))
answer.sort()
return answer
4. Learned
global키워드를 이용하여 전역변수로 지정할 수 있고, 또한 사용할 수 있음- 특정한 입력에 대해서 특정한 결과를 내는 방법은 하드코딩 보단 규칙을 구현하는 것이 좋음
- 참고 블로그 1, 참고 블로그 2
가장 큰 수
1. Problem
2. My Solution
- permutations 함수를 이용하여 조합을 다 구해봄 -> 시간초과
from itertools import permutations
def solution(numbers):
possible = list(permutations(numbers, len(numbers)))
possible_str = []
for i in possible:
possible_str.append(''.join(map(str,i)))
return max(possible_str)아래와 같은 방법을 생각해봄
- 숫자를 string 형태로 바꿈
- 맨 앞에 오는 수가 큰 순서대로 조합되어야함
- 따라서 아래와 같이 정렬
sort.arr(key = lambda x:(-x[0],-x[1],-x[2],-x[3])
하지만 자릿수가 1개인 것은 인덱스 에러가 발생하는 문제가 있기 때문에 자릿수를 맞추기 위해서 0으로 채운다 ? 도 생각해봤지만 1, 10, 100, 1000 을 구별할 방법이 없음. 또한 5, 54 는 5000, 5400 이 되서 545 가 됨 (554가 정답)
3. Others' Solutions
- 자릿수를 0으로 채우지말고 x*3 을 이용하여 채움
- 문자열 값들을 바로 (내림차순)정렬하면
sort.arr(key = lambda x:(-x[0],-x[1],-x[2],-x[3])처럼 적용됨 - 마지막에 int로 변환 후 다시 str 변환하는 이유는 모든 원소가 0일 때를 처리하기 위함
def solution(numbers):
numbers = list(map(str, numbers))
numbers.sort(key=lambda x: x * 3, reverse=True)
return str(int(''.join(numbers)))
4. Learned
- int 자료형을 정렬하면 숫자 크기 그대로 정렬되지만, str 자료형을 정렬하면 각 자리 순서대로 정렬
- 커스텀 정렬을 위해서 lambda 문법을 사용할 때, 정렬하는 원소의 값 그자체가 아닌 커스텀한 결과값으로 정렬할 수 있다는 사실을 잊지 말자
괄호 회전하기
1. Problem
2. My Solution
- 스택을 이용한 괄호 문제 해결법을 사용
- 올바른 괄호를 찾는 것이 아닌, 올바르지 않는 괄호의 경우를 찾아 break 를 통하여 시간을 단축
- s의 길이가 홀수인 경우
- 올바른 괄호를 회전 시킨 다음 괄호 (올바른 괄호에서 바로2회전)
- [{( 이 아닌 )}] 중에서 스택에 처음 삽입될 경우
- pop 한 괄호와 비교할 괄호가 다른 경우
위 경우 어느 것도 속하지 않으면 올바른 괄호임
from collections import deque
def solution(s):
if len(s) % 2 == 1:
return 0
answer = 0
s = deque(s)
pre = False
for x in range(len(s)):
stack = []
s.append(s.popleft())
flag = True
if pre == True:
pre = False
continue
for i in s:
if i in ["[", "{", "("]:
stack.append(i)
elif not stack:
flag = False
break
else:
j = stack.pop()
if (j == "[" and i != "]") or \
(j == "{" and i != "}") or \
(j == "(" and i != ")"):
flag = False
break
if flag == True:
answer += 1
pre = True
return answer
3. Learned
- Boolean 변수 삽입 연산을 자주
==연산으로 코딩하여 잘못된 부분을 찾느라 시간이 걸리는 경우가 자주 있는데 조심하자 !
배달
1. Problem
2. My Solution
- heapq (우선순위큐)를 사용하여 다익스트라 알고리즘을 구현
- heapq.heappop(h)가 되었다는 것은 최소 거리로 선택되었다는 것인데, 해당 거리가 더 크다는 것은 이미 처리된 노드라는 의미임. 변경될 때마다 heapq에 삽입되는 상황에서 만약 [(5,1), (4,1), (3,1)] 순으로 삽입되었다고 치면 (3,1) 이 제일 먼저 나가게되고 이는 heapq.heappop(h)가 수행되면서 최소거리가 판별된 것임. 그 다음 (4,1), (5,1) 은 전부 3보다 크므로 이미 처리된 것이라고 생각할 수 있음
import heapq
def dijkstra(start):
h = []
distance[start] = 0
heapq.heappush(h, (0,start))
while h:
dist, now = heapq.heappop(h)
if distance[now] < dist:
continue
for edge in graph[now]:
cost = dist + edge[1]
if cost < distance[edge[0]]:
distance[edge[0]] = cost
heapq.heappush(h,(cost,edge[0]))
def solution(N, road, K):
global distance, graph
answer = 0
inf = 10e10
distance = [inf] * (N+1)
graph = [[] for _ in range(N+1)]
for a,b,dist in road:
graph[a].append((b,dist))
graph[b].append((a,dist))
dijkstra(1)
for dist in distance:
if dist <= K:
answer += 1
return answer
3. Learned
- 다익스트라 알고리즘 구현 방법을 알게됨 (참고 유튜브)
- 리스트(배열) 방식은 고정된 크기의 distance 배열을 매번 순차탐색
- 우선순위큐 방식은 거리가 변경된 것 (측정된 것)들만 우선순위큐에 넣고 판단
- 시간복잡도는 평균적으로 우선순위큐 방식이 더 빠르지만, 정점의 개수가 적거나 간선의 개수가 매우 많다면 기본방식을 사용하는 것이 더 빠를 수가 있음 (참고 블로그)
- 우선순위큐에 튜플을 삽입하면 0번째 인덱스 원소를 기준으로 정렬이되는데, 기준을 변경하고 싶으면 아래코드처럼 바꿀 수 있음
예상 대진표
1. Problem
2. My Solution
- 대회 선수 참가 -> 큐 자료구조를 이용하여 순서대로 선수를 집어넣음
- 2명의 선수가 게임을 진행 -> 앞에서 2명의 선수를 pop
- 승자는 다음 라운드로 올라감 -> p1 이 이겼다고 하고 p1을 push
- 만약 p2 가 A 또는 B 라면 p2 를 push
- 다음 라운드로 올라가는 참가자는 n/2 명이므로 남은 참가자가 수가 round/2 명이면 라운드를 +1
from collections import deque
def solution(n,a,b):
# round of 8 = 8강
round = n
answer = 1
player_list = deque(range(1,n+1))
while(round > 1):
if len(player_list) == (round//2):
round //= 2
answer += 1
p1 = player_list.popleft()
p2 = player_list.popleft()
if (p1 == a and p2 == b) or (p1 == b and p2 == a):
break
if (p2 == a or p2 == b):
player_list.append(p2)
else:
player_list.append(p1)
return answer피로도
1. Problem
2. My Solution
- 최대값을 구하는 것이므로 그리디, DP, 브루트포스 알고리즘을 생각해봄
- 그리디를 이용한다면 매번 최선이되는 선택을 해야되는데, 그 선택 기준이 최소 필요 피로도가 낮은 순이여도 보장이 안되고 소모피로도가 낮은 순도 보장이 안됨
- DP를 이용한다면 던전의 개수를 n으로 설정할 수밖에 없는데, 던전이 하나 추가될 때마다 매번 모든 경우의 수를 따져봐야함
- 입력의 수가 최대 8이므로 브루트포스를 사용해도됨 -> 순열(permutations)이용
- n = 8, 8! = 40320 이므로 시간초과가 발생할 걱정은 없음
from itertools import permutations
def solution(k, dungeons):
routes = list(permutations(dungeons,len(dungeons)))
answer = 0
for route in routes:
cnt = 0
p = k
route = list(route)
while(route):
if route[-1][0] > p:
break
p -= route.pop()[1]
cnt += 1
answer = max(answer, cnt)
return answer
3. Learned
- 문제해결에 적용가능한 알고리즘 기법들을 생각해내고 하나씩 구현 가능한지 판단해보자
- 입력값의 범위는 사용 가능한 알고리즘을 암시한다
다단계 칫솔 판매
1. Problem
2. My Solution
- dict 자료형을 이용해서 문제에서 주어진 정보들을 한 번에 담음
- DFS 를 통해서 리프노드까지 간 후에 다시 루트까지 return 을 통해 복귀하면서 commission 값과 net_profit 값을 계산해나감 (예를들어 mary 는 commissions [12,2,450] 을 받게되고 자신은 [11,2,45] 에다가 자신의 판매금의 90% 를 더해 net_profit 을 가져가게됨)
10%를 계산한 금액이 1 원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.문제 조건 때문에 실적을 합산해서 DFS 를 수행하면 안되고 각각 나눠서 계산해야함
import sys
sys.setrecursionlimit(10**8)
def dfs(start):
commission = []
net_profit = []
for i in member[start][2]:
profit = i * 100
commission.append(int(profit * 0.1))
net_profit.append(profit - int(profit * 0.1))
for i in member[start][1]:
commissions = dfs(i)
for j in commissions:
if int(j * 0.1) < 1:
net_profit.append(j)
else:
net_profit.append(j - int(j*0.1))
commission.append(int(j*0.1))
member[start][3] = sum(net_profit)
return commission
def solution(enroll, referral, seller, amount):
global member
# {'나': [부모, 자식들[], 실적, 이익}
member = {'center':['',[],[],0]}
# 멤버 조직도 구성
for i in range(len(enroll)):
me = enroll[i]
parent = referral[i]
# {'나': [부모, 자식들[], 실적, 이익}
member[me] = ['',[],[],0]
if parent == "-":
member[me][0] = 'center'
member['center'][1].append(me)
else:
member[me][0] = parent # 나에다 부모 넣고
member[parent][1].append(me) # 나를 부모에 넣고
# 멤버 실적 반영
for i in range(len(seller)):
member[seller[i]][2].append(amount[i])
dfs('center')
return [member[i][3] for i in enroll]
3. Others' Solutions
- DFS 를 통해서 leaf 노드까지 내려갈 필요 없이 임의의 노드를 잡고 커미션을 계산후 부모로 올려주면 됨
