메모 8. 재귀와 동적 프로그래밍 재귀 관련 문제는 상당수가 패턴이 비슷함. 주어진 문제가 재귀 문제인지 확인해 보는 좋은 방법은 해당 문제를 작은 크기의 문제로 만들 수 있는지 보는 것임. 다음과 같은 문장으로 시작하는 문제는 재귀로 풀기 적당한 문제일 가능성이 높음. “n번째 … 를 계산하는 알고리즘을 설계하라” “첫 n개를 나열하는 코드를 작성하라.” “모든 … 를 계산하는 메서드를 구현하라.” 사람들이 직감적으로 이 문제가 재귀 문제 같다! 라고 했을 때, 실제로 그문제가 재귀 문제인 경우는 보통 50% 정도였음. 따라서, 재귀로 문제가 풀릴것 같더라도, 다른 방식으로 생각해보는 것을 게을리하면 안됨. 접근법 재귀적 해법 → 부분문제(subproblem)에 대한 해법을 통해 완성됨. ex) f(n..
메모 면접 문제 7.6 직소 N X N 크기의 직소(jigsaw) 퍼즐을 구현하라. 자료구조를 설계하고, 퍼즐을 푸는 알고리즘을 설명하라. 두 조각의 퍼즐 모서리가 주어졌을 때 그들이 들어맞는지 아닌지 알려주는 fitsWith 메서드는 제공된다. 7.7 채팅 서버 채팅 서버를 어떻게 구현할 것인지 설명하라. 특히, 다양한 백엔드 컴포넌트, 클래스, 메서드에 대해 자세히 설명하라. 어떤 문제가 가장 풀기 어려울 것으로 예상되는가? 7.8 오셀로 오셀로(Othello) 게임 규칙은 이러하다. 오셀로 말의 한쪽 면은 흰색, 반대 면은 검은색으로 칠해져 있다. 상대편 말에게 왼쪽과 오른쪽, 또는 위와 아래가 포위된 말은 색상을 뒤집어 상대편 말이 된 것으로 표시한다. 여러분은 여러분 차례에서 적어도 상대편 말 ..
메모 7. 객체 지향 설계 디자인 패턴들을 쏟아내도록 요구하는 것이 아님. 우아하고, 유지보수가 가능한 객체 지향적 코드를 만드는 방법을 이해하고 있는지 살펴보기 위한 것임. 이 문제들에서 낮은 성적을 받으면, 합격 전선에 빨간불이 켜질 수 있음. 접근법 객체 지향 설계에 관한 질문들은 거의 비슷한 방식으로 공략 가능함. 단계 #1: 모호성의 해소 면접관들은 여러분이 스스로 가정을 만들어내고 질문을 통해 명확히 해나가는 과정을 살펴보고 싶어하기 때문에 대부분의 문제들이 고의적으로 모호성을 띔. 객체 지향 설계에 관한 질문을 받으면 누가 그것을 사용할 것이며, 어떻게 사용할 것인지에 대한 질문을 던져야 함. 질문에 따라 육하원칙에 따른 질문을 던져야할 수도 있음. 상황에 따라 설계 자체가 완전히 뒤바뀌기 ..
메모 면접 문제 6.3 도미노 8x8 크기의 체스판이 있는데, 대각선 반대 방향 끝에 있는 셀(cell) 두 개가 떨어져 나갔다. 하나의 도미노로 정확히 두 개의 정사각형을 덮을 수 있을 때, 31개의 도미노로 보드 전체를 덮을 수 있겠는가? 여러분의 답이 옳다는 것을 증명하라(예를 들거나, 왜 불가능한지를 보이면 된다). 6.4 삼각형 위의 개미 개미 세 마리가 삼각형의 각 꼭짓점에 있다. 개미 세 마리가 삼각형 모서리를 따라 걷기 시작했을 때, 두 마리 혹은 세 마리 전부가 충돌할 확률은 얼마인가? 각 개미는 자신이 움직일 방향을 임의로 선택할 수 있는데, 같은 확률로 두 방향 중 하나를 선택한다. 또한 그들은 같은 속도로 걷는다. 이 문제를 확장해서 n개의 개미가 n각형 위에 있을 때 그들이 충돌할..
메모 소수 모든 자연수는 소수의 곱으로 나타낼 수 있는 규칙이 있음. 가분성(divisibility) 소수판별 어떤 소수 n이 소수인지 여부를 판단하는 방법 boolean primeNaive(int n) { if (n < 2) { return false; } for (int i = 2; i < n; i++) { if (n % i == 0) { return false; } } return true; } 가장 단순한 방법은 2에서 n-1까지 루프를 돌면서 나누어지는 경우가 있는지 확인하는 것임. 위 코드를 살짝 개선해 보면, 루프를 n이 아닌 n의 제곱근까지만 돌면 됨. boolean primeSlightlyBetter(int n) { if (n < 2) { return false; } int sqrt = ..
메모 면접 문제 5.4 다음 숫자 양의 정수가 하나 주어졌다. 이 숫자를 2진수로 표기했을 때 1비트의 개수가 같은 숫자 중에서 가장 작은 수와 가장 큰 수를 구하라. 5.5 디버거 다음 코드가 하는 일을 설명하라. ((n & (n - 1)) == 0 5.6 변환 정수 A와 B를 2진수로 표현했을 때, A를 B로 바꾸기 위해 뒤집어야 하는 비트의 개수를 구하는 함수를 작성하라. 5.7 쌍끼리 맞바꾸기 명령어를 가능한 한 적게 사용해서 주어진 정수의 짝수 번째 비트의 값과 홀수 번째 비트의 값을 바꾸는 프로그램을 작성하라(예: 0번째 비트와 1번째 비트를 바꾸고, 2번째 비트와 3번째 비트를 바꾸는 식으로). 5.8 선 그리기 흑백 모니터 화면은 하나의 바이트 배열에 저장되는데, 인접한 픽셀 여덟 개를 한..
메모 05. 비트조작 코드를 최적화할 때 융요하게 사용되는 기법으로 활용됨. 코드를 작성하는 것 뿐만 아니라 손으로도 그릴수 있도록 익숙해지는 것이 좋음. 손으로 비트 조작 해보기 세번째 열 트릭은 다음과 같음. 0110 + 0110 = 0110 * 2 와 같음. 따라서 0110 을 왼쪽으로 한 번 시프트 한 것과 같음. 0100은 4와 갓고, 4를 곱하는 것은 왼쪽으로 두 번 시프트하는 것과 같음. 따라서 0011을 왼쪽으로 두 번 시프트하면 1100이 됨. 어떤 비트와 그 비트를 부정한 값을 XOR 하면 항상 1이 됨. 따라서 a^(~a) 를 하면 모든 비트가 1이 됨. ~0을 하면 모든 비트가 1이 됨. 따라서 ~0
메모 면접 문제 4.7 순서 정하기 프로젝트의 리스트와 프로젝트들 간의 종속 관계(즉, 프로젝트 쌍이 리스트로 주어지면 각 프로젝트 쌍에서 두 번째 프로젝트가 첫 번째 프로젝트에 종속되어 있다는 뜻)가 주어졌을 때, 프로젝트를 수행해 나가는 순서를 찾으라. 유효한 순서가 존재하지 않으면 에러를 반환한다. 4.8 첫 번째 공통 조상 이진 트리에서 노드 두 개가 주어졌을 때 이 두 노드의 첫 번째 공통 조상을 찾는 알고리즘을 설계하고 그 코드를 작성하라. 자료구조내에 추가로 노드를 저장해 두면 안 된다. 반드시 이진 탐색 트리일 필요는 없다. 4.9 BST 수열 배열의 원소를 왼쪽에서부터 차례로 트리에 삽임함으로써 이진 탐색 트리를 생성할 수 있다. 이진 탐색 트리 안에서 원소가 중복되지 않는다고 할 때, ..
메모 면접 문제 4.1 노드 사이의 경로 방향 그래프가 주어졌을 때 두 노드 사이에 경로가 존재하는지 확인하는 알고리즘을 작성하라. 4.2 최소 트리 오름차순으로 정렬된 배열이 있따. 이 배열 안에 들어 있는 원소는 정수이며 중복된 값이 없다고 했을 때 높이가 최소가 되는 이진 탐색 트리를 만드는 알고리즘을 작성하라. 4.3 깊이의 리스트 이진 트리가 주어졌을 때 같은 깊이에 있는 노드를 연결리스트로 연결해 주는 알고리즘을 설계하라. 즉, 트리의 깊이가 D라면 D개의 연결리스트를 만들어야 한다. 4.4 균형 확인 이진 트리가 균형 잡혀있는지 확인하는 함수를 작성하라. 이 문제에서 균형 잡힌 트리란 모든 노드에 대해서 왼쪽 부분 트리의 높이와 오른쪽 부분 트리의 높이의 차이가 최대 하나인 트리를 의미한다...
메모 그래프 트리는 그래프의 한 종류임. 모든 그래프가 트리는 아님. 트리는 사이클이 없는 하나의 연결 그래프임. 그래프는 노드와 그 노드를 연결하는 간선을 하나로 모아놓은 것임. 그래프에는 방향성이 있을 수도 있고 없을 수도 있음. 그래프에는 여러 개의 고립된 부분 그래프(isolated subgraphs)로 구성될 수 있음. 모든 정점 쌍간에 경로가 존재하는 그래프는 ‘연결 그래프’라고 부름. 그래프에는 사이클이 존재할 수도 있고, 존재하지 않을 수도 있음. 사이클이 없는 그래프는 ‘비순환 그래프’(acyclic graph) 라고 부름. 프로그래밍으로 그래프를 표현할 때 일반적으로 다음 두 가지 방법을 사용함. 인접 리스트 (adjacency list) 그래프를 표현하는 가장 일반적인 방법 모든 정점..
메모 04 트리와 그래프 트리에서 탐색(search) 하는 것은 배열이나 연결리스트처럼 선형으로 구성된 자료구조에서 탐색하는 것보다 훨씬 까다로움. 최악의 수행 시간과 평균적 수행 시간이 매우 크게 바뀔 수 있어서, 알고리즘을 살펴볼 때, 두 가지 측면 모두를 반드시 따져봐야 함. 트리와 그래프를 밑바닥부터 능숙하게 구현할 수 있는 능력을 갖추면 분명히 도움이 될 것임. 트리의 종류 트리를 이해하기 가장 좋은 방법은 재귀적 설명법을 사용하는 것임. 트리는 노드로 이루어진 자료구조임. 트리는 하나의 루트 노드를 갖는다. 루트 노드는 0개 이상의 자식 노드를 갖고 있다. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의됨. 트리에는 사이클이 존재할 수 없음. 노드들은 특정 순서로..
메모 면접 문제 3.3 접시 무더기 접시 무더기를 생각해 보자. 접시를 너무 높이 쌓으면 무너져 내릴 것이다. 따라서 현실에서는 접시를 쌓다가 무더기가 어느 정도 높아지면 새로운 무더기를 만든다. 이것을 흉내 내는 자료구조 SetOfStacks를 구현해 보라. SetOfStacks는 여러 개의 스택으로 구성되어 있으며, 이전 스택이 지정된 용량을 초과하는 경우 새로운 스택을 생성해야 한다. SetOfStacks.push()와 SetOfStacks.pop()은 스택이 하나인 경우와 동일하게 동작해야 한다(다시 말해, pop()은 정확히 하나의 스택이 있을 때와 동일한 값을 반환해야 한다). 힌트 각 부분 스택의 크기를 알고 있어야 한다. 스택이 꽉 차면 새로운 스택을 만들어야 한다. 특정 부분 스택엑서 원..