🟩 S3 - Daily Coding

🟣 21_largestProductOfThree

정수를 요소로 갖는 배열을 입력받아 3개의 요소를 곱해 나올 수 있는 최대값을 리턴해야 한다.
└▶ 배열의 요소는 음수와 0을 포함한다.
└▶ 배열의 길이는 3이상.

⬜ 내가 생각한 방법

Algorithm

1. 양수/음수를 분리한다. 0은 양수에 넣는다.
2. 양수 중에서 가장 큰 수 3개를 뽑는다.
3. 절대값이 양수보다 큰 음수가 짝수개 있으면 선택.
(이때, 절대값이 양수와 같더라도 음수의 짝수개를 맞추기 위해 선택될 수 있다.)
4. 선택한 수들을 곱한 뒤 반환한다.

이렇게 하니까 코드가 너무 길어지고... 3번에서 막혀버렸다. 솔직히 왜 이렇게 복잡하게 생각했는지 그당시의 나를 이해할 수가 없다.

⬜ 래퍼런스

Algorithm

1. 주어진 배열을 오름차순으로 정렬한다.
2. 양수 절대값이 가장 클 경우를 구한다.
(오름차순이므로 제일 마지막 원소부터~이전 2개 인덱스까지)
3. 음수 절대값이 가장 클 경우를 구한다.
(음수는 짝수개여야 곱해서 양수가 되므로 0,1번째 인덱스+제일 큰 양수인 마지막 인덱스)

난 왜 이런 간단해 보이는 생각조차 하지 못 했을까? 뭐든 입력값이 배열, 그리고 최대값이 키워드로 들어가면 이제 정렬부터 떠올려야겠다.

🟧 기억할 부분

// 오름차순 정렬
const sorted = arr.slice().sort((a, b) => a - b);

이게 맨날 헷갈리는데, (지난 알고리즘 스터디에서도 sort 메서드를 활용하지 못해 래퍼런스를 참고한 적이 있었다) 계속해서 활용을 안 하니 금방 까먹고만다.

아래는 예전에 내가 배열 메서드를 블로깅 할 때 기록해두었던 것이다.

Array.prototype.sort

배열의 요소를 정렬한다. 원본 배열을 직접 변경하며 정렬된 배열을 반환한다.


기본적으로 오름차순으로 요소를 정렬한다.
정렬 순서는 유니코드 코드 포인트의 순서를 따르다.


그 문제로, 문자열 '2'와 '10'을 정렬하면 ['10', '2']와 같이 정렬된다.


또한 sort 메서드는 배열의 요소를 일시적으로 문자열로 변환한 후 정렬하므로 숫자 2, 10을 정렬해도 [10, 2] 와 같이 정렬 된다.


🔵 따라서 숫자 요소를 정렬할 때는 정렬 순서를 비교하는 비교 함수를 인수로 전달해야 한다.

• 반환값이 0보다 작으면 첫 번재 인수 우선 정렬.
• 0이면 정렬하지 않음.
• 0보다 크면 두 번째 인수 우선 정렬.

// 오름차순 정렬. 
points.sort((a,b)=>a-b);
// 내림차순 정렬
points.sort((a,b)=>b-a);

🌠 그리고 또, 내가 알고리즘 스터디에서 프로그래머스 문제를 풀면서 배우게 된 문자열 내림차순 정렬도 다시 기록해본다.

strNumbers.sort(function(a,b){
    return (b+a)-(a+b);
});

위 수식을 분석해보면 (a, b)에 4, 49가 들어갔을 때
‘494’-’449’ = 45 이고, 0보다 크기 때문에 b(=49)를 우선 정렬 한다.
문자열을 합쳤을 때 더 큰 수를 우선 정렬하여 내림차순으로 만든다.

🟣 22_fibonacci

피보나치 수열 중 n번째 항의 수를 리턴해야 한다.
└▶ for, while문 금지

⬜ 내가 생각한 방법

피보나치를 보자마자 재귀함수!가 가장 먼저 떠올랐다. 지난번 지옥 같던 재귀함수 코플릿 문제 중에 그나마 간단했던 피보나치 문제가 있었기 때문이다.

근데 머리가 나빠서 맨날 0번째, 1번째 피보나치는 따로... 처리해야 하는 거 맞지? 라고 고민하게 된다.

제발 이것만 기억하자.

0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의한다.

Algorithm

n번째 피보나치 수는 바로 직전의 두 피보나치 수의 합이므로,
1. 0번째, 1번째 수는 직전의 두 수라는게 존재하지 않으므로 각각 자기자신을 return
2. return fibonacci(n-1) + fibonacci(n-2)

⬜ 래퍼런스

그런데 위 해결방법 말고, 래퍼런스를 통해 재밌는 방법을 더 알게 되었다.

dynamic with meoization: O(N)
: 이미 해결한 문제의 정답을 따로 기억(memo)해두고, 다시 해결하지 않는 기법

재귀함수를 사용하면 O(2^N) 시간복잡도가 걸리는 반면 memoization 기법을 사용하면 고작 O(N) 밖에 걸리지 않는다.

재귀함수로 해결할 때,

fibo(10)
= fibo(9)+(8)
= fibo(8)+fibo(7)+fibo(7)+fibo(6)

이 되면서 동일한 문제가 두 번 계산되기 때문이다.

Algorithm

fibo(10)의 경우,
1. 0번째, 1번째 피보나치수 [0,1]을 기억한다.
2. memo[n]에 기억해둔 정답이 있으면 그걸 리턴한다.
3. 기억해둔 정답이 없으면 문제를 풀고 메모한다.

const fibonacci(n) {
  // 1.
  const memo = [0, 1];
  const aux = (n) => {
    // 2.
    if (memo[n] !== undefined) return memo[n];
    // 3.
    memo[n] = aux(n - 1) + aux(n - 2);
    return memo[n];
  };
  return aux(n);
};

🟧 기억할 부분

dynamic with meoization
: 이미 해결한 문제의 정답을 따로 기억(memo)해두고, 다시 해결하지 않는 기법

프로그래머스 문제를 풀 때 종종 이 방식을 머리로는 써야겠다 싶은데 막상 손으로 코딩하면 뜻대로 되지 않을 때가 있었다. memo 배열을 이렇게 만드는 게 맞는 건가? 오히려 헷갈리지 않나? 끊임없이 고민했었는데 실용적인 예시를 한 번 공부하고 나니까 감이 오는 것 같다.

🟣 23_bubbleSort

정수를 요소로 갖는 배열을 입력받아 버블정렬을 사용하여 오름차순으로 정렬한 뒤 리턴해야 한다.

⬜ 내가 생각한 방법

Algorithm

for pass = 1 to n-1 // pass: 한 바퀴 순회 횟수
	for i=1 to n-pass
		if (A[i-1] > A[i])
          	A[i-1]과 A[i]자리를 바꾼다
return A

⬜ 래퍼런스

Algorithm - naive solution

내가 생각한 방식이 나이브한 솔루션이다.

배열이 이미 정렬되어 있어도 모두 순회한 뒤에 결과를 반환한다.

Algorithm - optimized solution

1. swaps = 배열 횟수를 기록. 어떠한 요소도 swap되지 않은 경우 배열은 정렬된 상태.
2. for i=0 to arr.length
3. 		for j=0 to N-1-i
4.			if arr[j] > arr[j+1]
5. 				swaps++
6.				swap(j, j+1, arr);
7.		if swaps === 0
8.			break;
9. return arr

swaps가 0이면 이미 정렬된 상태이므로 최선의 경우 배열을 한 바퀴만 순회하고 결과를 반환한다.

🌠 두 변수를 바꾸는 swap 함수 만들기
const swap = function(idx1, idx2, arr){

• 임시 변수 tmp를 활용하기.

let temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;

• Destructuring assignment 활용하기.

[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];

• XOR 연산 활용하기.

arr[idx1] ^= arr[idx2];
arr[idx2] ^= arr[idx1];
arr[idx1] ^= arr[idx2];

}

🟧 기억할 부분

순회 알고리즘을 떠올릴 때, 이미 완성된 배열을 쓸데 없이 다 도는 경우를 고려하지 않고 문제만 해결되면 된다고 생각했는데

변수 하나를 더 추가하여 검사해주면 되는 걸 보고 앞으로 조금 더 생각한 다음 더 좋은 해결책을 찾아야겠다고 느꼈다...

🟣 24_isSubsetOf

두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴한다.
└▶ 시간복잡도 개선에 집중하라.

⬜ 내가 생각한 방법

Algorithm

1. 두 배열을 정렬한다.
2. 각 원소의 크기를 비교하여 넘길 숫자는 빠르게 넘긴다.

두루뭉술하게 저렇게 생각해보았지만, 코드로 어떻게 작성할지는 감도 오지 않았다.

⬜ 래퍼런스

Algorithm

1. 각 배열을 오름차순 정렬한다. sort((a,b)=>a-b)
2. 정렬 된 배열 안에서 숫자를 찾는 함수 findItem(item, arr, from) 을 정의한다.
* item: 찾고자 하는 요소
* arr: 탐색할 배열
* from: 몇 번째 인자부터 찾을 것인지
2-1. for i=from to arr.length
2-2. 	요소가 존재하면 return i
2-3. 	item < arr[i]면 return -1
3. baseIdx = 0
4. for i=0 to sample.length 
5. 		baseIdx = findItem(sample[i], base, baseIdx);
6. 		if(baseIdx === -1) return false
7. return true

5. 0번째 인자부터 요소를 비교한다.
   2-1. findItem 함수의 for문을 들어간다.
   2-2. 요소가 존재하면 앞으로 순회할 요소들은 i보다 크거나 같은 수이기 때문에 i를 반환하여 baseIdx = i 로 업데이트 해준다.
   2-3. item이 끝까지 순회한 arr[i]보다 작다는 건 부분집합으로 포함되어 있지 않다는 뜻이므로 -1을 반환한다.

7. 모든 순회를 정상적으로 마치면 true를 반환한다.

🟧 기억할 부분

여러모로 머리를 세게 때리는 문제였다.
바로 이전 문제에서 "쓸데 없이 다 도는 경우를 제거하자"라고 다짐해놓고 구체적인 방법을 떠올리지 못 했다...

1. 오름차순 정렬
2. 발견한 요소 인덱스부터 순회
3. 한 개라도 부분집합이 아니라면 바로 종료.

이것만 기억해두고 있어도 다음부터 겁내지 않을 것 같다.

근데 맨날 레퍼런스 보고 저런 말 해놓고 또 까먹어서 장담은 못 하겠다

🟣 25_tiling

세로 길이 2, 가로 길이 n인 2 x n 보드를 2 x 1 크기의 타일로 가득 채우는 경우의 수를 구하시오.

⬜ 내가 생각한 방법

Algorithm

....

⬜ 래퍼런스

Algorithm - naive solution : O(2^N)

1. 2*n 크기의 타일에 2*1 타일을 채우는 것이므로 어찌됐건 필요한 타일 개수는 n개가 된다.
1-1. 이를 a, b, c, d 로 구분한다.
2. 타일이 놓이지 않는 부분은 -
  	2 | a - - -
	1 | b - - -
3. 첫 번째 타일을 가로로 놓느냐, 세로로 놓느냐의 차이다.
3-1. 가로로 놓는 경우 그 바로 아래에는 가로로 놓을 수밖에 없다.
4. 2*4 보드에 타일을 놓는 방법 = 2*3 보드에 타일을 놓는 방법 + 2*2 보드에 타일을 놓는 방법
5. 결론적으로 재귀적이다.

------------------

tiling(n)
1. if(n<=2) return n
2. reurn tiling(n-1)+tiling(n-2);

Algorithm - dynamic with memoization : O(N)

1. memo = [0,1,2] // 해결한 문제의 경우의 수를 저장하는 변수. 인덱스==타일 사이즈 2*(idx). n>2 부터 재귀 계산을 할 것이므로 앞 부분을 저렇게 채운다.
2. 재귀를 위한 보조함수 aux(size)
2-1. 이미 경우의 수를 구한 타일 사이즈라면 return memo[size]
2-2. if(size <= 2) return memo[n]
2-3. memo[size] = aux(size-1)+aux(size-2)
2-4. return memo[size]
3. return aux(n)

Algorithm - dynamic with tabulation : O(N)

tabulation: 데이터를 테이블에 정리하면서 bottom-up 방식으로 해결하는 기법

1. memo = [0,1,2]
2. if(n<=2) return memo[n]
3. for size=3 to n
4. 		memo[size] = memo[size-1]+memo[size-2]
5. return memo[n]

위에서 본 memoization 방식은 n이 8이라면 최상단 root인 8에서부터 아래로 내려가는 방식이었다면

tabulation의 bottom-up 방식은 아래에서 위로 차근차근 계산하며 올라가기 때문에 재귀가 필요 없다.

Algorithm - dynamic with slicing window : O(N)

slicing window: 필요한 최소한의 데이터만을 활용하는 것
└▷ 크기 n의 문제에 대한 해결에는 오직 2개의 데이터만 필요하다.

1. fst = 1, snd = 2
2. if(n<=2) return n
3. for size=3 to n
4. 		next = fst + snd
5. 		fst = snd, snd = next
6. return snd

이게 뭐라고 싶지만 엄청 충격적이었다...

🟧 기억할 부분

문제를 너무 이미지화 해서 생각하다 보니 머릿속에 보이는 그대로 2차원 배열을 사용해야 하나..? 인덱스로 가로축 세로축을 계산해야 하나... 바보 같은 생각을 하였다.

우선 아무 입출력 예시를 떠올린 다음에 그 안에서 규칙을 찾는 훈련이 필요하다.

1. 재귀 규칙을 발견했다면, 그냥 재귀함수만 쓰지 말고 memoization으로 시간복잡도를 낮추자.
2. 현재 문제 = 이전 문제 + 이이전 문제 라면, bottom-up 방식으로 재귀 없이도 풀어보자.
3. 더 가독성 좋은 방법으로 memo 배열이 아닌 데이터 변수를 사용해보자.