(답은 귀찮아서 해답지 안보고 내 생각을 쓴건데 아마 맞을거임 ㅎㅎ)


1. 이진트리가 균형이 맞는지 알아내는 코드를 작성하라. 균형이 맞는 다는 것은 아무 노드나 선택했을 때 그 노드의 두 서브트리의 높이 차가 1보다 크면 안된다.


넓이 우선으로 현재 노드들과 다음 노드들을 재귀나 반복으로 구한 후, 다음 노드들의 갯수가 현재 노드들 갯수의 2배 이하가 되는 순간 한번 더 다음 다음 노드들의 존재 여부를 보면 됨.




2. 푸시, 팝, 최소값 이 세개의 연산을 지원하는 하나의 스택 알고리듬을 만들어라. 즉, 스택에 대해 언제든 push, pop, min 을 할 수 있어야 하고 시간복잡도는 O(1)이 되도록 하라


푸시 할때 값 a를 푸시하지 않과 [a, min(a, prev-min)] 을 푸시하고 팝은 [a, min] 중 a만 리턴하게 하면 됨




3. 싱글 링크드 리스트에서제 뒤로부터 N번째 노드 값을 구하는 알고리듬을 만들어라


간격이 N인 두개의 포인터를 동시에 움직이면서 앞선 포인터가 리스트 끝이 되는 순간 따라오는 포인터의 노드 값을 리턴하면 됨



4. 싱글 링크드 리스트 중간 아무 노드나 주어졌을 때 그 노드를 제거하는 알고리듬을 만들어라. 예) a->b->c->d->e 에서 c 제거: a->b->d->e


c가 가르키는 d의 값을 복사하여 c를 d로 업데이트 하고 d는 없애 버리면 됨


---------------------------------


1. 20개의 병 중 19개에 1그램의 무게가 들어있고, 1개에는 1.1 그램 무게가 들어있다. 정확한 값을 계측할 수 있는 저울을 단 한번만 사용하여 무거운 병을 찾는 방법은?

(이게 뭐지? 이건 아이디어가 안떠오르네 출근하면서 생각해 봐야될 듯)


2. (이건 길어서 번역하기 귀찮아서 복붙 ㅎㅎ)

You are given two 32-bit numbers, N and M, and two bit positions, land j. Write

a method to insert M into N such that M starts at bit j and ends at bit i. You can

assume that the bits j through i have enough space to fit all of M. That is, if

M = 10011, you can assume that there are at least 5 bits between j and i. You

would not, for example, have j = 3 and i = 2, because M could not fully fit

between bit 3 and bit 2.

EXAMPLE

Input: N = 10000000000, M = 10011, i = 2, j = 6

Output: N = 10001001100


3. n개의 계단을 계단 1개씩, 2개씩, 3개씩 올라갈 수 있다고 할때, 끝까지 오르는 모든 가능한 경우의 수는?


4. 카지노에서 쓰는 일반적 카드의 자료구조를 설계하고 블랙잭용으로 어떻게 확장할 수 있는지 보일것



포봄 및 취업 희망 게이들 오늘도 애써라. 형은 이만 화장실에 볼일보러 감