Family in August

파이썬으로 트라이(Trie) 자료구조 구현하기 문제 설명 문자열 배열 `words`와 단일 문자 `char`가 주어졌을 때, `char`를 최소 횟수로 추가하여 `words`의 모든 문자열을 완전히 포함할 수 있는 가장 짧은 문자열을 찾는 함수를 작성하세요. 예시 입출력 입력: words = ["cat", "cats", "catshey", "dog"], char = 's' 출력: "cats" 입력: words = ["hello", "hell", "hello"], char = 'l' 출력: "hello" 솔루션 코드 class TrieNode: def __init__(self): self.children = {} self.is_word = False self.word = None class Trie: de..

파이썬으로 슬라이딩 윈도우(Sliding Window) 기법 구현하기 문제 설명 문자열 `s`와 정수 `k`가 주어졌을 때, 길이가 `k`인 최대 무복 문자 부분 문자열의 길이를 구하는 함수를 작성하세요. 예시 입출력 입력: s = "abcabcbb", k = 3 출력: 3 (최대 무복 문자 부분 문자열은 "abc") 입력: s = "bbbbb", k = 3 출력: 1 (최대 무복 문자 부분 문자열은 "b") 솔루션 코드 def max_length(s, k): window = {} max_len = 0 left = 0 for right in range(len(s)): window[s[right]] = window.get(s[right], 0) + 1 while len(window) > k: window[..

파이썬으로 비트 조작(Bit Manipulation) 기법 익히기 문제 설명 정수 `n`이 주어졌을 때, `n`의 비트 표현에서 1의 개수를 계산하는 함수를 작성하세요. 예시 입출력 입력: n = 19 (0b10011) 출력: 3 입력: n = 32 (0b100000) 출력: 1 솔루션 코드 def count_bits(n): count = 0 while n: count += n & 1 n >>= 1 return count # 테스트 케이스 print("1의 개수:", count_bits(19)) print("1의 개수:", count_bits(32)) 코드 설명 이 포스팅에서는 비트 조작(Bit Manipulation) 기법을 활용하여 정수의 비트 표현에서 1의 개수를 계산하는 문제를 해결했습니다. 비트..

파이썬으로 탐욕 알고리즘(Greedy) 기법 구현하기 문제 설명 주어진 동전들을 이용하여 특정 금액을 최소 동전 개수로 거슬러 주는 문제를 탐욕 알고리즘으로 해결하세요. 예시 입출력 입력: 금액 = 23, 동전 종류 = [1, 5, 10] 출력: 5 (동전 개수) 솔루션 코드 def min_coins(amount, coins): coins.sort(reverse=True) count = 0 for coin in coins: count += amount // coin amount %= coin return count # 테스트 케이스 print("최소 동전 개수:", min_coins(23, [1, 5, 10])) print("최소 동전 개수:", min_coins(92, [1, 5, 10, 25])) 코..

파이썬으로 분할 정복(Divide and Conquer) 기법 구현하기 문제 설명 주어진 배열을 오름차순으로 정렬하는 병합 정렬(Merge Sort) 알고리즘을 분할 정복 기법으로 구현하세요. 예시 입출력 입력: nums = [38, 27, 43, 3, 9, 82, 10] 출력: [3, 9, 10, 27, 38, 43, 82] 솔루션 코드 def merge_sort(nums): if len(nums)

파이썬으로 동적 프로그래밍(DP) 기법 익히기 문제 설명 가능한 최대 구간 합(Maximum Subarray Sum) 문제를 동적 프로그래밍 기법으로 해결하세요. 주어진 배열에서 연속된 부분 배열의 합 중 최대값을 구하는 문제입니다. 예시 입출력 입력: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] 출력: 6 (구간 [4, -1, 2, 1]의 최대 합) 솔루션 코드 def max_subarray(nums): n = len(nums) dp = nums.copy() for i in range(1, n): dp[i] = max(dp[i - 1] + nums[i], nums[i]) return max(dp) # 테스트 케이스 nums = [-2, 1, -3, 4, -1, 2, 1, -5,..

파이썬으로 N-Queen 문제 해결하기 (백트래킹 알고리즘) 문제 설명 N-Queen 문제는 가로, 세로, 대각선으로 공격할 수 있는 퀸을 서로 공격하지 못하도록 N*N 크기의 체스판에 배치하는 문제입니다. N이 주어졌을 때, 퀸을 배치하는 방법의 수를 구하는 백트래킹 알고리즘을 작성하세요. 예시 입출력 입력: N = 4 출력: 2 입력: N = 8 출력: 92 솔루션 코드 def n_queens(n): def is_safe(board, row, col, n): # 같은 행에 퀸이 있는지 검사 for i in range(col): if board[row][i] == 1: return False # 왼쪽 대각선에 퀸이 있는지 검사 i, j = row, col while i >= 0 and j >= 0: i..

파이썬으로 그래프 탐색 알고리즘(BFS, DFS) 구현하기 문제 설명 그래프가 주어졌을 때, 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS) 알고리즘을 파이썬으로 구현하라. 예시 입력 graph = { 1: [2, 3, 4], 2: [5], 3: [5], 4: [], 5: [6, 7], 6: [], 7: [3] } 솔루션 코드 from collections import deque def bfs(graph, start): visited = [] queue = deque([start]) while queue: node = queue.popleft() if node not in visited: visited.append(node) queue.extend(graph[node]) return visited d..

파이썬으로 정렬 알고리즘 구현하기 문제 설명 다음 정렬 알고리즘들을 파이썬으로 구현하라. - 버블 정렬(Bubble Sort) - 선택 정렬(Selection Sort) - 삽입 정렬(Insertion Sort) 예시 입출력 입력 배열: [3, 1, 4, 2, 5] 버블 정렬 결과: [1, 2, 3, 4, 5] 선택 정렬 결과: [1, 2, 3, 4, 5] 삽입 정렬 결과: [1, 2, 3, 4, 5] 솔루션 코드 def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr def sele..

트리 순회(Traversal) 알고리즘 구현하기 문제 설명 이진 트리가 주어졌을 때, 전위(preorder), 중위(inorder), 후위(postorder) 순회 방식으로 트리를 탐색하는 알고리즘을 구현하라. 예시 입출력 입력 트리: 1 / \ 2 3 / \ 4 5 전위 순회 출력: 1 2 4 5 3 중위 순회 출력: 4 2 5 1 3 후위 순회 출력: 4 5 2 3 1 솔루션 코드 class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def preorder(root): result = [] def traverse(node): if node: res..