손코딩

접근 방법

삽입 정렬은 정렬된 구간을 확장하는 반복 구조를, 병합 정렬과 퀵 정렬은 분할 정복과 재귀 구현을 확인하기 좋습니다.

각 정렬의 핵심 불변식, 안정성, 시간·공간복잡도를 설명하면서 구현하는 것이 중요합니다.

핵심 키워드

• Insertion Sort
• Merge Sort
• Quick Sort
• Stable Sort

구현 포인트

• Insertion Sort: 현재 값을 앞쪽 정렬된 구간의 적절한 위치에 삽입합니다.
• Merge Sort: 배열을 반으로 나누고 정렬된 두 배열을 병합합니다.
• Quick Sort: pivot 기준으로 작은 값과 큰 값을 분할한 뒤 재귀 정렬합니다.

복잡도

• Insertion Sort 평균 및 최악: O(N^2), 최선: O(N)
• Merge Sort: O(N log N), 추가 메모리 O(N)
• Quick Sort 평균: O(N log N), 최악: O(N^2)

주의할 점

• Quick Sort는 pivot 선택이 중요합니다.
• Merge Sort 병합 과정에서 인덱스 경계 처리를 조심해야 합니다.

접근 방법

표준 컬렉션의 push/pop이나 queue 연산을 그대로 감싸지 않고, 고정 크기 배열과 인덱스로 핵심 동작을 구현합니다.

스택은 top 인덱스, 원형 큐는 front/rear와 현재 크기를 관리하는 것이 핵심입니다.

핵심 키워드

• Stack
• Queue
• Array
• Top
• Circular Buffer
• Front/Rear

구현 포인트

• Stack: push, pop, peek, isEmpty, overflow 검사
• Queue: offer, poll, peek, modulo를 이용한 원형 인덱스 처리

복잡도

• Stack/Queue 기본 연산: O(1)
• 고정 용량 배열 공간: O(capacity)

주의할 점

• 빈 자료구조, 원소 1개, 가득 찬 상태, 원형 인덱스가 배열 끝을 넘는 케이스를 확인해야 합니다.

접근 방법

한 번만 찾는다면 배열을 처음부터 끝까지 순회하며 원하는 값과 같은 인덱스를 모두 수집하면 됩니다.

같은 배열에서 여러 번 조회해야 한다면 값별 인덱스 목록을 해시맵으로 미리 만들어두는 방식이 좋습니다.

핵심 키워드

• Linear Search
• HashMap
• Index List
• Preprocessing

구현 포인트

• 단일 조회: for문으로 모든 인덱스를 확인합니다.
• 다중 조회: Map<Value, List<Index>>를 구성합니다.
• 값이 없을 때 빈 리스트나 -1을 반환하도록 정책을 정합니다.

복잡도

• 단일 조회: 시간 O(N), 추가 공간 O(K)
• 전처리 방식: 전처리 O(N), 조회 평균 O(1), 공간 O(N)

주의할 점

• “원하는 수가 하나가 아닐 수 있다”는 조건 때문에 첫 번째 발견에서 멈추면 안 됩니다.

접근 방법

부분집합 합 문제입니다.

숫자가 20개라면 모든 부분집합을 탐색해도 2^20이라 약 100만 개 수준이므로 브루트포스가 가능합니다.

더 일반화하면 DP나 meet-in-the-middle을 고려할 수 있습니다.

핵심 키워드

• Subset Sum
• Backtracking
• Bitmask
• Dynamic Programming
• Meet-in-the-middle

구현 포인트

• 비트마스크로 0부터 (1 << 20) - 1까지 순회하며 선택된 숫자의 합을 계산합니다.
• 백트래킹으로 현재 인덱스에서 선택/미선택 분기를 만들 수도 있습니다.
• 목표 합을 찾으면 즉시 true를 반환합니다.

복잡도

• 브루트포스: O(2^N * N) 또는 누적합 최적화 시 O(2^N)
• N=20이면 충분히 시도 가능합니다.

주의할 점

• 예시는 N=20 조건을 활용한 비트마스크 완전탐색이므로 음수도 처리할 수 있습니다.
• N이 더 커질 때 DP를 사용한다면 음수 포함 여부와 target 범위를 먼저 확인해야 합니다.

접근 방법

큰 값부터 대응되는 로마 숫자를 빼면서 문자열을 만들어갑니다.

900, 400, 90, 40, 9, 4처럼 감산 표기 케이스를 테이블에 포함하면 구현이 단순해집니다.

핵심 키워드

• Roman Numeral
• Greedy
• Mapping Table
• Subtractive Notation

구현 포인트

• 값과 문자를 배열로 둡니다: 900 CM, 500 D, 400 CD, 100 C, ...
• 숫자가 현재 값 이상이면 값을 빼고 해당 문자를 결과에 추가합니다.
• 1부터 999 범위 검증을 먼저 합니다.

복잡도

• 테이블 크기가 고정이라 시간과 공간은 사실상 O(1)입니다.

주의할 점

• 4, 9, 40, 90, 400, 900 감산 표기를 빼먹기 쉽습니다.

접근 방법

정렬하지 않는다는 조건이 있으므로 Quickselect를 사용해 k번째 원소를 찾습니다.

이 예시에서는 길이가 홀수면 N/2번째 값을, 짝수면 가운데 두 값의 산술평균을 중앙값으로 정의합니다.

핵심 키워드

• Median
• Quickselect
• Partition
• K-th Element

구현 포인트

• Quick Sort의 partition을 사용합니다.
• pivot의 최종 위치가 k이면 답입니다.
• k보다 크면 왼쪽, 작으면 오른쪽만 재탐색합니다.

복잡도

• 평균 시간 O(N), 최악 O(N^2)
• Quickselect 자체는 반복 구현 시 추가 공간 O(1)이지만, 예시는 원본 보존을 위한 복사 때문에 O(N)을 사용합니다.

주의할 점

• 빈 배열은 중앙값이 없으므로 오류로 처리합니다.
• 짝수 길이에서 평균, 하위 중앙값, 상위 중앙값 중 어떤 정의를 원하는지 면접관에게 확인하는 것이 좋습니다.

접근 방법

알파벳 범위가 제한되어 있으므로 boolean 배열이나 bitmask로 등장 여부를 기록한 뒤, a부터 z까지 순회하며 등장한 문자만 출력하면 됩니다.

핵심 키워드

• Deduplication
• Counting
• Boolean Array
• Bitmask
• Alphabet

구현 포인트

• 소문자만 있다면 크기 26 boolean 배열을 사용합니다.
• 대소문자가 섞이면 범위를 확장하거나 정규화 정책을 정합니다.
• 결과는 알파벳 순서로 boolean 배열을 순회해 만듭니다.

복잡도

• 시간 O(N + 26), 공간 O(26)

주의할 점

• 입력이 영어 알파벳만인지, 대소문자 구분을 하는지 확인해야 합니다.

접근 방법

추가 자료구조를 사용할 수 없으므로 배열 자체를 정렬한 뒤 투 포인터로 교집합을 찾는 방식이 적합합니다.

정렬이 허용되지 않는다면 한 배열을 순회하며 다른 배열에서 선형 탐색해야 합니다.

핵심 키워드

• Intersection
• Sorting
• Two Pointers
• In-place
• Duplicate Handling

구현 포인트

• 두 배열을 정렬합니다.
• 포인터 i, j를 두고 작은 값을 가진 쪽을 이동합니다.
• 값이 같으면 첫 번째 배열의 앞쪽 결과 구간에 덮어쓰고 둘 다 이동합니다.
• 중복을 제거할지 유지할지 정책을 정합니다.

복잡도

• 정렬 기반: O(N log N + M log M)
• 투 포인터 병합: O(N + M)
• 예시처럼 결과를 첫 번째 배열의 앞부분에 저장하면 별도 결과 컨테이너 없이 처리할 수 있습니다.

주의할 점

• 예시는 반환한 길이만큼 첫 번째 배열의 앞부분을 교집합 결과로 사용합니다.
• 중복 원소를 한 번만 반환할지, 등장 횟수만큼 반환할지 정책을 확인해야 합니다.

접근 방법

전체 정렬은 O(N log N)이므로 평균 O(N)인 Quickselect로 필요한 위치만 찾습니다.

최악 시간까지 O(N)을 보장해야 한다면 median-of-medians 같은 pivot 선택 전략이 필요합니다.

핵심 키워드

• K-th Largest
• Quickselect
• Min Heap
• Partition

구현 포인트

• K번째 큰 수는 오름차순 기준 N-K번째 원소입니다.
• Quickselect로 해당 인덱스를 찾습니다.
• 입력 배열을 복사한 뒤 partition을 반복해 원본 배열은 보존합니다.

복잡도

• Quickselect 평균 O(N), 최악 O(N^2)
• 예시는 원본 보존을 위해 추가 공간 O(N)을 사용합니다.

주의할 점

• K는 1부터 N까지의 1-based 값으로 검증합니다.
• 중복 값 처리 기준을 확인해야 합니다.
• 일반적인 Quickselect는 최악 O(N^2)이므로 평균 시간 조건임을 명시해야 합니다.

접근 방법

진짜 난수는 아니지만 시간 값을 seed처럼 사용해 pseudo-random 값을 만들 수 있습니다.

예를 들어 현재 시간의 나노초나 밀리초를 기반으로 선형 합동 생성기(LCG)를 구현할 수 있습니다.

핵심 키워드

• Pseudo Random
• Seed
• Time
• LCG
• Range Mapping

구현 포인트

• 현재 시간 값을 seed로 잡습니다.
• seed = (a * seed + c) % m 형태로 다음 값을 만듭니다.
• 범위는 min + seed % (max - min + 1)로 맞춥니다.
• 중복 없이 뽑아야 한다면 이미 뽑은 값 확인이 필요합니다.

복잡도

• 중복 허용: O(20)
• 중복 불허: 범위가 충분히 크면 평균 O(20), 범위가 작으면 재시도 비용 증가

주의할 점

• 보안적으로 안전한 난수가 아닙니다.
• 범위가 20개보다 작고 중복 불허라면 불가능합니다.

접근 방법

기본 정수 타입 범위를 넘으므로 문자열 기반 큰 수 덧셈을 구현합니다.

모든 입력 문자열의 가장 오른쪽 자리부터 같은 자릿값을 한 번에 더하면서 carry를 관리하면 여러 수를 중간 결과 문자열 없이 한 번에 합산할 수 있습니다.

핵심 키워드

• Big Integer
• String Addition
• Carry
• Digit
• Reverse

구현 포인트

• 각 숫자를 문자열로 입력받습니다.
• 가장 긴 입력의 길이를 기준으로 오른쪽부터 각 문자열의 같은 자릿값을 더합니다.
• 합이 10 이상이면 carry를 다음 자리로 넘깁니다.
• 각 자리의 합과 carry를 기록하고 마지막에 결과를 뒤집습니다.

복잡도

• 전체 자릿수를 D라고 하면 시간 O(D), 결과 공간 O(D)

주의할 점

• 앞자리 0 처리, 음수 여부, 입력 숫자 개수를 확인해야 합니다.

접근 방법

두 리스트의 head를 비교하면서 작은 노드를 결과 리스트에 붙입니다.

dummy head를 사용하면 head 처리 분기가 단순해집니다.

핵심 키워드

• LinkedList
• Merge
• Two Pointers
• Dummy Node

구현 포인트

• p1, p2, tail 포인터를 둡니다.
• 더 작은 값을 가진 노드를 tail.next에 연결합니다.
• 한쪽이 끝나면 남은 리스트를 그대로 붙입니다.

복잡도

• 시간 O(N + M)
• 추가 공간 O(1) 또는 새 노드 생성 시 O(N + M)

주의할 점

• 기존 노드를 재사용할지 새 노드를 만들지 면접관에게 확인하면 좋습니다.

접근 방법

2부터 sqrt(N)까지 나누어떨어지는 수를 찾고, 나누어떨어지는 동안 계속 나눕니다.

마지막에 남은 수가 1보다 크면 그 수도 소인수입니다.

핵심 키워드

• Prime Factorization
• sqrt(N)
• Trial Division
• Remainder

구현 포인트

• 먼저 2로 나누고, 이후 홀수만 검사하면 조금 최적화됩니다.
• 정수 overflow를 피하기 위해 i <= n / i 조건으로 반복합니다.
• 나누어떨어질 때마다 결과에 추가하고 n /= i를 수행합니다.

복잡도

• 기본 trial division은 O(sqrt(N))

주의할 점

• i * i가 overflow될 수 있는 언어에서는 i <= n / i 조건이 안전합니다.

접근 방법

단순하게는 1부터 1,000,000까지 문자열로 바꿔 0을 세면 됩니다.

범위가 고정되어 있고 100만 정도라면 충분히 가능합니다.

더 수학적으로는 자리수별 0의 등장 횟수를 계산할 수도 있습니다.

핵심 키워드

• Counting
• Digit
• String Conversion
• Positional Counting

구현 포인트

• 쉬운 구현: 반복문으로 String.valueOf(i) 후 문자 0 개수를 셉니다.
• 수학적 구현: 각 자리수별로 high/current/low 값을 나눠 0 등장 횟수를 계산합니다.

복잡도

• 문자열 방식: 전체 자릿수만큼 O(D), 여기서는 충분히 작습니다.
• 수학적 방식: 자리수 개수만큼 O(log N)

주의할 점

• 0 자체를 포함하는 범위인지 확인해야 합니다. 현재는 1부터라 숫자 0은 포함하지 않습니다.

접근 방법

스택 두 개로 큐를 만들 때는 입력 스택과 출력 스택을 나눕니다.

enqueue는 입력 스택에 넣고, dequeue는 출력 스택이 비었을 때 입력 스택의 모든 원소를 옮긴 뒤 꺼냅니다.

큐 두 개로 스택을 만들 때는 push를 비싸게 만들거나 pop을 비싸게 만들 수 있습니다.

push 비싼 방식은 새 원소를 빈 큐에 넣고 기존 큐 원소를 뒤에 붙여 front가 항상 top이 되게 합니다.

핵심 키워드

• Stack
• Queue
• LIFO
• FIFO
• Amortized O(1)

구현 포인트

• 스택 2개 큐:
  • inStack에 push
  • dequeue 시 outStack이 비어 있으면 inStack을 모두 옮김
  • outStack.pop() 반환
• 큐 2개 스택:
  • push 시 새 원소를 보조 큐에 넣고 기존 큐를 모두 옮김
  • 두 큐를 swap
  • pop은 메인 큐에서 poll

복잡도

• 스택 2개 큐: enqueue O(1), dequeue amortized O(1)
• 큐 2개 스택: 구현 방식에 따라 push 또는 pop이 O(N)

주의할 점

• amortized 시간복잡도와 worst-case 시간복잡도를 구분해서 설명해야 합니다.

접근 방법

해시맵으로 키의 노드를 평균 O(1)에 찾고 이중 연결 리스트로 최근 사용 순서를 관리합니다.

조회하거나 갱신한 노드를 리스트 앞으로 옮기고, 새 항목 추가 후 용량을 넘으면 가장 오래 사용하지 않은 마지막 노드를 맵과 리스트에서 함께 제거합니다.

핵심 키워드

• LRU
• HashMap
• Doubly Linked List
• Sentinel Node
• Eviction

구현 포인트

• 연결 리스트를 직접 구현한다면 head와 tail sentinel로 경계 분기를 줄입니다.
• get도 사용으로 간주해 노드를 앞으로 옮깁니다.
• 기존 키의 put은 크기를 늘리지 않고 값과 순서만 갱신합니다.
• 용량은 양수인지 검증합니다.

복잡도

• get, put: 평균 O(1)
• 공간: O(capacity)

주의할 점

• 해시맵과 연결 리스트에서 반드시 같은 노드를 제거해야 합니다.
• 부재를 실제 저장값과 충돌하는 magic number로 표현하지 않습니다.

접근 방법

슬라이딩 윈도우의 왼쪽·오른쪽 경계와 각 문자의 마지막 등장 위치를 관리합니다.

현재 윈도우 안에서 중복을 만나면 왼쪽 경계를 이전 위치 다음으로 옮기되, 왼쪽 경계가 뒤로 이동하지 않도록 합니다.

핵심 키워드

• Sliding Window
• Two Pointers
• Last Seen Index
• HashMap
• Unicode Code Point

구현 포인트

• 이전 위치가 현재 left 이상일 때만 경계를 갱신합니다.
• 각 위치에서 right - left + 1로 길이를 계산합니다.
• 빈 문자열은 0을 반환합니다.

복잡도

• 시간: O(N)
• 공간: O(min(N, U)), U는 문자 집합 크기

주의할 점

• C++ 예시는 Unicode code point로 디코딩된 u32string을 입력받습니다.
• 사용자에게 보이는 grapheme cluster와 Unicode code point는 다를 수 있습니다.

접근 방법

구간을 시작점과 종료점 순으로 정렬한 뒤 현재 시작점이 마지막 병합 구간의 종료점 이하라면 종료점을 확장합니다.

겹치지 않으면 새 구간을 결과에 추가합니다. 예시는 입력 원본을 바꾸지 않도록 복사본을 정렬합니다.

핵심 키워드

• Interval
• Sorting
• Greedy
• Sweep
• Closed Interval

구현 포인트

• 각 구간이 start <= end인지 검증합니다.
• 닫힌 구간이므로 [1,4]와 [4,5]는 병합합니다.
• 빈 입력은 빈 결과를 반환합니다.

복잡도

• 정렬: O(N log N)
• 병합: O(N)
• 입력 복사와 결과 공간: O(N)

주의할 점

• 반열린 구간에서는 경계가 같은 구간의 병합 정책이 달라질 수 있습니다.
• 결과가 입력 객체를 공유해 호출자의 원본을 바꾸지 않도록 주의합니다.