생각 생각

https://acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 여전히 손에 잘 익지 않은 다익스트라. 여러 번 반복하면서 체화하도록 하자.

https://acmicpc.net/problem/1584 1584번: 게임 첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 www.acmicpc.net 0-1 bfs에 대해 공부할 수 있는 문제였다. 일반 bfs와 동일하게 풀려고 보니 문제가 잘 풀리지 않아 알게 되었다. 일반 bfs와 대부분 유사하나, 이 경우에는 변수 time으로 표현된 생명력이 적게 드는 곳을 우선하여 탐색해야 한다는 점이 다르다. 즉, 동일한 곳을 방문하고자 할 때, 기왕이면 비용이 덜 드는 쪽부터 탐색해야 하는 경우이다. 이럴 때는 간단하게 항상 생명력이 ..

https://acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 이젠 문제를 모르겠으면 뭔가 다른 알고리즘이 있는지부터 의심하자. 또 새로운 알고리즘이 있었다...ㅋㅋ ​ 이번엔 벨만-포드 알고리즘이었다. 이로써 다익스트라, 플로이드-워셜에 이어 3번째 길찾기 알고리즘을 공부했다. 벨만-포드 알고리즘은 다익스트라와 동일하게 한 점에서 다른 점까지의 가는 최소 비용의 변을 찾는다. cf) 점(vertex)과 변(edge), 노드(node)와 링크(link)..

https://acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 내 방법으로 풀어도 아무 문제 없을 것 같아서 그냥 내 방법대로 풀었다. 이 문제에서 성가셨던 점은 양방향 간선이라 자꾸 dfs 처리 할 때 무한 순환이 되더라는 것이다. 1에 (5,1)이 있고 5에 (1,1)이 있고...와 같은 식으로 말이다. 그러나 visited를 만들고 초기화하기에는 내 방법에서는 리프 노드가 아닌 모든 노드를 다 확인해야 하니 시간 복잡도와 공간 복잡도 모든 측면..

https://acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 간만에 전적으로 아이디어부터 구현까지 혼자 한 문제...였으나 O(N)풀이법이 있더라. 내가 한 생각은 dfs를 돌되, 리프 노드까지 가면 그 점까지 가는 데 드는 최대한의 거리를 뱉는 것이었다. 그리고 이 때 자식 노드까지의 거리를 다 하나의 리스트에 저장해놓고, 자식 노드 중 가장 큰 것 두 개를 고르면 그게 부모 노드를 중심으로 한 트리의 지름이 된다. 이 때, 계산을 계속 돌면..

https://acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 알고리즘에 대해 공부했다. 발상은 간단했는데 참 신기했다. 기본 생각은, a부터 b까지 가려고 할 때, 특정한 점을 거쳐서 가는 게 빠른지를 전부 확인해본 뒤 거쳐서 가는 것이 더 빠르다면 거쳐서 가겠다는 것이다. 초기값은 a가 b로 향하는 직접적인 간선이 있다면 그 값, 아니면 inf다. ​ 첫 for문에서의 과정은 무언가를 거치지 않은 직접적인 간선의 초기값을 설정하는 과정이다. 두번째..

https://acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 이 문제를 풀기 위해 트리 구조에 대해 공부했다. 일단 예제도 잘 이해가 안 되었기 때문이다. 이해해본 바에 따라 정리해보면 전, 중, 후위 순회는 분할 정복과 유사한 방법으로 이해해야 하는 것 같다. 전위 순회 우선 가장 크게 본다. 지금 root, left, right를 나눠서 보려고 하는데, 크게 보면 root는 A, left는 B와 그 아래 딸린 것들(예제의 경우 D), right는 C..

https://acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 이어진 백트래킹 연습. N과 M (1)과 동일하나 특정 숫자를 뱉어내야 한다. 다른 건 sort된 nums를 만들고, 그 원소를 넣어야한다는 점이었다.