youngseo's TECH blog

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

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

비트마스킹을 이용하면 굳이 배열을 쓰지 않아도 되므로 메모리도 절약될 뿐만 아니라 배열의 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 사다리 문제. 일단 문제 파악이 쉽지 않아 여러 사다리를 마구 만들어봤다. 생각노트 세로선이 - - 이렇게 똑같은 높이에 그어지면 안된다. 앞에서부터 최대한으로 만족 시키다가 아무리 앞을 바꿔도 뒤에서 더이상 안되는 경우가 생긴다. 위의 경우처럼. 선을 추가하는 경우와 추가하지 않는 경우를 생각해볼 수 있는데, 선을 추가하는 경우 그 칸이 홀수일 때, 선을 추가하지 않는 경우는 그 칸이..

문제정리 https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net 생각노트 두 자동차가 가는 길이 있다고 했을 때 어떻게 하면 최소로 갈 수 있을까. 이때 각 자동차를 "무조건 가까운 곳"으로 선택해서 가는 방법은 조금 생각해보면 안 된다는 것을 알 수 있다. 몇 번째 사건을 누가 처리하느냐에 따라 의존성이 계속해서 바뀌기 때문이다. (아무리 경찰차2랑 현재 거리에서는 가깝다고 하더라도 경찰차1이 사건 1,2,3을 처리하다가 더 ..