17. 어려운 연습문제 17.21 막대 그래프의 부피 히스토그램(막대 그래프)을 상상해 보자. 누군가가 히스토그램 위에서 물을 부었을 때, 이 그래프가 저장할 수 있는 물의 양을 계산하는 알고리즘을 설계하라. 단, 막대의 폭은 1이라고 가정하자. 17.26 드문드문 유사도 서로 다른 단어로 구성된 두 문서의 유사도는 단어들의 교집합의 크기 나누기 합집합의 크기로 정의할 수 있다. 즉, 정수로 이루어진 두 문서 {1, 5, 3}과 {1, 7, 2, 3}의 유사도는 0.4가 된다. 왜냐하면 두 문서의 교집합의 크기는 2이고 합집합의 크기는 5이기 때문이다. 유사도의 밀도가 굉장히 ‘희박’할 것 같은 문서가 굉장히 많이 주어져 있다(각 문서는 ID로 표현된다). 여기서 희박하다는 뜻은 임의의 두 문서의 유사도..
17. 어려운 연습문제 17.16 마사지사 인기 있는 마사지사가 있다. 마사지 사이에 15분간 휴식이 필요하므로 마사지 예약이 연달아 들어온다면 그중에서 어떤 예약을 받을지 선택해야 한다. 연달아 들어온 마사지 예약 리스트가 주어졌을 때(모든 예약 시간은 15분의 배수이며 서로 겹치지는 않고 한번 예약이 되면 변경이 불가능하다), 총 예약 시간이 가장 긴 최적의 마사지 예약 순서를 찾으라. 17.19 빠진 숫자 찾기 1부터 N까지 숫자 중에서 하나를 뺸 나머지가 정확히 한 번씩 등장하는 배열이 있다. 빠진 숫자를 O(N) 시간과 O(1) 공간에 찾을 수 있겠는가? 만약 숫자 두 개가 빠져 있다면 어떻게 찾겠는가?
17. 어려운 연습문제 17.12 BiNode BiNode라는 간단한 자료구조가 있다. 이 자료구조 안에는 다른 두 노드에 대한 포인터가 들어 있따. public class BiNode { public BiNode node1, node2; public int data; } BiNode 자료구조는 이진 트리를 표현하는 데 사용될 수도 있고(node1은 왼쪽 노드를, node2는 오른쪽 노드를 가리키게 만들면 된다), 양방향 연결리스트를 만드는 데 사용할 수도 있다(node1은 이전 노드를, node2는 다음 노드를 가리키게 만든다). BiNode를 사용해서 구현된 이진 탐색 트리를 양방향 연결리스트로 변환하는 메서드를 작성하라. 값의 순서는 유지되어야 하며 모든 연산은 원래 자료구조 안에서(in-place..
17. 어려운 연습문제 17.9 k번째 배수 소인수가 3, 5, 7로만 구성된 숫자 중 k번째 숫자를 찾는 알고리즘을 설계하라. 3, 5, 7이 전부 소인수로 포함되어야 하는 건 아니지만 3, 5, 7 외에 다른 소수가 포함되면 안 된다. 이 조건을 만족하는 숫자의 예를 몇가지 나열해보면 1, 3, 5, 7, 9, 15, 21이 있다. 17.10 다수 원소 다수 원소란 배열에서 그 개수가 절반 이상인 원소를 말한다. 양의 정수로 이루어진 배열이 주어졌을 때 다수 원소를 찾으라. 다수 원소가 없다면 -1을 반환하라. 알고리즘은 O(N) 시간과 O(1) 공간 안에 수행되어야 한다.
17. 어려운 연습문제 17.8 서커스 타워 어느 서커스단은 다른 사람 어깨 위에 다른 사람이 올라서도록 하는 ‘인간 탑 쌓기’를 공연한다. 실질적이면서도 미학적인 이유 때문에 어깨 위에 올라서는 사람은 아래 있는 사람보다 가벼우면서 키도 작아야 한다. 단원의 키와 몸무게가 주어졌을 때, 최대로 쌓을 수 있는 인원수를 계산하는 메서드를 작성하라. 17.23 최대 검은색 정방행렬 정방형의 행렬이 있다. 이 행렬의 각 셀(픽셀)은 검은색이거나 흰색이다. 네 가장자리가 전부 검은색인 최대 부분 정방행렬을 찾는 알고리즘을 설계하라.
17. 어려운 연습문제 17.3 임의의 집합 길이가 n인 배열에서 m개의 원소를 무작위로 추출하는 메서드를 작성하라. 단, 각 원소가 선택될 확률은 동일해야 한다. 17.5 문자와 숫자 문자와 숫자로 채워진 배열이 주어졌을 때 문자와 숫자의 개수가 같으면서 가장 긴 부분배열을 구하라.
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은 너무 장황하게 표현된 경우가 많..