세상을 바꾸는 데이터

문제 링크: https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 유형: 브루트포스 알고리즘, 백트래킹, 다이나믹 프로그래밍 풀이 과정: 이 문제는 다이나믹 프로그래밍(DP)으로 풀 수도 있지만 아직 개념이 잡혀있지 않아 DFS를 이용해 풀어보았다. 특정한 수(n)가 주어지면 n을 1, 2, 3만을 이용해 표현해야하고 가능한 모든 경우의 수를 도출해내는 것이 목표다. 간단하게 DFS를 이용해 풀 수 있다. 더한 값(sum)이 구하는 값(num) 보다 크다면 return, 같다면 개수(count)에 1을 추가해주면 된다. 여기서 DFS 개념을 ..

문제 링크: https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 유형: 브루트포스 알고리즘, 백트래킹, 깊이 우선 탐색, 너비 우선 탐색 풀이 과정: 이 문제의 풀이 과정은 2가지가 있다. ★ 첫 번째 방법은 필자가 풀은 방법인 순열 라이브러리와 BFS를 이용한 방법이다. 먼저 연산자의 기호들을 차례대로 받아 순열을 이용해 가능한 모든 경우의 수를 계산하여 큐에 삽입한다. (예를 들어 '..

문제 링크: https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 과정: 이 문제는 DFS(깊이 우선 탐색 알고리즘)과 BFS(너비 우선 탐색 알고리즘)의 가장 기초가 되는 문제이다. DFS에서는 인접 행렬(이웃해 있는 행렬의 값이 모두 일치)을 이용하여, BFS에서는 데크(deque)를 호출해 큐(queue)를 이용하여 문제를 풀었다. DFS는 스택의 자료 구조와 같다고 말할 수 있는 재귀 함수(자기 자신..