남남서의 블로그

ㄴ

A번. 그냥 위치가 x에 있으면 x+(a_x) 로 이동한다는 말 같아서 대충 했더니 잘 된거같다.B번.연결되어있는 수(=교환할 수 있는 수)들을 BFS로 묶고, 정렬해서, 재배치하고, 끝.그런데 지금 보니까 시스템 테스트 통과를 못했다. 어...?C번.첫 번째로 읽을 책과, 나머지 책들을 생각해보자.첫 번째 책이 중간에 꽂혀있으면, 그걸 다 들어내고 읽어야 하고, 결국 나머지 책들의 순서는 그대로인채 첫번째 책만 제일 위에 놓이게 된다.그러면 애초에 아무것도 안 드는게 이득이겠지? 그래서 첫 번째로 읽을 책은 제일 위에 가야 한다.두 번째로 읽을 책을 찾기 위해 다른 책들을 들어낼 때도, 어차피 그 두번째 책이 어디에 꽂혀있었든 결과는 같다.그렇다면 최소한으로 책을 드는 것이 최적이겠고, 첫번째 책이 방..

일단 이 문제는 대충 짠 소스가 200줄이 넘는다 (...)솔직히 너무 복잡한 것 같다. 일단, 모든 정점을 두 가지로 나눈다.(이 작업이 꼭 필요하진 않지만 이렇게 안하면 아마 400줄쯤 됐던 것 같다... 디버깅도 힘들어서 포기함) 한 정점은 가장 아름다운 길로 가고, 한 정점은 두 번째로 아름다운 길로 간다.그러고 나서는 각 간선을 '잘 생각해서' 연결한다(...) 그러니까, 첫 번째 정점에 연결해야 할지 두 번째 정점에 연결해야 할지를 잘 따지면서 연결하면 된다.그러면 전체 그래프는 방향 그래프가 되고, 각 정점은 최대 한 개의 사이클에 포함되게 된다. 모든 방문되지 않은 정점에서 DFS를 돌면서, 이미 탐색한 정점 만나면 거꾸로 가면서 P까지의 거리를 기록해준다.예를 들어 한 점에서 사이클 까지..

Baekjoon Online Judge 링크(5813) 어떤 이상적인 도시가 있다. 이 곳은 구획들이 블럭으로 이루어지는데, 이 도시에는 구멍이 없다. 즉 블럭이 없는 곳 사이에는 항상 경로가 있고, 블럭끼리도 항상 경로가 있다. 블럭들간의 최단 경로의 합을 구하는 문제이다. 처음에 생각하기로는 도시에서 튀어나온 부분을 고려하면서 조금씩 제거한다든가 하는 걸 생각해봤는데, 너무 복잡하더라. 정해에 가까운 해답을 생각했으나 코딩력이 딸려서(...) 그걸 실제로 구현하려는 생각은 못했었다. 예제이다. 먼저, 두 점 사이에 x축 상으로 움직이는 거리를 살펴보자. 이렇게 보면 두 점 사이에 x축에 평행하게 움직이는 거리는 두 노드 사이의 거리와 정확히 같다. 그런데 전체에 구멍이 없고, 전체가 연결되어 있기 때..

dovelet 링크 R*C 크기의 격자가 있고, 이 격자에 각각 숫자가 있다(1부터 (R*C)까지 unique하게). 이제 여기서 H*W 크기의 임의의 직사각형을 잡으면, 그 안에 있는 숫자들의 median(중간값)을 구할 수 있다. 그러면 약 (R-H+1)*(C-W+1) 가지의 직사각형이 나오고 각각의 median이 나오겠지? 그 중 최댓값을 구하는 문제이다. (1≤H≤R≤3000, 1≤W≤C≤3000) 새로운 수가 들어왔다 나갔다 하면서 Median이 계속 변하는 문제는 O(lgN)만에 새로운 값을 추가하고, O(1)만에 중간값을 알아내고, O(1)만에 값을 삭제할 수 있다. 그래서 이 문제의 경우, H*W 크기의 격자를 전체 격자 위에서 ㄹ자 모양으로 움직이도록 밀면 모든 경우의 median을 따질..

1번은 그냥 규칙에 맞게 달팽이(나선) 테이블을 만들어주면 된다.2번은 오른쪽이나 위쪽 벽에 부딪힌 후에의 움직임을, 그 부분에 표를 하나를 대칭시켜서 보면 된다.무슨 말이냐면... 이것을 이렇게 생각하자는 것이지.(사실 여기서 위로 한번 더 뒤집어야 한다) 3번은 각각의 물건에서 다른 물건으로의 '방향간선'을 그어보면 전체가 DAG(Directed Acyclic Graph, 방향 간선으로만 이루어져 있고 사이클이 없는 그래프)임을 알 수 있다.여기서 두 물건의 크기 비교가 가능하다는 것은 한 물건에서 다른 물건으로 가는 경로가 있는지를 판단하면 된다.n A로 끝남[1] -> AB로 끝남...[5] -> ABCB로 끝남[6] -> 모든 가짓수(위에 있는 것 포함) [6]을 왜 저렇게 잡냐면,어차피 다른 ..