log 2021-09-02
sport
코테연습 - kakao 2021 다시풀기
카드 짝 맞추기
다시시도.
저번 접근 방법의 문제점:
- 집합을 사용하니 포문 안에서 다른 같은 타입의 카드를 찾기가 어려움.
- 최소 비용 이동을 위해 보드 정보가 결국 필요함.
- 그냥 완전 탐색은 어떤 문제가 있나?
- 일단 탐색 순서는 최대 2^6 * 6! (각 카드 종류당 어느 카드를 먼저 할 지 * 어떤 카드 종류 순서로 할 지) 가지가 있고, 그래봐야 얼마 되지 않는다. 문제는 이런 탐색 순서를 구현하는 것과, 한 카드를 선택했을 때 다른 카드를 최소 비용으로 찾아야 한다.
- 백트래킹으로 시도해볼 예정
- 백트래킹으로 탐색하려면, 결국 재귀로 짜야 하는 것 아닌가.
- 카드 번호 정보와 위치를 어떻게 관리하는게 좋을 까? 번호 기준? 인덱스 기준?
- 생각을 좀 해보자. 재귀를 어떻게 짜야 하는가. 아예 그냥 퍼뮤테이션으로 만들어서 하는건 어떨까
- 그렇게 했더니 결국 시간초과가 났다. 모든 카드들을 퍼뮤테이션 돌려서, 각 퍼뮤테이션을 그 순서대로 다익스트라로 따라가도록 시뮬레이션 했는데, 매 번 cost 테이블 초기화 및 탐색을 해야 해서 연산량이 많은 듯하다.
- 그렇다면, 어떻게 해야 캐싱을 할 수 있을까. 현재 위치와 남은 카드의 종류가 같다면 무조건 답은 같게 된다.
- 즉 상태는 (현재 위치+남은 카드 집합)으로 결정된다.
- 문제는, 이 캐시에 언제 할당을 해주어야 하는지 모른다는 점이다.
- 현재 상태로서는 전체 시뮬레이션을 시행하고 나면 이전의 상태들을 모르고, 완료 전에는 최종 비용을 알 수가 없다.
- 그렇다면, 들어간 비용 기록들을 이용하여, 시행 완료 후에 (전체 패턴 (1,2,3,…,6), (2,3,…,6) 이런 모든 부분 패턴들에 대해, dp(당시 위치, 남은 카드 집합)로 캐싱하면 될 듯하다.)
- 이렇게 하려면 반복문을 어떻게 해야 하나?
- 위와 같은 방식으로 캐싱을 해도 왜인지 틀린다. 아무래도 그 이후로 업데이트 가능이 있어서 아닌가 싶은데,
-
궁금한 점: 사실 (현재 위치+선택한 카드 집합)으로 보고 남은 최소 비용으로 생각해도 같지 않나?
결국 다른 블로그 참고함. 다른 블로그에서는 dp같은 방식이 아니라 그냥 bfs로 탐색함. 또한, 매번 상태공간 배열을 복사하는 대신, 문자열로 맵을 나타냄.
이걸 알고 다시 짜보았는데도 자꾸 틀리는데, ctrl 이동 함수의 로직에 문제가 있었다. 무슨 차이인지는 잘 모르겠다.
py move function
def move(b, r, c, dr, dc):
nr, nc = r + dr, c + dc
if(nr >= 0 and nr < 4 and nc >= 0 and nc < 4):
if(b[nr*4+nc] != 0):
return (nr, nc)
return move(b, nr, nc, dr, dc)
return (r, c)
# def move(b, y, x, dy, dx):
# ny, nx = y + dy, x + dx
# if ny >= 0 and ny < 4 and nx >= 0 and nx < 4 and b[ny * 4 + nx] == "0":
# return move(b, ny, nx, dy, dx)
# else:
# if ny >= 0 and ny < 4 and nx >= 0 and nx < 4:
# return (ny, nx)
# else:
# return (y, x)
아래가 해당 블로그에서의 이동 함수고, 위가 직접 짠 것인데, 어떤 경우에 예외상황이 되는지 잘 모르겠다.
…찾았다. 비교에서 숫자 0이 아니라 ‘0’을 썼어야 했다…
py solution
from collections import deque
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def move(b, r, c, dr, dc):
nr, nc = r + dr, c + dc
if(nr >= 0 and nr < 4 and nc >= 0 and nc < 4):
if(b[nr*4+nc] != '0'):
return (nr, nc)
return move(b, nr, nc, dr, dc)
return (r, c)
def end(b):
return b.count('0') == 16
def remove_element(b, e):
b = b.replace(e, "0")
return b
def solution(board, r, c):
best = 999999999
b = ''
for row in range(4):
for col in range(4):
b += str(board[row][col])
q = deque()
visited = set()
cost = 0
enter = -1
state = (r, c, cost, b, enter)
q.append(state)
while(len(q) > 0):
r,c,cost,b,enter = q.popleft()
# print('state', r, c, cost, b, enter)
pos = 4*r+c
if((r,c,b,enter) in visited):
continue
visited.add((r,c,b,enter))
if(end(b)):
return cost
# 1. 기본 이동
for (dr, dc) in d:
nr = r + dr
nc = c + dc
if(nr < 0 or nr >= 4 or nc < 0 or nc >= 4):
continue
q.append((nr, nc, cost+1, b, enter))
# 2. ctrl 이동
for (dr, dc) in d:
# (nr, nc) = move(dr, r, c, b)
(nr, nc) = move(b, r, c, dr, dc)
if (nr == r and nc == c):
continue
q.append((nr, nc, cost+1, b, enter))
if b[pos] != 0:
if enter == -1:
n_e = pos
q.append((r, c, cost+1, b, n_e))
else:
if enter != pos and b[enter] == b[pos]:
b = remove_element(b, b[enter])
q.append((r, c, cost+1, b, -1))
return best
코테연습 - kakao 2020 다시풀기
괄호 변환
그냥 그대로 구현함.
py solution
from collections import deque
def process(s):
if(s == ''):
return ''
oc=cc=0
idx = 0
u = deque()
v = []
check = []
right = True
while(oc != cc or oc == 0):
nex = s[idx]
if(nex == '('):
oc+=1
check.append('(')
else:
cc+=1
if(check):
check.pop()
else:
right = False
u.append(nex)
idx+=1
while(idx<len(s)):
v.append(s[idx])
idx+=1
# print('u', u, 'v', v)
vv = ''.join(v)
if(right):
return ''.join(u) + process(vv)
else:
gen = '(' + process(vv) + ')'
u.popleft()
u.pop()
li = list(u)
# reverse two symbol ( <-> ) for u
uu = [ '(' if x == ')' else ')' for x in li]
return gen + ''.join(uu)
blog
들은 취업 팁
- 최대한 지원
- 면접 경험으로 피드백
- 그 회사 그 팀에서 하는 일 알거나 하면 가능성 높음
Comments