백준 9095번 1, 2, 3 더하기https://www.acmicpc.net/problem/9095문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.   문제 풀이 문제 유형 다이나믹 프로그래밍 문제 이해 및 접근 주어진 정수 n을 1, 2, 3의..

백준 11047번 - 동전 0https://www.acmicpc.net/problem/11047문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)출력첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.  문제 풀이  문제 유형 그리디 알고리즘 풀이 도출 과정N과 K를 주어지기 때문에 ..

선형 탐색 (Linear Search)  선형 탐색은 배열 또는 리스트의 처음부터 끝까지 차례대로 요소를 비교하여 원하는 값을 찾는 방법입니다.시간 복잡도는 O(n)입니다. 선형 탐색은 정렬되지 않은 데이터나 작은 데이터 셋에 간단히 적용 가능합니다. 예시 코드 def linear_search(arr, target): for i in range(len(arr)): if arr[i] == target: return i # 찾은 경우 인덱스 반환 return -1 # 찾지 못한 경우 -1 반환# 사용 예제arr = [4, 2, 7, 1, 9, 3]target = 7result = linear_search(arr, target)  이진 탐색 (Binary Sear..

DFS (Depth-First Search)깊이 우선 탐색은 한 경로를 끝까지 탐색한 후 다시 돌아와 다른 경로를 탐색하는 방식입니다. 스택 자료구조나 재귀를 사용하여 구현됩니다.  DFS는 모든 경로를 탐색하므로 그래프의 깊이가 깊을 경우 적합합니다. 예시 코드 def dfs(graph, start): visited = set() # 방문한 노드 집합 route = [] # 탐색 경로 stack = [start] # 스택에 시작 노드 추가 while stack: vertex = stack.pop() # 스택의 맨 위 노드를 꺼냄 if vertex not in visited: route.append(vertex) # 경로에 추가 ..

우선순위 큐 (Priority Queue)  우선순위 큐는 큐(Queue) 자료구조의 변형으로, 각 요소가 우선순위(priority)를 가지고 있습니다.큐에서 데이터를 꺼낼 때 우선순위가 가장 높은 요소가 먼저 나옵니다.일반적인 큐는 FIFO(선입선출) 방식으로 작동하지만, 우선순위 큐는 우선순위에 따라 데이터를 처리합니다. 힙 (Heap) 힙은 이진 트리(Binary Tree) 기반의 완전 이진 트리(Complete Binary Tree)입니다. 이진 트리란?- 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조입니다. 완전 이진트리란?- 말단 노드를 제외하고 모든 노드가 2개의 자식을 갖고 있는 이진 트리입니다.   각 노드가 특정한 규칙을 따르는 트리 자료구조입니다. 힙은 각 노드가 하위 노드보..