모의면접 2 — Medium 3문제 실전

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity
    
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # 접근한 키를 맨 뒤로 이동 (최근 사용)
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        # 용량 초과 시 가장 오래된 (맨 앞) 항목 제거
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

def num_islands(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(r, c):
        # 범위 밖이거나 물이면 종료
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] == '0':
            return
        
        grid[r][c] = '0'  # 방문 표시
        dfs(r + 1, c)     # 상하좌우 탐색
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)  # 연결된 모든 땅을 물로 변환
    
    return count

def coin_change(coins, amount):
    # dp[i] = 금액 i를 만드는 최소 동전 수
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 0원은 동전 0개
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1