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

배열 특징 : 연속한 메모리 공간에 할당

 

5.1 네덜란드 국기 문제 (그룹들의 묶음)

배열 A와 인덱스 i 가 주어졌을 때 A[i](피벗)보다 작은 원소, 피벗과 같은 원소, 피벗보다 큰 원소 순으로 재배열하라

 - 공간을 사용하는 방법 : 세가지 리스트 만든 후 차례로 A에 넣어주면 됨 (공간복잡도 O(n) / 시간 복잡도 O(n))

 - 시간을 사용하는 방법 :

 1) 배열 순회하며 피벗보다 작은 원소 그룹 스왑 후 피벗보다 큰 원소 그룹 스왑

 

5.2 임의의 정수값 증가시키기

십진수 D를 나타낸 배열 A가 있고, D+1의 결과를 다시 배열 A에 갱신하라

예) {1,2,9} => {1,3,0}  //힌트 : 실제 예제 입력 사용해보자

유한 정밀도 산술로 이루어진 프로그램 언어로도 동작해야 한다(?)

 

- 무식하게 배열의 숫자를 정수로 바꾼 후 1더한 결과를 배열에 쓴다({1,2,9} => 129 => 130 => {1,3,0})

(정수의 범위에서만 작동하며 범위를 벗어나는 값엔 작동하지 않음)

 

 - 배열에 연산을 바로 적용 > 최하위 숫자부터 덧셈 후 올림수 넘겨주는 방식 이용(시간복잡도 O(n))

올림수가 있으면(10이라면) 자릿수가 하나 더 필요함 > 1로 업데이트 후 끝에 0 추가

 

5.3 임의의 두 정수값 곱하기

정수를 나타내는 두개의 문자열이 주어졌을 때, 이 둘의 곱셈결과를 반환하라

예) {1,9,3,7,0,7,7,2,1} 와 {-7,6,1,8,3,8,2,5,7,2,8,7} => {-1,4,7,5,7,3,9,5,2,5,8,9,6,7,6,4,1,2,9,2,7}

(193707721) * (-761838257287) => -147573952589676412927

- 배열을 정수로 바꾸어 계산시 오버플로 문제가 발생할 수 있음

- 초등학생때 배운 곱셈연산 사용 => 각 자릿수에 있는 숫자 곱한 후 모두 더하기 (123 * 978 => 1 *978 + 2*978 + 3*978)

- 결괏값의 자릿수는 최대 n+m / m개의 부분곱셉이 존재하고, 각각 최대 n+1개의 자릿수와 곱셈을 수행함

- 총 시간 복잡도는 O(nm) 

 

5.4 배열에서 이동하기

주어진 위치 정보를 차례대로 가야 하는 보드게임에서, 각 위치엔 음이 아닌 정수값이 있고
해당 위치에서 최대 그 숫자만큼 앞으로 나아갈 수 있다. 첫번째 위치에서 마지막까지 도달할 수 있는지 판단하라
(단, A[i]는 i번째 위치에서 나아갈 수 있는 최대 거리를 뜻한다.)

- 배열 값을 차례로 살펴보면서 최대한 움직일 수 있는 거리가 얼마나 되는지 기록(i위치에서는 i+A[i]까지 움직일 수 있음)

- 만약 최대 움직일 수 있는 거리가 마지막 위치보다 작다면 도달 불가

예) A = {3,3,1,0,2,0,1} 은 최대한 움직일 수 있는 거리가 0,3,4,4,4,6,6,7

시간복잡도 O(N), 공간복잡도는 3개변수 사용시 O(1)

 

5.5 정렬된 배열에서 중복 제거하기

정렬된 배열 중복 제거 후 빈 공간 없게 원소들을 모두 왼쪽으로 시프트하는 프로그램, 유효한 원소의 개수를 반환

- O(n) 시간복잡도 : 해시테이블

- O(1) 공간복잡도 :  배열순회하며 A[i] 와 A[i +1]이 같을 때, i+2 이후의 원소들을 모두 왼쪽으로 한칸씩 옮긴다.(시간복잡도 O(n^2))

=> 시프팅이 시간복잡도 원인이므로 개선하려면 시프팅 횟수 줄여야 한다. 정렬된 배열이므로 모든 원소를 옮길 필요 없이 새로운 값 나타나면 자리만 옮겨준다(이걸 반복) {2,3,5,5,5,7}이면 7을 두번째 5자리로 이동(시간복잡도 O(n), 공간 O(1))

 

5.6 주식 한 번 사고팔기

특정 기간, 주식 한 주를 사서 되팔았을 때 최대 이익
모든 매매는 시작가 기준, 매도는 매입 후 발생 

예) {310, 315, 275, 295, 260, 270, 290, 230, 255, 250}에서 한번 사고 팔아 최대이윤 남기려면 260에 사서 290에 팔면 됨

=> 최대 이윤은 30

- 최대이윤은 현재가와 지금까지의 최저가의 차이 비교

 

5.7 주식 두 번 사고팔기

주식 한 주를 최대 두 번까지 매매가능, 최대 이익

- (i+1)번째 원소 다루고 있을 때, i개의 원소에서 어떤 정보를 얻어야 하는지 생각해볼 것

- 무식하게 매수-매도-매수-매도 조합 구하기 (시간복잡도 O(n^4))

- 위의 알고리즘을 두 배열에 적용하기(시간복잡도 O(n^2)) => 이전 값 기록하면 더 효율적(시간복잡도O(n), 공간 O(n))

 

5.8 대체 연산

숫자 n개를 원소로 가지는 배열 A를, B[0] <= B[1] >= B[2] <= B[3] >= B[4] >= B[5]... 특징 가지도록 새로운 배열 B에 재배치하라

- 배열 A를 정렬 후 아래쪽과 위쪽 절반을 교차로 배치한다.

- 또는 정렬 후 (A[1], A[2]) 와 (A[3], A[4])를 서로 교환, 나머지도 마찬가지

시간복잡도 O(n log n)

 

- 정렬없이 중간값 주위 원소 재배열 후 교차배치할 수도 있다.

 

5.9 n보다 작은 모든 소수 나열하기

소수 : 1보다 큰 자연수 중 1과 자기 자신 이외의 수로 나누어 떨어지지 않는 수

양의 정수 n 주어짐, 1과 n 사이에 있는 모든 소수 반환

예) 입력 18 => {2,3,5,7,11,13,17} 

- 모두 순회하면서 합성수 제외하기

- 휴리스틱이지만 소수 발견할 때마다 그 숫자의 배수를 후보리스트에서 제거(에라토스테네스의 체)

 

5.10 배열 안의 원소로 순열 구하기

순열 : 일련의 순서로 나열된 원소들을 새로운 순서로 재배열 하는 것

길이가 n인 배열 A와 순열 P가 주어졌을 때, P를 A에 적용해보라

예) {a,b,c,d}는 {b,a,d,c} , {d,a,b,c}와 같은 24개의 서로 다른 순열이 존재

모든 순열은 순환 순열의 집합안에 있다고 말할 수 있다.

 - 공간사용 : 주어진 배열과 길이같은 배열 B 사용하여 모든 i 에 대해 B[P[i]] = A[i]로 값 할당한 뒤 B 결과를 A로 복사

(시간복잡도O(n), 공간복잡도 O(n)) => 개선방법은 순열을 간략한 구조로 분해 후 순서대로 처리

 

5.11 다음 순열 구하기

어떤 순열이 주어졌을 때 다음 순열을 구하는 함수를 작성하라
(단, 순열의 순서는 사전순, 주어진 순열이 가장 마지막 순열이라면 빈 순열 반환)

예) p = {1,0,3,2} 다음은 {1,2,0,3}

- 무식하게 입력과 길이 같은 모든 순열을 사전 순 나열 후 입력 순열 바로 다음에 등장하는 순열 찾기

- 순열의 값이 아닌 순서를 재배치하는 특징 =>