코딩 인터뷰

검색 자동완성 시스템은 Trie 자료구조로 접두사 매칭을 O(N)에 처리하는 것이 핵심입니다. 정렬 기반 풀이에서 시간 복잡도 벽에 부딪혀 Trie로 갈아타며 통과했던 1인칭 시행착오와 Python/Java 자바 코드를 함께 정리했습니다.

LeetCode 380번 RandomizedSet 구현 문제입니다. HashSet 단독으로 시작했다가 getRandom O(1) 조건에서 막혔고, swap-and-pop 트릭으로 해결했습니다. remove의 val==lastVal 엣지케이스까지 정리합니다.

역순으로 저장된 두 연결 리스트의 자릿수를 더해 결과를 다시 연결 리스트로 반환하는 문제를 다룹니다. carry 누락, 길이 불일치, 정순 반환 변형까지 정면으로 짚습니다.

재귀로 시작했다가 면접관에게 O(1) 비트 연산을 배운 경험을 정리합니다. n > 0 조건을 빠뜨리거나 n & (n+1) 로 잘못 쓰는 실수, 언어별 정수 범위 함정까지 실제 사례 기반으로 다룹니다.

너무나 유명한 고전 알고리즘입니다. 편집 거리는 문자열 유사도를 수량화하는 방법으로, 자연어 처리와 생물정보학에서 폭넓게 사용되고 있습니다. 코딩 인터뷰 단골 주제이기도 합니다.

이진 트리 반전은 이름만 들으면 어려워 보이지만, 막상 풀면 몇 줄 안 되는 깔끔한 재귀 알고리즘입니다. 실제 면접에서 저도 처음엔 자식 교체 순서에서 한참을 헤맸던 기억이 있어, 그 경험을 정리해 봤습니다.

LCS 재귀에서 TLE 맞고, 글자 다를 때 +1 실수 직접 해보고, dp[n-1][m-1] 함정 두 번 밟은 경험을 바탕으로 정리한 DP 실전 가이드입니다.

CTCI/LeetCode 문자열 압축 문제를 Java로 풀면서 String의 불변성이 왜 O(N²)을 만드는지, StringBuilder로 어떻게 O(N)을 달성하는지 초보자도 이해할 수 있게 설명합니다.

모든 순환 경우를 직접 만들어 비교하다 O(N²)을 지적받았고, 빈 문자열 엣지 케이스를 빠뜨려 Wrong Answer를 맞은 경험에서 배운 A+A 트릭의 진짜 의미를 정리합니다.

처음엔 Coin Change 2 복붙하면 된다고 생각했는데, Wrong Answer를 3번 받고 나서야 '정확히 n개를 전부 써야 한다'는 결정적 차이를 깨달았습니다. 모듈로를 마지막에만 적용해 오버플로가 났던 경험, base case를 0으로 초기화해 결과가 전부 0이 되었던 삽질까지 함께 정리합니다.

두 개의 구간 배열을 비교해 겹치는 구간을 찾아 반환하는 투 포인터 알고리즘을 상세히 설명하고, 시간·공간 복잡도와 구현 포인트를 제공합니다.

동일 문자열을 true로 반환하는 실수, NullPointerException을 면접관 앞에서 보여준 경험, '정확히 1번'과 '최대 1번'을 혼동한 함정까지 직접 겪은 이야기로 정리합니다.

방문 표시를 빠뜨려 무한 루프 빠지고, 경계 체크 순서 바꿔 ArrayIndexOutOfBoundsException 맞은 실제 경험으로 정리하는 DFS 섬 개수 풀이입니다.

마지막 등장 위치를 미리 계산하지 않아 O(N²)이 된 실수, 파티션 크기를 end-start로 계산해 1을 빼먹은 함정, 다음 시작점을 잘못 설정한 경험을 정리합니다.

O(N!)로 모든 순열을 생성하다 TLE 맞은 실수, 공백·대소문자 처리 빠뜨려 틀린 경험, 비트마스크 최적화로 면접관을 놀라게 한 과정을 정리합니다.