문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 1789 수들의 합 제출 언어: Swift 알고리즘 분류: 수학 그리디 이론 풀이 그리디 이론 그리디 이론에 대한 설명은 그리디 알고리즘에 정리해놨으므로 생략하겠다 복잡하게 생각하지 않고 단순하게 while문을 사용하여 구현하니 쉽게 해결이 되었다 알고리즘 설계 해 선택 : N이 최대가 되려면 그 서로 다른 자연수들의 값이 최소가 되어야 하므로 1부터 커지는 방향으로 해 집합에 추가한다 실행 가능성 검사 : 해 집합에 있는 해들의 합이 S를 넘는지 확인한다 해 검사 : 해 집합에 하나의 해를 추가했을 때 S를 넘을 경우, 알고리즘을 종료하고 해의 개수를 count한다 이러한 알고리즘을 바탕으로 다음과 같은 코드를 짰다 합이 S가 되는 서로 다른 자연수..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 1197 최소 스패닝 트리 제출 언어: Swift 알고리즘 분류: 그래프 이론 최소 스패닝 트리 풀이 최소 스패닝 트리 그래프 내의 모든 node들을 최소의 간선 비용으로 연결하는 트리이다 cycle이 없는 조건일 경우 사용한다 Greedy를 이용한 그래프 탐색 알고리즘이다 Kruskal알고리즘과 Prim알고리즘 이 두 알고리즘으로 해결할 수 있다 Kruskal's Alg 1) 그래프 내의 모든 edge(간선)들을 비용에 따라 오름차순으로 정렬한다 2) 1)에서의 edge들을 최소 스패닝 트리에 추가한다 3) cycle을 형성하는 edge는 건너뛴다 Prim's Alg 1) 임의의 node를 시작 node로 설정 2) 각 node마다 최소 스패닝 트리..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 1916 최소비용 구하기 제출 언어: Swift 알고리즘 분류: 그래프 이론 데이크스트라 풀이 DIJKSTRA Negative Cycle이 없는 directed graph에서만 사용 가능하다 시작 node에서 다른 node로 가는 가장 짧은 경로를 구하여 최종적으로 시작 node에서 끝 node까지의 최종 최단경로를 구한다 이 문제에서는 다양한 버스 노선 중 주어진 도시 1에서 5로 가능 최단 경로를 찾는 알고리즘을 작성해야한다 다익스트라 알고리즘 작동 원리는 다음과 같다 각 node까지의 경로 길이를 무한대로 초기화 시작 node의 경로 길이를 0으로 초기화 아직 포함되지 않은 node 중 최소인 것 선택하여 최단경로에 추가 최단경로에 새로 추가된 ..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 14888번 연산자 끼워넣기 제출 언어: Swift 알고리즘 분류: 브루스포스 백트래킹 DFS 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들..
