# 코딩 인터뷰 완전 분석

## VI big-O

파일 전송

* 온라인 전송 : O(s)
* 비행기로 전송 : O(1)
* 선형식은 언젠가 상수를 뛰어넘는다.

### 시간 복잡도

#### big-O, big-theta, big-omega

O(big-O)

* 학술적으로 실행 시간의 상한을 의미함
* O(N)으로 표현되는 알고리즘은 O(N^2), O(N^3)로도 표현 가능.

O(big-Omega)

* 알고리즘의 실행 시간 하한을 의미
* Omega(1)이면 전체 순회는 반드시 하게 된다는 뜻

O(big theta)

* big-O랑 big-Omega랑 같을 때 업계의 big-O는 사실 학계의 big theta와 같은 의미

#### 최선, 최악, 평균

최선의 경우는 아무 알고리즘이나 취한 뒤 특수한 입력을 넣으면 O(1)이다. 대부분의 알고리즘은 최악과 평균이 같다.

### 공간 복잡도

재귀 스택 공간도 공간 복잡도에 포함된다. 꼬리 재귀 최적화하면 안 늘어남.

### 상수항은 무시하라

O(2N)이 O(N)보다 빠를 수도 있다. for문 안에 식 두 개 적으면 O(N), for문을 따로 적으면 O(2N)이다. 둘 중 뭐가 더 빠를까? 고려할 세부사항이 너무 많다.

### 지배적이지 않은 항은 무시하라

O(X!) > O(2\*x) > O(x^2)

### 상환 시간

Java의 ArrayList, C++의 vector 등의 동적 배열은 꽉 차면 크기를 늘린다. 이것까지 감안할 때 삽입 연산의 수행 시간은?

배열의 크기가 1,2,4,8,16 ... X 일 때 새 원소 삽입하면 배열의 크기를 두배로 증가시킨다. 원소들을 새 배열로 복사시켜줘야 한다 기존 원소 크기 1+2+4+...+X = 대략 2X X로 분할 상환해보면 삽입에 필요한 시간은 O(1)

### log N 수행 시간

어떤 문제에서 원소 개수가 절반씩 줄어들면 O(logN) 가능성 크다 big-O에선 로그의 밑을 고려할 필요 없다.

### 재귀적으로 수행 시간 구하기

재귀가 자신을 재호출하는 횟수를 A라 하고 호출 깊이를 B라 하면 이 재귀 함수의 수행 시간은 보통 A^B으로 표현된다

### 예제 및 연습 문제

#### O(AB)와 O(N^2) 혼동 조심

```
void printUnorderedParis(int[] arrA, int[] arrB {
	for(int i=0; i<arrA.length; i++) {
		for(int j=0; j< arrB.length; j++) {
			if(arrA[i] < arrB[j]) {
				if(arrA[i] < arrB[j]) // 뭔가 함
			}
		}
	}
}
```

이건 O(N^2)이 아니라 O(AB)이다

#### N 혼용 조심

문자열 배열이 주어졌다. 각각의 문자열을 정렬한 뒤, 전체 문자열을 사전순으로 정렬한다. 수행 시간은?

문자열 정렬이 O(NlogN)이고 그게 배열만큼 있으니까 O(N^2logN) 다시 정렬하면 O(NlogN + N^2logN) 라고 하면 틀린다

문자열 길이 S와 배열 길이 A를 혼동했기 때문 실제로는 문자열 정렬은 O(SlogS), 그걸 배열만큼 반복하면 O(ASlogS), 다시 정렬하면 O(AS(logA + logS)가 된다. (배열에 대해 정렬할 때 문자열 비교 때문에 그냥 AlogA가 아니라 SAlogA)

변수 이름 붙일 때도 A,B,M,N 이런거 쓰지 말고 안 헷갈리게 연상 가능한 이름을 붙여라

## VII 기술적 문제

### 알고 있어야 할 것들

#### 2의 승수 표

| 지수 x | 2^x 값             | 근사치         | 메모리 요구량 (1바이트 기준) |
| ---- | ----------------- | ----------- | ----------------- |
| 10   | 1,024             | ≈ 1천        | ≈ 1 KB            |
| 16   | 65,536            |             | ≈ 64 KB           |
| 20   | 1,048,576         | ≈ 100만 (1M) | ≈ 1 MB            |
| 30   | 1,073,741,824     | ≈ 10억 (1G)  | ≈ 1 GB            |
| 32   | 4,294,967,296     |             | ≈ 4 GB            |
| 40   | 1,099,511,627,776 | ≈ 1조 (1T)   | ≈ 1 TB            |

### 실제 문제 살펴보기

1. 경청하기

* 주어진 정보를 기억해두거나 써둬라

2. 예제를 직접 그려보기

* 문제 듣자마자 화이트보드에 그려라
* 명확하고 일반적인 예제를 만들어라

3. 일단 브루트포스로 시도해보라

* 너무 뻔하더라도 일단 시간 및 공간복잡도 설명한 뒤 개선해라

4. 최적화

* 간과한 정보가 있는지 찾아보자
* 새로운 예제를 만들어보자
* 시간과 공간의 실익을 따져 보고 균형을 맞추라
* 필요한 정보를 미리 계산해두라
* 해시테이블을 사용하라
* 최선의 수행 시간이 무엇인지 생각하라

5. 검토하기

* 최적 알고리즘 완성해도 바로 코딩하지 마라
* 화이트보드 코딩은 오래 걸리니까 가능하면 완벽하게 만들고 코딩해라
* 어떤 변수를 사용하여 언제 값을 변경할 건지 등 세세한 부분도 미리 정해라

6. 코드 작성하기

* 화이트보드에 작성할 때 각 줄이 비스듬해지지 않게 조심하라
* 모듈화된 코드를 사용하라
* 에러를 검증하라
* 필요한 경우 다른 클래스나 구조체를 사용하라. 그 클래스의 세부사항은 시간 남을 때.
* 좋은 변수명을 사용하라. 변수명이 반복되면 앞으론 줄여서 쓰겠다고 면접관에게 설명한다.
* 리팩토링할 부분을 발견하면, 면접관에게 설명 후 시간을 들일지 판단하여 리팩토링 여부 결정한다.

7. 테스트

* 손으로 직접 테스트하면 느리다
* 1. 개념적 테스트부터 시작하라: 코드를 한 줄 한 줄 읽어나가며 어떤 일을 수행하는지 분석하라
* 2. 코드에서 평소와 다르게 돌아가는 부분을 살펴보라: x=length-2, i=1부터 시작하는 for문 등
* 3. 버그가 자주 발생하는 부분을 살펴보라: 재귀함수 base case, 정수 나눗셈, 이진 트리 null 노드, 연결리스트 시작 끝 등
* 4. 작은 규모 테스트 돌려보라: 너무 큰 크기 테케 쓰지 마라
* 5. 특별한 경우 테스트하라: null, 단일 원소, 극단적 입력 등

### 최적화 및 문제풀이 기술 #1: BUD를 찾으라

#### 병목 현상

* big-O가 가장 큰 곳을 파악하고 줄이려 해본다
* 검색 여러 번 하는 것처럼 반복 수행하는 부분 줄이려 해본다

예제: 서로 다른 정수로 이루어진 배열이 있을 때 두 정수의 차이가 k인 쌍의 개수를 세라.

* 무식한 방법: 배열 원소 for문 2번 돌린다
* 정렬 후 탐색: 정렬할 때 O(NlogN), 이진탐색으로 x-k 또는 x+k 찾으려면 O(logN)을 N번. 결국 O(NlogN).
* 해시테이블: 모든 원소를 해시테이블에 넣은 뒤 x+k 또는 x-k가 있는지 확인하면 O(N)

#### 불필요한 작업

예제 : a,b,c,d가 1<, <1000일 때 a^3+b^3=c^3+d^3 만족하는 모든 자연수 출력

* 무식한 방법 : 4중 루프
  * d for문은 찾았을 때 break하면 최적화
* 아예 for문 안 돌리고 수식으로 있는지 확인 가능
  * O(n^4)에서 O(n^3)으로 줄어든다

#### 중복되는 작업

위의 예제 다시 살펴보기

* 근본적으로 모든 (a,b) 쌍에 대해 수식 만족 (c,d) 찾는 것
* 그런데 왜 모든 (a,b)에 대해 가능한 모든 (c,d)를 찾는 건가?
* 그냥 해시테이블에 (c,d) 리스트를 만들어두고, (a,b) 쌍에 대해 대응되는 (c,d)를 리스트에서 찾아보면 된다
  * (c,d) 쌍은 (a,b) 쌍과 사실상 같으므로 (a,b) 쌍을 따로 for문 돌릴 필요도 없이 해시테이블에 저장한 리스트의 중복조합 하면 된다
  * O(n^2)으로 줄어든다

### 최적화 및 문제풀이 기술 #2: 스스로 풀어보라

일단 컴퓨터가 아니라 직관적으로 문제를 풀어봐라.

예제: 짧은 문자열 s와 긴 문자열 b가 주어졌을 때, 문자열 b 안에 존재하는 문자열 s의 모든 순열을 찾는 알고리즘

* s의 모든 순열 찾고 그걸 b에서 찾으면 `O(S!*B)`가 된다
* 컴퓨터 대신 직접 세려 하면 훨씬 간단한 방법으로 셀 것이다
  * 방법 1: b를 s의 개수로 끊어서 차례로 살펴본 뒤 s의 순열을 만족하는지 확인한다
  * 방법 2: b를 순회하면서 s에 속한 문자가 있으면 거기서부터 s의 순열 만족하는지 확인한다
  * `O(B*S)`, `O(B*SlogS)`, `O(B*S^2)` 중 하나가 된다. 최적은 사실 `O(B)`지만, 처음보단 나아졌다.

### 최적화 및 문제풀이 기술 #3: 단순화, 일반화하라

* 단계 1: 자료형 같은 제약조건을 단순화하거나 변형시킨다
* 단계 2: 단순화된 버전의 문제를 푼다
* 단계 3: 단순화 알고리즘 완성되면 복잡한 형태로 다듬는다

예제: 문자열에서 잘라낸 단어들로 특정 문자열을 만들 수 있는지 확인

* 글자 하나씩 잘라내는 걸로 단순화해보자
  * 특정 문자열에서 각 문자가 출현한 횟수를 세서 배열에 저장한 다음,
  * 참조 문자열에 출현한 문자 수보다 같거나 많은지 확인한다
* 일반화해도 비슷하다. 단어를 key로 하는 해시테이블 이용하면 된다

### 최적화 및 문제풀이 기술 #4: 초기 사례(base case)로부터 확장

초기 사례 (n=1같은 문제) 를 푼 뒤, 해법을 확장해나간다.

예제: 문자열 모든 순열 구하라 (모든 문자는 고유하게 등장)

* a의 순열을 구하고, ab의 순열을 구해본다, abc의 순열은?
* ab의 가능한 모든 자리에 c를 우겨넣어본다

### 최적화 및 문제풀이 기술 #5: 자료구조 브레인스토밍

일련의 자료구조를 차례차례 살펴보며 하나씩 적용해본다. "트리를 써 보자"라는 결심만으로 문제가 자연스럽게 풀리는 경우가 있다.

### 가능한 최선의 수행 시간 (Best Conceivable Runtime(BCR))

최선 수행 시간이 무엇일지 생각하는 것만으로 힌트 발견 가능

예제: 정렬된 배열 2개가 주어졌을 때 공통으로 들어있는 원소 개수 찾아라. 두 배열의 길이는 같고, 하나의 배열 안에서 동일한 원소는 하나만 존재한다.

* brute force는 A의 각 원소가 B에 존재하는지 찾아보는 것. O(N^2)이 걸린다.
* 이 문제의 BCR은 O(N)이다. 모든 원소를 적어도 한 번씩 살펴봐야 하기 때문이다.
  * 보장은 못하지만 O(N)까지 개선할 수도 있는 가능성이 있다는 것
* 탐색하는 부분 때문에 두번째 O(N)이 나왔다. O(N)보다 빠르게 탐색 가능한가?
  * 이진 탐색을 이용하면 O(logN)에 원소 찾기 가능
* BCR이 O(N)이므로 그 이하인 건 자유롭게 시도해봐도 된다
  * B의 원소를 해시테이블에 모두 넣어놓는건 O(N)안에 할 수 있고, 검색은 O(1)이다
  * 전체 수행 시간은 O(N)으로 줄어든다
* 더 개선할 수 있을까? BCR보다 작아질 순 없으므로 공간 복잡도를 개선해야 한다
  * 가능하면 O(1) 공간에 동작했으면 좋겠다
  * 가능하면 O(N) 시간에 동작했으면 좋겠다
  * 배열이 정렬됐다는 조건을 사용하자
* 현재까지 최선 알고리즘 중 추가 공간 사용하지 않는 건 이진 탐색이다
  * 배열이 정렬돼있으므로, 이진 탐색할 때 이전 위치에서 시작하면 된다
  * 사실 이진 탐색할 필요도 없다. 선형 탐색하면서 이전 위치에서 시작하면 된다.
  * O(N) 시간과 O(1) 공간에 동작한다

## IX 면접 문제

### 01 배열과 문자열

#### 해시 테이블

간단한 구현

* 배열, 연결리스트, 해시 코드 함수 사용
* 1. 키의 해시 코드를 계산한다.
  * 자료형은 보통 int 혹은 long이다.
  * 키의 개수는 무한하지만 int는 유한하기 때문에 충돌 가능
* 2. 해시 코드로 배열의 인덱스를 구한다
* 3. 배열의 각 인덱스에는 키와 값으로 이루어진 연결 리스트가 존재한다.
  * 키와 값을 해당 인덱스에 저장한다.

균형 이진 탐색 트리로 구현할 수도 있다.

#### 면접 문제

1.1 중복이 없는가 문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘 작성하라. 자료구조 추가로 사용하지 않고 풀 수 있는 알고리즘도 고민하라.

내 접근

* 방법 1: 해시테이블에 문자 등록 이미 돼있으면 중복 판정
* 방법 2: 문자마다 나머지 배열 훑으며 자신과 같은지 확인. 시간 O(N^2), 추가 공간 없음

해법

* 먼저 면접관에게 문자열이 ASCII인지 유니코드인지 물어봐야 한다
* ASCII라고 가정하고 문제 풀면,
* 해법 1: ASCII 문자 집합의 bool 배열을 선언한 뒤, 찾으면 true, 이미 true면 중복 처리
* 자료 구조 추가 사용 불가하다면
  * 방법 1: 내 접근 2와 동일
  * 방법 2: O(nlogn)으로 문자열 정렬한 뒤 순회하며 인접한 문자 중복 검사
    * 많은 정렬 알고리즘이 공간을 추가로 쓴다는 사실에 주의

***

1.2 순열 확인 문자열 두 개가 주어졌을 때 이 둘이 서로 순열 관계에 있는지 확인하는 메서드 작성하라.

내 접근

* 문자 집합 크기 int 배열 두 개 선언 후 문자마다 각 배열 +1. 두 배열 같은지 점검. O(N).

해법

* 방법 1: 정렬한 뒤 같은지 확인. 최적은 아니지만 이해가 쉽다.
* 방법 2: 내 접근과 동일

***

1.4 회문 순열 문자 편집 방법이 세 가지 주어진다. 문자 삽입, 문자 삭제, 문자 교체. 문자열을 같게 만들기 위한 편집 횟수가 1회 이내인지 확인하는 함수 작성

내 해법 (정답)

* 문자열 길이가 같으면 문자 교체해서 가능한지 확인
  * flag 세워놓고 문자가 다를 때 아직 true라면 교체하고, false면 return false
* 문자열 길이의 절대값 차이가 1이라면 문자 삭제로 가능한지 확인
  * 필요한 문자를 삽입하는 건, 다른 문자를 삭제하는 것과 본질적으로 동일
  * 문자열을 순회하다 달라지는 문자는 flag를 세워 1번만 무시.
* flag로 1번만 무시하는 식으로 로직 통합
* 아예 길이도 상관 없이 순회 중에 한 쪽 배열 다 탐색해버리면 false 처리

***

1.5 하나 빼기 aabcccc → a2bc4로 압축하는 메서드를 작성하라 압축된 문자열의 길이가 기존 문자열보다 길면 기존 문자열 반환하라

내 해법

* a는 a1이 되니까 1에서 2, +1
* aa는 a2가 되니까 2에서 2, +0
* aaa는 a3가 되니까 3에서 2, -1
* (2 - 압축할 문자 substr)를 합산하면서 새로운 배열에 문자열을 삽입한다
  * 같은 배열에 하면 1을 압축할 때 뒤의 문자열이 오염된다
* 합산했던 값이 음수면 기존 문자를 반환한다
  * 이걸 위해서도 기존 배열을 건드리면 안된다


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/books/undefined-1.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.