빅맥좋아요

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 백준 11052번 카드 구매하기를 풀었다. dp[i]의 값은 i개의 카드를 구매하는 최대 비용이다. 초기값은 dp[1] = cardpack[1] 이고, 반복문을 사용해서 dp[n]까지 구한다. 아래는 전체 코드입니다. #include #include #include #include #include #pragma warning(disable:4996) using namespace std; int n; in..

https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 백준 10217번 KCM Travel 을 풀었다. 특정 노드에서 시작하고 간선의 가중치가 양수이므로 다익스트라를 사용했다. 변수가 비용과 시간 두개이므로 2차원 배열을 사용해서 풀어야 한다. dp[i][j] 는 시작 노드 1에서 i 노드까지 j 비용을 썼을 때의 소요시간을 저장하는 배열이다. https://maivve.tistory.com/226 위 블로그를 ..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 백준 10282번 해킹 문제를 풀었다. 의존성을 반대로 입력받은 뒤 감염된 컴퓨터에서 다익스트라 알고리즘을 사용하면 된다. 그러면 감염시킬 수 있는 컴퓨터의 개수와 걸리는 시간을 구할 수 있다. 출력과 초기화를 주의하자. 아래는 전체 코드입니다. #include #include #include #include #include #include #include #pragma warning(disable:..

https://www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 백준 1219번 오민식의 고민을 풀어봤다. 처음엔 벨만 포드 알고리즘을 사용해서 음의 사이클이 존재하면 무조건 Gee를 출력하도록 했다가 틀렸습니다를 받고 생각을 다시 해봤다. 질문 검색 게시판에서 음의 사이클이 존재하고 음의 사이클에서 도착 지점에 도달할 수 있을 때 Gee를 출력해야 한다는 것을 찾았다. 그래서 벨만 포드 알고리즘을 사용해서 음의 사이클이 존재함을 알았을 때, 플로이드 와샬 ..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 백준 1967번 트리의 지름을 풀었다. 트리의 모든 경로중 가장 긴 경로를 구하면 그것이 트리의 지름이다. 먼저 루트 노드인 1에서 다익스트라 알고리즘을 사용해서 가장 멀리 있는 노드(A)를 구했다. 가장 멀리 있는 노드(A)에서 다시 다익스트라를 사용한다. 그 때 다시 가장 멀리 있는 노드(B)와의 거리가 트리의 지름이 된다. 아래는 전체 코드입니다. #include #inc..

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 백준 2887번 행성 터널 문제를 풀었다. 처음엔 행성 사이의 모든 간선을 넣고 풀었는데 메모리 초과가 나왔다. 10만개의 행성 사이의 가능한 간선의 수는 100,000*(100,000-1)/2 므로 메모리 초과가 나올만 하다. 질문 검색란을 봤는데 행성을 x좌표 순으로 정렬하고 인접한 행성 사이의 거리를 x좌표로만 계산하고 노드로 넣은 뒤 y좌표, z좌표도 똑같은..

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 백준 4386번 별자리 만들기를 풀었다. 좌표로 입력된 별자리를 노드와 간선으로 바꿔준 뒤 크루스칼 알고리즘을 사용했다. 자료형만 신경써서 알고리즘을 구현하면 될 것 같다. 아래는 전체 코드입니다. #include #include #include #include #include #include #include #pragma warning(disable:4996) using namespace std;..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 백준 1647번 도시 분할 계획을 풀었다. 마을을 두 개로 분리하면서 집과 집 사이를 모두 연결하는 최소 비용을 구하는 문제다. 먼저 하나의 마을에 최소 스패닝 트리 문제를 적용한 후에 마지막으로 추가한 n-1번째 간선을 빼면 된다. 그러면 가장 큰 비용의 간선을 삭제함과 동시에 마을이 두 개로 나뉘어진다. 집의 최대 개수가 100,000개, 간선의 최대 개수..

https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 백준 1922번 네트워크 연결 문제를 풀었다. 모든 노드를 최소 비용으로 연결하는 최소 스패닝 트리 문제다. 프림 알고리즘 두개와 크루스칼 알고리즘을 모두 사용해서 풀어봤다. 정점의 수가 최대 1,000개, 간선의 수가 최대 100,000개라서 시간복잡도가 O(V^2)인 프림 알고리즘이 제일 빨랐다. 아래는 전체 코드입니다. #include #include #include #include #include #include #pragma warning(disable:4996) using n..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 백준 1197번 최소 스패닝 트리를 풀었다. 스패닝 트리는 그래프 내의 모든 정점을 포함하는 트리다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 스패닝 트리가 된다. 최소 스패닝 트리는 이러한 스패닝 트리 중에 간선의 가중치 합이 최소인 트리다. 최..