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..

메타클래스로 파이썬 클래스 작성을 한 단계 업그레이드하기 파이썬에서 모든 것이 객체라는 말이 있듯이, 클래스 자체도 객체입니다. 그리고 이 클래스 객체를 생성하는 것이 바로 메타클래스입니다. 메타클래스를 직접 정의하면 클래스 생성 프로세스 자체를 커스터마이징할 수 있습니다. 메타클래스란? 메타클래스는 클래스 객체를 생성하는 "클래스의 클래스"입니다. 파이썬의 type 클래스가 기본 메타클래스 입니다. class MetaExample(type): def __new__(cls, name, bases, attrs): print(f"새 클래스 {name}이(가) 정의되었습니다.") return super().__new__(cls, name, bases, attrs) class MyClass(metaclass=M..

숨은 고수의 기술 - 파이썬 디스크립터로 캡슐화 완성하기 파이썬의 객체지향 프로그래밍에서 캡슐화는 핵심 원칙입니다. 데이터 속성에 대한 접근을 제어하고 무결성을 보장하는 것이 중요합니다. 이를 위해 프로퍼티를 사용하지만, 디스크립터를 활용하면 더 강력하고 유연한 캡슐화가 가능합니다. 디스크립터란? 디스크립터는 객체 속성에 접근할 때의 행위를 정의하는 클래스입니다. get, set, delete 메서드를 구현하여 속성 값의 가져오기, 설정, 삭제를 제어합니다. class DescriptorExample: def __init__(self, value=None): self.value = value def __get__(self, obj, obj_type): print('Getting value') return..