돌이 코딩하는 방

문제 태그 : https://www.acmicpc.net/problem/4243 문제 설명 문제 풀이 (사고의 흐름) 일단 DP라는 것을 어느정도 바로 생각할 수 있었다. 직선에서 하는 DP인데 N이 작기 때문에 N^2이라고 생각을 했고, 이러면 보통 DP[i][j]는 i에서 j까지 ~~~ 라고 생각했다. 여기서 우리는 i 부터 j까지 다 들렀다면 당연히 최종위치는 i또는 j라는 것을 알 수 있다. 들르는데 걸리는 시간은 0이기 때문에 중간에 띄고 건널 이유가 아예없다. 그래서 관찰한 사실을 토대로 DP[state][i][j]는 state의 방향에 있으면서 i부터 j까지 들리는데 기다림의 합의 최소라고 생각할 수 있다. 하지만 이러면 문제가 있다. 지금까지 대기시간의 총합이 최소가 되는 경우가 지금까지 ..

이번에는 최소 스패닝 트리 (Minimum Spanning Tree 약칭 MST)에 대해 이야기 해보려고 한다. MST란? 최소 스패닝 트리로 스패닝 트리 중 간선의 가중치의 합이 최소인 트리이다. 그럼 스패닝 트리는 무엇일까? 그래프에 n개의 정점이 있을때 n-1개의 간선으로 모든 점을 이은 트리이다. 사이클이 존재하지 않으며, 임의의 두 정점에 대해서 이동할 수 있는 경로가 유일하다. 다시 말하자면 그래프에서 n-1개의 간선을 뽑아내 사이클이 없는 트리를 완성하고 이때의 간선의 가중치의 합이 최소이면 이를 최소 스패닝 트리, 즉 MST라고 한다. MST를 구하는 방법 그래프에서 MST를 구하는 방법에는 크게 두가지가 있다. 바로 크루스칼 알고리즘과 프림 알고리즘이다. 둘 다 그리디를 기반으로 하고 있..

원래 안 하려고 했는데, 너무 오랫동안 코드포스를 안하는 것 같아서 양심의 가책을 느낄 정도까지 되었다. 실제로 꽤나 많은 코포를 할 수 있었는데 걸렀다. 그래서 이번만큼은 하기로 했다. stonejjun이라 크게 부담도 없고 말이다. A. Heating 두 숫자 n과 m이 주어지면 m을 n개의 숫자로 분리 한 후에 (a1+a2+a3+...an=m) 각 값을 제곱해서 더한 값의 최댓값을 출력하는 문제이다. 테스트케이스 수가 주어진 후, 여러번 주어진다. 굉장히 느낌이 좋았다. 문제 설명은 보지도 않고 example과 노트만 보고 a1,a2,a3...an이 최대한 비슷해야 한다는 사실을 깨달았다. 예를 들면 (3,10) -> (3,3,4) 가 된다. 00:03. in 20등. 뭔가 되는 날. B.Obtai..

문제 태그 : https://www.acmicpc.net/problem/1848 다익스트라에 관해 포스팅을 하다가 백준 다익스트라 문제들을 살펴보았는데, 한 문제 시도하다가 틀린 흔적을 발견했다. 그래서 그 문제를 풀게 되었는데, 굉장히 좋다고 생각하여, 풀이도 저장할겸 포스팅을 하게 되었다. 문제 설명 양 방향 그래프가 주어지는데 일반적인 양방향 그래프와 다른 점은 A점에서 B점으로 갈 때의 비용과 B점에서 A점으로 갈 때의 비용이 다르다는 것이다. 이때 목적은 1번 정점에서 출발하여 1번 정점으로 다시 돌아오는 최단거리를 구하는 것이다. 이때 한 번 지난 간선은 역으로도 다시 올 수 없다는 것이다. 즉 다시 말해, 1->3->1의 경로로 이동하는 것은 안된다는 것이다. 문제 풀이 (사고의 흐름) 일단..

문제 태그 : https://www.acmicpc.net/problem/1753 문제 설명 이 문제에서 요구하는 것은 방향그래프에서 특정 정점이 주어졌을 때 그 점으로부터 모든 점까지의 거리를 각각 구하는 것이다. 이는 다익스트라 알고리즘이 하는 일과 정확히 일치한다. 맞다. 다익스트라를 한번 연습해보라는 뜻이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include using namespace std; typedef long long int ll; typedef pair pii; #define ff first #define ss..

이번에 그래프 관련 알고리즘 다익스트라 (dijkstra) 를 들고 오게 되었다. 우리가 앞으로 그래프 문제를 많이 보게 될 텐데, 그래프 문제에서 가장 많이 다루게 되는 요소가 무엇일까? 바로 거리일 것이다. 가장 짧은 거리, 가장 짧은 거리의 경로, 임의의 두 노드 사이의 거리 등 정말 다양한 거리들을 알아야 할 필요성이 앞으로 생기게 된다. 다익스트라는 그 중 한 노드에서부터 모든 노드까지의 각각의 거리를 알아내고 싶을 때 사용되어진다. 어느정도 bfs랑 비슷한 느낌일 수 있다. bfs를 할 때는 queue의 맨 앞 노드에서 도달할 수 있는 모든 노드를 다시 queue에 넣어 탐색을 한다. 다익스트라는 도달할 수 있는 노드 중 기준노드로부터 가장 가까운 점을 뽑아 그 점을 거쳐 도달할 수 있는 다른..

USACO February 2016 Contest Gold 2번이다. BOJ 11994번에 등록되어 있으며 문제는 여기서 볼 수 있다. 문제 설명 영어 디스크립션을 읽기 싫을 수도 있으니 대충 문제 설명을 하려고 한다. 첫째줄에 N과 K가 주어진다. N은 총 방의 갯수로 방은 중앙 정원을 기준으로 원형으로 둘러져 있다. 시계처럼 생각하면 된다. 소들은 모두 중앙에 있고, 우리는 그 중 잘 K개의 방문을 연다. 그 다음에는 N개의 숫자가 주어진다. 이는 최종적으로 1부터 N번방에 들어가야하는 소의 수이다. 소들은 열려진 방으로 들어가서 시계방향으로만 이동할 수 있다. 이때 소들의 이동거리의 합의 최솟값을 구하는 것이다. 예제 설명 위 링크의 예제에서 2번방돠 5번방을 열면 2,3,4번방에 가야하는 소들은 ..

USACO 풀이글들을 본격적으로 적기 전에, 이런저런 이야기를 적어보려고 한다. USACO는 나와 굉장히 관련이 깊다. 옛날에 한창 늅늅이고 잘해지고 싶던 마음이 강했던 시절, 정올 국대님 몇 분 한테 무슨 문제를 풀면 좋을지를 물어보았었다. :GOD:들의 답은 한결같았다. USACO를 돌아라. 멀리 메일을 보냈더니 근처 사람이 대답해준 사건도 있었지만, 아무튼 USACO는 좋은 셋이다라고 많이 이야기한다. 문제의 질 자체도 괜찮을 뿐만이 아니라 풀이도 다 제공이 되기 때문이다. 그래서 나는 USACO를 많이 돌았다. silver를 쭉 돌고, 공부 좀 하다가 다시 gold를 돌았다. 셋을 도는 것의 장점은 지금까지 내가 배운 내용들 중 문제에 맞는 적합한 알고리즘을 선택하는 과정부터 시작할 수 있다는 것..

문제 태그 : https://www.acmicpc.net/problem/1260 문제 설명 사실 풀이라고 할 것은 딱히 없다. 문제의 제목 부터 내용까지 DFS와 BFS를 한 번 해보시오 라는 뜻의 연습문제이다. DFS와 BFS에 대한 개념을 알아야지 풀 수 있으며, 알 면 풀 수 있다. DFS와 BFS에 대한 설명은 여기에 나와있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include using namespace std; int vid[10101]; int vib[10101]; vector ed..

BFS 와 DFS는 정말 노드와 간선이 있으면 어디에서든 쓰일 여지가 있는 알고리즘이다. 정확히 말하자면 탐색방법이다. BFS는 Breadth First Search의 약자로 한국어로는 넓이 우선 탐색이다. 말 그대로 넓이를 우선시 하는 탐색 방법이다. DFS는 Depth First Search의 약자로 한국어로는 깊이 우선 탐색이다. 역시 말 그대로 깊이를 우선시 하는 탐색 방법이다. BFS 와 DFS를 처음 공부할때는 뉴비인 경우가 많기 때문에 보통은 바로 트리나 그래프를 그리기 전에 예시를 든다. 보통은 이러한 예시를 든다. '우리가 만약 넓고 좋은 새 집을 보러간다고 하자. BFS는 처음 들어선 거실에서 연결된 방을 다 가보는 것이다. 여러 방들을 둘러보면, 그제서야 보았던 방 중 하나를 기억해서..