12일차 게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 3.3 ~ 3.6 내용 정리 9 면접 문제 3.3 접시 무더기 접시 무더기를 생각해보자. 접시를 너무 높이 쌓으면 무너져 내릴 것이다. 따라서 현실에서는 접시를 쌓다가 무더기가 어느 정도 높아지면 새로운 무더기를 만든다. 이것을 흉내 내는 자료구조 SetOfStacks를 구현해 보라. SetOfStacks는 여러 개의 스택으로 구성되어 있으며, 이전 스택이 지정된 용량을 초과하는 경우 새로운 스택을 생성해야 한다. SetOfStacks.push()와 SetOfStacks.pop()은 스택이 하나인 경우와 동일하게 동작해야 한다(다시 말해, pop()은 정확히 하나의 스택이 있을 때와 동일한 값을 반환해야 한다). ...
12일차 게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 p.144 ~ p.146, 3.1, 3.2 내용 정리 9 면접 문제 03 스택과 큐 스택 구현하기 스택 자료구조는 데이터를 쌓아 올린다(stack)는 의미이다. LIFO(Last-In-Fisrt-Out)에 따라 자료를 배열한다. 연산은 다음과 같다. pop(): 가장 위에 있는 항목을 제거한다. push(item): item 하나를 가장 윗 부분에 추가한다. peek(): 가장 위에 있는 항목을 반환한다. isEmpty(): 스택이 비어 있을 때에 true를 반환한다. 배열과 달리 상수 시간에 i번째 항목에 접근할 수 없다. 데이터를 추가하거나 삭제하는 연산은 상수시간에 가능하다. 재귀함수에서 많이 사용한다. 큐 구현하기 FIFO(First-In-First-Out) 순서를 따른다. 연산은 다음과 같다. add(item): item을 리스트의 끝부분에 추가한다. remove(): 리스트의 첫 번째 항목을 제거한다. peak(): 큐에서 가장 위에 있는 항목을 반환한다. isEmpty(): 큐가 비어 있을 때에 true를 반환한다. 큐를 연결리스트로 구현할 수 있다. BFS나 캐시를 구현할 떄 종종 사용한다. 면접 문제 3.1 한 개로 세 개 배열 한 개로 스택 세 개를 어떻게 구현할지 설명하라. ...
11일차 게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 2.3~ 2.8 내용 정리 9 면접 문제 2.3 중간 노드 삭제 단방향 연결리스트가 주어졌을 때 중간(정확히 가운데 노드일 필요는 없고 처음과 끝 노드만 아니면 된다)에 있는 노드 하나를 삭제하는 알고리즘을 구현하라. 단, 삭제할 노드에만 접근할 수 있다. 예제 입력 : 연결리스트 a->b->c->d->e 에서 노드 c 결과 : 아무것도 반환할 필요는 없지만, 결과로 연결리스트 a->b->d->e가 되어 있어야 한다. 답 : 예제에서 삭제할 노드인 c의 다음 노드 d를 복사해서 c에 붙여 넣는다. d(c였으나 복사하여서 d가 된)를 d(원래 d)의 다음 노드인 e에 연결한 후 d를 삭제한다. ...
10일차 게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 p.139 ~ p.141, 2.1, 2.2 내용 정리 9 면접 문제 02 연결리스트 연결리스트는 차례로 연결된 노드를 표현해주는 자료구조이다. 단방향 연결리스트에서 각 노드는 다음 노드를 가리킨다. 양방향 연결리스트에서 각 노드는 다음 노드와 이전 노드를 함께 가리킨다. 배열과는 달리 연결리스트에서는 특정 인덱스를 상수 시간에 접근할 수 없다. K번째 원소를 찾고 싶다면 처음부터 K번 루프를 돌아야 한다. 연결리스트의 장점은 리스트의 시작 지점에서 아이템을 추가하거나 삭제하는 연산을 상수 시간에 할 수 있다는 점이다. 연결리스트 만들기 LinkedList 자료구조를 사용할 수 있다. ...
9일차 게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 예제 1.4~1.9 내용 정리 9 면접 문제 1.4 회문 순열 주어진 문자열이 회문(palindrome)의 순열인지 아닌지 확인하는 함수를 작성하라. 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미하며, 순열이란 문자열을 재배치하는 것을 뜻한다. 회문이 꼭 사전에 등장하는 단어로 제한될 필요는 없다. 예제 입력 : Tact Coa 출력 : True (순열: “taco cat”, “atco cta” 등) 1 2 3 4 5 6 7 def main(s): arr = list(s) new_arr = set(arr) if 2*len(new_arr) - len(arr) <= 1: return True else: return False 1.5 하나 빼기 문자열을 편집하는 방법에는 세 가지 종류가 있다. 문자 삽입, 문자 삭제, 문자 교체. 문자열 두 개가 주어졌을 때, 문자열을 같게 만들기 위한 편집 횟수가 1회 이내인지 확인하는 함수를 작성하라. ...
8일차 게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 p.133 ~ p. 136, 예제 1.1~1.3 내용 정리 9 면접 문제 01 배열과 문자열 해시테이블 해시테이블(hash table)은 효율적인 탐색을 위한 자료구조 키(key)를 값(value)에 대응시킨다. 연결리스트(linked list)와 해시 코드 함수(hash code function)로 구현할 수 있다. 키와 값을 넣는 과정 키의 해시 코드를 계산한다. 키의 자료형은 보통 int 혹은 long. hash(key) % array_length와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구한다. 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재한다. 키와 값을 해당 인덱스에 저장한다. 반드시 연결리스트릴 이용한다. 충돌 : 서로 다른 두개의 키가 같은 해시 코드를 가리키거나 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우 ...
7일차 게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 p.108 ~ p. 130 내용 정리 7. 기술적 문제 가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)) BCR이 무엇일까 생각해 보는 것으로도 문제를 푸는데 유용한 힌트를 발견할 수 있다. 가능한 최선의 수행시간(Best Conceivable Runtime): 상상할 수 있는 모든 해법 중 가장 빠른 알고리즘의 수행 시간을 의미 최선의 경우의 수행 시간(Best Case Runtime): 특정 알고리즘이 가장 빠르게 동작할 경우의 수행 시간을 의미 따라서 둘은 아무 관계가 없다. ...
6일차 게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 p.89 ~ p. 108 내용 정리 7. 기술적 문제 최고의 테크 회사들은 면접의 기초로 기술적 문제들을 삼는다. 준비하기 직접 풀도록 노력하라 : 직접 답을 찾도록 노력하고 포기하지 말자 코드를 종이에 적으라 : 코드 문법 강조, 코드 자동 완성 없는 것에 익숙해져보자. 코드를 테스트하라 : 종이에서 해야한다. 종이에 적은 코드를 그대로 컴퓨터로 옮긴 뒤 실제로 실행해 보라 : 어디에서 실수가 있었는지 체크하고 유의하자. 가상 면접 경험도 중요하다. ...
5일차 게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 p.59 ~ p. 70 내용 정리 6. big-O big-O 시간은 알고리즘의 효율성을 나타내는 지표 혹은 언어이다. 비유하기 파일을 보낼 때 크기가 작다면 전송하는게 빠르지만 굉장히 크다면 물리적으로 직접 가는게 빠를것.(1테라를 미국에 메일로 보내느니 들고 비행기타고 가는게 낫다!) 시간 복잡도 점근적 실행 시간(asymptotic runtime), 또는 big-O 시간에 대한 개념에 대해 얘기해보자. 데이터 전송 ‘알고리즘’의 실행 시간에서 온라인 전송: O(s), s가 파일의 크기이다. 파일의 크기가 증가함에 따라 전송 시간 또한 선형적으로 증가 비행기 전송: O(1), 파일 크기랑 상관없다. 크든 작든 비행기 한대 가는 시간이니까! O(s)가 커지다 보면 어느 순간 O(1)보다 커지게 된다. O(1)이 얼마든, O(s)가 얼마나 천천히 커지든 언젠가는 무조건! ...
4일차 게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 p.39 ~ p. 58 내용 정리 4. 면접 전에 적절한 경험 쌓기 탄탄한 이력서를 위해 필요하다. 큰 규모의 프로젝트 수업 듣기 인턴 자리 알아보기 무언가 하기 : 개인 프로젝트, 해커톤, 오픈 소스 프로젝트 등 탄탄한 이력서 작성하기 적절한 이력서 길이 너무 길지 않게, 인상적인 항목만 적어 주의를 산만하지 않게 한다. 우선순위를 매겨라. 고용 이력 관련된 고용 이력만 나열하자. 무엇을 구현해서 무엇을 성취했고 무엇을 이루었는지 구체적으로 쓰자. ...