[CT스터디] DP, 백트래킹, 투 포인터 기출 문제를 문제해결형으로 다시 정리하기

1. 짧은 도입부

이번 CT 스터디에서는 프로그래머스 문제를 단순히 “정답 코드 제출”로 끝내지 않고, 내가 어떤 지점에서 막혔고 왜 그 부분이 어려웠는지까지 같이 정리했다. 이번에 다룬 문제는 가장 큰 정사각형 찾기, 도둑질, 스티커 모으기(2), 불량 사용자, 보석 쇼핑이다. 앞의 세 문제는 DP 중심으로 풀었고, 뒤의 두 문제는 각각 백트래킹과 투 포인터/슬라이딩 윈도우 기출 문제로 다시 복습이 필요한 문제로 분류했다.

이번 학습에서 가장 중요했던 점은 “문제 유형을 맞히는 것”보다 “왜 그 유형으로 풀어야 하는가”를 이해하는 것이었다. 특히 DP 문제에서는 dp[i]가 무엇을 의미하는지, 원형 구조에서는 왜 첫 번째와 마지막을 동시에 고려하면 안 되는지, 백트래킹에서는 왜 선택 후 다시 취소해야 하는지, 투 포인터에서는 left와 right가 각각 어떤 상태를 표현하는지 이해하는 과정이 핵심이었다.

2. 핵심 작업 요약

이번 실습에서 해결한 문제는 총 5개다.

첫 번째는 가장 큰 정사각형 찾기였다. 이 문제는 2차원 배열에서 1로 이루어진 가장 큰 정사각형의 넓이를 구하는 문제였고, 현재 칸을 오른쪽 아래 꼭짓점으로 보는 DP 관점이 핵심이었다.

두 번째는 도둑질이었다. 원형으로 배치된 집에서 인접한 집을 털 수 없다는 조건이 있었고, 첫 번째 집과 마지막 집이 연결되어 있다는 점 때문에 문제를 두 개의 선형 DP 케이스로 나누어 해결했다.

세 번째는 스티커 모으기(2)였다. 도둑질 문제와 구조가 거의 같았지만, 스티커가 1개 또는 2개일 때의 예외 처리가 필요했고, 원형 배열을 선형 배열 두 개로 나누는 사고가 다시 사용되었다.

네 번째는 불량 사용자였다. 이 문제는 문자열 패턴 매칭과 백트래킹을 결합해야 했다. *가 포함된 banned_id 패턴에 user_id를 매칭하고, 이미 고른 사용자는 다시 고르지 않으며, 순서만 다른 같은 제재 목록은 하나로 세야 했다.

다섯 번째는 보석 쇼핑이었다. 모든 보석 종류를 포함하는 가장 짧은 연속 구간을 찾는 문제로, 투 포인터와 슬라이딩 윈도우를 사용했다. 특히 total_type_count, gem_count, left_gem, return answer의 들여쓰기 위치에서 헷갈림이 있었고, 이 부분은 다시 풀어볼 문제로 표시했다.

3. 문제 인식

이번 실습에서 가장 먼저 인식한 문제는 “정답 코드를 외워도 다음에 다시 풀 수 있을까?”였다. 특히 DP 문제는 코드만 보면 짧아 보이지만, 실제로는 dp 배열이 무엇을 저장하는지 이해하지 못하면 같은 유형을 만나도 다시 막히기 쉽다. 예를 들어 dp[i] = max(dp[i - 1], dp[i - 2] + 현재값)이라는 형태는 도둑질과 스티커 문제에서 반복되지만, 이 식을 단순 공식으로 외우면 왜 i - 2를 더하는지, 왜 i - 1은 그대로 가져오는지 설명하기 어렵다.

두 번째로 인식한 문제는 “문제에서 직접 말하지 않은 관점”을 코드가 요구한다는 점이었다. 가장 큰 정사각형 찾기에서는 문제에서 “현재 칸을 오른쪽 아래 꼭짓점으로 보라”고 말하지 않는다. 하지만 DP로 풀기 위해서는 현재 칸을 기준점으로 정하고, 왼쪽·위·왼쪽 위 값을 비교해야 한다. 이 관점은 문제 본문에 적힌 문장이 아니라 풀이자가 설정해야 하는 해석이다. 그래서 처음에는 “왜 갑자기 오른쪽 아래 꼭짓점이라는 말을 하는가”가 헷갈릴 수밖에 없었다.

세 번째 문제는 기출 문제에서 더 두드러졌다. 불량 사용자에서는 is_match()로 문자열 모양을 검사하는 부분과, selected_users로 이미 고른 사용자를 막는 부분이 서로 다른 역할을 한다. 하지만 처음에는 둘 다 “후보를 거르는 것”처럼 보여서 역할 구분이 어려웠다. 보석 쇼핑도 마찬가지였다. total_type_count는 전체 목표 종류 수이고, gem_count는 현재 구간 상태인데, 둘 다 “보석 종류”와 관련되어 있어 처음에는 차이가 흐릿하게 느껴졌다.

4. 문제 정의

이번 실습의 문제는 단순히 “문제를 맞히는 것”이 아니라, 각 알고리즘이 어떤 상태를 저장하고 어떤 기준으로 다음 선택을 하는지 스스로 설명할 수 있게 만드는 것이었다. 특히 이번 문제들은 모두 상태 관리가 핵심이었다. DP에서는 dp 배열이 이전 선택의 결과를 저장했고, 백트래킹에서는 selected_users가 현재까지의 선택 상태를 저장했으며, 투 포인터에서는 gem_count가 현재 구간 안의 보석 상태를 저장했다.

즉, 이번 실습의 핵심 문제는 “상태를 어떻게 정의할 것인가”였다. 상태 정의가 불명확하면 코드의 각 줄이 갑자기 등장한 것처럼 보인다. 예를 들어 shortest_length = len(gems) + 1은 단순히 큰 값을 넣는 코드처럼 보이지만, 실제로는 “아직 정답을 찾지 못했으므로 가능한 구간보다 더 큰 기준값을 둔다”는 의미가 있다. gem_count[gem] = gem_count.get(gem, 0) + 1 역시 단순 딕셔너리 문법이 아니라, right가 새 보석을 현재 구간에 추가했기 때문에 해당 보석의 개수를 1 늘리는 상태 갱신 코드다.

이번 문제 정의는 다음과 같이 정리할 수 있다.

각 문제에서 필요한 상태를 먼저 정의하고, 그 상태가 언제 증가하고 언제 감소하는지 설명할 수 있어야 한다.

5. 왜 이것을 문제로 인식했는가

이것을 문제로 인식한 이유는 같은 유형의 문제가 반복되는데도 매번 새로운 문제처럼 느껴졌기 때문이다. 예를 들어 도둑질과 스티커 모으기(2)는 둘 다 원형 구조에서 인접한 값을 동시에 선택할 수 없다는 조건을 가진다. 하지만 한 문제를 풀었다고 해서 바로 다음 문제가 쉽게 풀리지는 않았다. 이유는 “원형이라서 첫 번째와 마지막을 동시에 선택하면 안 된다”는 조건을 어떻게 코드로 분리해야 하는지 완전히 내 것으로 만들지 못했기 때문이다.

또한 불량 사용자와 보석 쇼핑은 기출 문제라서 다시 풀어볼 가치가 크다고 판단했다. 불량 사용자는 후보 목록을 만든 뒤 DFS로 조합을 탐색해야 하고, 보석 쇼핑은 right로 구간을 늘리고 left로 구간을 줄이는 슬라이딩 윈도우 상태 갱신을 해야 한다. 두 문제 모두 코드가 짧아 보여도, 실제로는 “왜 이 시점에서 이 변수를 바꾸는가”를 이해하지 못하면 다시 풀기 어렵다.

특히 보석 쇼핑에서는 left_gem = gems[left] 이후 gem_count[left_gem] -= 1이 왜 가능한지 헷갈렸다. 처음에는 gems[0] 같은 문자열 값에서 1을 빼는 것처럼 느껴졌지만, 실제로는 문자열에서 빼는 것이 아니라 딕셔너리에 저장된 해당 보석의 개수를 줄이는 것이었다. 이처럼 코드의 표면 문법과 실제 의미가 다르게 느껴지는 지점이 많았고, 이 부분을 문제 해결 기록으로 남기는 것이 필요했다.

6. 문제 해결 경험 1: 가장 큰 정사각형 찾기

가장 큰 정사각형 찾기는 1과 0으로 이루어진 2차원 배열에서 1로 이루어진 가장 큰 정사각형의 넓이를 구하는 문제다. 처음에는 단순히 모든 칸을 돌면서 정사각형을 직접 확인하는 방식을 떠올릴 수 있지만, board의 행과 열 크기가 각각 최대 1,000이기 때문에 모든 정사각형 후보를 직접 검사하면 비효율적이다.

문제 해결의 핵심은 현재 칸을 “오른쪽 아래 꼭짓점”으로 해석하는 것이었다. 현재 칸이 1이라면, 왼쪽·위·왼쪽 위 세 방향이 만들어낼 수 있는 정사각형 크기 중 가장 작은 값에 1을 더해 현재 칸 기준의 정사각형 한 변 길이를 구할 수 있다. 이때 dp[row][col]은 현재 칸을 오른쪽 아래 꼭짓점으로 하는 가장 큰 정사각형의 한 변 길이를 의미한다.

def solution(board):
    row_count = len(board)
    col_count = len(board[0])

    dp = [[0] * col_count for _ in range(row_count)]

    max_side = 0

    for row in range(row_count):
        for col in range(col_count):
            if board[row][col] == 1:
                if row == 0 or col == 0:
                    dp[row][col] = 1
                else:
                    dp[row][col] = min(
                        dp[row][col - 1],
                        dp[row - 1][col - 1],
                        dp[row - 1][col]
                    ) + 1

            max_side = max(max_side, dp[row][col])

    return max_side * max_side

이 문제에서 어려웠던 점은 board[row][col] 자체를 바꾸는 풀이와 별도의 dp 배열을 사용하는 풀이의 차이였다. board를 직접 갱신하면 메모리는 줄일 수 있지만, 원래 0과 1을 담던 배열이 어느 순간부터 “정사각형 한 변 길이”를 담는 배열로 의미가 바뀐다. 이 의미 변화가 헷갈릴 수 있어 별도 dp 배열을 두는 방식으로 정리했다.

이미지 1 — 가장 큰 정사각형 찾기에서 2차원 DP 기준을 잡고 정답 제출을 완료한 결과

7. 문제 해결 경험 2: 도둑질

도둑질은 원형으로 배치된 집에서 인접한 두 집을 동시에 털 수 없을 때 훔칠 수 있는 돈의 최댓값을 구하는 문제다. 기본 구조는 “현재 집을 털 것인가, 털지 않을 것인가”를 비교하는 DP다. 하지만 일반적인 선형 DP와 달리 첫 번째 집과 마지막 집이 서로 인접해 있다는 점이 추가된다.

처음 문제를 풀 때의 핵심 문제는 원형 구조를 어떻게 선형 DP로 바꿀 것인가였다. 원형에서는 첫 번째 집을 털면 마지막 집을 털 수 없고, 마지막 집을 털면 첫 번째 집을 털 수 없다. 그래서 문제를 두 케이스로 나누었다. 하나는 마지막 집을 제외한 경우이고, 다른 하나는 첫 번째 집을 제외한 경우다. 두 케이스를 각각 선형 DP로 풀고 더 큰 값을 반환했다.

def solution(money):
    def steal_line(money):
        house_count = len(money)

        dp = [0] * house_count
        dp[0] = money[0]
        dp[1] = max(money[0], money[1])

        for i in range(2, house_count):
            dp[i] = max(dp[i - 1], dp[i - 2] + money[i])

        return dp[house_count - 1]

    case_without_last_house = steal_line(money[:-1])
    case_without_first_house = steal_line(money[1:])

    return max(case_without_last_house, case_without_first_house)

여기서 dp[i]는 i번째 집까지 고려했을 때 훔칠 수 있는 최대 금액이다. 현재 집을 털면 바로 전 집은 털 수 없으므로 dp[i — 2] + money[i]가 된다. 현재 집을 털지 않으면 이전까지의 최댓값인 dp[i — 1]을 그대로 가져온다. 결국 두 선택지 중 더 큰 값을 고르면 된다.

이미지 2 — 원형 집 배치 조건을 두 개의 선형 DP 케이스로 분리해 정답 제출을 완료한 결과

8. 문제 해결 경험 3: 스티커 모으기(2)

스티커 모으기(2)는 도둑질 문제와 거의 같은 구조를 가진다. 스티커가 원형으로 연결되어 있고, 하나의 스티커를 뜯으면 양쪽 인접 스티커는 사용할 수 없다. 따라서 인접한 값을 동시에 선택할 수 없고, 첫 번째 원소와 마지막 원소가 서로 연결되어 있다는 조건도 동일하다.

차이는 입력 길이가 1부터 시작한다는 점이다. 그래서 스티커가 1개 또는 2개일 때는 DP 배열을 만들 필요 없이 바로 최댓값을 반환해야 한다. 이 예외 처리를 하지 않으면 dp[1]을 설정하는 과정에서 인덱스 오류가 발생할 수 있다.

def solution(sticker):
    sticker_count = len(sticker)

    if sticker_count <= 2:
        return max(sticker)

    def cut_sticker(line_sticker):
        line_sticker_count = len(line_sticker)

        dp = [0] * line_sticker_count
        dp[0] = line_sticker[0]
        dp[1] = max(line_sticker[0], line_sticker[1])

        for i in range(2, line_sticker_count):
            dp[i] = max(dp[i - 1], dp[i - 2] + line_sticker[i])

        return dp[line_sticker_count - 1]

    case_without_last_sticker = cut_sticker(sticker[:-1])
    case_without_first_sticker = cut_sticker(sticker[1:])

    return max(case_without_last_sticker, case_without_first_sticker)

이 문제를 통해 원형 DP 문제에서 자주 사용하는 전략을 다시 확인했다. 원형 구조를 직접 DP로 처리하려고 하기보다, 충돌하는 양 끝 중 하나를 제외한 두 케이스로 나누면 선형 DP 문제로 바뀐다. 이 사고방식은 도둑질과 스티커 문제 모두에서 동일하게 적용된다.

이미지 3 — 스티커 모으기(2)에서 원형 구조를 두 케이스로 분리하고 정답 제출을 완료한 결과

9. 문제 해결 경험 4: 불량 사용자

불량 사용자는 이번 실습에서 다시 풀어볼 문제로 분류했다. 이 문제는 단순 문자열 비교가 아니라, *가 포함된 banned_id 패턴과 user_id를 매칭해야 한다. 또한 같은 사용자가 중복해서 제재 아이디 목록에 들어가면 안 되고, 순서만 다른 같은 목록은 하나로 세야 한다.

처음에는 is_match() 함수가 모든 문제를 해결해주는 것처럼 보일 수 있다. 하지만 is_match()는 오직 user_id 하나가 banned_id 패턴 하나와 모양이 맞는지만 확인한다. 이미 선택한 사용자인지 여부는 selected_users가 따로 관리해야 한다. 이 역할 분리가 이 문제의 핵심이었다.

def solution(user_id, banned_id):
    candidate_list = []

    def is_match(user, banned):
        if len(user) != len(banned):
            return False

        for index in range(len(user)):
            if banned[index] == "*":
                continue

            if user[index] != banned[index]:
                return False

        return True

    for banned in banned_id:
        candidates = []

        for user in user_id:
            if is_match(user, banned):
                candidates.append(user)

        candidate_list.append(candidates)

    result_set = set()

    def dfs(banned_index, selected_users):
        if banned_index == len(banned_id):
            result_set.add(tuple(sorted(selected_users)))
            return

        for user in candidate_list[banned_index]:
            if user in selected_users:
                continue

            selected_users.add(user)
            dfs(banned_index + 1, selected_users)
            selected_users.remove(user)

    dfs(0, set())

    return len(result_set)

이 문제에서 복잡했던 부분은 백트래킹의 세 줄이었다.

selected_users.add(user)
dfs(banned_index + 1, selected_users)
selected_users.remove(user)

이 세 줄은 “선택한다 → 다음 단계로 간다 → 다시 선택을 취소한다”는 흐름이다. 처음에는 왜 다시 remove를 해야 하는지 헷갈릴 수 있지만, 한 후보를 선택한 경우를 모두 확인한 뒤에는 다른 후보도 시도해야 하므로 현재 선택을 되돌려야 한다. 이것이 백트래킹의 핵심이다.

또한 완성된 제재 목록을 저장할 때 tuple(sorted(selected_users))를 사용했다. 순서만 다른 같은 목록을 하나로 세야 하므로 먼저 정렬하고, set에 넣을 수 있도록 tuple로 변환했다. 이 부분은 기출 문제로 다시 풀어볼 때 반드시 다시 확인해야 할 지점이다.

이미지 4 — 불량 사용자에서 패턴 매칭, DFS, 중복 제거를 결합해 정답 제출을 완료한 결과

10. 문제 해결 경험 5: 보석 쇼핑

보석 쇼핑 역시 다시 풀어볼 기출 문제로 분류했다. 이 문제는 모든 종류의 보석을 적어도 하나 이상 포함하는 가장 짧은 연속 구간을 찾아야 한다. 배열 길이가 최대 100,000이기 때문에 모든 시작점과 끝점을 조합하는 방식은 적절하지 않다. 따라서 left와 right 두 포인터로 현재 구간을 관리하는 슬라이딩 윈도우 방식이 필요했다.

이 문제에서 어려웠던 부분은 변수들의 역할이었다. total_type_count는 전체 보석 종류 수이고, gem_count는 현재 left부터 right까지 구간 안에 들어 있는 보석 개수표다. len(gem_count)는 딕셔너리의 key 개수를 세므로 현재 구간에 존재하는 보석 종류 수가 된다. 따라서 len(gem_count) == total_type_count이면 현재 구간이 모든 보석 종류를 포함한다는 뜻이다.

def solution(gems):
    total_type_count = len(set(gems))

    gem_count = {}

    left = 0

    shortest_length = len(gems) + 1
    answer = [1, len(gems)]

    for right in range(len(gems)):
        gem = gems[right]
        gem_count[gem] = gem_count.get(gem, 0) + 1

        while len(gem_count) == total_type_count:
            current_length = right - left + 1

            if current_length < shortest_length:
                shortest_length = current_length
                answer = [left + 1, right + 1]

            left_gem = gems[left]
            gem_count[left_gem] -= 1

            if gem_count[left_gem] == 0:
                del gem_count[left_gem]

            left += 1

    return answer

이 문제에서 실제로 막혔던 지점은 gem_count[gem] = gem_count.get(gem, 0) + 1이었다. 이 코드는 현재 구간에 새 보석을 하나 추가하는 코드다. get(gem, 0)은 기존에 해당 보석이 있으면 그 개수를 가져오고, 없으면 0으로 시작한다. 여기에 1을 더하는 이유는 right가 현재 보석을 새로 담았기 때문이다.

또 다른 헷갈림은 gem_count[left_gem] -= 1이었다. 처음에는 gems[left]가 문자열인데 문자열에서 1을 빼는 것처럼 보일 수 있다. 하지만 실제로는 문자열에서 빼는 것이 아니라, 딕셔너리에 기록된 해당 보석의 개수를 하나 줄이는 것이다. 즉 left_gem = "DIA"라면 gem_count["DIA"] -= 1이 실행된다.

마지막으로 오류가 발생했던 부분은 return answer의 위치였다. return answer가 for문 안에 들어가 있으면 right = 0일 때 첫 번째 보석만 보고 바로 함수가 끝나버린다. 실제로 첫 번째 테스트에서 [1, 8]이 반환된 이유도 이 때문이었다. 이 문제는 알고리즘 자체보다 들여쓰기 위치가 결과를 바꾼 사례였다.

11. 복잡한 문제 해결 경험

이번 실습에서 가장 복잡했던 문제는 불량 사용자와 보석 쇼핑이었다. 두 문제는 모두 상태가 계속 변한다는 공통점이 있다. 불량 사용자에서는 DFS가 깊어질수록 selected_users가 변하고, 탐색이 끝나면 다시 원래 상태로 되돌려야 한다. 보석 쇼핑에서는 right가 이동할 때 gem_count가 증가하고, left가 이동할 때 gem_count가 감소한다.

이 두 문제는 “상태를 추가하는 코드”와 “상태를 제거하는 코드”를 정확히 짝지어야 한다. 불량 사용자에서는 selected_users.add(user)와 selected_users.remove(user)가 한 쌍이다. 보석 쇼핑에서는 gem_count[gem] = gem_count.get(gem, 0) + 1과 gem_count[left_gem] -= 1이 한 쌍이다.

복잡한 문제를 해결할 때 단순히 코드를 따라 쓰는 것보다 중요한 것은 이 쌍을 이해하는 것이었다. 어떤 값을 추가했으면, 언제 제거해야 하는지 설명할 수 있어야 한다. 그리고 제거했을 때 그 값이 완전히 사라졌다면 딕셔너리에서 key까지 삭제해야 한다. 그렇지 않으면 len(gem_count)가 실제 보석 종류 수와 달라지기 때문이다.

12. 성과

이번 실습을 통해 DP, 백트래킹, 투 포인터 문제를 한 번에 정리했다. 단순히 정답을 제출한 것뿐 아니라, 각 문제에서 내가 헷갈렸던 지점을 명확히 분리했다.

가장 큰 정사각형 찾기에서는 2차원 DP에서 기준점을 어떻게 잡는지 익혔다. 도둑질과 스티커 모으기(2)에서는 원형 구조를 선형 DP 두 개로 분리하는 전략을 반복해서 확인했다. 불량 사용자에서는 패턴 매칭과 백트래킹, 중복 제거를 결합했다. 보석 쇼핑에서는 투 포인터로 현재 구간을 확장하고 축소하는 방식을 익혔다.

마지막 두 문제는 기출 문제이기도 하고, 상태 관리가 복잡했기 때문에 다시 풀어볼 문제로 남겨두었다. 특히 불량 사용자는 add → dfs → remove 흐름을, 보석 쇼핑은 right로 담고 left로 줄이는 흐름을 다시 손으로 써보며 복습할 필요가 있다.

13. 사용한 주요 수식/코드 정리

13–1. 정사각형 DP 점화식

dp[row][col] = min(
    dp[row][col - 1],
    dp[row - 1][col - 1],
    dp[row - 1][col]
) + 1

이 식은 현재 칸을 오른쪽 아래 꼭짓점으로 하는 정사각형의 한 변 길이를 구하기 위해 사용했다. 왼쪽, 위, 왼쪽 위 중 하나라도 작으면 큰 정사각형을 만들 수 없기 때문에 세 값 중 최솟값에 현재 칸 1개를 더한다.

13–2. 인접 선택 금지 DP 점화식

dp[i] = max(dp[i - 1], dp[i - 2] + money[i])

이 식은 현재 값을 선택하지 않는 경우와 선택하는 경우를 비교한다. 현재 값을 선택하면 바로 전 값은 선택할 수 없으므로 두 칸 전의 최댓값을 사용한다.

13–3. 백트래킹 선택과 취소

selected_users.add(user)
dfs(banned_index + 1, selected_users)
selected_users.remove(user)

이 코드는 한 후보를 선택해 다음 단계로 넘어간 뒤, 다른 후보를 시도하기 위해 다시 선택을 취소하는 구조다.

13–4. 슬라이딩 윈도우 보석 개수 갱신

gem_count[gem] = gem_count.get(gem, 0) + 1

이 코드는 right가 새 보석을 담았을 때 현재 구간 안의 보석 개수를 하나 늘리는 코드다.

gem_count[left_gem] -= 1

if gem_count[left_gem] == 0:
    del gem_count[left_gem]

이 코드는 left가 이동하면서 구간의 맨 앞 보석을 하나 제거하는 코드다. 개수가 0이 되면 현재 구간에 그 보석 종류가 없다는 뜻이므로 딕셔너리에서 삭제한다.

14. 최종 정리

이번 CT 스터디는 문제를 많이 푸는 것보다, 각 문제에서 필요한 상태를 정확히 정의하는 데 집중한 실습이었다. DP에서는 dp가 무엇을 저장하는지, 백트래킹에서는 현재 선택 상태가 무엇인지, 투 포인터에서는 현재 구간 상태가 무엇인지 계속 확인했다.

가장 중요한 학습 포인트는 “변수는 그냥 이름이 아니라 문제의 상태를 담는 그릇”이라는 점이었다. total_type_count, gem_count, selected_users, result_set, shortest_length 같은 변수들은 각각 문제 해결에서 다른 역할을 가진다. 이 역할을 구분하지 못하면 코드가 갑자기 복잡해 보이고, 역할을 구분하면 코드가 문제 조건을 그대로 옮긴 것처럼 보인다.

마지막 두 문제인 불량 사용자와 보석 쇼핑은 다시 풀어볼 문제로 남겨두었다. 두 문제 모두 기출이며, 단순 구현보다 상태 변화의 순서를 이해해야 풀 수 있다. 다음 복습에서는 코드를 보지 않고 candidate_list → dfs → result_set, right → gem_count 증가 → while → left 감소 흐름을 직접 다시 작성하는 것을 목표로 한다.

15. Portfolio Summary

This study session focused on solving algorithmic problems not only for correctness, but also for understanding how each algorithm manages state. The problems covered dynamic programming, backtracking, and two-pointer sliding window techniques. Rather than treating the submitted code as isolated answers, I analyzed why each variable was needed, what state it represented, and how the state changed during execution.

A key outcome of this session was identifying which problems require further review. The backtracking problem required a clear understanding of candidate generation, duplicate prevention, recursive exploration, and rollback. The sliding window problem required careful handling of dictionary-based counts, pointer movement, and return placement. These details are directly relevant to coding interviews because they test whether I can reason through state transitions instead of only memorizing solution templates.

16. Key skills practiced

• 2차원 DP 상태 정의
• 정사각형 DP 점화식 구성
• 원형 배열을 선형 케이스로 분리하는 사고
• 인접 선택 금지 DP 문제 해결
• 작은 입력에 대한 예외 처리
• 문자열 패턴 매칭
• 백트래킹의 선택/탐색/취소 구조
• set을 이용한 중복 조합 제거
• tuple과 sorted를 이용한 순서 무관 조합 저장
• 투 포인터와 슬라이딩 윈도우 구간 관리
• 딕셔너리를 이용한 빈도 계산
• Python 인덱스와 문제 번호 체계 변환
• return 위치와 들여쓰기 오류 디버깅
• 기출 문제 재풀이 대상 선정 및 복습 전략 수립