날마다 새로운 코딩

1. 문제 : https://www.acmicpc.net/problem/1321 1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net 2. 풀이 : Indexed Tree 3. 설명 각 부대의 군사 수 1, 4, 3, 5, 2를 구간합 트리로 표현하면 그림[1]과 같다. 그림[1]에서 6번 군인은 3번 부대에 속해 있으며, 6번 군인을 탐색하는 과정은 그림[2]와 같다. 2번 부대에서 3명의 감원이 일어나면 그림[3]과 같이 구간합 트리가 업데이트 된다. 그림[3]에서 6번 군인은 4번 부대에 속해 ..

Algorithm/Indexed Tree 2021. 9. 18. 19:27

1. 문제 : https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 2. 풀이 : Binary Search 3. 설명 그림[1]과 같이 3개의 전깃줄을 제거하였을 때, 남아있는 모든 전깃줄이 교차하지 않음을 확인할 수 있다. 전봇대A를 기준으로 위치 1부터 10까지 차례대로 전깃줄을 연결하였을 때, 연결되는 전봇대 B의 위치 순서는 그림[2]와 같으며, 교차하지 않는 전깃줄은 최대 증가수열임을 알 수 있다. 마찬가지로, 전봇대 B를 기준으로 위치 1부터 ..

Algorithm/LIS 2021. 8. 17. 22:38

1. 문제 : https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 2. 풀이 : Binary Search 3. 시간복잡도 : O(NlogN) 4. 설명 최장 증가 수열(LIS, Longest Increasing Subsequence) 문제이다. 그림[1]과 같이 LIS를 저장할 배열을 만든다. 상자를 처음부터 하나씩 LIS 배열에 위치를 찾아 넣는다. 위치를 찾을때에는 이분탐색을 사용하며, 동일한 크기의 상자가 들어올 수도 있으므로 lower bound를 ..

Algorithm/LIS 2021. 8. 9. 20:46

1. 문제 : https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 2. 풀이 : Bellman-Ford 3. 설명 '한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우'는 문제에서 주어진 그래프에 음수 싸이클이 존재하는 경우이다. 문제에서 출발 지점을 명시해 주지 않았기 때문에 출발 지점으로 임의의 지점을 선택하여 Bellman-Ford를 수행한 ..

Algorithm/Bellman-Ford 2021. 8. 3. 23:50

1. 문제 : https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 2. 풀이 : Bellman-Ford 3. 시간복잡도 : O(VE) 4. 설명 Bellman-Ford 알고리즘은 'V-1'회의 edge relaxation 수행으로 한 노드로부터 다른 노드까지의 최단 경로를 구할 수 있다. 그림[1]에서 1번 도시로부터 다른 모든 도시까지의 최단 경로를 구해보자. edge relaxatio..

Algorithm/Bellman-Ford 2021. 7. 29. 22:20

1. 문제 : https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 2. 풀이 : Dijkstra 3. 설명 문제의 조건은 아래와 같다. 1. 모든 컴퓨터를 최소 개수의 회선으로 복구한다. 2. 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 시간이 최소가 되어야 한다. 모든 컴퓨터를 최소의 회선으로 복구하려면 (컴퓨터 수 - 1) 만큼의 회선이 필요하다. 슈퍼컴퓨터로부터 모든 컴퓨터를 최소의 시간으로 연결하면서 경로를 갱신..

Algorithm/Dijkstra 2021. 7. 21. 20:22

1. 문제 : https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 2. 풀이 : 다익스트라 3. 설명 그림[1]에서 도착점인 5번 노드까지의 최단 경로는 다익스트라의 구현 방법에 따라 1->3->5 혹은 1->4->5 2가지의 최단 경로가 가능하다. 경로 추적 배열은 출발점인 1번 노드는 -1로 갱신하고, 각 노드의 최단 거리가 갱신되는 시점에 갱신한다. 최단 경로를 다 찾은 후, 도착점부터 출발점까지 경로를 역추적..

Algorithm/Dijkstra 2021. 7. 14. 21:45

1. 문제 : https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 2. 풀이 : 다익스트라 3. 설명 그림[1]과 같이 네트워크 시설이 존재할 때, 1번 컴퓨터를 해킹하면 그림[2]와 같다. 5번 컴퓨터를 제외한 총 4대의 컴퓨터가 감염이되며, 이때 마지막 컴퓨터까지 감염이 되는 시간은 5초이다. 4. 코드

Algorithm/Dijkstra 2021. 7. 14. 21:05