[262가지 문제로 정복하는 코딩 인터뷰 간단요약] 5장 배열(2)

5.12 오프라인 데이터 샘플 구하기

서로 다른 원소로 이루어진 배열과 부분 집합의 크기 주어졌을 때, 주어진 크기의 부분집합 결과를 반환하라
(모든 부분 집합이 생성될 확률은 같아야 한다.)

힌트 : 크기가 k인 임의의 부분 집합이 존재할 때 크기가 k+1인 임의의 부분 집합을 어떻게 구할 수 있을까?

- 배열 A의 길이는 n, 부분 집합의 크기는 k라고 하면

가장 단순한 방법은 입력 배열 순회하며 각 원소를 k/n의 확률로 선택하기

 

- 크기가 k인 모든 부분 집합 나열 후 임의로 하나의 부분집합 선택하기(시간 및 공간복잡도 매우 큼)

 

- 크기가 k-1인 부분 집합 만든 후 임의의 나머지 원소 추가하기

 

5.13 온라인 데이터 샘플 구하기

패킷 스니퍼 : 네트워크 세션에 균일한 샘플의 패킷을 제공

어떤 정수값 k가 주어졌을 때, 실시간으로 패킷이 유입되는 상황에서, k개의 임의의 패킷을 균일한 확률로 유지하기

힌트 : n개의 패킷 중에서 이미 k개를 가지고 있다고 가정해보자. 이때, n+1번째 패킷이 입력으로 들어온다면??

- 무식하게 모든 패킷 읽은 후 저장할 수 있다.(공간복잡도 O(n)으로 매우 큼)

 

5.14 임의의 순열 계산하기

{0,1,2, ..., n-1}로 이루어진 임의의 순열을 동일한 확률로 만들어내기

임의의 순열 생성은 생각보다 간단하지 않다.

힌트 : 결과를 배열 A에 저장한다면 A[n-1]에 올바른 값이 할당되었을 때 어떻게 처리하겠는가?

- 무식하게 0부터 n-1까지의 숫자를 임의로 선택한다.(뽑은숫자면 무시하고 다시, 뽑은숫자 확인은 해시테이블로)

공간복잡도는 해시테이블 사용하므로 O(n) / 시간복잡도는 반복이 얼마나 될지 모르므로 분석어려움(평균시도횟수는 O(n log n)) => 시간 복잡도 계산 위해 중복을 피해야 하고, 이를 위해 임의로 선택하는 집합의 개수를 제한한다.

 

5.15 임의의 부분 집합 만들기

양의 정수 n과 크기 k(k < n)가 입력으로 주어졌을 때 {0,1,2, ..., n-1}의 집합에서 크기가 k인 부분 집합을 반환하기 (부분집합은 배열로 표현한다.)

- 5.12참고, 배열 A를 A[i]로 초기화 후 k개의 원소를 샘플링(공간복잡도 O(n))

- 해시테이블 사용시 공간복잡도 O(n)

 

5.16 균등하지 않은 임의의 숫자 생성하기 

로드 테스트(부하 테스트)를 위한 요청의 도착 간격 시간 구하기
n개의 숫자와 각 숫자의 확룰이 주어졌다(모두 더하면 1), 주어진 확률에 따라 n개의 숫자를 생성하려면?

- 힌트 : 실제로 어떤 숫자가 생성되는지 보다는 n개의 결과를 확률로 선택하고 싶을 뿐

모든 확률이 같다면(1/n) => 임의의 숫자 생성기 한번 호출 뒤 i / n과 (i + 1) / n 사이에 있는 i를 선택하면 됨

같지 않다면 => 구간을 확률의 크기에 비례하도록 설정 후 값을 임의로 선택하여 그 값이 속한 구간의 숫자를 반환하면 됨

 

5.17 스도쿠 체크

9 * 9 크기의 미완성된 격자판이 2차원 배열로 주어졌을 때, 하위 3 * 3 하위 격자판에 [1,9] 사이의 숫자가 하나씩 배열해야 함
해법이 존재하는지?

- 비트 배열을 사용하여 제한사항, 즉 [1, 9] 사이의 숫자가 한번 이상 등장했는지 테스트

 

5.18 2차원 배열에 나선형으로 원소 배치하기

n * n 크기의 2차원 배열에 나선형으로 쓰는 방법

- 힌트 : 케이스 분석과 분할정복법을 사용하라

 

5.19 2차원 배열 회전하기

n * n 크기의 2차원 배열 시계방향으로 90도 회전시키기

 

5.20 파스칼의 삼각형에서 행 계산하기

파스칼의 삼각형 : 각 행은 이전 행보다 엔트리가 하나 많고, 그 밑에는 한 개 혹은 두 개의 엔트리를 접하고 있다.

첫번째 행의 첫번째 엔트리는 1로 시작한다. 다음 엔트리는 바로 위 인접한 엔트리의 합으로 표현된다.

음이 아닌 정수 n이 주어졌을 때, 파스칼의 삼각형에 해당하는 첫 n개의 행을 출력하라

힌트 : 파스칼의 삼각형을 수식으로 작성해보자