C++33 [C/C++] 백준 1197: 최소 스패닝 트리 (Kruskal 알고리즘) 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 최소 스패닝 트리는 크게 프림의 알고리즘과 크루스칼 알고리즘을 통해 구현이 가능하다. 이 문제에서는 크루스칼 알고리즘을 이용하여 최소 스패닝 문제를 해결했다! 크루스칼(Kruskal 알고리즘)? 크루스칼 알고리즘의 가장 기본적인 아이디어는 사이클이 만들어지지 않는 한에서 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가하는 것이다. .. 2023. 10. 10. [C/C++] 백준 1504: 특정한 최단 경로 (다익스트라 풀이) https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이!!! 다익스트라 알고리즘! 다익스트라를 제대로 구현을 한 상태라면 사실 쉽게 풀 수도 있다. 다익스트라를 4번에서 6번 사용을 한다면 최단거리를 1부터 N까지 V1과 V2를 거치면서 최단거리를 구하면 된다. 이 문제에서 한번 이동했던 정점을 다시 이동할 수 있다는 것은 다익스트라를 여러번 사용할 때 같은 정점을 지나도 된다는 것이지 한번의 다익스트.. 2023. 9. 30. [C/C++] 백준 5639: 이진 검색 트리 (backtrack을 통한 후위순회) https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이!! 맨 처음에는 괄호를 이용한 후위 표기식 문제와 같이 stack에 넣음으로써 문제를 해결하려고 했지만 그렇게 할 경우 코드가 너무 복잡해지고 구현할 수가 없어 다른 방법을 모색하였다. 전위 순회의 특성상 루트-왼쪽 자식-오른쪽 자식 순으로 이동하기 때문에 전체의 루트를 하나만 잡았을 때 배열이 루트(1)-왼쪽자식 (n개)-오른쪽 자식(m)개가 된다. 예를 들어 50 30 24 .. 2023. 9. 26. [C/C++] 백준 2206: 벽 부수고 이동하기 (BFS,tuple 이용 풀이) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 구현! 사실 원래의 BFS를 이용한 최단거리 알고리즘에서 조금만 추가하면 쉽게 풀 수 있는 문제이다. 여기서 중요한 것은 tuple안의 4개의 원소를 집어넣어 각각 x좌표, y좌표, 벽을 뚫고 지나갔는지에 대한 여부, 현재까지의 거리를 저장해야 하는 것이다. 또한 중요한 것이 visit 배열인데 기존의 2차원으로만 표현하면 안되고 3차원으로 표현하여 벽을 뚫고 지나갔는지에.. 2023. 9. 18. 이전 1 2 3 4 5 6 7 ··· 9 다음
