빅맥좋아요

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)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 스패닝 트리가 된다. 최소 스패닝 트리는 이러한 스패닝 트리 중에 간선의 가중치 합이 최소인 트리다. 최..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 백준 11779번 최소비용 구하기 2 를 풀었다. 최대 도시의 개수가 1000개이고 간선에 음수 가중치가 없어서 다익스트라 알고리즘을 사용했다. 다익스트라 알고리즘에 최단 경로 출력을 합치면 된다. 경로를 저장하기 위해 path_temp 배열을 사용했다. 어느 도시에서 오는지 저장하는 배열이다. index 1 2 3 4 5 value 0 1 1 1 4 예제의 경우 ..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 백준 2573번 빙산 문제를 풀었다. 빙산을 BFS나 DFS로 탐색하는 문제다. 빙산이 두 덩어리 이상으로 분리되면 BFS나 DFS 탐색을 두 번 이상 할 것이다. 그러면 year를 출력해주면 된다. 만약 빙산이 동시에 사라져서 탐색을 하지 않는다면 0을 출력하면 된다. 빙산이 녹는 과정에서 주의할 것은 next_map배열에 빙산이 녹는 값을 넣어두고 일괄적으로 map배열을 갱신시켜줘야 한다..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 백준 4485번 녹색 옷 입은 애가 젤다지?를 풀었다. 문제가 특정 노드에서 특정 노드까지의 최단 거리를 요구하고 간선에 음수 가중치가 없어서 다익스트라 알고리즘을 사용했다. 입력으로 주어진 2차원 배열을 다익스트라 알고리즘에 맞게 노드와 간선으로 바꿔준 후 다익스트라를 실행했다. 테스트케이스가 끝나면 항상 초기화를 해야한다. 정답을 맞추고 다른 사람들의 코드를 참고해보니 typ..