백준 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) # 경로에 추가 ..

Hash Table 해시 테이블(Hash Table)은 데이터를 빠르게 저장하고 검색할 수 있는 자료구조입니다.기본적인 아이디어는 데이터를 배열의 인덱스에 매핑하여 검색 시간을 최소화하는 것입니다.이 구조는 특히 데이터가 많을 때 매우 효율적입니다. 해시 테이블은 키(Key)를 값(Value)에 매핑할 수 있는 구조로 구성되어 있습니다. 키(Key) : 데이터를 구분하는 고유한 값값(Value) : 키에 해당하는 실제 데이터    키를 해시 함수를 통해 인덱스로 변환하고, 그 인덱스에 해당하는 위치에 값을 저장합니다. 해시 함수 (Hash Function) 해시 함수란 입력된 키를 해시 테이블의 인덱스로 변환하는 함수입니다.해시 함수는 다음과 같은 특성을 가져야 합니다. 충돌 최소화 : 서로 다른 키가 ..