알고리즘 난이도별 실전 문제 풀이와 코딩테스트 꿀팁

11.1 단계별 난이도별 문제 리스트

1. 입문(기초) 문제

• 배열/문자열 다루기:
  • 배열에서 최댓값/최솟값 찾기
  • 문자열 뒤집기
  • 팰린드롬 판별
• 자료구조 기본:
  • 스택/큐 구현
  • 해시맵(딕셔너리) 사용
• 기초 탐색/정렬:
  • 선형 탐색, 이진 탐색
  • 버블/선택/삽입 정렬

2. 중급 문제

• 재귀, 분할정복:
  • 피보나치 수열
  • 병합 정렬
  • 하노이의 탑
• 그리디:
  • 동전 거스름돈
  • 회의실 배정
• 그래프 탐색:
  • BFS/DFS로 미로 탐색
  • 연결 요소 개수 세기
• DP:
  • 계단 오르기
  • 최대 연속 부분합
  • 동전 조합

3. 고급 문제

• 최단 경로:
  • 다익스트라, 플로이드-워셜
• 최소 신장 트리:
  • 크루스칼, 프림
• 위상 정렬:
  • 작업 순서, 순환 참조 판별
• 네트워크 플로우:
  • 최대 유량
• 고급 DP:
  • 0-1 배낭 문제
  • 최장 증가 부분 수열
  • LCS(최장 공통 부분 수열)
• 기타:
  • 트라이, 세그먼트 트리
  • 비트마스킹

11.2 실전 문제 풀이 및 해설

예시 1: 배열에서 두 수의 합 (Two Sum, 기초)

문제:

정수 배열 nums와 정수 target이 주어질 때, 합이 target이 되는 두 수의 인덱스를 반환하세요.

풀이:

• 해시맵을 사용해 한 번에 해결 (O(n))
• 각 원소를 순회하며, target-현재값이 해시맵에 있으면 정답

def two_sum(nums, target):
    num_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i
*# 예시 실행*
print(two_sum([2, 7, 11, 15], 9))  *# [0, 1]*

예시 2: 미로 탐색 (BFS, 중급)

문제:

0은 이동 가능, 1은 벽인 2D 배열에서 (0,0)에서 (N-1,M-1)까지 최단 거리 구하기.

풀이:

• BFS로 레벨별로 탐색, 방문 체크 필요

from collections import deque

def bfs_maze(maze):
    n, m = len(maze), len(maze[0])
    visited = [[False]*m for _ in range(n)]
    queue = deque([(0, 0, 1)])  *# (x, y, 거리)*
    visited[0][0] = True
    dx, dy = [1,0,-1,0], [0,1,0,-1]
    while queue:
        x, y, dist = queue.popleft()
        if x == n-1 and y == m-1:
            return dist
        for d in range(4):
            nx, ny = x+dx[d], y+dy[d]
            if 0<=nx<n and 0<=ny<m and not visited[nx][ny] and maze[nx][ny]==0:
                visited[nx][ny] = True
                queue.append((nx, ny, dist+1))
    return -1
*# 예시 실행*
maze = [
    [0,1,0,0],
    [0,1,0,1],
    [0,0,0,0]
]
print(bfs_maze(maze))  *# 7*

예시 3: 0-1 배낭 문제 (DP, 고급)

문제:

각 물건의 무게와 가치가 주어질 때, 최대 무게 W를 넘지 않으면서 최대 가치를 얻는 조합의 가치를 구하세요.

풀이:

• DP 테이블을 사용해 부분 문제의 최적해를 저장

ef knapsack(W, weights, values):
    n = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(W+1):
            if weights[i-1] > w:
                dp[i][w] = dp[i-1][w]
            else:
                dp[i][w] = max(dp[i-1][w], values[i-1]+dp[i-1][w-weights[i-1]])
    return dp[n][W]
*# 예시 실행*
print(knapsack(5, [2,3,4,5], [3,4,5,6]))  *# 7*

11.3 실전 코딩 테스트 팁

1. 문제 읽기와 이해

• 문제를 꼼꼼히 읽고, 예시 입력/출력을 직접 손으로 따라해보기
• 입력 범위, 시간 제한, 특이 조건(음수, 중복 등) 체크

2. 알고리즘/자료구조 선택

• 입력 크기(1~1,000: 완전탐색/브루트포스, 1,000,000: O(n)~O(n log n) 알고리즘)
• 그래프 문제는 BFS/DFS, 최단 경로는 다익스트라/플로이드워셜 등

3. 빠른 입출력 활용

• Python: input() 대신 sys.stdin.readline() 사용
• 대량 입력은 미리 리스트로 받아 처리

4. 디버깅/테스트

• 예외 케이스(빈 배열, 최대/최소값, 중복 등) 직접 넣어보기
• print로 중간 값 확인, 시간 초과 시 부분 주석 처리로 범위 줄여보기

5. 시간 관리

• 한 문제에 너무 오래 매달리지 말고, 막히면 다음 문제로 넘어가기
• 쉬운 문제 먼저 풀고, 어려운 문제는 나중에

6. 코드 스타일

• 변수명, 함수명 명확히
• 주석 활용, 불필요한 코드 제거
• 제출 전 불필요한 print문 제거

7. 실전 연습

• 백준, 프로그래머스, LeetCode 등에서 실전처럼 시간 재고 문제 풀기
• 최근 출제 경향(구현, 그리디, 그래프, DP 등) 파악