면접 문제
8.9 괄호
- n 쌍의 괄호로 만들 수 있는 모든 합당한(괄호가 적절히 열리고 닫힌) 조합을 출력하는 알고리즘을 구현하라.
8.10 영역 칠하기
- 이미지 편집 프로그램에서 흔히 쓰이는 ‘영역 칠하기(paint fill)’ 함수를 구현하라. 영역 칠하기 함수는 화면(색이 칠해진 이차원 배열)과 그 화면상의 한 지점, 그리고 새로운 색상이 주어졌을 때, 주어진 지점과 색이 같은 주변 영역을 새로운 색상으로 다시 색칠한다.
8.11 코인
- 쿼터(25센트), 다임(10센트), 니켈(5센트), 페니(1센트)의 네 가지 동전이 무한히 주어졌을 때, n센트를 표현하는 모든 방법의 수를 계산하는 코드를 작성하라.
8.12 여덟 개의 퀸
- 8x8 체스판 위에 여덟 개의 퀸(queen)이 서로 잡아 먹히지 않도록 놓을 수 있는 모든 가능한 방법을 출력하는 알고리즘을 작성하라. 즉, 퀸은 서로 같은 행, 열, 대각선상에 놓이면 안 된다. 여기서 ‘대각선’은 모든 대각선을 의미하는 것으로, 체스판을 양분하는 대각선 두 개로 한정하지 않는다.
8.13 박스 쌓기
- 너비 w_i, 높이 h_i, 깊이 d_i인 박스 n개가 있다. 상자는 회전시킬 수 없으며, 다른 상자 위에 올려 놓을 수 있다.단, 아래 놓인 상자의 너비, 높이, 깊이가 위에 놓인 상자의 너비, 높이, 길이보다 더 클 때에만 가능하다. 이 상자들로 쌓을 수 있는 가장 높은 답을 구하는 메서드를 작성하라. 탑의 높이는 탑을 구성하는 모든 상자의 높이 합이다.
8.14 불린값 계산
- 0(false), 1(true), &(AND), |(OR), ^(XOR)으로 구성된 불린 표현식과, 원하는 계산 결과(역시 불린 값)가 주어졌을 때, 표현식에 괄호를 적절하게 추가하여 그 값이 원하는 결과값과 같게 만들 수 있는 모든 경우의 개수를 출력하는 함수를 구현하라.
- 예제
- countEval(”1^0|0|1”, false) → 2
- countEval(”0&0&0&1^1|0, true) → 10
댓글