Dev_Diary

https://www.acmicpc.net/problem/14285 14285번: 간선 끊어가기 정점 n개, m개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 그래프 내에 있는 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 제 www.acmicpc.net 설명은 복잡하지만 결국 어떤 경로를 제외한 모든 간선을 제거하고, 남은 경로에서 한 간선을 제거한 뒤, 남은 간선들의 가중치의 합을 총 가중치 합에서 빼주면 되는 문제입니다. 물론 그 값이 최댓값이 되어야 한다는 것이 문제지만 생각을 조금 달리 해보면 쉽게 풀 수 있습니다. 총 가중치 합 - 특정 간선의 가중치 합 을 최대로 만들어야 하는 문제인데, 총 가중치 합은 정해져 있으므로 특정 간선의 ..

https://www.acmicpc.net/problem/5551 5551번: 쇼핑몰 첫째 줄에 도시의 수 N, 도로의 수 M, 쇼핑몰이 있는 도시의 수 K가 주어진다. 도시는 1번부터 N번까지 번호가 매겨져 있다. (2 ≤ N ≤ 3000, 1 ≤ M ≤ 105, 1 ≤ K ≤ N) 다음 M개 줄에는 도로의 정보 a, b, www.acmicpc.net 최단거리 목록을 초기화하지 않고 다른 노드에서 시작하는 다익스트라를 돌리면 어떻게 되는지 생각해보자. 다익스트라 알고리즘은 기본적으로 시작 노드에서 다른 노드들 까지의 최단거리를 구하는 알고리즘이므로 여러 시작노드에서 알고리즘을 돌리면 어느 노드에서 시작했는지는 모르겠지만 하여튼 해당 노드까지 도달하는 최단 거리를 기록하게 된다. 또, a->b / b->..

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 다익스트라로 최단 경로를 구한 뒤 최단 경로를 모두 제외시키고 다시 다익스트라로 최단경로를 구하면 풀 수 있습니다. 다만 최단경로 중복을 염두에 두고 현재 가중치가 최단 가중치보다 같거나 작을 때 우선순위큐에 넣는 방식으로 풀면 시간이 초과되므로 같을 때와 작을 때로 나누어 알고리즘을 실행해야합니다. #include #include #include #include #..

https://www.acmicpc.net/problem/2325 2325번: 개코전쟁 “앙두레 강”이 개미와 코끼리 결혼식에서 기차를 아름답게 만드는 것을 실패했기 때문에 식장이 아수라장이 되고 결혼이 물거품이 되어버렸다. 급기야는 왕국 간에 분쟁으로 이어져 개미왕 www.acmicpc.net 다익스트라를 여러 번 써주면 풀 수 있는 문제입니다. 우선 어느 경로도 제외하지 않은 상태로 다익스트라를 사용해 최단 경로를 구합니다. 구해진 최단 경로에 포함된 도로들을 하나씩 제외시켜주며 다익스트라를 통해 최단경로의 최댓값을 갱신시켜주면 됩니다. 여기서 최단 경로가 여러 개 나올 수 있다고 생각하고 최단경로를 모두 저장하는 경우가 있습니다. 하지만 모든 최단 경로를 구할 필요는 없습니다. 문제의 1번 예시를 ..

https://www.acmicpc.net/problem/23832 23832번: 서로소 그래프 우석이는 심심할 때마다 그래프를 그린다. 우석이는 매달 새로운 그래프를 그리는데, 이번 달에는 서로소 그래프를 그린다. 서로소 그래프는 $1$부터 $N$까지의 번호를 가진 $N$ 개의 정점으로 이 www.acmicpc.net 오일러 피 함수 정의에 따라 풀어주면 됩니다. 오일러 피 함수 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 오일러 파이 함수의 그래프. ϕ(1)부터 ϕ(1000)까지의 값들을 나타낸다. 수론에서 오일러 파이 함수(-函數, 영어: Euler’s phi (totient) function)는 정수환의 몫환의 가 ko.wikipedia.org #include #inclu..

https://www.acmicpc.net/problem/1797 1797번: 균형잡힌 줄서기 첫째 줄에는 한 줄로 선 팬들의 수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 그 다음 N개의 줄에는 남녀의 성별을 나타내는 수(남자는 0, 여자는 1)와 이들이 서있는 x좌표가 공백으로 구분되어 주어진다. x www.acmicpc.net 누적합과 해시맵을 함께 써서 풀 수 있는 문제입니다. 남여의 성별 코드가 ( 0 ,1 ) 로 존재하는데 이를 ( -1, 1 ) 로 치환하면, 즉 남자의 성별코드를 -1 로 치환하면 누적합을 통해 남여의 수가 같은 구간을 쉽게 구할 수 있습니다. 당연히 한 줄로 서있기 때문에 x 값을 기준으로 정렬해주어야 합니다. 인덱스 1 2 3 4 5 6 7 8 9 성별 남(-1) ..

https://www.acmicpc.net/problem/15554 15554번: 전시회 승원이는 미술품 N개를 가지고 있다. 각각의 미술품은 1번부터 N번까지 번호가 매겨져 있다. i번 미술품의 크기는 Ai, 가치는 Bi로 나타낸다. 오늘은 승원이의 저택 1층에서 미술품을 전시하려고 www.acmicpc.net 우선 최대 무게와 최소 무게를 지정했다고 가정하겠습니다. 그렇다면 두 미술품 사이에 정렬되어 있는 미술품은 모두 전시하는 것이 S - (A_max - A_min) 의 값을 크게 만듭니다. A_max 와 A_min 은 고정되어 있는 반면 S 는 값이 커지기 때문입니다. 그렇다면 어느 미술품을 고를 때, 크기별로 정렬되어 있다면 연속된 구간을 모두 선택하는 것이 최적의 해를 구하는 방법이라고 할 수..

https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 다익스트라와 DP 를 함께 사용해 푸는 문제였습니다. 포장 횟수, pave 를 행으로 도시번호를 열로 최단거리 어레이를 만든 뒤 pave 에 따른 최단거리를 기록해가며 풀어주면 됩니다. pave 가 다를 경우에는 포장의 선후관계가 다음 최단거리에 영향을 끼치지만, pave 가 같은 최단거리에서는 먼저 포장을 했던 지금 포장을 했던 선후 관계가 다음 최단거리에 영..

https://www.acmicpc.net/problem/1451 1451번: 직사각형으로 나누기 첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 50보다 작거나 같은 자연수이 www.acmicpc.net 직사각형을 작은 세 개의 직사각형으로 자르는 문제입니다. 네 개의 꼭짓점을 세 개의 직사각형이 나누어 차지하는 문제로 생각해보면 두 개의 꼭짓점을 가지는 직사각형 + 한 개의 꼭짓점을 가지는 직사각형 두 개 로 나눌 수 밖에 없다는 것을 알 수 있습니다. 그렇기 때문에 한 변을 포함하는 직사각형을 미리 지정하고 나머지 덩어리를 세로 혹은 가로로 잘라보는 과정을 방향별로 네 번 반복해주..

https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 백준 11758 Python https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수..