카우에의 삶의 방식
LeetCode Hard 문제를 풀다 보면 마치 거대한 벽에 부딪힌 듯한 기분이 들 때가 많습니다. 하지만 동적 계획법(Dynamic Programming), 백트래킹(Backtracking), 그래프 이론(Graph Theory)처럼 이해하기 쉬운 패턴으로 문제를 쪼개어 보면 훨씬 수월하게 접근할 수 있습니다.
이 글에서는 제가 Go로 해결한 가장 흥미로운 LeetCode Hard 문제 7가지를 공유합니다. 이 가이드를 최대한 유용하게 활용할 수 있도록 **핵심 직관(intuition)**과 **복잡도(complexity)**에 집중하여 설명을 정리했으며, 문제 설명에서 실제 동작하는 코드로 넘어가는 과정을 쉽게 이해할 수 있도록 구성했습니다.
과 가 주어졌을 때, 부터 까지의 숫자로 이루어진 순열 중 번째 순열 수열을 반환하세요.
예를 들어, 이면 순열은 "123", "132", "213", "231", "312", "321"입니다. 이라면 정답은 "213"입니다.
모든 순열을 생성하는 대신(너무 느립니다), 팩토리얼을 활용한 수학적 접근법을 사용할 수 있습니다.
개의 숫자에 대해 총 개의 순열이 존재합니다. 첫 번째 숫자를 고정하면 나머지 숫자들로 만들 수 있는 순열은 개가 됩니다. 따라서 번째 순열이 개짜리 블록 중 몇 번째 블록에 속하는지 계산하면 첫 번째 숫자를 결정할 수 있습니다. 사용 가능한 숫자들의 정렬된 리스트에서 다음 숫자의 인덱스는 단순히 이 됩니다. 숫자를 하나 선택한 후에는 를 나머지 값인 로 갱신하고 재귀 호출을 수행합니다.
import "fmt"
func getPermutation(n int, k int) string {
factorial := 1
digits := []int{}
// 팩토리얼을 계산하고 digits 슬라이스를 채웁니다
for i := 1; i <= n; i++ {
factorial *= i
digits = append(digits, i)
}
return solvePermutation(n-1, k-1, factorial/n, digits)
}
func solvePermutation(n, k, factorial int, digits []int) string {
// 'k'가 어느 순열 블록에 속하는지 찾습니다
index := k / factorial
res := fmt.Sprintf("%d", digits[index])
if n <= 0 {
return res
}
// 다음 단계를 위해 k 갱신: k % factorial
// 다음 단계를 위해 factorial 갱신: factorial / n
// 선택된 숫자를 슬라이스에서 제거
nextK := k % factorial
nextFactorial := factorial / n
remainingDigits := append(digits[:index], digits[index+1:]...)
res += solvePermutation(n-1, nextK, nextFactorial, remainingDigits)
return res
}
.(임의의 단일 문자와 일치)과 *(앞선 요소가 0번 이상 반복됨을 의미)를 지원하는 정규 표현식 매칭을 구현하세요. 매칭은 입력 문자열 전체를 포괄해야 합니다.
이 문제는 고전적인 동적 계획법(Dynamic Programming) 문제입니다. 중복 계산을 피하기 위해 메모이제이션(memoization)을 사용할 수 있습니다.
문자열 s와 패턴 p의 특정 문자 조합에서 패턴의 다음 문자가 *인 경우, 우리에게는 두 가지 선택지가 있습니다.
s에서 문자 하나를 소비하되 추가로 더 매칭할 가능성을 열어두기 위해 p에서는 * 위치에 그대로 머무릅니다.func isMatch(s string, p string) bool {
sn, pn := len(s), len(p)
memo := make([][]int, sn+1)
for i := range memo {
memo[i] = make([]int, pn+1)
}
return solveRegex(s, p, sn, pn, 0, 0, memo)
}
func solveRegex(s, p string, sn, pn, si, pi int, memo [][]int) bool {
if memo[si][pi] == 1 { return false }
if memo[si][pi] == 2 { return true }
res := false
if si == sn && pi == pn {
res = true
} else if pi+1 < pn && p[pi+1] == '*' {
// 옵션 A: 0번 등장하는 경우
if solveRegex(s, p, sn, pn, si, pi+2, memo) {
res = true
// 옵션 B: 1번 이상 등장하는 경우 (현재 문자가 일치할 때)
} else if si < sn && (p[pi] == '.' || p[pi] == s[si]) && solveRegex(s, p, sn, pn, si+1, pi, memo) {
res = true
}
} else if si < sn && pi < pn && (p[pi] == '.' || p[pi] == s[si]) {
// 일반 문자 일치
res = solveRegex(s, p, sn, pn, si+1, pi+1, memo)
}
if res {
memo[si][pi] = 2
} else {
memo[si][pi] = 1
}
return res
}
비어 있지 않은 이진 트리가 주어졌을 때 최대 경로 합을 구하세요. 경로는 부모-자식 연결을 따라 위아래로 이동할 수 있지만 반드시 루트를 거칠 필요는 없습니다.
깊이 우선 탐색(DFS)을 사용합니다. 모든 노드에서 두 가지 유형의 경로를 평가합니다.
fromRoot): 현재 노드에서 시작하여 자식 중 한쪽 브랜치로 내려가는 최대 경로입니다. 부모 노드는 이 경로를 이어받아 사용할 수 있습니다.other): 현재 서브트리 내부에 완전히 포함된 최대 경로입니다(예: 왼쪽 자식에서 올라와 현재 노드를 거쳐 오른쪽 자식으로 내려가는 아치형 경로). 이 경로는 “닫혀” 있으므로 부모 노드 쪽으로 더 확장할 수 없습니다.전체 최댓값은 우리가 찾은 모든 “확장 불가능한” 경로들과 루트의 확장 가능한 경로 중 가장 큰 값이 됩니다.
import "math"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func maxPathSum(root *TreeNode) int {
fromRoot, other := solveTree(root)
if fromRoot > other {
return fromRoot
}
return other
}
func solveTree(root *TreeNode) (int, int) {
if root == nil {
return math.MinInt, math.MinInt
}
left, otherLeft := solveTree(root.Left)
right, otherRight := solveTree(root.Right)
// 확장 가능한 경로 (한쪽 브랜치만 선택하거나 현재 노드에서 멈출 수 있음)
currentFromRoot := max([]int{
root.Val,
sum([]int{root.Val, left}),
sum([]int{root.Val, right}),
})
// 닫힌 경로 (현재 노드를 가로지르는 아치 형태이거나 자식 서브트리 내부에 완전히 포함됨)
currentOther := max([]int{
left, right, otherLeft, otherRight,
sum([]int{root.Val, left, right}),
})
return currentFromRoot, currentOther
}
func max(s []int) int {
res := math.MinInt
for _, v := range s {
if v > res { res = v }
}
return res
}
func sum(s []int) int {
res := 0
for _, v := range s {
if v == math.MinInt { return math.MinInt }
res += v
}
return res
}
9x9 스도쿠 퍼즐을 푸는 프로그램을 작성하세요. 표준 스도쿠 규칙(행, 열, 3x3 서브 박스)을 만족해야 합니다.
이 문제는 백트래킹(backtracking) 알고리즘이 필요합니다. 알고리즘을 효율적으로 만들고 LeetCode에서 시간 초과(TLE) 오류를 피하기 위해 휴리스틱(heuristic)을 사용하여 탐색을 최적화합니다. 즉, 가능한 유효 숫자의 개수가 가장 적은 빈 칸부터 먼저 채우기를 시도합니다. 특정 숫자가 행, 열 또는 3x3 박스에서 사용 가능한지 즉시 확인하기 위해 불리언(boolean) 배열을 사용합니다.
func solveSudoku(board [][]byte) {
var rows, cols [9][9]bool
var boxes [3][3][9]bool
// 초기 상태 기록
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if board[i][j] != '.' {
idx := board[i][j] - '1'
rows[i][idx], cols[j][idx], boxes[i/3][j/3][idx] = true, true, true
}
}
}
backtrackSudoku(board, &rows, &cols, &boxes)
}
func backtrackSudoku(board [][]byte, rows, cols *[9][9]bool, boxes *[3][3][9]bool) bool {
bestI, bestJ := -1, -1
minOptions := 10 // 가능한 최대 선택지 수(9)보다 큰 값으로 시작
// 휴리스틱: 유효한 선택지가 가장 적은 칸을 찾습니다
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if board[i][j] == '.' {
options := 0
for val := 0; val < 9; val++ {
if !rows[i][val] && !cols[j][val] && !boxes[i/3][j/3][val] {
options++
}
}
if options < minOptions {
minOptions = options
bestI, bestJ = i, j
}
}
}
}
// 기저 사례: 더 이상 빈 칸이 없음
if bestI == -1 { return true }
// 선택된 최적의 칸에 유효한 숫자들을 넣어봅니다
for val := 0; val < 9; val++ {
if !rows[bestI][val] && !cols[bestJ][val] && !boxes[bestI/3][bestJ/3][val] {
board[bestI][bestJ] = byte(val + '1')
rows[bestI][val], cols[bestJ][val], boxes[bestI/3][bestJ/3][val] = true, true, true
if backtrackSudoku(board, rows, cols, boxes) {
return true
}
// 백트래킹
board[bestI][bestJ] = '.'
rows[bestI][val], cols[bestJ][val], boxes[bestI/3][bestJ/3][val] = false, false, false
}
}
return false
}
부터 까지 번호가 매겨진 개의 강좌가 있음을 나타내는 정수 이 주어집니다. 또한 선수 과목 관계를 나타내는 배열 relations(relations[i] = [prevCourse, nextCourse])가 주어집니다. 한 학기에 최대 개의 강좌를 수강할 수 있습니다. 모든 강좌를 수강하는 데 필요한 최소 학기 수를 반환하세요.
이 작기 때문에(), 너비 우선 탐색(BFS)과 비트마스크(Bitmasks)를 결합하여 사용할 수 있습니다.
비트마스크는 지금까지 완료한 강좌들의 상태를 나타냅니다. 매 학기마다 수강 가능한 모든 강좌(선수 과목 조건이 모두 충족된 강좌)를 파악합니다. 수강 가능한 강좌가 개를 초과하면, 서브마스크 열거를 통해 크기가 인 모든 가능한 조합을 순회해야 합니다. 동일한 조합을 다시 방문하는 것을 방지하기 위해 방문 여부 맵(added)을 사용합니다.
func minNumberOfSemesters(n int, relations [][]int, k int) int {
// prerequisites[i]는 강좌 i를 듣기 전에 반드시 수강해야 하는 강좌들의 비트마스크입니다
prerequisites := make([]int, n)
for _, relation := range relations {
prevCourse := relation[0] - 1
nextCourse := relation[1] - 1
prerequisites[nextCourse] |= 1 << prevCourse
}
// states와 costs는 BFS 큐 역할을 합니다
states := []int{0}
costs := []int{0}
added := map[int]bool{0: true}
for cur := 0; ; cur++ {
state := states[cur]
cost := costs[cur]
// 기저 사례: 모든 강좌를 수강 완료함
if state == (1<<n)-1 {
return cost
}
// 이번 학기에 수강 가능한 모든 강좌를 찾습니다
courses := []int{}
next := state
for course := 0; course < n; course++ {
bit := 1 << course
if (state&bit) == 0 && (prerequisites[course]|state) == state {
courses = append(courses, course)
next |= bit
}
}
add := func(next int) {
if added[next] {
return
}
added[next] = true
states = append(states, next)
costs = append(costs, cost+1)
}
// 수강 가능한 모든 강좌를 한 학기에 다 들을 수 있다면 그대로 진행합니다
if len(courses) <= k {
add(next)
continue
}
// 그렇지 않다면 크기가 k인 모든 조합을 탐색합니다
var addStates func(next, k, from int)
addStates = func(next, k, from int) {
if k == 0 {
add(next)
return
}
for i := from; i < len(courses); i++ {
addStates(next|(1<<courses[i]), k-1, i+1)
}
}
addStates(state, k, 0)
}
}
행렬과 정수 가 주어졌을 때, 행렬 내부의 직사각형 중 그 합이 이하인 최대 합을 반환하세요.
왼쪽과 오른쪽 열 경계를 고정하면 2차원 행렬을 1차원 배열로 압축할 수 있습니다. 두 열 사이의 행 합을 나타내는 1차원 배열을 얻고 나면, 문제는 합이 이하인 부분 배열(subarray)을 찾는 것으로 축소됩니다. 누적 합(prefix sums)의 정렬된 리스트를 유지하면(이진 탐색 트리나 단순 정렬 배열 삽입 활용) current_prefix - past_prefix <= k를 만족하는 가장 작은 과거 누적 합을 효율적으로 쿼리할 수 있으며, 또는 2차원 누적 합 테이블을 미리 계산해 두어 임의의 부분 직사각형 합을 시간에 구할 수도 있습니다.
import "math"
func maxSumSubmatrix(matrix [][]int, k int) int {
n := len(matrix)
m := len(matrix[0])
res := math.MinInt
sums := make([][]int, n)
for i := 0; i < n; i++ {
sums[i] = make([]int, m)
}
// 2차원 누적 합 사전 계산
sums[0][0] = matrix[0][0]
for i := 1; i < n; i++ {
sums[i][0] = matrix[i][0] + sums[i-1][0]
}
for j := 1; j < m; j++ {
sums[0][j] = matrix[0][j] + sums[0][j-1]
}
for i := 1; i < n; i++ {
for j := 1; j < m; j++ {
sums[i][j] = matrix[i][j] + sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1]
}
}
// 포함-배제 원리를 사용하여 가능한 모든 부분 직사각형 평가
for starti := 0; starti < n; starti++ {
for startj := 0; startj < m; startj++ {
for endi := starti; endi < n; endi++ {
for endj := startj; endj < m; endj++ {
sum := sums[endi][endj]
if starti > 0 {
sum -= sums[starti-1][endj]
}
if startj > 0 {
sum -= sums[endi][startj-1]
}
if starti > 0 && startj > 0 {
sum += sums[starti-1][startj-1]
}
if sum <= k && sum > res {
res = sum
}
}
}
}
}
return res
}
방향 그래프에서 부모가 없는 루트 노드를 제외한 모든 노드는 정확히 하나의 부모를 가집니다. 여기에 추가적인 방향 간선 하나가 더해졌습니다. 이 간선을 제거했을 때 결과 그래프가 유효한 루트 트리가 되도록 하는 간선을 찾으세요. 가능한 답이 여러 개라면 입력에서 가장 마지막에 등장하는 간선을 반환하세요.
방향 그래프이기 때문에 추가된 간선은 다음 두 가지 문제 중 하나(또는 둘 다)를 일으킵니다.
먼저 두 개의 부모를 가진 노드가 있는지 스캔합니다. 만약 있다면 불필요한 간선은 반드시 그 노드를 가리키는 두 간선 중 하나여야 합니다. 그렇지 않다면 추가 간선이 방향 사이클을 형성한 것입니다. 입력의 역순으로 후보 간선들을 테스트하면서, 후보 간선을 제거했을 때 루트에서 사이클 없이 모든 개의 노드에 도달 가능한 유효한 루트 트리가 되는지 DFS(또는 유니온 파인드)로 검증할 수 있습니다.
func findRedundantDirectedConnection(edges [][]int) []int {
n := len(edges)
parents := map[int][]int{}
outs := map[int][]int{}
for _, edge := range edges {
src := edge[0] - 1
dst := edge[1] - 1
parents[dst] = append(parents[dst], src)
outs[src] = append(outs[src], dst)
}
roots := map[int]bool{}
bad := -1
for i := 0; i < n; i++ {
if len(parents[i]) == 0 {
roots[i] = true
}
if len(parents[i]) > 1 {
bad = i
}
}
if len(roots) == 0 {
for i := 0; i < n; i++ {
if check(n, outs, i, -1, -1, map[int]bool{}) {
roots[i] = true
}
}
}
if len(roots) > 1 {
for i := len(edges) - 1; i >= 0; i-- {
edge := edges[i]
src := edge[0] - 1
dst := edge[1] - 1
if roots[dst] {
return []int{src + 1, dst + 1}
}
}
}
for root := range roots {
if len(parents[root]) > 0 {
return []int{parents[root][0] + 1, root + 1}
}
for from := len(parents[bad]) - 1; from >= 0; from-- {
if check(n, outs, root, parents[bad][from], bad, map[int]bool{}) {
return []int{parents[bad][from] + 1, bad + 1}
}
}
}
return []int{-1, -1}
}
func check(n int, outs map[int][]int, from, badfrom, badto int, visited map[int]bool) bool {
if visited[from] {
return false
}
visited[from] = true
if len(visited) == n {
return true
}
for _, to := range outs[from] {
if from == badfrom && to == badto {
continue
}
if check(n, outs, to, badfrom, badto, visited) {
return true
}
}
return false
}
이 분석이 도움이 되셨나요? LeetCode Hard 문제는 인내심을 요구하지만, 근본적인 패턴을 공부하면 풀이 과정을 반복 가능하게 만들 수 있습니다. 계속해서 만들고 연습하세요. 면접에서 좋은 결과가 있기를 응원합니다!
카우에의 삶의 방식 오프라인 에디션을 받아보세요—🍏 건강, 💰 부, ❤️ 사랑, 🧘 의미를 최적화하기 위한 실전 가이드입니다.
더 나은 삶을 위한 새로운 에세이, 도서 요약, 실전 가이드를 발행할 때 알림을 받아보세요. 스팸은 없으며 언제든 구독을 취소할 수 있습니다.
질문, 의견 또는 제안이 있으신가요? 아래에 생각을 남겨주세요. 댓글은 GitHub Discussions(광고 및 스팸 없음)를 통해 제공됩니다—댓글이나 반응을 남기려면 아래의 GitHub으로 로그인을 클릭하세요(무료 GitHub 계정은 1분 이내에 만들 수 있습니다).
최종 업데이트: 2026. 10. 11..
면책 조항: 본 사이트의 콘텐츠는 정보 제공 및 교육 목적으로만 제공되며 의학, 심리, 재무, 투자, 세무 또는 법률 자문을 구성하지 않습니다. 여기에 제시된 생각, 큐레이션 및 의견은 전적으로 저 개인의 것이며 고용주의 입장을 대변하지 않습니다. 도서, 강연 및 아티클 요약은 독립적인 교육적 해설이며 각 저자의 지적 재산입니다. 편집, 서식 지정 및 요약을 돕기 위해 AI 도구가 사용될 수 있으며, 정확성을 기하기 위해 최선을 다하고 있으나 오류가 포함될 수 있습니다. 개인정보 처리방침: 본 사이트는 선택적 뉴스레터 구독(follow.it), 댓글(giscus / GitHub Discussions) 및 임베디드 미디어(YouTube)를 위해 제3자 서비스를 사용하며, 해당 서비스들은 각자의 개인정보 처리방침에 따라 방문자의 IP 주소와 쿠키를 처리할 수 있습니다.