📕[책] 코딩 인터뷰 완전 분석

이강욱·2023년 10월 23일

📕책

목록 보기

3/4

세 번째 책너두 도전. 벌써 7기.
회사 동료였던 민규님의 추천으로 알게된 책. 책너두 독서 목록에 있길래 바로 신청했다.

첫날 다짐

전반적인 내용

실리콘 벨리에서 실제로 이뤄지는 기술면접 문제들을 소개하고, 그에 대한 전략적/실용적인 접근법을 제시하는 책인듯.
실전(면접)에서 행해지는 Problem Solving을 예시 문제를 통해 연습시켜 주는 것으로 보인다. 좀 어려워 보인다.
저자와 옮긴이의 이력이 화려하다.
책이 무려 904쪽이나 된다. 말그대로 책이 너무 두껍다...
<발췌>
그리고 기억하세요. 면접은 어렵습니다! ('지은이의 글' 中)

독서 전략

최대한 점심시간을 활용해서 독서하겠다. 점심 도시락 구독해야겠다.
하나의 포스트에 계속 업데이트 하면서 정리하겠다.
책의 목차 그대로 독서일지 구조를 잡아볼까 생각 중.

다짐

저번에 node.js 디자인 패턴 책을 첫주에 바로 드랍했었는데, 이번엔 그러지 말아야겠다.
재밌게 꾸준히 읽어보자!!

면접 과정

문제풀이(problem solving) 능력을 보여줘야함. 알고리즘과 코딩으로.
구체적으로는,

분석 능력 : 문제를 푸는데 얼마나 도움을 받았는지, 걸린 시간, 최적화, 디자인/설계
코딩 능력 : 알고리즘을 적절한 코드로 표현하는 능력, 에러처리, 스타일
기술적 지식 및 컴퓨터 과학 기본
경험 : 기술적인 결정, 프로젝트
문화 / 의사소통

지원자들이 흔히 하는 불평 과 글쓴이의 일갈.

많은 수의 훌륭한 지원자들은 이런 방식의 면접을 잘 하지 못함
-> 부정 오류(false negative)는 사실 괜찮다. 즉, 잘하는 사람을 놓치는 것은 괜찮다. 그것보단 못하는 사람을 실수로 데려오는 것이 더 걱정.
-> 문제 풀이 능력은 가치있다. 최적 알고리즘을 개발할 수 있기 때문. 그리고 그런 사람들은 똑똑하다. 그래서 좋은 일을 할 가능성이 높다.
이미 나온 문제는 해법을 찾아볼 수 있다 그리고
실무에선 이진 탐색트리 같은 자료구조 안쓴다. 필요하다면 공부할 것
-> 기초적인 자료구조/알고리즘 지식은 유용하다. 이진 탐색트리가 존재하는 지도 모르는 상태에선 이진 탐색 트리를 사용해야겠다고 판단하긴 어렵다. 그리고 자료구조/알고리즘 과 훌륭한 개발자 사이에 꽤 믿을만한 연관이 있다고 알려져 있다. 자료구조/알고리즘 없이 문제풀이 능력을 측정할 수 있는 문제를 만들기가 어렵기도 하다.
실무에서 화이트보드에 코딩할 일은 확실히 없다.
-> 화이트보드 코딩의 좋은 점은 '큰 그림'을 그리는 데 집중할 수 있게 해준다는 것이다. 클래스 정의나 보일러 플레이트 코드를 작성할 필요 없이, 실제로 문제를 풀어내는 함수 부분에만 신경을 쓸 수 있다. 그리고 화이트보드를 이용할 경우 지원자가 자신의 생각을 좀 더 소리내어 설명하는 경향이 있다.

결국 올바른 상황에서 면접이 잘 이루어졌을 때, 문제풀이 능력을 보여 준 지원자가 똑똑하다고 얘기하는 것은 합리적인 판단이다.
면접 후에 아무 연락을 받지 못했더라도 보통은 떨어진 것이 아니다. 탈락한 지원자에게 연락을 주지 않는다는 정책을 갖고 있는 회사는 얼마 되지 않는다.

장막 너머 (Behind the Scenes)

면접 대상자로 선정되면, 보통 사전 면접(screening interview)을 함. 만약 엔지니어가 해당 면접에 참여하면 기술적인 질문이 나오는 경우가 많다.
대면 면접은 보통 3 ~ 6 번 정도. 그 중에 점심식사를 같이 하는 면접이 있기도 하나 기술적인 문제는 다루지 않고 평가에 포함되지 않기도 한다. 평소 관심사, 회사 문화에 대해 질문할 수 있는 좋은 기회.

<마이크로소프트 면접>

geek, 기술에 열정적인 사람을 원함.

<아마존 면접>

난이도 조정권자(bar raiser) 역할을 맡은 면접관이 한 명씩 있다. 면접 문턱(interview bar)를 높이는 역할. 어떤 면접이 특별히 다르고 어렵다면 그 면접관이 난이도 조정권자 일 것.
아마존은 규모 확장성(scalability)에 신경을 많이 씀. 또한 객체 지향 디자인에 대한 질문을 많이 하는 경향.

<구글 면접>

어렵다는 소문이 많지만, 마소나 아마존 면접과 크게 다르지 않음.
전화 사전 면접을 구글 엔지니어가 직접 보는데, 기술적 문제가 까다롭게 나올 수 있음.
규모 확장 가능한 시스템(scalable system)을 어떻게 설계하느냐에 관심. 그리고 경력보다는 분석(알고리즘) 능력에 큰 비중.

<애플 면접>

점심이 면접의 일부
면접 볼 팀에서 만든 제품에 대해 공부하면 좋음.
애플 제품에 대한 열정이 있으면 좋음.

<페이스북 면접>

전화 면접 후 숙제가 있는데, 코딩 스타일에 신경써야함.
기업가 정신 (빠르게 결과) 을 좋아함.
언어 선택에 구애 받지 않기를 바람. 페이스북은 C++, 파이썬, 얼랭 등 다양한 언어로 설계되어 있다. 물론 PHP도 포함.
특정 팀 보다는 전사적인 관점에서 면접이 진행됨. 채용 후에도 부트캠프 라는 훈련과정을 거친 후 프로젝트를 선택.

<팰런티어 면접> (미국의 빅 데이터 프로세싱 기업. CIA, FBI, FDA, 미국방부 등 정부 사업 많이 함. 나무위키)

특정 팀을 위해 면접을 봄.
대부분 알고리즘 문제가 어렵다는 후기가 많다.
어렵다. 문제가 극도로 어려울 수 있다.

특별한 상황에서의 면접

이것 또한 여지 없이 '문제를 풀어내는 능력: 알고리즘과 코딩' 이 가장 중요.

[경력자]
시스템 디자인 방면의 경험은 직업적으로만 얻을 수 있다고 여겨지기 때문에, 시스템 디자인/설계 와 관련된 질문을 받을 가능성이 높다.

[테스터 or SDET(Software Design Engineers in Test)]
실제 제품이 아닌 테스트를 위한 코드를 작성하는 직군.
코딩과 테스트 둘 다 잘해야함.
SDET에서 개발 직으로 직무 전환 하기는 아주 어렵다. 신중히 결정할 것.

[PM]
코딩과 관계된 일을 주로 하는 PM들은 코딩도 잘해야 함.

모호한 상황에 잘 대응하는가
고객에 초점을 맞추는 태도(고객 중심적 사고)와 기술(제품에 대한 이해도)을 지녔는가
다층적 의사소통 능력
기술에 대한 열정
팀워크/리더십

[개발 책임자(dev lead) 와 관리자]
코딩 능력과 인성.

[스타트업]
개인적으로 추천을 받아서 지원하는 것이 베스트.
바로 활용할 수 있는 코딩 능력 뿐만 아니라 사업가적 자질이 요구되는 환경.
대기업은 개발과 관련된 일반적 적성을 평가하는 반면, 스타트업은 지원자의 인성, 기술, 과거 경력을 자세히 들어다보는 경향.

[기업 인수 및 인재 영입]
기업 인수 시에, 모회사가 스타트업의 전직원과 면접을 하고자 할 수 있음.
이 면접은, 해당 모회사의 일반적인 지원자와 거의 비슷한 면접을 보게 될 것. (이 책에 나오는 면접 내용과 굉장히 비슷해질 것)
떨어지면, 인수될 회사에 입사할 수 없다. 만약 대다수의 직원이 면접을 망치면 인수 자체가 무산될 수 있다.
전사적으로 함께 면접을 준비하는 것이 좋고, 시간적 여유를 너무 부리지 않는 것이 좋음.

[면접관들에게 주는 조언]

한 가지 힌트나 조언이 문제 풀이에 큰 영향을 미친다면, 그 문제는 좋은 문제가 아니다.
지식 자체를 측정하는 것을 지양해야 한다. 이런 맥락에서, 지원자에게 기대해도 될 만한 지식은 널리 잘 알려진 자료구조와 알고리즘.
멀리서 봤을 때, 면접 질문에는 네 가지 방식이 존재
1. sanity check : 쉬운 문제. 최악을 걸러내기 위함.
2. quality check : 문제가 철저히 설계되어 있고, 지원자로 하여금 생각하게끔 만들어짐. 알고리즘과 문제풀이 능력을 잘 측정할 수 있음.
3. specialist questions : 자바나 머신러닝 같은 특정 분야의 전문지식과 관련된 문제. 실제 해당 분야 전문가를 평가하기 위한 문제.
4. proxy knowledge : 전문 분야와 관련되어 있긴 하나, 지원자의 현재 레벨에서 알고 있을법한 지식에 관한 문제.

면접 전에

[이력서 준비]
훌륭한 경험 -> 탄탄한 이력서 -> 면접 기회 획득
이미 직장인인 경우,

얻을게 많은 프로젝트에 집중할 것
- 코딩을 많이 할 수 있는 업무
- 가능하면 대형 프로젝트
- 관련 기술을 많이 사용해 볼 수 있는 프로젝트
업무 외에, 재미로 만들어 보는 경험을 할 것

결국, 코딩을 할 수 있고 영리한 사람임을 보여줘야 함.

[이력서 작성]
이력서는 짧으면 짧을 수록 인상에 남는다.
미국에서는 경력이 십 년 미만인 경우 이력서를 한 페이지로 만들도록 권장
구인 담당자는 이력서를 기껏해야 10초 정도 봄. 어떤 사람은 긴 이력서를 아예 무시해 버리기도

이력서 각 항목에 대해서는 다음과 같은 조언

경력 사항
- "Y를 구현해서 X를 성취했고, 그 결과 Z를 이루었다."
  - e.g. 분산 캐시를 구현해서 오브젝트 렌더링 시간을 75% 줄였고, 그 결과 로그인 시간을 10% 경감할 수 있었다.
- 결과를 가급적 측정 가능한 형태로
프로젝트
- 가장 중요했던 프로젝트 2~4개
- 무슨 프로젝트 였고 어떤 언어/기술 을 사용했는지
언어
- 가능하면 사용했던 모든 언어를 적되, 언어에 대한 숙련도도 함께. (기간으로 적는 것은 별로)

아래 같은 경우들은 '낙인'으로 작용할 수동 있음

특정 언어의 사용
- 기업 언어 (e.g. 비주얼 베이직 or .NET 플랫폼 언어) 는 쉬운 것으로 간주되는 경우가 많음.
- 이 외에도 하나의 언어에 지나치게 몰입된 경우는 '좋은 소프트웨어 엔지니어'라는 인상을 줄 수 없음
자격증
- 회사에 따라 자격증을 나열하는 것에 대한 편견이 있을 수 있음
한두 가지 언어만 아는 경우
- 아직 많은 문제를 경험해 보지 못한 사람으로 보일 수 있음
- 새로운 것을 배우는 데 문제가 있는 사람으로 보일 수 있음

평소에도 다양한 언어로 애플리케이션을 만들어 보는 경험이 좋음.

행동 문제 (Behavioral Preparation)

기술 질문과 대응되는 '행동 질문(behavioral questions)' 에도 대비해야 함.
경험 관련 질문이라고 이해할 수 있음.
보통,

인성을 알기 위해
이력서에 적힌 내용을 좀 더 깊이 알기 위해
긴장을 풀어주기 위해

한다.

[프로젝트 경험]

세 개 정도의 프로젝트에 대해서는 자세히 말할 수 있어야 한다.
기술적인 부분에 대해서 깊이 있게 논의할 수 있어야 한다.

이력서에 작성한 프로젝트에 대해 아래의 테이블을 작성해본다. 그리고 면접 전에 이 테이블을 사용해 공부한다.

흔히 나오는 문제	프로젝트 1	프로젝트 2	프로젝트 3
가장 도전적이었던 것
실수 혹은 실패담
즐거웠던 것
리더십
팀원과의 갈등
남들과 다르게 행동했던 것

[단점]
단점을 얘기할 때는 '진짜 단점'을 얘기하라. 완벽주의 같은 대답은 오만하거나 실수를 인정하지 않는 사람이라는 인상을 줄 수 있음

[면접관에게 할 질문]
면접관에게 할 양질의 질문을 준비해야 함. 의식/무의식 적으로 면접관의 결정에 영향을 줌.

순수한 질문
- 팀에서는 계획을 어떤 식으로 수립하나요?
- 어떻게 이 회사에 오시게 되었나요?
통찰력을 보여줄 수 있는 질문
- X라는 기술을 쓰시는 걸 봤는데, OO문제는 어떻게 해결하고 계신가요?
열정을 보여줄 수 있는 질문
- ㅁㅁ 에 관해서 관심이 많고 많이 배우고 싶은데, 그런 기회가 있을까요?

[대처 요령]

오만하지 않으면서도 깊은 인상을 심어주려면 '구체적' 으로 답변하면 된다.
- 사실만을 전달하고, 해석은 면접관에게 맡긴다.
- 구체적이되 세부적일 필요는 없다.
- 자신이 맡았던 부분을 뭉뚱그리지 말고 어떤 실행을 했는지 구체적으로 설명하되, 원리를 설명할 필요는 없다는 것.
'우리 팀'에 대한 이야기가 아니라, '나'에 대한 이야기를 해야 한다.
- 면접관은 '나'의 역할에 관심이 있다.
구조적으로 답변해야 한다.
- 두괄식, 그리고 S.A.R (Situation. Action. Result)
- 상황(S: situation) 보다 행동(A: action) 을 더 중점적으로 설명해야 함.

[자기 소개]
한국 기업 면접에서 하는 '1분 자기소개' 와는 조금 다른 늬앙스 같기는 하지만, tell me about yourself 라는 질문을 받았을 때.
보통, 시간순 구조로 이야기를 풀면 자연스럽다.

현재 직업 (서두) - 학교 - 졸업 후 지금까지 - 현재 역할 - 업무 외(취미 혹은 직무 관련 활동) - 마무리

취미는 사실 이야기 하지 않아도 무방하지만, 유용할 때가 있다.

취미가 굉장히 독특한 경우 -> '나는 불을 뿜을 수 있어요' : 호의적인 분위기 형성.
취미에 기술적인 면이 있는 경우 -> 자명.
취미가 긍정적인 성격적 특성을 보여주는 경우 -> e.g. 셀프 리모델링 : 새로운 것을 배우고, 위험을 감수하고, 손을 더럽히는 것을 두려워하지 않음.

어쨌든 간에, 자연스럽게 나의 성공사례를 드러낼 수 있는 이야기를 해야 한다.

big-O

[시간 복잡도]
알고리즘의 '점근적 실행 시간' (asymptotic runtime). (asymptotic: 점근선의)

O (big-O) - 시간의 상한. 알고리즘의 실행시간이 시간보다 낮기만 하면 표기 가능.
Ω (big-Omega) - 시간의 등가 혹은 하한. 알고리즘의 실행시간이 시간보다 높기만 하면 표기 가능.
Θ (big-theta) - O(N) 이면서 Ω(N) 이면, Θ(N) 이다.

업계(면접)에서 big-O 는 big-theta 의 의미와 가깝다. 즉, 수행시간을 딱 맞게 표현한 것이 big-O.

[최선 / 최악 / 평균]
최선/최악/평균의 경우는 그 입력(상황)을 의미. big-O, big-Omega, big-theta 와는 무관.
그 각각의 입력(상황)의 수행시간을 big-O 시간으로 설명하는 것일 뿐.
보통은 평균의 경우를 가정하는 듯.

e.g. 퀵정렬
최선의 경우 - 배열에서 모든 원소가 동일할 경우, 수행 시간은 O(N). (배열이 정렬되어 있을 때 이럴 수 있는 구현 방식이 존재)
최악의 경우 - 배열에서 가장 큰 원소가 계속해서 pivot으로 선정될 경우 (배열이 역순으로 정렬되어 있고, 항상 첫 번째 원소를 pivot으로 할 경우), 수행시간은 O(N^2).
평균의 경우 - O(N*logN)

[공간 복잡도]
메모리 공간을 얼마나 차지하느냐.
길이가 n개인 배열을 만들기 위해서는 O(n)의 공간이 필요.
재귀 호출을 n번 하면 O(n) 만큼 호출 스택 공간을 사용하게 됨.
단순 함수 호출을 n번 하면 단지 O(1) 만큼의 호출 스택 공간을 사용하게 됨. (각 호출이 호출 스택에 동시에 존재하지 않으므로)

[최고차항]
최고차항을 제외한 나머지항 그리고 상수항은 무시해도 된다.

[상환 시간]
어떤 연산의 수행시간이 조건에 따라 달라질 때 평균적인 수행시간을 계산하는 방법.
최악의 경우는 가끔 발생하지만, 한 번 발생하면 그 후로 꽤 오랫동안 나타나지 않는다.
따라서 최악의 경우에 발생한 비용(수행 시간)을 나머지 일반적인 경우에서의 수행시간에서 분할상환 한다는 개념.

ArrayList 에 원소를 삽입할 때, 배열이 꽉 차 있으면 기존 배열 크기의 2배인 새로운 배열을 만들고 기존 원소를 그대로 복사한다.
만약 N개의 원소가 꽉 차있는 배열에 원소 하나를 삽입하려면 O(N) 수행시간이 걸린다.
하지만 꽉 차 있지 않은 경우에 원소를 삽입할 때는 언제나 O(1) 수행시간이 걸린다.

배열의 크기가 1,2,4,8,16,...,X 로 증가 한다고 하면, 각 증가시에 복사해야 하는 원소의 개수는 1,2,4,8,16,...,X 이다.
이 개수들의 합은 X+X/2+X/4+X/8+...+1 과 같으므로 대략 2X 가 된다.
따라서 X개의 원소를 삽입했을 때 필요한 시간은 O(2X) 이고, 이를 X번의 삽입에 대해 분활 상환한다고 하면 삽입 한 번에 필요한 시간은 O(2X/X) 즉 O(1)이다.

[log N 수행 시간]
어떤 문제에서 원소의 개수가 절반씩 줄어든다면, 그 문제의 수행시간은 O(logN)이 될 가능성이 크다. (N개의 노드를 가진 균형이진탐색트리의 높이는 logN)
로그의 밑은 상관없다. 로그의 밑에 따른 차이는 상수항 만큼의 차이이기 때문이다.

[재귀적인 수행 시간]
다수의 호출로 이루어진 재귀 함수에서 수행시간은 보통 O(분기^깊이) 로 표현되곤 함. (등비 수열의 합에 big-O 적용)
분기(branch) : 재귀 함수가 자신을 재호출 하는 횟수
깊이 : 재귀 함수의 종료 조건과 관련 (if n<=1 에서 종료하면 깊이는 n이 되는 것)

[예제 및 연습문제]
중첩 반복문

for (int i = 0; i < n; i++) {
	for (int j = i+1; j < n; j++) {
    	System.out.println(i + "," + j);
    }
}

반복 회수를 세어보기 :
안쪽 반복문이 n-1번, n-2번, n-3번, ... , 1번 수행되기 때문에 이를 다 더하면 됨.
1부터 x까지의 합은 x(x+1)/2 이므로 (n-1)n/2 번, 즉 O(n^2) 의 수행시간을 가짐.
평균을 이용한 방법 :
안쪽 반복문이 n-? 번 반복될 것.
바깥쪽 반복문이 n 번 , 그 때마다 안쪽 반복문이 n-? 번 반복하기 때문에 n(n-?) 번, 즉 O(n^2) 의 수행시간을 가짐.

재귀 호출

// 균형 이진 탐색 트리에서 모든 노드의 값을 더하는 코드
int sum(Node node) {
	if (node == null) {
    	return 0;
    }
    return sum(node.left) + node.value + sum(node.right);
}

재귀 호출의 경우, 수행시간은 함수 호출 횟수 즉, 호출 트리의 노드 개수와 비례한다.
이 경우, 입력 자체가 균형 이진 탐색 트리이므로 균형 이진 탐색 트리의 노드의 개수가 n이면 수행시간은 O(n)이다.
위에서 언급된 O(분기^깊이)로 접근하고자 하면 분기는 2, 깊이는 logn 이 될 것이다. 그래서 결국 O(2^logn)=O(n)이 된다.

알고리즘이 만들어내는 결과물의 개수와 함수의 호출 횟수를 혼동하면 안된다.

길이가 n인 문자열에 대한 순열을 전부 구하는 알고리즘이 있다고 하자. 이 알고리즘은 재귀 호출로 동작한다.
가능한 순열의 개수는 총 n! 임을 익히 알고 있다. 하지만 함수 호출 횟수(수행시간)이 n! 인 것은 아니다.
호출 트리에서 리프 노드의 개수가 n!이 될 것이고, 루트에서 각 리프 노드까지의 거리가 n이 될 것이기 때문에, 전체 노드(함수 호출)의 개수는 n*n! 개를 넘지 못할 것이다.
즉, 총 수행시간은 O(n*n!)을 넘지 않을 것이다.

기술적 질문 (Technical Questions)

[준비하기]

직접 풀도록 노력할 것.
코드를 종이에 작성해 볼 것.
코드를 테스트 할 것.
종이에 적은 코드를 그대로 컴퓨터로 옮겨서 실행해 볼 것.
가상 면접을 가능한 많이 해볼 것.

[필수 기본기]
자료구조 / 알고리즘

자료구조

연결리스트 (Linked Lists)

트리, 트라이 (Tries), 그래프

스택 & 큐

힙

Vector / ArrayList

해시테이블

알고리즘

BFS

DFS

이진 탐색

병합 정렬

퀵 정렬

개념

비트 조작 (Bit Manipulation)

메모리 (스택 vs 힙)

재귀

동적 프로그래밍 (Dynamic Programming)

big-O 시간 & 공간

사용법, 구현법, 애플리케이션, 그리고 공간 & 시간 복잡도에 대해서 알아두어야.
직접 구현해보기를 추천 (종이 -> 컴퓨터)

[실제 문제 살펴보기]

경청하기
문제에서 주어진 정보를 모두 사용하고 있는지 확인. e.g. 정렬된 배열이 주어졌을 때, ...
예제를 직접 그려보기
문제에 맞는 실제 숫자와 문자열을 이용해서, 충분히 큰 예제를 직접 그려보자. 특별한 예제를 지양해야 한다.
brute force로 일단 해보기
알고리즘 최적화 시작점이 바로 brute force 접근법. 이 과정이 문제에 집중하도록 도움을 준다.
최적화
brute force로 만든 알고리즘을 최적화 한다.
- 간과한 정보가 있는가? (e.g. 이미 정렬된 배열)
- 새로운 예제
- 잘못된 방식으로 문제를 풀어보기. 그로 부터 개선하기
- 시간 / 공간의 실익을 따져서 균형 맞추기.
- 정보를 미리 계산해 두기
- 해시테이블 적극 활용하기
검토하기
코드 작성하기
- 모듈화된 코드를 사용하라. 행렬을 초기화해야 하는 경우라면, 그런 함수가 있다고 가정해도 좋다.
- 에러 검증하라. todo로 대신하고 설명을 해도 좋다.
- 필요한 경우 다른 클래스나 구조체를 사용하라. 그런 클래스가 있다고 가정하고 코딩.
- 좋은 변수명을 사용하라. 반복문의 i,j 말고는 한 글자를 쓰지 말자. 변수명을 줄여 쓰더라도 처음에는 풀네임으로 쓰고 나중에 줄일 때 설명하자.
테스트
이전에 만든 예제, 크기가 큰 예제는 피하자
- 완성된 코드를 읽어보며 머릿속으로 테스트 해본다.

[최적화 및 문제풀이 기술]
#1. BUD를 찾으라
BUD는 다음의 약자이다.

병목 현상 (Bottlenecks)
불필요한 작업 (Unnecessary Work)
중복되는 작업 (Duplicated Work)

병목현상 : 알고리즘에서 전체 수행 시간을 잡아먹는 부분.

예제: 서로 다른 정수로 이루어진 배열이 있을 때 두 정수의 차이가 k인 쌍의 개수를 세라. 예를 들어 주어진 배열이 {1, 7, 5, 9, 2, 12, 3}이고 k=2면, 두 정수의 차이가 2인 쌍은 다음과 같이 네 개가 존재한다. (1,3), (3,5), (5,7), (7,9)

아래와 같은 분석을 할 수 있다.

brute force -> 가능한 쌍을 전부 만들고, 각 쌍 내부의 차이를 모두 구한 뒤 그 값이 정확히 k가 되는 쌍의 개수를 센다.
-병목지점 -> 가능한 쌍을 전부 만드는 것. 즉, 각 쌍의 두 번째 원소를 반복적으로 찾는 것.
개선안 -> 배열을 정렬하면, 각 쌍의 첫 번째 원소에 대해 k만큼 앞 뒤로 차이나는 정수를 이진 탐색으로 찾을 수 있다.
-신 병목지점 -> 배열을 정렬해야 한다(nlogn). 검색하는 부분 (지금은 이진 탐색) 을 아무리 개선해도 정렬하는 시간은 그대로.
신 개선안 -> 모든 원소를 해시 테이블에 넣으면(n) 배열을 정렬하지 않아도 되고, 두 번째 원소를 찾는 것도 해시테이블로 상수시간에 찾을 수 있다.

불필요한 작업

예제: a,b,c,d가 1에서 1000 사이에 있는 정수 값 중 하나일 때 a^3 + b^3 = c^3 + d^3 을 만족하는 모든 자연수를 출력하시오.

아래와 같은 분석을 할 수 있다.

brute-force -> O(n^4)

n = 1000
for a from 1 to n
	for b from 1 to n
    	for c from 1 to n
        	for d from 1 to n
            	if a^3 + b^3 == c^3 + d^3
                	print a, b, c, d

-불필요한 작업 -> d값이 정해졌으면, 나머지 d의 후보들은 확인하지 않아도 된다.

n = 1000
for a from 1 to n
	for b from 1 to n
    	for c from 1 to n
        	for d from 1 to n
            	if a^3 + b^3 == c^3 + d^3
                	print a, b, c, d
                    break // 루프에서 빠져나온다.

-불필요한 작업 -> a,b,c 값이 정해진 상황에서 유효한 d의 값은 수식으로 구할 수 있다. -> O(n^3)

n = 1000
for a from 1 to n
	for b from 1 to n
    	for c from 1 to n
        	d = pow(a^3 + b^3 - c^3 , 1/3) // 정수로 반올림 됨
            if a^3 + b^3 == c^3 + d^3
            	print a, b, c, d

중복되는 작업
위와 같은 예제.

-중복되는 작업 -> (a,b)에 대하여 이를 만족하는 (c,d)를 매번 구해야 함.
(c,d) = c^3 + d^3 가 만들 수 있는 '값'들은 정해져 있으므로, 매번 구하지 말고 미리 다 계산을 해두어 필요할 때 찾아 쓴다.
즉, 해시테이블을 이용해 가능한 '값'들을 key로 하고 그 '값'을 만들 수 있는 (c,d)의 쌍의 리스트를 value로 관리한다.

n = 1000
for c from 1 to n
	for d from 1 to n
    	result = c^3 + d^3
        map[result] 에 (c,d) 추가.
for a from 1 to n
	for b from 1 to n
    	key = a^3 + b^3
        list = map.get(key)
        for pair in list
        	print a, b, pair

사실 (a,b) 쌍 또한 같은 조건(각각의 세제곱의 합)이기 때문에 (c,d)의 계산된 리스트를 그대로 사용할 수 있다.

n = 1000
for c from 1 to n
	for d from 1 to n
    	result = c^3 + d^3
        map[result] 에 (c,d) 추가.

for result, list in map
	for pair_1 in list
    	for pair_2 in list
        	print pair_1, pair_2

결국 O(n^2) 시간이 걸리게 된다.

#2. 문제의 답을 손으로 직접 구해보라
실제 예제를 통해 직관적으로 문제를 풀어나가는 것에서부터 시작할 수 있다.

예제: 길이가 작은 문자열 s와 길이가 긴 문자열 b가 주어졌을 때, 문자열 b안에 존재하는 문자열 s의 모든 순열을 찾는 알고리즘을 설계하라. 각 순열의 위치를 출력하면 된다.

알고리즘을 설계해야 겠다고 접근하다보면,
문자열 s의 모든 순열 -> O(s!)
각 순열을 문자열 b 안에서 찾는다 -> O(b)
결국 -> O(s!*b)

예제와 함께 직관적으로 답을 내려고 접근해보면,

s: abbc
b: cbabadcbbabbcbabaabccbabc

b를 앞에서부터 4글자씩 끊어서 차례로 살펴본다. 각 글자를 s에서 하나씩 뽑아올 수 있다면 순열을 찾은 것이다. -> O(b*s^2)

문제에 적합하고 크기가 크며 구체적인 예제를 바탕으로 직관적으로, 손으로, 머리로 문제의 답을 직접 내본다.
그 직관적인 풀이과정을 역으로 이용해 알고리즘을 설계. 나도 모르게 직관으로 행했던 '최적화'를 알아낸다.

#3. 단순화, 일반화하라
문제의 제약조건을 단순화하거나 변형시킨 형태로 해결한 후에, 복잡한 형태로 다듬어 간다.

예제: 랜섬 노트(ransom note)는 잡지에서 오린 단어를 이용해서 만들어 낸 새로운 문장을 의미한다. 잡지(문자열)가 주어졌을 때, 그 잡지에서 문자열로 표현 특정 랜섬 노트를 만들 수 있는지 어떻게 확인할까?

'오린 단어'를 '오린 글자'로 단순화 해본다.
그러면 배열을 사용해 특정 랜섬 노트에 나타난 글자들의 각 개수를 파악하고, 잡지의 글자를 순회하면서 이 개수들을 다 소진할 수 있는지 확인하면 된다.
결국 단어로 일반화 하면, 해시테이블을 사용해 각 단어의 개수를 파악하고, 잡지의 단어를 순회하면서 이 개수들을 다 소진할 수 있는지 확인하면 된다.

#4. base case로부터 확장하기
n=1 과 같은 base case에 대한 문제를 풀고, 거기서 해법을 확장해 나간다.

예제: 문자열의 모든 순열을 계산하는 알고리즘을 설계하라. 모든 문자는 문자열 내에서 고유하게 등장한다.

입력 문자열로 abcdefg 가 주어졌다고 하면,

case "a" -> {"a"}
case "ab" -> {"ab", "ba"}
case "abc" -> ?

P("abc") 는 P("ab")에서 "c"를 사이사이에 끼워넣으면 얻을 수 있다. 이런 식으로 재귀 호출을 만들 수 있다.
이렇듯 base case로 부터의 확장 알고리즘은 자연스럽게 재귀 알고리즘으로 구현되는 경우가 많다.

#5. 자료구조 하나씩 대입해보기
단순하게 일련의 자료구조를 차례차례 살펴보면서 하나씩 적용해 보기. 너저분하지만 은근 자주 통한다.

예제: 임의의 숫자를 만들어 낸 뒤 확장 가능한 배열에 차례로 저장한다. 새로운 입력이 들어올 때마다 중간값(median)을 구하려면 어떻게 해야 할는가?

연결리스트 -> 정렬과 바로 접근에 취약. 아닐듯
배열 -> 이미 주어져 있다. 배열을 정렬된 상태로 유지? 비용이 상당할 듯
이진 트리 -> 순서를 유지하는데 장점. 하지만 중간값을 쉽게 얻기 위해선 항상 트리의 균형을 유지해야할 듯. 그리고 원소 개수가 짝수이면 중간값은 가운데의 두 원소의 평균. 이것도 신경쓰일듯
힙 -> 최댓값 최솟값을 유지하는 데 최적. 최소-힙 과 최대-힙을 동시에 운영한다고 하면, 원소들을 두 분류로 나눠서 큰 쪽은 최소-힙에 작은 쪽은 최대-힙에 넣어 중간 값 후보자들을 각 힙의 루트로 관리할 수 있을 듯. 힙들의 원소 개수의 균형만 잘 맞추면 딱일 듯.

[가능한 최선의 수행 시간]
BCR : Best Conceivable(생각해볼 수 있는) Runtime

어떤 문제를 푸는데, 상상할 수 있는 모든 해법 중에 수행 시간이 가장 빠른 것.
주어진 문제에 대해 어떤 알고리즘도 이 보다는 빠를 수 없다는 것을 알려주는 것.
e.g. 각각 길이가 A, B 인 배열이 있다고 했을 때 두 배열에 공통으로 들어있는 원소를 세는 경우 수행시간은 O(A+B) 보다 빠를 수 없을 것.
Best Conceivable Runtime: 가능한 최선의 수행 시간
-> 모든 해법 중 가운데 가장 빠른 알고리즘의 수행 시간
Best Case Runtime: '최선의 경우'의 수행 시간
-> 특정 알고리즘이 가장 빠르게 동작하는 '경우'(case)의 수행 시간
둘은 전혀 무관.

사용법에 관한 예제를 살펴보자.

예제: 정렬된 배열 두 개가 주어졌을 때, 공통으로 들어 있는 원소의 개수를 찾으라.
A: 13 27 35 40 49 55 59
B: 17 35 39 40 55 58 60

brute-force: O(N^2)
최적 알고리즘: ?
BCR: O(N)
- 원소는 총 2N이고, 모든 원소를 적어도 한 번씩은 살펴봐야 하기 때문.

결국 O(N)까지 줄여볼 수 있다는 이야기.
O(N*N) 에서 첫번째 N은 더이상 줄일 수 없을 것 같으니(BCR 활용 지점), 두번째 N을 어떻게 줄일까?
두번째 N은 탐색하는 부분에서 나온 것이므로, 이를 이진 탐색을 통해 logN으로 최적화 해볼 수 있음.

brute-force: O(N^2)
개선안: O(N logN)
최적 알고리즘: ?
BCR: O(N)

더 개선할 수는 없는가? 정렬되어 있다 하더라도 탐색을 O(logN)보다 줄일 수는 없다.
하지만 BCR보다 수행시간이 빠르거나 같은 모든 작업은 전체 수행시간에 아무런 영향을 주지 않는다 (BCR 활용 지점).
그래서 O(N) 안에 할 수 있는 사전 작업은 무엇이든 해두어도 된다 -> 사전에 해시테이블을 O(N)에 만들 수 있음 -> 탐색 자체는 O(1)에 가능.
그러면 총 수행시간은 O(N)이 될 수 있다.

brute-force: O(N^2)
개선안: O(N logN)
최적 알고리즘: 시간 - O(N), 공간 - O(N)
BCR: O(N)

도출한 알고리즘의 수행시간이 BCR이 같아졌으니 더 이상 '수행시간' 에서의 최적화는 끝 (BCR 활용 지점).
'공간 복잡도' 를 최적화 해보자. O(N)보다 공간복잡도를 낮추려면 해시테이블을 포기해야 함. -> 다시 이진탐색으로.

brute-force: O(N^2)
개선안: O(N logN)
최적 알고리즘: 시간 - O(N logN), 공간 - O(1)
BCR: O(N)

이 상태에서 다시 탐색 시간을 최적화 해보자.
둘다 "정렬된 배열"이라는 큰 힌트가 있다.
A배열의 첫번째 원소부터 차례로 방문하며 B배열의 원소를 차례로 살피게 될텐데,
A배열의 n번째 원소를 B배열의 어떤 위치에서 찾았다면 A배열의 n+1번째 원소는 그 위치의 뒤 부터 탐색하면 된다. 전체적으로는 두 배열의 모든 원소 개수인 2n개를 하나씩 방문해 보면 끝낼 수 있다.
즉 O(N)에 탐색을 할 수 있는 상황이다.

brute-force: O(N^2)
개선안: O(N logN)
최적 알고리즘: 시간 - O(N), 공간 - O(1)
BCR: O(N)

수행시간이 BCR과 같아지고 공간 복잡도가 O(1) 이 되었다면, big-O 시간과 공간은 더 이상 최적화 할 수 없다 (BCR 활용 지점).

[오답에 대한 대처법]
다 맞출 필요는 전혀 없다. 맞았냐 틀렸냐로 평가하지 않는다.
평가 기준은,

최적 해법에 근접한가
푸는데 시간이 얼마나 걸렸나
힌트가 얼마나 필요했냐
코드가 얼마나 깔끔했냐

그리고 상대평가이다. 저자가 구글에서 수천 명을 심사하면서 아무 '결점' 없이 면접을 마친 사람을 딱 한명 봤다.

[알고 있던 문제가 면접에 나왔을 때]
이실직고하라. 이유는,

이미 알고있는 문제로는 정확한 평가가 어렵다.
만약 들킨다면 아주 부정직한 인상을 준다. (밝힌다면 반대로 아주 정직한 인상을 준다)

[면접용 언어]

내가 가장 편한 언어
널리 사용되는 언어
가독성이 좋은 언어 ( <-> Scala, Objectiv-C)
언어가 작동하는 방식 (C++: 메모리 관리, 포인터 관리가 수동)
장황함
- 자바는 장황하고 파이썬은 간결하다. 하지만 임의로 축약한 코드를 작성해도 무방하다.
편리한 기능
- 파이썬은 함수에서 값 두개 반환하는게 매우 쉽다든지 하는 것. 하지만 임의의 함수를 가정하고 문제를 풀어도 매우 무방.

[좋은 코드]

적절한 자료구조 사용
- 필요하다면 클래스를 만들어 사용하는 것도 방법.
적절한 재사용
모듈화
유연성 (3x3 틱택토 보다는 nxn 틱택토를 구현하듯)
- 단, 너무 복잡해지거나 지금은 그럴 필요가 없다는 판단이 들면, 일단은 단순하게 구현
오류 검사
- 간단한 if 문으로 오류를 검사
- 당장 추가할 수 없다면 공간을 남겨두고 나중에 작성하겠다는 언급.

[포기하지 말 것]
까다로운 문제에 당당히 맞서기.
추가 '점수'를 받기 위해 어려운 문제를 즐기며 푸는 모습을 보여라.

합격한 뒤에

[입사 결정]

보통 회사가 제안을 하면, deadline이 있음 (주로 1~4주)
기한 연장을 요청할 수 있고, 대부분 회사는 가능한 들어주려고 함
거절할 때는 공격적이지 않고 명백한 이유를 댈 것

[입사를 고민할 때]

금전적인 부분
- 연봉은 고려해야 할 것들 가운데 하나 일 뿐
- 계약 보너스, 주거 생활 비용, 연간 보너스, 스톡옵션
커리어
회사의 안정성 (해고 가능성)
- 안정적인 회사일수록 느리게 성장하는 경향
행복
- 제품, 관리자, 동표, 문화, 근무 시간

[연봉 협상]

일단 지르고 보라
- 대부분 협상을 좋아하지 않음. 하지만 그래서 해볼만 함.
- 협상을 시도한다고 해서 채용 제안을 철회하는 회사는 없음.
구체적으로 요구하고, 많이 요구해라
- 협상이란 그런 것. 어차피 무슨 요구를 하든 처음부터 들어주지 않음.
대기업은 연봉 테이블이 정해져 있다.

[입사 후]

로드맵 설정
- 하는 일을 즐기다 보면, 현실에 안주하게 됨.
- 십년 뒤에는 어디에 있고 싶은지, 그러기 위해서는 어떤 단계를 거쳐야 할지,
- 작년에 비해 나의 경력과 기술은 얼마나 성장했는지 살펴보아야 함.
네트워크 형성
- 새로운 일을 할 때 (이직을 포함해서) 온라인으로 시작하는 것 보다는 개인적인 추천과 도움을 받는 것이 훨씬 좋다.
원하는 것을 요구
- 나의 목표를 적절한 수준으로 솔직하게 관리자에게 표현
꾸준히 면접을 보기
- 적어도 일년에 한 번.
- 최신 면접 기술을 유지할 수 있고, 나에게 어떤 기회(연봉)이 있는지 알 수 있다.

면접 문제

배열과 문자열

배열과 문자열에 관한 문제는 서로 대체 가능.

해시테이블

효율적인 "탐색"을 위한 자료구조
key를 value에 대응시키는 형태

배열과 연결리스트, 해시코드 함수로 구현하는 방식 - O(1)
- 저장
  1. 해시코드 함수로 key의 해시 코드를 계산
  2. 해시코드로 배열의 인덱스를 계산 (e.g. hashCode % arrayLength)
  3. 인덱스에 있는 연결리스트에 key와 value를 저장
- 탐색
  - 위의 a, b 이후에 연결리스트에서 key를 통해 찾는다
- 충돌
  - 서로 다른 두 개의 키가 같은 배열 인덱스를 가지는 경우. 이래서 연결리스트를 사용.
균형 이진 트리로 구현하는 방식 - O(logN)

ArrayList 가변 크기 배열

크기를 자동으로 조절해주는 배열
데이터가 늘어남에 따라 배열의 크기를 증가시키는 방식
상환 시간 개념을 통해 O(1)의 접근 시간을 가짐

StringBuilder

(자바에서) String 자료형은 immutable 하기 때문에, 문자열에 대한 연산을 하려면 복사가 필요함.
길이가 모두 s인 문자열 n개를 전부 이어붙인다면
- s개, 2s개, 3s개, ..., nx개 : 이런 식으로 붙일 때 마다 복사를 해야함 -> O(sn^2)
StringBuilder 는 가변 길이 배열을 이용해, 매번 복사하는 것이 아니라 필요할 때만 복사할 수 있게 해줌.

면접 문제

1.1_ ascii 면, 가능한 문자의 종류가 정해져 있기 때문에, 그 종류의 개수만큼 미리 배열을 만들어두고, 문자열의 문자들을 하나씩 보면서 그 종류에 해당하는 인덱스에 표시를 해두면서 체크하면 중복 확인이 가능 -> O(n). 배열 공간을 사용하지 않는다면, 모든 쌍을 다 검사하거나(n^2) 정렬을 해서 인접한 문자만 비교한다(nlogn).

1.2 길이가 같아야 하고, 두 문자열의 '문자 구성'이 정확히 일치하는지 판단하면 됨. counter 배열을 문자 종류 크기만큼 할당해 두고, 첫번째 문자열의 문자 종류의 개수를 센 후, 두번째 문자열을 확인할 때 이 개수들을 지워나가면서 확인.

1.3 문자열을 직접 조작하는 문제를 풀 때, "문자열을 뒤에서부터 거꾸로 편집" 하는 패턴이 자주 쓰임.
입력으로 받은 문자열에 대고 직접 편집을 하는 것이기 때문에, 앞에서부터 편집을 하다가 아직 활용하지 못한 기존 문자를 덮어쓸 염려가 있음.
그래서 편집에 필요한 여유공간을 미리 계산하고, 기존 문자열의 길이에 그 여유공간 만큼을 더한 총 공간을 확보 후 뒤에서부터 편집을 시작.

1.4 역시나 문자의 종류가 제한되어 있으므로 종류별로 개수를 세서 각 종류의 개수들이 전부 짝수이거나, 하나만 1개 이면 된다. 공간 효율적으로, 비트 벡터를 이용해서 해당 종류가 발견될때 토글하는 식으로 기록해두어도 된다.

이때 결과를 판정하기 위해 비트 벡터(숫자)가 아예 0 이거나, 하나의 비트만 1인 상황을 검사해야 한다. 후자의 경우, 숫자에서 1(2^0) 을 뺀 값과 기존 숫자를 AND 연산했을 때 0이 나온다면, 해당 숫자는 정확히 하나의 비트만 1이었다는 사실을 알 수 있다.

ex)
00010000 - 1 = 00001111
00101000 - 1 = 00100111

1.5 두 문자열에 대해 포인터를 동시에 이동하며 조건에 부합하는지 판단

1.6 문자열에 다른 문자열을 이어 붙일때, 두 문자열을 모두 읽어들여 새로운 문자열에 복사해야 한다. 공간 효율성을 위해 StringBuilder를 적극 사용해야 한다.(가변 길이 배열로 동작)

1.8 어떤 행렬에 대해서, 특정 행/열에 모두 적용하는 속성을 행렬의 첫번째 행/열에 작성해 두면 공간효율을 O(1)로 가져갈 수 있다.

연결리스트

차례로 연결된 노드를 표현해주는 자료구조
단방향 또는 양방향
배열과 달리 특정 원소(인덱스)를 상수 시간에 접근 할 수 없음.
시작점에서 원소를 추가/삭제 하는 연산을 상수 시간에 할 수 있음.
(특정 원소의 주소를 알고 있다면 그곳에 추가/삭제 또한 상수 시간에 할 수 있음)
각 노드 원소를 관리하는 더 큰 클래스(LinkedList 클래스)가 없다면, 결국 head가 가리키는 노드에 접근하는 것이 곧 연결리스트에 접근하는 것이 됨. -> head가 변경될 때, 이 연결리스트에 접근하는 모든 객체가 가지고 있는 head 정보가 동기화 되지 않는 경우 생김.
Node 클래스를 포함하는 LinkedList 클래스를 만들어 사용하는 것이 좋다.

Runner 기법

연결리스트를 순회할 때 두 개의 포인터를 동시에 사용하도록 해서 문제를 해결.
Runner 포인터가 Current 포인터보다 앞서도록 하면서 순회하는 방법.

예를 들어, a1->a2->a3->a4->a5->b1->b2->b3->b4->b5 같은 연결리스트가 있을 때,
a1->b1->a2->b2->...->an->bn 와 같이 재정렬 하고 싶다고 하자.
Current 포인터는 한 칸씩 진행하고, Runner 포인터는 두 칸씩 진행하면, Runner가 끝에 도달했을 때 Current는 가운데 지점에 있게 된다. 이때 Runner 를 다시 맨 앞으로 옮겨서 한칸씩 진행하도록 하되 Current 가 앞으로 가리키게 될 원소들을 Runner의 다음 자리에 밀어넣으면 된다.

재귀 문제

재귀 호출은 단방향 흐름에서 뒤로 정보를 전달할 수 있는 방법.
연결리스트 관련 문제 가운데 상당수는 재귀 호출에 의존함.

면접 문제

2.2 결론은 Runner 포인터를 사용해서 Current 포인터가 항상 자신보다 k개 뒤에 있도록 순회하면 된다.
brute-force로 생각해보면 연결리스트의 끝까지 순회해서 총 길이를 구하고, 뒤에서 k번째 원소의 인덱스를 계산해(n-k 번째) 해당 인덱스로 접근하면 된다. 연결리스트에서 특정 인덱스로 접근하기 위해서는 첫 번째 원소부터 다시 시작해야하기 때문에, 총 길이 계산 시에 Current 포인터를 뒤따르게 해두어서 바로 접근할 수 있게 하는 방식.

2.3 단방향 연결리스트 이므로, 현재 노드의 뒤에 있는 노드들의 정보만 조회하고 수정할 수 있다. 그래서 지금 삭제하려는 노드가 마치 그 다음노드처럼 존재하도록 수정해볼 수 있다. 삭제하려는 노드의 data를 그 다음 node의 data로, next 정보를 그 다음 node의 next 정보로 수정하면 된다.

2.4 포인터 두개를 사용해서 하나(p1)는 자신이 지나온 곳에는 무조건 x보다 작은 원소가 있는 것을 보장하도록 하고, 나머지 하나(p2)는 x보다 작은 원소들을 찾으러 먼저 나가서 찾아보게 하도록 하면 된다. p1이 x보다 크거나 같은 원소를 만났을 때, p2는 자신이 마지막으로 찾았던 지점에서부터 시작해서 x보다 작은 원소가 있는지 확인하고, 발견하면 p1 자리의 원소와 교체한다. p2는 항상 p1과 같은 위치 혹은 더 진행한 위치에 있어야 한다. p2가 리스트의 끝에 도달하면 종료한다.

아니면 새로운 연결리스트를 만든다. 방법은 여러가지인데, 어떤 node를 재배치 하고자 할 경우, node.next를 미리 꺼내두고 node.next가 원하는 곳을 가리키도록 수정하면 된다.

2.6 재귀 호출을 사용하는 방법은 Stack을 활용하는 방법과 흡사하다.
재귀 함수의 결과값이 2개 이상이어도 무방하다. 파이썬이 아니라면 클래스를 만들어서 활용한다.

2.8 Tortoise & Hare Algorithm
1) T가 한 칸씩, H가 두 칸씩 움직이도록 했을 때, 연결리스트에 루프가 있다면 T와 H는 결국 만나게 된다.
2) 한 포인터를 연결리스트의 시작점, 다른 포인터를 둘이 만난 지점에 두고 둘 모두를 한 칸씩 진행시키면, 루프의 시작 지점에서 만나게 된다.

간단한 증명 1 : 루프가 없다면, H는 결국 연결리스트의 끝에 도달할 것이다. 루프가 있다면, H가 T보다 무조건 빠르기 때문에 T가 루프의 시작에 도달 했을 때 H는 루프의 어딘가에 위치해 있을 것이다. 루프는 결국 '원'이기 때문에 한쪽 방향으로만 움직인다면 이미 루프 어딘가에 있는 H가 루프 시작에 있는 T를 뒤쫓는 관점으로 바라볼 수 있다. 이때, T는 한 번에 한 칸씩 H는 한 번에 두 칸씩 움직이므로, 결국 H가 T에 한 번에 한 칸씩 가까워 지는 꼴이 된다. 그렇다면 둘은 무조건 만날 수 밖에 없다.

간단한 증명 2: T가 1칸 갈때 H는 2칸 간다. T가 k칸 갈때 H는 2k칸 간다. T가 k만큼 움직여 루프 시작점에 도착했다면 그동안 H는 2k만큼 움직였을 텐데, H는 이미 루프 안을 돌고 있을 것이다. H가 루프 시작점으로부터 움직인 거리는 2k-k=k 이다. 이때 k는 루프의 총 길이보다 클 수 있으므로 좀 더 정확하게 H는 루프 시작점으로부터 k%LOOP_SIZE = K 만큼 진행해 있다. 이런 상황에서 루프 시작점에 있는 T에 대해 H가 LOOP_SIZE-K 만큼 뒤쳐져 있다는 관점으로 볼 수 있고 (루프 시작에서 K만큼 뒤쳐져 있는 것과 다른 표현. 그건 그냥 K만큼 뒤쳐져 있는 것), T는 H에게 한 번에 한 칸씩 따라잡히므로 LOOP_SIZE-K 단위시간 만큼 움직이면 둘은 만난다. 둘이 만나는 지점은 T의 움직임을 통해 계산해 볼 수 있는데, T는 루프의 시작점에서 출발해 한 번에 한 칸씩 움직이므로, LOOP_SIZE-K 단위 시간 이후에는 루프 시작지점으로부터 LOOP_SIZE-K 진행한 곳에 있을 것. 그곳을 달리 말하면 루프의 시작점으로 부터 K 만큼 뒤쳐져 있는 곳이 되고, K 만큼 뒤쳐져 있는 것은 k만큼 뒤쳐져 있는 것과 같다(뱅글뱅글 돌면 어차피 같은 곳).

스택과 큐

스택 : Last In First Out - 가장 최신의 정보를 반환
큐 : First In First Out - 들어온 순서대로 정보를 반환

면접 문제

3.2 스택의 각 원소를 노드로 관리하면 value 외의 meta data 도 저장해 둘 수 있다. 단, 이 경우엔 O(n)만큼의 추가 공간이 필요하게 된다. 공간 낭비가 너무 심할 경우 meta data가 스택 전체의 상태와 관련한 것이라면, 또 다른 스택을 추가로 관리하는 것이 더 효율적일 수 있다.

3.4 3.5 스택의 원소들을 하나씩 pop해서 다른 스택에 차례로 push 해두면 아래 두 가지가 가능하다.
1) push 해둔 스택에서 차례로 pop 을 하면 기존 데이터를 큐에서 꺼내쓰는 것과 같이 사용할 수 있다.
2) push 해둔 스택의 원소를 다시 차례로 pop해서 원래 스택에 push하면, 원래 스택 데이터의 순서를 유지할 수 있다.

3.6 큐를 단방향 연결리스트로 구현할 경우, 큐의 진행방향을 tail -> head 로 두어 tail에 넣고 head에서 꺼내써야 한다.
큐에서 꺼낸다는 것은 내 이전 노드의 next를 null로 바꾸면서 꺼낼 원소를 연결리스트에서 제외하는 것인데, 큐의 진행방향을 head -> tail 로 두어 head에 넣고 tail에서 꺼내쓰면 tail의 이전 노드에 접근할 수 없게 된다.

트리와 그래프

트리

노드로 이루어진 자료구조
하나의 루트 노드를 갖음
루트 노드는 0개 이상의 자식 노드를 갖음
그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의 됨
자식이 없는 노드는 말단 노드(leaf node)라고 부름
사이클은 존재할 수 없음
각 노드는 어떤 자료형으로도 표현 가능
각 노드는 부모 노드로의 연결이 있을 수도 없을 수도
Node 클래스를 포함하는 Tree 클래스는 보통 쓸모 없음

트리/그래프 문제는 보통 세부사항과 가정이 불분명하거나 부정확한 경우가 많음. 면접관에게 명확하게 해줄 것을 요구.

트리의 종류

[이진트리]
binary tree

모든 트리가 이진 트리는 아님. 삼진 트리(ternary tree)도 있음

[이진 탐색 트리]
binary search tree

"모든" 왼쪽 자식들 <= n < "모든" 오른쪽 자식들

의 속성을 만족하는 이진 트리.
바로 아래 자식 뿐만 아니라, 내 밑에 있는 "모든" 자식들에 대해서도 참이어야 함.

모든 이진 트리가 항상 이진 탐색 트리는 아니다. 헷갈리면 안됨

[균형 vs 비균형]

트리가 균형 잡혀 있다는 것이 무조건 왼쪽과 오른쪽 부분의 트리의 크기가 완전히 같다는 말은 아님.
O(logN) 시간에 삽입과 조회가 가능할 정도로만 균형 잡혀있으면 균형 트리라고 할 수 있음
대표적으로 레드-블랙 트리, AVL 트리 가 있음

[ 완전(complete) / 전(full) / 포화(perfect) ]

완전 이진트리 : complete binary tree
- 마지막 레벨을 제외한 트리의 모든 레벨에서 노드가 꽉차 있고
- 마지막 레벨은 왼쪽부터 채워져 있는 트리
전 이진트리 : full binary tree
- 자식이 하나만 있는 노드가 없는 트리
포화 이진트리 : perfect binary tree
- full 이면서 complete 인 트리
- 트리의 높이가 k일 때, 노드의 개수가 정확히 2^k - 1 인 트리

이진 트리 순회

중위 순회 : in-order

왼쪽 자식 , 현재 노드 , 오른쪽 자식

def go(node):
	if node is not None:
        go(node.left)
        print(node)
        go(node.right)

전위 순회 : pre-order

현재 노드를 가장 먼저

def go(node):
	if node is not None:
        print(node)
        go(node.left)
        go(node.right)

후위 순회 : post-order

현재 노드를 가장 마지막에

def go(node):
	if node is not None:
        go(node.left)
        go(node.right)
        print(node)

이진 힙 (최소힙/최대힙)

최소힙과 최대힙은 정렬의 방향만 다르고 본질은 같음. 여기선 최소힙만.
각 노드의 원소가 자식'들'의 원소보다 작다.
완전 이진 트리 (complete)
삽입
- 가장 밑바닥 오른쪽 위치에 삽입 후
- 최소 힙의 성질을 만족할 때까지 부모 원소와 교환해 나감
- 노드의 개수가 n일 때 O(logN)
최소값 추출
- 그냥 루트에 있는 값을 뽑으면 그게 최소값
- 빈 루트 자리에 가장 밑바닥 오른쪽에 위치한 원소를 꺼내서 넣고
- 최소 힙의 성질을 만족할 때까지 자식 원소"들"과 교환해 나감
- 왼쪽 자식과 오른쪽 자식 중 더 작은 자식과 교환해야 최소 힙의 성질 만족 가능
- 노드의 개수가 n일 때 O(logN)

트라이 (접두사 트리)

prefix tree. trie.
재밌는 자료구조.
면접에선 빈출. 보통 알고리즘 책에서는 소홀.

각 노드에 문자(character)를 저장하는 자료구조 (문자열X)
루트에서 아래쪽 끝까지 순회하면 단어 하나가 나옴
null node로 단어의 끝을 표현
ALPHABET_SIZE+1 개수까지의 자식을 가질 수 있음.
(null node 없이 node 내의 플래그로 단어끝을 표현하면 ALPHABET_SIZE 개수까지)

입력 문자열이 저장된 문자열의 '접두사' 인지 확인하는 데에 매우 유리.
(X문자열이 Y문자열의 접두사인지 -> Y문자열이 X문자열로 시작하는지)

저장된 문자열들이 트라이 자료구조 안에 저장되어 있다면, 입력된 문자열의 길이가 K일때 O(K) 시간에 입력된 문자열이 '유효한 접두사' 인지 (저장된 문자열 중 입력된 문자열을 접두사로 갖는 문자열이 있는지) 확인 가능.
해시테이블은 완결된 단어 단위로 대응시키기 때문에,
- 저장된 문자열들 중 입력된 문자열이 있는지는 O(K)에 확인할 수 있지만
- 저장된 문자열들 중 입력된 문자열을 접두사로 갖는 문자열은 확인할 수 없다.

해시테이블도 해싱을 할 때 입력 문자열을 한글자씩 읽기 때문에, K인 단어를 검색하는데 O(K) 시간이 걸림

저장된 문자열 모음(유효한 단어 집합) 을 이용하는 많은 문제를 트라이로 최적화할 수 있음
e.g. 서로 연관된 접두사를 반복적으로 검색해야 하는 상황 (M, MA, MAN, MANY 를 차례로 검색)에서 항상 루트에서 시작하는 것이 아니라, 현재 노드의 위치를 기억해 최적화 가능.

그래프

노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 것
트리는 '사이클이 없는' 하나의 '연결 그래프'
그래프는 여러개의 '고립된 부분그래프'(isolated subgraphs)로 구성될 수 있음
(어떤 두 정점에 대해 '경로'가 존재하지 않을 수도 있음)
모든 정점 쌍에 대해 '경로'가 존재하는 그래프를 '연결 그래프' 라고 함.
사이클이 없는 그래프를 '비순환 그래프' 라고 함.
사이클 : 시작점과 끝점이 같은 경로. 정점을 중복으로 방문하지 않고, 최소한 하나의 간선을 포함해야 함.

[인접 리스트 / 인접 행렬]
인접리스트

배열(혹은 해시테이블)의 각 원소를 각 정점에 대응시키되, 각 원소는 또 다른 배열/가변크기배열/연결리스트 로 구성하여 인접 정보를 저장.

인접 행렬

N*N boolean 행렬로 표현. matrix[i][j]가 true 이면 정점 i에서 정점 j로 간선이 있다는 뜻.
무방향 그래프를 인접행렬로 표현하면, 그 행렬은 대칭행렬(symmetric)이 된다.

[그래프 탐색]
DFS: depth-first search

임의의 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법
모든 노드를 방문하고자 할 때 선호됨
트리 순회는 DFS의 한 종류. 하지만 그래프 탐색에선 중복 방문 여부를 반드시 검사해야함.

void search(Node root) {
	if (root == null) return;
    
    visit(root);
    root.visited = true;
    
    for each (Node n in root.adjacent) {
    	if (n.visited == false) {
        	search(n);
        }
    }
}

BFS: breadth-first search

인접한 노드를 먼저 탐색하는 방식
두 노드 사이 최단 경로 혹은 임의의 경로를 찾고 싶을 때 선호됨
거리에 따라 단계별로 탐색한다고 볼 수 있음
큐(queue)를 사용해 구현

void search(Node root) {
	if (root == null) return;
    
    Queue queue = new Queue();
    root.marked = true;
	queue.enqueue(root);
    
    while (!queue.isEmpty()) {
    	Node r = queue.dequeue();
        visit(r)
        foreach (Node n in r.adjacent) {
        	if (n.marked == false) {
            	n.marked = true;	// enqueue 했다고 바로 방문하지 않기 때문에, 큐에 중복으로 들어가지 않도록 check 후 enqueue 한다.
                queue.enqueue(n);
            }
        }
    }
}

양방향 탐색: bidirectional search

출발지와 도착지 두 노드에서 동시에 BFS를 수행한 뒤, 두 탐색 지점이 충돌하는 경우에 경로를 찾는 방식
예시:
모든 노드가 적어도 k개의 이웃 노드와 연결되어 있고, s에서 t로의 최단 거리가 d가 되는 그래프가 있다고 하자.
- BFS
  최단 거리가 d라는 말은 d단계의 BFS가 필요하다는 뜻.
  맨 처음엔 k개의 노드를 탐색하고, 그 다음 단계에서는 그 k개의 노드가 또 각각 k개의 노드를 탐색해야함. 이것을 d번 반복.
  즉, 총 O(k^d)개의 노드를 탐색해야 함.
- 양방향 탐색
  s와 t의 중간지점까지 각각의 BFS가 진행될 것. 각 BFS가 대략 d/2 단계로 진행됨.
  그러면 각각의 BFS에서 방문하게 될 노드는 K^(d/2) 개이고, 두개의 BFS를 합쳐 총 2*K^(d/2) 즉 O(K^(d/2))
방문할 수 있는 노드의 개수가 한정적이라고 하면(시스템의 자원이 한정적이라면), 양방향 탐색이 BFS보다 2배 더 긴 경로까지 찾을 수 있다는 얘기.

면접 문제

4.2 배열을 잘라서 전달하지 말고, 원본 배열의 인덱스를 전달하면서 계산

4.3 이진트리에서는 '전위 순회(pre-order)'가 단계별 순회를 가능하게함

4.5 이진트리의 속성은 "현재 노드에서, 왼쪽의 모든 노드가 현재 노드보다 작거나 같고, 오른쪽의 모든 노드가 현재 노드보다 크다" 이다. 즉 서브트리들의 최대/최소 범위로 검사가 가능하다.

4.6 현재 노드가,

오른쪽 자식을 가지고 있다면, 오른쪽 자식의 가장 좌측 노드.

부모의 왼쪽 자식이었다면, 부모.

부모의 오른쪽 자식이었다면, 부모의 부모들 중 그들을 왼쪽 자식으로 가지는 가장 첫번째 노드.

4.7 위상정렬 (topological sort)
"어떤 그래프의 간선 (a,b)가 a를 위해서 b가 먼저 충족되어야 하는 조건을 나타낼 때, 노드를 선형 순서대로 나열하는 방법"

def topological_sort(nodes):
	stack = []
    for node in nodes:
    	if node.state == "BLANK":
        	if not complete_dfs(node, stack):
            	return False

    return stack[::-1]

def complete_dfs(node, stack):
	if node.state == "PARTIAL":
    	return False	# 사이클 감지
  
    if node.state == "BLANK":
    	node.state = "PARTIAL"
	    for child in node.children:
    		if not complete_dfs(child, stack):
            	return False
        node.state = "COMPLETE"
        stack.append(node)

    return True

개념과 알고리즘

비트 조작

비트 조작을 할 때 알아야 할 사실들과 트릭들

^(XOR) 연산은 연산자와 피연산자의 비트가 '다를 때' 참이 된다.
어떤 수를 왼쪽으로 n번 shift 하는 것은 2^n 을 곱하는 것과 같다.
~0을 하면 모든 비트가 1이 된다.
-1도 모든 비트가 1이다.
i 번째 비트만 1인 수에서 1을 빼면,
최상위 비트부터 i 번째 비트까지는 0이 되고, i-1 번째 비트와 그 하위 비트들이 전부 1이 된다.
알아두면 좋은 표현식
x ^ 0s = x
x ^ 1s = ~x
x ^ x = 0

2의 보수와 음수

보수(補數)는 보충을 해주는 수를 의미한다.
이를테면 1에 대한 10의 보수는 9, 4에 대한 15의 보수는 11의 개념이다. 1에 대한 2의 보수는 1이다.

자릿수가 8개(8비트) 일 경우 음의 정수 -6을 아래와 같이 1의 보수 방식과 2의 보수 방식으로 표현할 수 있다.

자리수가 8개(8비트) 일 경우, 표현할 수 있는 경우의 수는 256가지 이고, 0을 포함한다면 0부터 255까지의 정수를 표현할 수 있다.

음수란 무엇인가? 그 절대값(양수)과 자기자신(음수)을 더하면 0 이 되는 수이다.
즉 어떤 양수에 "어떤 수" 를 더해서 0이 나온다면, 그 "어떤 수"는 음수일 것이다.

그런데 지금과 같이 자리수(8개)가 정해져 있다면, 어떤 양수에 "어떤 수"를 더해서 256이 되어도 무방하다. 256은 9번째 자리만 1이고 나머지 8개 자리는 전부 0이기 때문에, 8개의 자리수가 표현할 수 있는 경우에 수에서는 0이라고 볼 수 있기 때문이다.

이때 아까 8개의 자리수에서 만들 수 있는 최대의 정수는 255라고 했다. 8자리에서 만들 수 있는 최대 정수는 당연하게도 8개 자리 모두 1이면 된다. 그리고 여기서 1을 더하면 256이 된다.

그렇다면 어떤 양수에 "어떤 수"를 더해 255를 만들 수 있으면, "어떤 수" + 1 로는 256을 만들 수 있게 된다.
즉 "어떤 수" + 1 이 우리가 찾던 음수가 되는 것이다.

그럼 일단 255를 만들어 보자. 255에서 양수를 빼면 "어떤 수"를 만들 수 있을 것이다.
255 즉, 8개 자리 모두 1인 이진수에서 양수를 빼면 되는데, 이를 직접 해보면 원래 양수의 모든 비트를 반전시킨 결과와 같음을 알 수 있다.

결국 양수의 비트를 모두 반전시키고, 1을 더한 것이 "어떤 수" + 1 즉 음수가 된다.
여기서 "어떤 수" 가 1의 보수, "어떤 수" + 1이 2의 보수라고 한다.

그런데 이진수는 하필이면 한 자리에 '두 가지'의 숫자만 올 수 있으므로, '두 가지' 로 표현되는 음/양 부호를 수 표현으로 대신 사용한다.
구체적으로는, 가장 상위 자리의 1 / 0이 음 / 양을 표현한다.
그리고 자리 1개가 줄었으므로, 표현 가능한 정수의 범위도 ~128 ~ 0 ~ 127 로 바뀐다. 단, 표현할 수 있는 경우의 수는 여전히 같다.

우측 시프트

우측 시프트는 최상위 비트가 항상 빈공간이 되는데 하필 이게 부호비트이다.
그래서, 아래와 같이 두가지 방법이 가능하다.

산술 : 기존 부호비트를 그대로 빈공간에 넣음 (>>)
논리 : 빈공간에 0을 넣음. (>>>)

기본적인 비트 조작

[비트값 확인] -> 켜져있는지 확인하는 것

1을 시프트해서 원하는 비트 위치만 1이 되도록 한 후에
&연산이 참인지 확인

[비트값 채워넣기] -> 해당 비트 1로 만들기

1을 시프트해서 원하는 비트 위치만 1로 만들고 ~연산을 그 위치만 0이 되도록 한 후에
&연산이 참인지 확인

[비트값 삭제하기] -> 해당 비트(들) 0으로 만들기

원하는 범위를 0으로 세팅한 mask를 만들고 &연산.

[비트값 바꾸기] -> 0또는 1로 바꾸기

원하는 범위를 0으로 바꾼 후에
OR 연산을 통해 원하는 비트를 넣어줌

면접 문제

5.6 어떤 정수 a의 '1비트'의 개수를 센다고 했을 때,

한 칸씩 오른쪽 시프트 하며, 최하위 비트를 검사
def check(a):	# a는 양수라고 하자. 음수이면 논리 시프트를 써야한다.
	count = 0
	while a != 0:
    	count += a & 1
        a >> 1
   
    return count
최하위 비트를 뒤집어 가며, a가 0이 되는데 얼마나 걸리는 지를 계산.
다시 말해, a가 0이 될 때 까지 a = a & (a - 1) 을 반복

최하위 비트가 1이면,
-1 했을 때 최하위 비트는 0이 되고, 기존 값과 & 하면 기존값의 그 1이 사라짐.

최하위 비트가 0이면,
-1 했을 때 가장 오른쪽에 있는 1이 0이 되고, 그 하위 비트들은 전부 1이 됨. 그리고 & 하면 기존값의 가장 오른쪽에 있던 1만 사라짐.
왜냐하면, 그 하위 비트는 전부 0이었기 때문.
def check(a)
	count = 0
	while a != 0:
    	a = a & (a - 1)

    return count

5.7 홀수 비트를 마스킹할 수 있는 수를 어떻게 만들까?
16진수를 사용하면 비트를 시각화한 것 처럼 수를 만들기 편하다.
예를 들어, 10101010(2) 는 0xAA 이다. 01010101(2) 는 0x55 이다. 11111111(2) 는 0xFF 이다.
16진수이기 때문에, 한 자리수에 4비트씩 차지하고 있다고 생각하면 된다. 그리고 그 4비트에 해당하는 숫자를 자릿수별로 쭉 나열하면 된다.

수학 및 논리 퍼즐

수수께끼 (brain teasers) 혹은 퍼즐.
논란의 여지가 많지만 어쨌든 출제될 수 있음.

소수

모든 자연수는 소수의 곱으로 나타낼 수 있다.

[가분성]
x를 y로 나눌 수 있으려면, y를 이루는 소수들은 x를 이루는 소수들의 부분집합이어야 한다.

x = 2^{j0} * 3^{j1} * 5^{j2} * 7^{j3} * 11^{j4} * \ldots

y = 2^{k0} * 3^{k1} * 5^{k2} * 7^{k3} * 11^{k4} * \ldots

여기서 $j_i <= k_i$ 를 만족해야 한다는 뜻.

그래서 최대공약수는 각 지수들의 최소값으로 표현될 수 있고 (한쪽이라도 0이면 0이 될 수 있음),

최대공약수: gcd(x, y) = 2^{\min(j_0, k_0)} * 3^{\min(j_1, k_1)} * 5^{\min(j_2, k_2)} * \ldots

최소공배수는 각 지수들 중 큰값을 취한다.
각각의 배수중에 가장 처음으로 같은 수이기 때문에 각각의 큰 지수와 작은 지수의 차이만큼 작은 지수를 가진 수에서 배수(곱해짐)이 되는 원리.

최소공배수: lcm(x, y) = 2^{\max(j_0, k_0)} * 3^{\max(j_1, k_1)} * 5^{\max(j_2, k_2)} * \ldots

그리고 그 둘을 곱한 결과는 공교롭게도 $x*y$ 와 같다.

gcd * lcm = 2^{\min(j_0, k_0) + \max(j_0, k_0)} * 3^{\min(j_1, k_1) + \max(j_1, k_1)} * \ldots \\ = 2^{j_0 + k_0} * 3^{j_1 + k_1} * \ldots = x * y

[소수 판별 (에라토스테네스의 체)]

어떤 수 n이 소수를 판별하는 가장 쉬운 방식은, 2부터 n-1 까지 돌면서 n이 나뉘어지는 경우가 있는지 확인하는 것.
좀더 똑똑하게는, $\sqrt{n}$ 까지만 돌면서 n이 나뉘어지는 경우가 있는지 확인하는 것.
그 이상으로 나뉘어지는 경우가 있다면, 이미 그 이전에서 확인이 되어야 했기 때문.

이것보다 더 똑똑한 사람 -> 에라토스테네스.

"소수가 아닌 수들은 반드시 다른 소수로 나누어진다."
1부터 max까지 수가 들어있는 리스트가 있을 때,
2로 나누어 떨어지는 수를 전부 지우고, 3으로 나누어 떨어지는 수를 전부 지우고, 5로, 7로 , ... .

단, 나누어 떨어지는 수를 지울 때, 자기 자신보다 크기가 낮은 배수를 적용할 필요는 없다.
이미 이전 소수에서 현재의 자기자신이 배수로 사용되었을 것이기 때문에.

def sieve_of_eratosthenes(int max):
    flags = [True for _ in range(max+1)]	# inclusive
    count = 0

    flags[0] = flags[1] = False
    prime = 2

    while prime <= math.sqrt(max):	# 우리가 소수인지 판별하고 싶은 수 중 가장 큰 수는 max.
        cross_off(flags, prime)
        prime = get_next_prime(flags, prime)	# 바로 다음에 있는 True 플래그 찾기

    return flags

def cross_off(flags, prime):
    i = prime	# 이전 소수에서 이미 지워진 값들은 건너 뜀. 즉, 1부터 시작하지 않음.
    x = i * prime

    while x < len(flags):
        flags[x] = False
        x += prime

리스트에 홀수만 넣으면 메모리 절반.

확률

👉 다트를 던졌을 때, 두 원의 공통된 부분에 들어갈 확률.

A에 떨어질 확률
A에서 A와B가 겹치는 부분의 비율

둘을 곱하면, 두 원의 공통된 부분에 들어갈 확률을 계산할 수 있다.

P(A \cap B) = P(B|A) \cdot P(A)

예를 들어, 1부터 10까지 수에서 하나를 뽑는다고 할 때, 5보다 작으면서 짝수를 뽑을 확률은
5보다 작은 수를 뽑을 확률과, 5보다 작으면서 짝수를 뽑을 확률을 곱해서 구할 수 있다.

P(A \cap B) = (2/5) * (1/2) = 1/5

한편,

P(A \cap B) = P(B|A) \cdot P(A) = P(A|B) \cdot P(B)

라고 할 수 있으므로, B에 속하면서 A에도 속할 확률은 다음과 같이 표현할 수도 있다.

P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)}

이를 베이즈 정리라고 부른다.

👉 다트를 던졌을 때, 두 원 중에서 하나에 떨어질 확률.

P(A \cup B) = P(A)+P(B)-P(A \cap B)

겹치는 부분이 두번 계산되므로 한 번은 빼주어야 한다.

예를 들어, 1부터 10까지 수에서 하나를 뽑는다고 할 때, 짝수를 뽑거나 1~5 중에서 뽑을 확률은
짝수를 뽑을 확률과 1~5 중에서 뽑을 확률을 더하고, 짝수이면서 1~5 중에서 뽑을 확률을 한 번 빼주면 구할 수 있다.

P(A \cup B) = (1/2) + (1/2) - (1/5) = 4/5

👉 독립 사건
한 사건의 발생 여부가 다른 사건에 아무런 영향을 미치지 않는 경우.

P(A|B) = P(A)\\

P(A \cap B) = P(A|B) \cdot P(B) = P(A) \cdot P(B)

👉 상호 배타성 (배반 사건)
한 사건이 일어난 경우 다른 사건은 발생할 수 없는 경우.

P(A \cap B) = 0

P(A \cup B) = P(A) + P(B)

둘은 동시에 만족할 수 없음.
왜냐하면 독립 사건은 한 사건의 발생 여부가 다른 사건에 영향을 끼치면 안되는데, 상호 배타성은 영향을 받는 경우(일어나면 안됨)이기 때문. 단, 두 사건 중 하나의 확률이라도 0이면 가능.

나름의 요령

입을 열라
- 사고의 과정을 말로 표현해보자.
규칙과 패턴을 찾으라
최악의 경우를 최소화 하라
- 초기에 어떤 결정을 통해 최악의 경우가 한쪽 방향으로 쏠리면, 그 결정을 다른 방식을 바꿔서 최악의 경우가 '균형 잡히도록' 하는 식.
알고리즘적 접근 법
- 초기사례 (base case)로부터의 확장, 실제 손으로 풀어보기 (DIY) 가 유용할 수 있음.

[면접 문제]

6.6 모든 사람들이 똑똑하고, 자신의 눈동자가 푸르다는걸 알면 그날 떠날 것이라는 가정이 있음.

6.7 정해진 가족의 수가 없기 때문에, 거의 무한한 개수의 가족들이 있다고 보면 됨.

객체 지향 설계

기술적 문제 / 실생활에 적용할 수 있는 객체를 직접 클래스 / 메소드로 구현
디자인 패턴보다는 객체 지향적('우아'하고 유지보수 가능한) 코드를 작성하는지를 중점적으로 평가

접근법

모호성 해소: 질문 던지기
- 객체 지향 설계 관련 문제들은 대부분 고의적으로 모호성을 띄고있음.
  -> 스스로 가정을 만들어내고, 질문을 통해 명확히 해나가는 과정을 평가하고자 하기 때문
- 질문을 해야함.
  e.g. 커피메이커에 대한 객체 지향 설계. 대규모 카페에서 사용되는 것인가, 컴팩트한 가정용인가?
핵심 객체의 설계
- 시스템에 들어갈 '핵심 객체(core object)'를 생각해본다.
- e.g. 식당에 대한 객체 지향적 설계
  Table, Guest, Party, Order, Meal, Employee, Server, Host
관계 분석
- 핵심 객체들 사이의 관계 분석
- 어떤 객체가 다른 객체의 member인지, 상속(inherit)관계가 필요한 객체가 있는지, many-to-many 인지 one-to-many 인지.
- e.g. 식당에 대한 객체 지향적 설계
  - Party 는 Guests 배열을 갖고 있어야 한다.
  - Server 와 Host는 Employee를 상속받는다.
  - Party는 여러개의 Table을 가질 수 있지만, Table은 하나의 Party만 가질 수 있다.
행동 분석
- 객체가 수행해야 하는 핵심 행동(core action)이 무엇일지를 생각해본다.
- e.g. 식당에 대한 객체 지향적 설계
  한 Party가 식당으로 입장하고, 한 Guest가 Host에게 Table을 부탁한다.
  Host는 Reservation을 살펴보고, 남은 자리가 있으면 해당 Party에게 그 Table을 배정할 것.
  남은 자리가 없다면, Reservation 대기 리스트 마지막에 해당 Party를 추가할 것.
  다른 Party가 식사를 마치고 떠나면, Reservation 대기 리스트에 맨 앞에 있는 Party에게 자리가 난 Table을 배정할 것.

디자인 패턴

보통 면접 범위 밖이지만, 알아두면 좋은 패턴들이 있음.
디자인 패턴에 관한 책을 하나 골라서 공부하는 것이 가장 좋은 방법.
단, 특정 문제에 '가장 적합한' 디자인 패턴을 '골라야'한다는 함정에 빠지진 말길.
이미 만들어진 패턴이 적합한 경우는 특별한 경우이고 보통은 직접 만들어서 써야한다.

싱글톤(singleton)
어떤 클래스가 오직 하나의 객체만을 갖도록하고, 프로그램에서 오직 그 객체만을 사용하도록 보장.
팩토리 패턴(factory pattern)
어떤 클래스의 객체를 생성하기 위한 인터페이스를 제공하되, 어떤 클래스를 생성할지를 하위 클래스에서 결정할 수 있도록 도와줌.
- 팩토리 메소드 패턴 :
  객체 생성을 할 수 있는 인터페이스(팩토리 메소드)를 직접적으로 구현한 객체 생성 클래스(팩토리)를 만든다.
- 추상 팩토리 패턴 :
  여러 팩토리가 구현하게 될, 상위의 추상(abstract) 클래스를 만든다. 즉 팩토리 클래스들을 추상화한 상위의 팩토리 클래스를 abstract로 선언한다.

재귀와 동적 프로그래밍

재귀와 관련된 문제의 패턴

해당 문제를 작은 크기의 문제들로 만들 수 있는가?
다음과 같은 문장으로 시작하는가?
- "n번째 ... 를 계산하는 알고리즘을 설계하라"
- "첫 n개를 나열하는 코드를 작성하라"
- "모든 ...를 계산하는 메서드를 구현하라"

접근법

재귀적 해법은, 부분 문제(subproblem)에 대한 해법을 통해 완성된다.

f(n-1)에 대한 해답에 더하거나/제거하거나/변경하여 f(n)을 계산해낸다.
혹은 데이터를 반으로 나눠 각각 문제를 풀고 이들을 병합(merge)하기도 함.

부분 문제로 나누는 방법 중 가장 흔한 세가지.

[bottom-up]
가장 직관적. 주로 순환적인 구현.
간단한 경우들에 대한 풀이법을 발견하는 것으로 시작.
이전에 풀었던 사례를 확장하여 다음 풀이를 찾는다.

[top-down]
덜 명확해서 복잡해 보일 수도. 주로 재귀적인 구현.
어떻게 하면 N에 대한 문제를 부분 문제로 나눌 수 있을지 생각.
나뉜 부분문제의 경우가 서로 겹치지 않도록 주의해야.

[half-and-half]
이진탐색이나 병합정렬이 사용하는 접근법.

recursive vs. iterative

재귀적 해법(recursive)은 공간 효율성이 나쁨.
재귀의 깊이가 n일 때, O(n)만큼의 공간을 스택에서 쓰게됨.

모든 재귀적 알고리즘은 순환적(iterative)으로 구현될 수 있음.
순환적인 구현은 공간 효율성이 더 좋지만 코드가 훨씬 복잡할 수 있음.

동적계획법 & 메모이제이션

많은 사람들이 무서워하지만, 한 번 감을 잡으면 쉽게 풀어낼 수 있다.

동적 프로그래밍은

재귀적 알고리즘 (혹은 순환적 형태)
반복적으로 호출되는 부분문제

를 찾아내고, 각 부분문제의 해답을 캐싱하면 된다.

다음과 같이 용어 구분을 하기도 한다.

top-down 동적 프로그래밍 : 메모이제이션

bottom-up 접근법 : 동적 프로그래밍

bottom-up은 주로 iterative한 구현이기 때문에 '메모'가 딱히 필요하지 않을 수도 있기 때문인듯. 하지만 책에서는 전부 '동적 프로그래밍'으로 부른다.

[피보나치 수열]
동적 프로그래밍에 대한 가장 간단한 예시.

💡 재귀

def fib(i):
	if i == 0: return 0
    if i == 1: return 1
    return fib(i-2) + fib(i-1)

수행시간은?
각 호출에 수행되는 시간은 O(1)이기 때문에, 호출트리 그려서 호출횟수를 계산해보면 됨.
높이가 n에 각 노드들이 대부분 두 개의 자식노드를 가지고 있음 -> O(2^n).
실제로는 오른쪽 부분트리의 크기가 왼쪽 부분트리의 크기보다 작음 -> O(1.6^n)

💡 하향식 동적 프로그래밍(메모이제이션)
위의 방식에는 중복 호출이 많다. 매번 fib(i)를 계산할 때 마다 캐싱하고 나중에 활용하면 된다.
그게 바로 메모이제이션.

def fib(i):
    memo = [0, 1]
    return fib_with_memo(i, memo)

def fib_with_memo(i, memo):
    if i < len(memo):
        return memo[i]
    
    a = fib_with_memo(i-2, memo)
    b = fib_with_memo(i-1, memo)
    memo.append(a + b)
    
    return memo[i]

수행시간은?
호출트리가 깊이 n까지 한쪽으로 거의 곧장 내려감. 각 노드의 자식노드는 두개 씩. -> O(N)

💡 상향식 동적 프로그래밍
재귀적인 메모이제이션으로 접근하되, 뒤집어서 구현한다고 생각.
초기 사례(base case)인 fib(0), fib(1)를 먼저 계산하고, 이를 이용해 차례로 fib(2), fib(3), ... 를 계산.

def fib(n):
	memo = []
    memo.append(0)	# fib(0)
    memo.append(1)	# fib(1)
    
    i = 2
    while i <= n:
    	a = memo[i-2]
        b = memo[i-1]
    	memo.append(a + b)	# fib(i)
    	n += 1
        
    return memo[i]

단, 현재 진행중인 인덱스에서 2이상 지난 값들을 더이상 활용하지 않으므로,
루프에 변수를 두고 사용해도 된다.

def fib(n):
    a = 0	# fib(0)
    b = 1	# fib(1)
    c = n
    
    i = 2
    while i <= n:
    	c = b + a	# fib(i)
        a = b
        b = c

    return c

면접 문제

8.1
위에서 언급된 재귀적 해법을 적용.
"f(n-1)에 대한 해답에 더하거나/제거하거나/변경하여 f(n)을 계산해낸다."

n번째 계단에 도달할 수 있는 경우는,

n-1번째 계단까지 도달한 후, 1계단 오른다

n-2번째 계단까지 도달한 후, 2계단 오른다

n-3번째 계단까지 도달한 후, 3계단 오른다

이를 top-down 접근법으로, 메모이제이션을 사용해 해결.
memo = [0 for _ in range(n+1)]
memo[0] = 1	# for memo[3]
memo[1] = 1
memo[2] = 2

def go(n, memo):
	if memo[n] != 0:
    	return memo[n]

    memo[n] = go(n-1, memo) + go(n-2, memo) + go(n-3, memo)
    return memo[n]
다만, 메모이제이션과 관계없이, n=37만 되어도 경우의 수가 int 자료형의 범위를 넘어선다. 면접에서 해결할 필요는 없는 문제이지만(자바에선 BigInteger같은 클래스를 사용해 해결), 이 문제점을 면접관에게 지적하면 점수를 얻을 수 있다.

8.2
마찬가지로 재귀적 해법. 더불어서,
"반복적으로 호출되는 부분문제를 찾아내고, 각 부분문제의 해답을 캐싱"

(r, c)로 가기 위해서는, (r-1, c)에서 아래로 한 칸 이동하거나, (r, c-1)에서 오른쪽으로 한 칸 이동하면 된다. 그런데 각 이전칸에서 다시 생각해보면 둘다 (r-1, c-1)에 대한 검사를 중복해서 진행한다. 이를 캐싱한다.
def get_path(maze, r, c, path, failed):
    if r < 0 or c < 0 or not maze[r][c]:
        return False
   	if (r,c) in failed:
    	return False
   
    if (r==0 and c==0) or \
            get_path(maze, r-1, c, path, failed) or \
            get_path(maze, r, c-1, path, failed):
        point = (r,c)
        path.append(point)
        return True
  
    failed.append((r,c))
    return False
여기서 보면 도달할 수 없는 지점만 저장해두고(failed), 도달할 수 있는 지점은 따로 저장하지 않는다. 이는 결국 지금 해답을 찾는 방식이 수많은 분기(가지치기)를 시도하면서 딱 하나만 성공시키는 것이기에 그렇다. 그 무수히 많은 분기 중에 하나가 어떤 특정 콜스택들에서 성공할 것이고, 그 과정에서 이미 실패했던 분기들만 다시 보지 않으면 된다는 점을 생각해보자.
백트래킹 기법을 참고.

8.3 half-and-half 접근법.
문제에는 없지만 각 원소들은 정수라는 가정. 거의 이분탐색과 흡사한 방법으로 해답을 찾으면 됨.

8.4 초기 사례로부터의 확장' 접근법.

먼저, 시간복잡도 계산을 위해 부분집합의 경우의 수 생각해보기.
부분집합을 만든다고 했을 때, 각 원소가 포함되거나/안되거나 인 경우가 원소의 개수만큼 곱해진다고 생각해볼 수 있다.
즉 n개의 원소를 가진 집합의 부분집합 개수는 {2*2*2*...} 를 n번 해야 하므로, 2^n 이다.
결국 모든 부분집합의 리스트를 반환해야 하므로, 모든 부분집합의 원소의 개수의 총합만큼은 걸릴 것이다.
이때, 하나의 원소는 모든 부분집합의 모음 중의 절반에는 속하게 된다. -> {1(속한경우)*2*2*...} + {1(안속한경우)*2*2*...}
다시 말해, 하나의 원소는 모든 부분집합의 모음에서 2^(n-1) 번만큼 그곳의 원소로 출현하게 된다.
결국 모든 부분집합의 모음의 총 원소의 개수는 n*2^(n-1) 가 되므로, 이것이 BCR(가능한 최선의 수행시간)이 된다.

이후엔 초기 사례로부터 확장법 적용.

8.5 half-and-half 접근법.

8.6 초기 사례로부터의 확장 접근법.

8.7 초기 사례로부터의 확장 접근법.

8.9 초기 사례로부터의 확장 접근법.
base case에서 확장하여 일반패턴을 도출하고, 중복을 제거한다.
하지만 약간 비효율적.

처음부터 그려나갈 수도 있다. 왼쪽 괄호와 오른쪽 괄호를 분기해가며 그리되, 각 괄호의 개수를 추적하며 그리고 괄호 문법에 어긋나지 않는지 확인하며 그리면 된다.

시스템 설계 및 규모 확장성

예상 외로, 가장 쉬운 종류의 문제
지원자가 실제 세계에서 어떻게 행동할지를 보기 위해 설계된 문제
실제로 일을 하듯이 문제를 풀어나가면 된다. 면접관을 참여시켜서 질문하고 토론하라.

문제를 다루는 방법

얼마나 최고의 설계를 하느냐 보다는 그 과정이 중요하게 평가됨.

소통 : 이 문제의 가장 큰 목적은 의사소통 능력 평가
포괄적 접근: 알고리즘으로 바로 뛰어들거나 특정 부분에 지나치게 파고들지 말 것.
화이트 보드 사용: 그림 그려가며 해결/설명
면접관의 지적: 인정하고 적절하게 수정하라.
명확한 가정: 가정을 할때는 명확하게 하고 면접관에게 공유한다.

시스템 설계

문제의 범위를 한정
- 내가 만들고자 하는 시스템과 면접관이 원하는 것이 같은지 반드시 확인
합리적인 가정을 생성
- 합당한 가정을 해야함.
  - 시스템이 하루에 100명의 사용자를 처리할 수 있으면 된다 / 메모리에 제약이 없다 -> 합당하지 못한 가정
  - 하루에 최대 백만 개의 요청을 처리하는 시스템 -> 합당한 가정
- 때로는 합당함의 기준이 만들고자 하는 제품에 대한 일반적인 '감(sense)'일수 있다.
중요한 부분을 먼저 그림
- 일단 화이트보드에 서서 시스템의 흐름을 처음부터 끝까지 그린다.
- 지금 단계에선 단순하고 명백하게 동작한다고 생각하고 그린다.
핵심 문제점 찾기
- 병목지점을 찾는다.
- 시스템이 주요하게 풀어야할 문제를 찾는다.
문제를 해결할 수 있도록 다시 설계

규모 확장을 위한 알고리즘

시스템 전체를 설계하라는 요청이 아닌,

시스템의 한 부분
알고리즘 (혹은 일반적인 설계 문제에서 '실제로' 중요한 알고리즘 부분)

을 설계해보라는 요청을 받았을 때, 규모 확장성에 신경 써야한다.

질문하라
- 문제를 제대로 이해하고, 세부사항을 명확히한다.
현실적 제약을 무시하라
- 일단은, 메모리 제약이 없고 컴퓨터 한 대에서 모든 데이터를 다 처리할 수 있다고 가정.
- 정답에 대한 윤곽을 그리는데 도움
현실로 돌아오라
- 현실에서 발생할 수 있는 문제점을 도출
- 예를 들어, 위의 경우 컴퓨터 한 대에 저장할 수 있는 데이터 크기는 얼마인지 / 데이터를 어떻게 나눠 저장할 것인지
문제를 풀어라
- 발견한 문제점들을 어떻게 해결할 것인지 생각.
- '순환적 접근법(iterative approach)': 문제 해결 -> 새로운 문제 발생 -> 다시 문제 해결 -> 반복...
- 자신의 답안에서 새로운 문제점을 만들어내는 것이, 문제를 분석하고 풀 수 있는 능력을 증명하는 가장 좋은 방법

시스템 설계의 핵심 개념

알아두면 좋을 지식. 매우 피상적이므로 인터넷을 통해 추가 공부할 것.

수평적 vs. 수직적 규모 확장
- 수직적 규모 확장 : 특정 노드의 자원의 양을 늘리는 방법
- 수평적 규모 확장 : 노드의 개수를 늘리는 방법
- 일반적으로 수직적이 수평적 보다 쉬움. 하지만 제한적(메모리 혹은 디스크 같은 것만 추가 가능).
로드 밸런서
- 여러 서버에 부하를 분산시키고, 하나의 서버 때문에 전체 시스템이 다운되는 상황을 방지.
데이터베이스 역정규화 & NoSQL
- 관계형 데이터베이스의 join 연산은 규모가 커질수록 굉장히 무거워짐.
- 역정규화는 join 연산을 피하기 위해 데이터베이스에 여분의 정보를 추가해 읽기 연산 속도를 향상시킨 것.
- NoSQL을 사용하면 비슷한 효과. join 연산 자체 지원이 안되어서 자료 저장시 조금 다른 방식으로 구성이됨.
데이터베이스 분할(샤딩)
- 데이터를 여러 컴퓨터에 나눠서 저장하는 동시에, 어떤 데이터가 어떤 컴퓨터에 저장되어 있는지 알 수 있는 방식
- 흔하게 사용되는 분할 방식들
  - 수직적 분할 : 자료의 특성별로 분할. e.g. 소셜네트워크를 만든다면 개인정보 관련 부분, 메시지 관련 부분, ... 으로 분할 가능. 특정 테이블의 크기가 너무 커질수도 있음.
  - 키/해시 기반 분할 : like 해시테이블. 해시 값 (또는 키)에 따라 해당 서버에 저장. 이 경우 서버의 개수가 사실정 고정되어 있어야 함.
  - 디렉터리 기반 분할 : 데이터를 찾을 때 사용할 조회 테이블(lookup table)을 유지하는 방법. 서버를 추가하기는 좋지만, 조회 테이블이 단일 장애 지점(single point of failure)가 될 수 있고, 지속적으로 조회테이블을 읽는 행위가 성능이슈 야기할 수도.
캐싱
비동기식 처리 & 큐
- 작업을 기다리지 않도록
- 비동기로 처리하거나, 큐에 넣어두고 끝나면 알림 주도록
네트워크 성능 척도
- 대역폭(bandwidth) : 단위 시간에 전송할 수 있는 데이터의 최대치. 최상의 조건을 가정.
- 처리량(throughput) : 단위 시간에 실제로 전송된 데이터의 양. 실제 상황을 가정.
- 지연 속도(latency) : 발송자가 데이터를 보낸 시점부터 수신자가 데이터를 받는 시점까지 걸린 시간
MapReduce (823p)
- 구글에서 만들어진 프로그램.
- 굉장히 커다란 데이터를 처리하는 데 사용됨.

시스템 설계 시 고려할 점

실패 : 시스템의 어떤 부분이든 실패 가능성 존재. 대비책 준비해야.
가용성(availability) 및 신뢰성(reliability) : 가용성은 사용 가능한 시스템의 시간을 백분율로 나타낸 것. 신뢰성은 특정 단위 시간에 시스템이 사용가능할 확률.
읽기 중심 vs. 쓰기 중심 : 읽기 연산이 많다면 캐시 사용을 고려. 쓰기 연산이 많다면 큐 사용을 고려.
보안

완벽한 시스템은 없다

말 그대로.
이런 문제를 받았을 때 우리가 해야할 일은

사례를 잘 이해하고
문제의 범위를 설정하고
합리적인 가정을 세운 뒤
명확하게 설계한 시스템을 만들기

설계한 시스템의 약점에 대해 열린 마음으로 받아들여야.

정렬과 탐색

널리 사용되는 정렬/탐색 알고리즘을 완벽히 이해하는 건 굉장히 가치있는 일.
상황에 맞는 알고리즘을 떠올릴 수 있어야.

널리 사용되는 정렬 알고리즘

[버블 정렬] | 평균 및 최악 실행시간: $O(n^2)$ , 메모리: $O(1)$
배열의 첫 원소부터 순차적으로, 현재 원소가 그다음 원소보다 크면 서로 바꾸는 작업을 반복. n-1번 비교, n-2번 비교, ... , 1번 비교.

[선택 정렬] | 평균 및 최악 실행시간: $O(n^2)$ , 메모리: $O(1)$
배열에서 가장 작은 원소를 계속해서 골라내 앞쪽부터 차곡차곡 쌓는 방법.

[병합 정렬] | 평균 및 최악 실행시간: $O(nlogn)$ , 메모리: $상황에 따라 다름$
배열을 절반씩 나누어 각각을 정렬한 다음, 이 둘을 합하여 다시 정렬하는 방법.
나눈 절반을 정렬할 때도 같은 알고리즘이 사용되고, base case 에는 한개짜리 배열 두개를 합하여 정렬하게 됨.
이 알고리즘에서는 '병합(merge)'를 처리하는 것이 가장 복잡.
기존 배열을 temp에 복사해 두고, 이 temp의 왼쪽 절반의 시작, 오른쪽 절반의 시작을 동시에 보면서 작은 순서대로 원래 배열에 차곡차곡 쌓아나간다. 두 쪽 중 한 쪽의 순회가 먼저 끝났을 때, 다른 쪽의 남은 부분을 원래 배열에 남김없이 복사해 넣는다. 이 때, 왼쪽의 순회가 먼저 끝났을 경우에는 오른쪽의 남은 부분을 복사해 넣을 필요가 없다. 해당 부분의 위치는 병합 시 원래 배열 상에서 덮어씌워지지 않았고, 남은 부분이 애초에 원래 배열에서 복사해왔기 때문이다.

[퀵 정렬] | 실행시간: 평균 $O(nlogn)$ , 최악 $O(n^2)$ . 메모리: $O(logn)$
무작위로 선정된 pivot에 따라, 그 보다 작은 원소들은 pivot 앞에 큰 원소들은 pivot 뒤로 보낸다. 그리고 그 pivot값의 위치를 기준으로 배열을 나누어 각각에서 다시 반복. pivot값이 중간에 가까운 값이 되리라는 보장이 없기 때문에, 최악의 경우 $O(n^2)$ 시간이 걸릴 수 있음.

[기수 정렬] | 평균 및 최악 실행시간: $O(kn)$ (k는 자릿수의 개수)
정수처럼 유한한 비트로 구성되어 있는 경우에 사용. 가장 낮은 자리수에서 시작해 가장 높은 자리수까지, 각 자리수를 순회하며 각 자리의 값에 따라 그룹을 만든다. 이 그룹들이 가지고 있는 순서가, 다음 자리수에서 정렬을 수행할 때 각 그룹 내의 정렬 순서를 결정한다. 예를 들어, 12 와 10 이 있으면 첫번째 자리수 그룹에서는 0그룹에 10이, 2그룹에 12가 속할 것이다. 두번째 자리수 그룹에서는 두개 다 1그룹에 속하게 되는데, 이 때 내부에서의 순서가 이전 자리수 그룹의 순서에 따라 정해진다. 0그룹에 속했던 10이 2그룹에 속했던 12보다 앞서게 된다. 이렇게 가장 큰 자리수까지 정렬을 완료하면 배열 전체에 대한 정렬이 완성된다.

탐색 알고리즘

[이진 탐색] | $O(logn)$
정렬된 배열에서 원소 x를 찾고자 할때 사용하는 방법. 중간에 위치한 원소에서 시작해서, x와의 대소비교에 따라 왼쪽/오른쪽 부분 중 한 부분만 같은방법으로 다시 살펴보는 것.

이진탐색에만 얽매이지 않도록 주의하자. 이진트리 혹은 해시테이블 통해 탐색할 수도 있다.

10.1

테스팅

테스팅 관련 질문들은 보통 네 가지 범주 중 하나에 속함

실생활에서 접하는 객체를 테스트
소프트웨어 하나를 테스트
주어진 함수에 대한 테스트 코드 작성
발생한 이슈에 대한 해결책 찾아내기 (디버깅)

면접관이 평가하는 것

큰 그림을 이해하고 있는가
- 소프트웨어가 지향하는 바를 잘 이해하고
- 그에 따라 테스트 케이스 간의 우선순위를 적절히 매길 수 있는가
퍼즐 조각을 제대로 맞추는 방법을 아는가
- 각 소프트웨어가 더 큰 생태계의 일부로서 어떻게 동작하는지를 이해하는가
- e.g. 구글 스프레드시트를 테스트한다고 하면, 기본 동작 뿐만 아니라 Gmail이나 다른 플러그인 등과 제대로 통합되는 지도 테스트
조직화
- 생각나는대로 아무 방법이나 이리저리 찔러보는 것이 아니라
- 구조적으로 접근하는가
- 잘 정리된 범주로 시스템을 나누고 테스트를 만들어 가는가
실용성
- 실제로 적용 가능한 합리적인 테스트 계획을 세울 수 있는가
- 실행 가능하고 실제로 구현 가능한, 그리고 실제로 사용에 도움이 되는 테스트를 만들 수 있는가

실제 세계의 객체 테스트

어떤 사용자가 어떤 목적으로 사용하게 될지 면접관과 논의
유스케이스(use case)를 도출
한계 조건(영구적 손상 혹은 약간의 손상이 가능한 사용) 확인
스트레스 조건(사소한 문제를 발생)과 장애 조건(기능에 극심한 장애 유발하지만 받아들일 수 있는) 확인
테스트를 어떻게 수행할 것인지

소프트웨어 테스팅

실제 세계 객체 테스트와 아주 유사
다만 성능 테스트(performance test)의 세부사항이 강조되는 경향이 있음
수작업 테스트 vs. 자동화된 테스트
- 이상적으로는 모두 자동화하면 좋겠지만 불가능
- 인간과 컴퓨터는 둘 다 테스트 프로세스의 핵심적 부분
블랙박스 테스트 vs. 화이트박스 테스트
- 화이트박스 테스트는 그 내부의 개별 함수들을 프로그램적으로 접근하여 테스트 가능
- 블랙박스 테스트도 자동화 가능은 하나 훨씬 어려움

접근법

블랙박스 테스트인지 화이트박스 테스트인지
- 되도록 일찍 질문하는 것이 좋음
누가 사용? 왜 사용? (큰 그림)
어떤 유스케이스?
- 유스케이스를 '마술적으로' 생각해내는 것이 아닌, 면접관과 상의하여 도출
한계 조건
스트레스 조건과 장애 조건
테스트 실행은 어떻게?
- 자동화는 좀 더 강력한 테스트를 가능하게 해주지만, 큰 문제를 일으킬 수도.
- 그래서 수작업 테스트 또한 테스트 절차에 포함되어야 한다.

함수 테스트

가장 쉬운 종류의 테스트.
그래도 면접관과 대화 중요.

접근법
e.g. 정렬 함수가 주어졌을 때,

테스트 케이스 정의
- 정상적인 케이스 : 전형적인 입력에 대해 정확한 출력을 내는가?
전형적이라고 해서 꼭 하나인 것은 아니다. 배열의 길이가 짝수일 때 홀수일 때 모두 전형적이라고 볼 수 있다.
- 극단적인 케이스 : 빈배열, 원소가 하나인 배열, 아주 작은/큰 크기의 배열
- null 입력, 잘못된(illegal) 입력 : 양수만 가능한데 음수 등.
- 특수한 입력 : 이미 정렬된 배열, 역순으로 정렬된 배열
예상되는 결과를 정의
- 예상되는 결과는 대체로 올바른 출력 결과를 의미
- 단, 이외의 확인하고 싶은 사항도 있을 수 있음. 예를 들어 원본 배열이 바뀌지 않았는지.
테스트 코드 작성

문제 해결에 관한 문제

소프트웨어를 재설치하라 -> 이런 소리 하면 안됨.

접근법
e.g. 구글 크롬이 실행하자마자 죽는다는 버그 리포트.

시나리오를 이해하라
- 상황을 가능한 한 정확하게 이해할 수 있도록 많은 질문을 던지기
  - 문제가 얼마나 지속되었나?
  - 브라우저 버전? 운영체제 버전?
  - 항상 발생하는가? 빈도는? 특정한 경우에만 발생?
  - 오류가 발생하면 오류리포트가 뜨는가?
문제를 쪼개라
- 다음과 같은 상황 전개 가능
  - Windows의 시작 메뉴로 간다
  - 크롬 아이콘을 클릭한다
  - 브라우저가 시작된다
  - 브라우저가 설정을 읽어 들인다
  - 브라우저가 홈페이지에 HTTP 요청을 날린다
  - 브라우저가 HTTP 응답을 받는다
  - 브라우저가 웹 페이지를 파싱한다
  - 브라우저가 웹 페이지를 화면에 표시한다
- 어떤 지점에서 어떤 문제가 발생했을까
구체적이고 관리 가능한 테스트들을 생성하라
- 상황 구성요소들 각각에 대한 현실적인 지시사항
- 사용자에게 뭘 해달라는 지시는 할 수도 없고 그들이 해주지도 않는다.

이강욱

I think I think too much.

이전 포스트

📕[책] Node.js 디자인 패턴 바이블

다음 포스트

📕[책] 컴퓨터 밑바닥의 비밀

2개의 댓글

봄

2023년 10월 23일

강욱시 강녕하신지요 .. 강욱시의 알고리즘 .. 기대 만땅입니다 .. 아좌좡~

1개의 답글