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와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구한다. 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재한다. 키와 값을 해당 인덱스에 저장한다. 반드시 연결리스트릴 이용한다. 충돌 : 서로 다른 두개의 키가 같은 해시 코드를 가리키거나 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우 ...