17. 어려운 연습문제 17.1 덧셈 없이 더하기 두 수를 더하는 함수를 작성하라. 단, +를 비롯한 어떤 연산자도 사용할 수 없다. 17.2 섞기 카드 한 벌을 ‘완벽히’ 섞는 메서드를 작성하라. 여기서 ‘완벽’의 의미는, 카드 한 벌을 섞는 방법이 52!가지가 있는데 이 각각이 전부 같은 확률로 나타날 수 있어야 한다는 뜻이다. 단, ‘완벽한’ 난수 생성기(random number generator)는 주어져 있다고 가정해도 좋다.
16. 중간 난이도 연습문제 16.23 Rand5로부터 Rand7 rand5()를 사용해서 rand7() 메서드를 구현하라. 즉, 0부터 4까지 숫자 중에서 임의의 숫자를 반환하는 메서드를 이용해서 0부터 6까지의 숫자 중에서 임의의 숫자를 반환하는 메서드를 작성하라. 16.24 합이 되는 쌍 정수형 배열이 주어졌을 때, 두 원소의 합이 특정 값이 되는 모든 원소 쌍을 출력하는 알고리즘을 설계하라. 16.25 LRU 캐시 가장 오래된 아이템을 제거하는 ‘최저 사용 빈도(least recently used)’ 캐시를 설계하고 구현하라. 캐시는 특정 키와 연관된 값을 입력하거나 읽어 들일 수 있어야 하며 그 크기는 최대로 초기화되어 있다. 캐시가 꽉차면 가장 오래된 아이템을 제거하고 새 아이템을 입력해야 한..
16. 중간 난이도 연습문제 16.20 T9 과거의 핸드폰에서는 문자 입력을 돕기 위해 각 숫자에 0~4개의 알파벳을 대응시켰다. 이에 따라 어떤 수열이 주어지면 그 수열에 대응되는 단어 리스트를 만들 수 있었다. 유효한 단어 리스트(여러분이 원하는 방식으로 자료구조가 주어진다)와 어떤 수열이 주어졌을 때, 해당 수열에 매핑되는 단어 리스트를 출력하는 알고리즘을 작성하라. 각 숫자에 대응되는 알파벳은 다음과 같다. 1 2 (abc) 3 (def) 4 (ghi) 5 (jkl) 6 (mno) 7 (pqrs) 8 (tuv) 9 (wxyz) 0 16.21 합의 교환 정수형 배열 두 개가 주어졌을 떄, 각 배열에서 원소를 하나씩 교환해서 두 배열의 합이 같아지게 만들라. 16.22 랭턴 개미 검은색과 하얀색 셀(..
16. 중간 난이도 연습문제 16.16 부분 정렬 정수 배열이 주어졌을 떄, m부터 n까지의 원소를 정렬하기만 하면 배열 전체가 정렬되는 인덱스 m과 n을 찾으라. 단, n - m을 최소화하라 (다시 말해, 그런 순열 중 가장 짧은 것을 찾으면 된다). 16.17 연속 수열 정수 배열이 주어졌을 때 연속한 합이 가장 큰 수열을 찾고 그 합을 반환하라. 16.18 패턴 매칭 패턴 문자열과 일반 문자열 두 개가 주어져있다. a와 b로 이루어진 패턴 문자열은 일반 문자열을 표ㅕ현하는 역할을 한다. 예를 들어 catcatgocatgo는 aabab 패턴과 일치한다(여기서 a는 cat이 되고, b는 go가 된다). 이 문자열은 a, ab, b 패턴과도 일치한다. 일반 문자열이 패턴 문자열과 일치하는지 판단하는 메서..
16. 중간 난이도 연습문제 16.13 정사각형 절반으로 나누기 2차원 평면 위에 정사각형 두 개가 주어졌을 떄, 이들을 절반으로 가르는 직선 하나를 찾으라. 정사각형은 x축에 평행하다고 가정해도 좋다. 16.14 최고의 직선 2차원 평면 위에 점이 여러 개 찍혀 있을 때 가장 많은 수의 점을 동시에 지나는 직선을 구하라 16.15 Master Mind Master Mind 게임의 룰은 다음과 같다. 빨간색(R), 노란색(Y), 초록색(G), 파란색(B) 공이 네 개의 구멍에 하나씩 들어 있다. 예를 들어 RGGB는 각 구멍에 차례대로 빨간색, 초록색, 초록색, 파란색 공이 들어 있다는 뜻이다. 여러분은 공의 색깔을 차례대로 맞춰야 한다. 구멍에 들어 있는 공의 색깔을 정확히 맞췄다면 ‘히트’를 얻게 되..
16. 중간 난이도 연습문제 16.10 살아 있는 사람 사람의 태어난 연도와 사망한 연도가 리스트로 주어졌을 때, 가장 많은 사람이 동시에 살았던 연도를 찾는 메서드를 작성하라. 모든 사람이 1900년도에서 2000년도에 살아 있었다고 봐야 한다. 예를들어 어떤 사람이 1908년에 태어나서 1909년에 사망했다면 이 사람은 1908년과 1909년 모두에 삶을 살았던 사람이 된다. 16.11 다이빙 보드 다량의 널빤지를 이어 붙여서 다이빙 보드를 만들려고 한다. 널빤지는 길이가 긴 것과 짧은 것 두 가지 종류가 있는데, 정확히 K개의 널빤지를 사용해서 다이빙 보드를 만들어야 한다. 가능한 다이빙 보드의 길이를 모두 구하는 메서드를 작성하라. 16.12 XML 인코딩 XML은 너무 장황하게 표현된 경우가 많..
16. 중간 난이도 연습문제 16.7 최대 숫자 주어진 두 수의 최댓값을 찾는 메서드를 작성하라. 단, if-else나 비교 연산자는 사용할 수 없다. 16.8 정수를 영어로 정수가 주어졌을 때 이 숫자를 영어 구문으로 표현해주는 프로그램을 작성하라. 예를 들어 1,000이 입력되면 ‘One Thousand’, 234가 입력되면 ‘Two Hundred Thirty Four’를 출력한다. 16.9 연산자 덧셈 연산자만을 사용하여 정수에 대한 곱셈, 뺄셈, 나눗셈 연산을 수행하는 메서드를 작성하라. 연산에 대한 결과는 항상 정수가 되어야 한다.
16. 중간 난이도 연습문제 16.4 틱-택-토의 승자 틱-택-토(tic-tac-toe) 게임의 승자를 알아내는 알고리즘을 설계하라. 16.5 계승(factorial)의 0 n!의 계싼 결과에서 마지막에 붙은 연속된 0의 개수를 계산하는 알고리즘을 작성하라. 16.6 최소의 차이 두 개의 정수 배열이 주어져 있다. 각 배열에서 숫자를 하나씩 선택했을 때 두 숫자의 차이(절댓값)가 최소인 값을 출력하라.
16. 중간 난이도 연습문제 16.1 숫자 교환 임시 변수를 사용하지 않고 숫자를 교환(swap)하는 함수를 작성하라. 16.2 단어 출현 빈도 어떤 책에 나타난 단어의 출현 빈도를 계싼하는 메서드를 설계하라. 이 알고리즘을 여러 번 수행해야 한다면 어떻게 해야 할까? 16.3 교차점 시작점과 끝점으로 이루어진 선분 두 개가 주어질 때, 이 둘의 교차점을 찾는 프로그램을 작성하라.
15. 스레드와 락 스레드로 알고리즘을 구현하라는 문제를 출제하는 일은 흔하지 않음. 하지만 스레드, 특히 교착상태(deadlock)에 대한 일반적 이해도를 평가하기 위한문제느 어떤 회사에서도 상대적으로 자주 출제하는 편임. 자바의 스레드 자바의 모든 스레드는 java.lang.Thread 클래스 객체에 의해 생성되고 제어됨. 독립적인 응용 프로그램이 실행될 때, main() 메서드를 실행하기 위한 하나의 사용자 스레드(user thread)가 자동으로 만들어짐. 이를 주 스레드(main thread) 라고 함. 자바에서 스레드를 구현하는 방법은 2가지가 있음. java.lang.Runnable 인터페이스 구현하기 java.lang.Thread 클래스 상속받기 Runnable 인터페이스를 구현하는 방법 ..
14. 데이터베이스 SQL 질의문에는 수많은 변종이 있음. 여러분은 그 가운데 하나를 사용했을 것임. SQL 문법과 그 변종들 묵시점(implicit) JOIN과 명시적(explicit) JOIN은 둘다 동등함. 어느 쪽을 사용할 것이냐는 개인 취향의 문제임. 비정규화 vs. 정규화 데이터베이스 정규화 데이터베이스는 중복을 최소화하도록 설계된 데이터베이스임. 대신 상당수의 일상적 질의를 처리하기 위해 JOIN을 많이 하게 되는 단점이 있음. 비정규화 데이터베이스는 읽는 시간을 최적화하도록 설계된 데이터베이스임. 대신 데이터베이스에 데이터를 중복해서 저장할 수 있음. 소규모 데이터베이스 설계 면접장에서 데이터베이스를 설계해 보라는 요청을 받을 수 있음. 1단계 : 모호성 처리 데이터베이스에 관계뙨 문제는 ..
12. C와 C++ 좋은 면접관은 지원자에게 익숙하지 않은 언어로 코딩하라고 요구하지 않음. 만약 C++로 코딩해 보라는 요구를 받았다면, 이력서에 C++를 적어놨기 때문임. API를 모두 기억하지 못해도 괜찮지만, 관련된 문제를 쉽게 풀 수 있도록 기본적인 C++ 문법은 공부해 둘 것을 추천함. 클래스와 상속 C++ 클래스는 다른 객체 지향 언어의 클래스와 비슷한 특성을 가짐. C++에서 모든 데이터 멤버와 메서드는 기본적으로 private 임. public 키워드를 사용하여 그 값을 변경할 수 있음. 생성자와 소멸자 생성자 : 객체가 생성되면 자동으로 호출됨. 소멸자 : 객체가 소멸될 때 자동으로 호출됨. 기본값 함수 선언 시, 기본값(default values)을 명시할 수 있음. 반드시 함수 선언..