[Python] 자주 나오는 코딩테스트 유형 정리
1. 문자열 처리
`회문 검사`
- 주어진 문자열이 거꾸로 읽어도 같은지 확인하는 문제
- `s == s[::-1]` 를 사용하여 문자열을 뒤집은 후 원래 문자열과 비교
def is_palindrome(s):
return s == s[::-1]
print(is_palindrome("level")) # True
print(is_palindrome("hello")) # False
`아나그램 검사`
- 두 문자열이 같은 문자들로 이루어졌는지 확인하는 문제
- 두 문자열을 sorted()로 정렬한 후 비교
def is_anagram(s1, s2):
return sorted(s1) == sorted(s2)
print(is_anagram("listen", "silent")) # True
print(is_anagram("hello", "world")) # False
`부분 문자열 찾기`
- 주어진 문자열 내에 특정 패턴이 포함되어 있는지 확인하는 문제
- in 연산자를 사용해 패턴이 포함되어 있는지 확인
def find_substring(s, pattern):
return pattern in s
print(find_substring("hello world", "world")) # True
print(find_substring("hello world", "python")) # False
`문자열 압축`
- 연속된 문자의 개수를 세어 압축된 형태로 문자열을 변환하는 문제
- 반복되는 문자를 세고, 그 결과를 문자열로 저장
def compress_string(s):
compressed = []
count = 1
for i in range(1, len(s)):
if s[i] == s[i-1]:
count += 1
else:
compressed.append(s[i-1] + str(count))
count = 1
compressed.append(s[-1] + str(count)) # 마지막 문자 붙이기
return ''.join(compressed)
print(compress_string("aaabbcccc")) # a3b2c4
2. 리스트/배열 조작
`투 포인터로 두 수의 합 찾기`
- 정렬된 배열에서 두 수의 합이 특정 값이 되는 쌍을 찾는 문제
- 배열의 양 끝에서 시작하는 두 포인터를 이동시켜 합을 찾음
def two_sum(nums, target):
nums.sort()
left, right = 0, len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
return [nums[left], nums[right]]
elif current_sum < target:
left += 1
else:
right -= 1
return []
print(two_sum([2, 7, 11, 15], 9)) # [2, 7]
`슬라이딩 윈도우로 최대 부분 합 찾기`
- 고정된 크기의 윈도우를 이동시키며 배열의 최대 부분합을 구하는 문제
- 윈도우 크기를 유지하면서 합을 계산해 최대값을 찾음
def max_subarray_sum(arr, k):
max_sum = sum(arr[:k])
current_sum = max_sum
for i in range(k, len(arr)):
current_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, current_sum)
return max_sum
print(max_subarray_sum([1, 2, 3, 4, 5, 6, 7, 8, 9], 3)) # 24
`이진 탐색 정렬된 배열에서 특정 값을 효율적으로 찾는 문제`
- bisect 모듈을 이용해 이진 탐색으로 값의 위치를 찾음
import bisect
def binary_search(arr, target):
index = bisect.bisect_left(arr, target)
if index < len(arr) and arr[index] == target:
return index
return -1
print(binary_search([1, 2, 3, 4, 5], 3)) # 2
print(binary_search([1, 2, 3, 4, 5], 6)) # -1
3. 스택/큐
`괄호 검사`
- 주어진 문자열에서 괄호들이 올바르게 쌍을 이루고 있는지 확인하는 문제
- 스택을 이용해 여는 괄호를 저장하고, 닫는 괄호가 나올 때 쌍을 맞춤
def is_valid_parentheses(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack
print(is_valid_parentheses("()[]{}")) # True
print(is_valid_parentheses("(]")) # False
`BFS 탐색`
- 그래프에서 너비 우선 탐색을 통해 모든 노드를 방문하는 문제
- 큐를 사용해 가까운 노드부터 차례로 방문
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
print(node, end=" ")
queue.extend(graph[node] - visited)
graph = {'A': {'B', 'C'}, 'B': {'A', 'D', 'E'}, 'C': {'A', 'F'}, 'D': {'B'}, 'E': {'B', 'F'}, 'F': {'C', 'E'}}
bfs(graph, 'A') # A B C D E F
4. 해시/딕셔너리
`두 수의 합 (해시맵 사용)`
- 배열에서 두 수의 합이 특정 값이 되는 쌍을 찾는 문제
- 이미 본 숫자와의 합이 목표값이 되는지 해시맵을 이용해 빠르게 확인
def two_sum(nums, target):
hash_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hash_map:
return [hash_map[complement], i]
hash_map[num] = i
return []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
`빈도수 계산`
- 문자열 또는 리스트에서 각 요소의 빈도수를 계산하는 문제
- collections.Counter를 사용해 빈도수를 빠르게 계산
from collections import Counter
def count_frequencies(s):
return Counter(s)
print(count_frequencies("aabbcc")) # Counter({'a': 2, 'b': 2, 'c': 2})
5. 그래프
`DFS 탐색`
- 그래프에서 DFS로 모든 노드를 방문하는 문제
- 재귀적으로 각 노드를 방문하며 방문한 노드를 기록
def dfs(graph, node, visited=set()):
if node not in visited:
print(node, end=" ")
visited.add(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
graph = {'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']}
dfs(graph, 'A') # A B D E F C
`다익스트라 알고리즘`
- 가중치가 있는 그래프에서 특정 시작점에서 모든 노드까지의 최단 경로를 찾는 문제
- 우선순위 큐를 사용해 가장 짧은 경로를 먼저 탐색
import heapq
def dijkstra(graph, start):
queue = [(0, start)]
distances = {node: float('inf') for node in graph}
distances[start] = 0
while queue:
current_distance, current_node = heapq.heappop(queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
print(dijkstra(graph, 'A')) # {'A': 0, 'B': 1, 'C': 3, 'D': 4}
6. 동적 프로그래밍 (DP)
`피보나치 수열 (메모이제이션)`
- 피보나치 수열의 값을 효율적으로 계산하는 문제
- 이미 계산한 값을 저장해 반복 계산을 피하는 메모이제이션 사용
def fibonacci(n, memo={}):
if n in memo:
return memo[n]
if n <= 2:
return 1
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
print(fibonacci(10)) # 55
`최대 부분 합 (Kadane's Algorithm)`
- 배열에서 연속된 부분 배열의 합 중 최대값을 찾는 문제
- 현재 부분 배열의 합을 계속 업데이트하며 최대값을 추적
def max_subarray(nums):
max_current = max_global = nums[0]
for num in nums[1:]:
max_current = max(num, max_current + num)
if max_current > max_global:
max_global = max_current
return max_global
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 6
7. 트리
`이진 트리 순회`
- 이진 트리에서 노드를 특정 순서로 방문하는 문제
- 전위(preorder), 중위(inorder), 후위(postorder) 순회 방법 구현
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def preorder(root):
if root:
print(root.val, end=" ")
preorder(root.left)
preorder(root.right)
def inorder(root):
if root:
inorder(root.left)
print(root.val, end=" ")
inorder(root.right)
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.val, end=" ")
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
preorder(root) # 1 2 4 5 3
inorder(root) # 4 2 5 1 3
postorder(root) # 4 5 2 3 1
8. 백트래킹
`N-Queens 문제`
- 체스판에서 N개의 퀸을 서로 공격하지 않도록 배치하는 문제
- 백트래킹을 사용해 모든 가능한 배치를 탐색하며 유효한 배치를 찾음
def solve_n_queens(n):
def is_safe(board, row, col):
for i in range(row):
if board[i] == col or board[i] - i == col - row or board[i] + i == col + row:
return False
return True
def solve(board, row):
if row == n:
solutions.append(board[:])
for col in range(n):
if is_safe(board, row, col):
board[row] = col
solve(board, row + 1)
board[row] = -1
solutions = []
solve([-1] * n, 0)
return solutions
print(solve_n_queens(4)) # [[1, 3, 0, 2], [2, 0, 3, 1]]
`순열 생성`
- 주어진 리스트의 모든 순열을 생성하는 문제
- 백트래킹을 사용해 순서에 따라 숫자를 교환하며 순열을 생성
def permute(nums):
def backtrack(start):
if start == len(nums):
result.append(nums[:])
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start]
result = []
backtrack(0)
return result
print(permute([1, 2, 3])) # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
9. 비트 조작
'부분집합 생성'
- 주어진 집합의 모든 부분집합을 생성하는 문제
- 비트마스크를 사용해 가능한 모든 부분집합을 표현
def subsets(nums):
result = []
for i in range(1 << len(nums)):
subset = []
for j in range(len(nums)):
if i & (1 << j):
subset.append(nums[j])
result.append(subset)
return result
print(subsets([1, 2, 3])) # [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
10. 기타
'Flood Fill'
- 알고리즘 2D 배열에서 특정 색을 새로운 색으로 채우는 문제
- DFS를 사용해 연결된 모든 영역을 새로운 색으로 바꿈
def flood_fill(image, sr, sc, new_color):
rows, cols = len(image), len(image[0])
color_to_replace = image[sr][sc]
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != color_to_replace or image[r][c] == new_color:
return
image[r][c] = new_color
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
dfs(sr, sc)
return image
image = [
[1, 1, 1],
[1, 1, 0],
[1, 0, 1]
]
print(flood_fill(image, 1, 1, 2)) # [[2, 2, 2], [2, 2, 0], [2, 0, 1]]