youngseo's TECH blog

세상에서 제일 화나는 TOP DOWN DP 유형이다. 저번 글에서 본 것처럼 DP-TOPDOWN의 형식적인 코드는 다음과 같다 (느낌만 알아두자) def topdown: if 마지막 노드에 다다른 조건: return ~~ if 이미 DP 테이블에 값이 있다면(memoization): return 그냥 그거 가져온다. #밑에 있는 노드를 호출해서 답 갱신 + 필요하다면 DP 테이블에도 값 갱신 DP[][]+= 또는 min .. topdown() return 해당 노드값 이 문제에서는 ‘되냐 안되냐’의 문제를 다룬다. 이럴 때 0, 1, max를 사용해서 풀 수 있다. 만약 조건에 만족하는 것이 하나라도 나올 시에는 return 1을 하고 안 나오면 계속 return 0을 한다. memoization 방법은..

일단 이 문제는 구현이 되게 생소하고 어렵다. 그래프를 표현하는 방법에 대해 생각을 많이 해볼 수 있는 문제라 좋다. 그래프를 배울 때 가장 먼저 배우는 것이자 많이 사용하는 것이 바로 계산하는 순서인 전위/중위/후위 표기식이다. 이런 표기식을 잘 생각해 보면서 문제를 풀어야 한다. 잘 나타내 보면, 규칙은 다음과 같다. ‘+’일 때는 그냥 내려간다. ‘-’일 때는 -오른쪽 자식의 상태를 switch 시킨다. -왼쪽은 그냥 내려간다. 이런 식으로 계속 상태를 바꾸어 주다가 마지막 노드인 1~N까지의 수에 도달하였을 때 연산자가 -라면 -가 몇 개 나오는지 모두 더해준다. 마지막으로 -의 개수(만약 3개라면) 에 따라서 가장 작은 수(3개)의 개수만큼을 최소 heapq에서 뽑아 SUM 값에서 빼준다. SU..

지금껏 다익스트라는 adj라는 배열만 만들어서 사용했었는데, 이 문제는 dijkstra를 눈치채고 다익스트라를 구현하기까지 쉽지 않았다. 일단 맨 처음 문제를 보았을 때에는 floodfill 먼저 떠올랐는데(GridWorld라서 더 그랬다), floodfill과는 결이 다르다. 왜냐면 이미 갔던 곳도 더 빠른 방법이 있다면 왼/오/위/아래 의 방법을 선택해서 빠른 방법으로 갱신해낼 수 있기 때문이다. 그래서 가중치를 가지는 다익스트라로 구현할 수 있다. 다익스트라의 특징은 다음과 같다. 가중치가 모두 양수이다. 방문하지 않은 노드 중 최단 거리인 노드를 선택하는 과정을 반복한다. 각 단계마다 탐색 노드로 한 번 선택된 노드는 최단 거리를 갱신하고, 그 뒤에는 더 작은 값으로 다시 갱신되지 않는다. 우선순..

밑은 내가 맨 처음에 호다닥 작성한 코드. 그리고 시간초과를 받았다😥 bottom up 방식으로, 외판원이 현재 위치에서 갈 수 있는 위치로 간 후 갱신 -> 다시 그 위치에서 갈 수 있는 위치로 간 후 갱신 ---> 이 방법을 반복하였다. 어떻게 보면 DFS 느낌?으로 해결하려 했다.(이 발상이 이게 참 문제임 ) 이 코드의 문제는 DP에서 가장 중요한 문제인 MEMOIZATION이었다. DP 테이블을 갱신하는 방법은 이미 계산된 결과 이용하기 가 바탕이고, 다양한 방법이 있는데, 내가 짠 건.. 앞에서 왔던 길을 보는 게 아니라 갈 길에 체크를 하는 ,, 아주 바보같고 느린 방법을 사용했다. 암튼 이 코드는 매우 비효율적. '차곡차곡 쌓자'라는 접근방식을 자꾸 생각하는 걸 줄여나갈 필요가 있다. 배낭..

분할정복의 시간복잡도는 NlogN이다. (단계 별 문제 개수 (N//2^K) X 해당 단계에서 쪼개는/병합하는 시간(2^K) X 단계 개수(크기가 이진탐색 수준으로 줄기 때문에 logN)) 이것을 밑으로 내려가면서 쪼갤 때 / 위로 올라오면서 병합할 때 2번해서 어차피 2 NlogN이므로 시간복잡도는 그냥 NlogN이다. (DP테이블은 문제 종류가 M이라고 하면 O(NM)이라 더 효과적인 것을 확인할 수 있음) ★DP와 다른 점 부분 문제가 서로 중복되지 않는다. 위 사항 덕분에 Memoization이 필요하지 않다. 굳이 내가 알아낸 데이터를 저장하지 않는다. ★이분탐색트리 또는 세그먼트 트리와 다른 점 이분탐색/세그먼트는 일단 아는 노드를 쭉 나열해 두고 둘씩 짝지어서 위로 올라가며 판단하는 과정을 ..

binary search, 이분법적으로 딱 ' 이 시간. 이 숫자. 이 갯수 '를 구하고 싶을 때 매우 강력한 툴이다. 하지만 너무 생각할 게 많다.. 그래서 꾸준히 정리를 해보도록 하겠다!!! (자꾸 끼워 맞추면서 풀다가 실전에서 시간 너무 오래 잡지 말자...) [1, 2, 3, 3, 3, 3, 4, 5, 5] 라는 배열이 있다. 우리는 3을 찾고 싶다. 음.. 3 중에서도 가장 최소의 index를 가지는 3을 찾고 싶다면, 이렇게 mid가 가장 왼쪽을 향하게 하도록 극한으로 몰아세운다. (직접 해보면 이해 잘 됨) while lo target: return binary_search(array, target, start, mid) #중간값의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 elif ar..

비트마스킹을 이용하면 굳이 배열을 쓰지 않아도 되므로 메모리도 절약될 뿐만 아니라 배열의 index로도 쓸 수 있어(0001은 1로, 0010은 2로 쓸 수 있다.) 매우 강력한 툴이다! 주로 있다/없다 의 이분법적 현상을 반영해서 표현할 수 있다. 이것만 알면..!! 된다!! & -> 모두 1일때 1반환 | -> 하나라도 1일때 1 반환 / 모두 0일 때 0반환 ^ -> 대응하는 두 비트가 서로 다를 때 1반환 >> -> 오른쪽으로 비트 옮김 100>>2:1 ★삽입 시! i번째 비트를 i값으로 변경할 때 10101에서 11101 만들고 싶다면 10101 | 1

문제정리 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 사다리 문제. 일단 문제 파악이 쉽지 않아 여러 사다리를 마구 만들어봤다. 생각노트 세로선이 - - 이렇게 똑같은 높이에 그어지면 안된다. 앞에서부터 최대한으로 만족 시키다가 아무리 앞을 바꿔도 뒤에서 더이상 안되는 경우가 생긴다. 위의 경우처럼. 선을 추가하는 경우와 추가하지 않는 경우를 생각해볼 수 있는데, 선을 추가하는 경우 그 칸이 홀수일 때, 선을 추가하지 않는 경우는 그 칸이..