책너두 (코딩 인터뷰 완전분석) 25일차 (8.4 ~ 8.8)

면접 문제

8.4 부분 집합

• 어떤 집합의 부분 집합을 전부 반환하는 메서드를 작성하라.

8.5 재귀 곱셈

• • 연산자를 사용하지 않고 양의 정수 두 개를 곱하는 재귀 함수를 작성하라. 덧셈(addition), 뺄셈(subtraction), 비트 시프티(bit shifting) 연산자를 사용할 수 있지만 이들의 사용 횟수를 최소화해야 한다.

8.6 하노이타워

• 전형적인 하노이타워(Towers of Hanoi)에서는 크기가 서로 다른 N개의 원반을 세 개의 기둥 중 아무 곳으로나 옮길 수 있다. 초기에 원반은 크기가 맨 위에서부터 아래로 커지는 순서대로 쌓여 있다. 그리고 이 문제에는 다음과 같은 제약조건이 있다.

  (1) 원반을 한 번에 하나만 옮길 수 있다.

  (2) 맨 위에 있는 원반 하나를 다른 기둥으로 옮길 수 있다.

  (3) 원반은 자신보다 크기가 작은 디스크 위에 놓을 수 없다.

• 스택을 사용하여 모든 원반을 첫 번째 기둥에서 마지막 기둥으로 옮기는 프로그램을 작성하라.

8.7 중복 없는 순열

• 문자열이 주어졌을 때 모든 경우의 순열을 계산하는 메서드를 작성하라. 단, 문자는 중복되어 나타날 수 없다.

8.8 중복 있는 순열

• 문자열이 주어졌을 때 모든 경우의 순열을 계산하는 메서드를 작성하라. 문자는 중복되어 나타날 수 있지만, 나열된 순열은 서로 중복되면 안 된다.