알고리즘&자료구조 3편 - 문제해결(2) 패턴

김영현·2023년 5월 16일

알고리즘 & 자료구조

목록 보기

3/6

자주 나오는 패턴들이다.
자주 나온다해서 무조건 나오는건 아니니 주의바람.

알고리즘 패턴

frequency counter
multiple pointer
sliding window
divide and conquer
dynamic programming
greedy
backtracking
...etc

Frequency counter(빈도 카운터)

두 개 이상의 값을 비교할때 자주 쓰임

문제) make a same

예) same이라는 함수를 작성하라. 두 배열이 주어지고, 다른배열이 한 배열의 모든 값이 제곱된 배열이라면 true 아니라면 false. 순서는 상관없다.

이런식으로 입출력이 나오는 함수를 작성하면된다.

풀이1. 순진한 해결법

보통 알고리즘을 잘 모르면 이런식으로 2중for문을 통해 순회한다. 나 역시 비슷한 문제를 풀면서 2중for문밖에 생각하지 못했다. 그러다 시간제한에 걸려 풀지못한 문제도 있었다.
2중 for문의 시간복잡도는 O(n^2). 상당히 시간을 잡아먹는 녀석이다.

풀이2. 빈도카운터!

두 객체를 생성한다.
두 객체에 각 숫자의 빈도수를 센다.
=> ex) arr1 = [1,2,3,2] arr2 = [9,1,4,4]라면 1번1객체 = {1:1, 2:2, 3:1} 2번객체 = {1:1, 4:2, 9:1} 이렇게 들어간다.
둘 중 제곱되지 않은 값의 객체를 기준삼아 for...in문을 돌린다.
=> 어떻게 가능할까? 두 객체의 Key값이 알아서 오름차순으로 정렬되어있다. 객체를 순서를 보장하지 않는다고 들었는데...무슨일이 일어난걸까? 흠...
==> 찾아보니 JS가 공식으로 지원하는건 아니고, 환경에따라 다를수 있다고 한다. 근데 브라우저와 node, deno 등 유명한 환경에선 다 오름차순으로 정렬되어 보인다. 개발자가 넣은 순서대로 나오지 않는다라...뭔가 꺼림칙하네.

Multiple pointer

인덱스나 위치에 해당하는 포인터나 값을 만든다음 특정조건에따라 끝이나 중간 등 특정지점으로 이동시키는것.
설명만 들어선 잘모르겠다. 역시 예제부터 보자.

문제1) make a sumZero

오름차순으로 정렬된 숫자 배열이 주어질때 두 값을 더해 0이되는 숫자들을 출력. 없으면 undefined

풀이1. 순진한 해결법

역시나 중첩for문이다. 알고리즘 공부하며 느끼는건 자신이 만든 해답이 중첩for문이라면 한번은 다른방법을 고민해봐야겠다.

풀이2. 다중 포인터!

이번엔 강의를 듣기전에 5분만이라도 알고리즘을 먼저 생각해보겠다.

function sumZero(arr) {
  // 두 값을 더하면 0이되는 값을 찾는다.
  // 참고로 두 값은 정렬되어있다!
  // 이름이 다중포인터니까, 일단 첫부분과 끝 부분을 잡아보자.
  for (let i = 0; i < arr.length; i++) {
    const lastIndex = arr.length - 1;
    const frontNum = arr[i];
    const backNum = arr[lastIndex - i];
}
sumZero([-3, -1, 0, 1, 2, 3]);

5분이라는 시간은 너무 짧구나. 내가 생각해본 알고리즘이다. 첫점과 끝점을 잡고, 첫점을 기준으로 끝점을 더했을때 0이면 리턴, 0보다 크면 끝점을 줄이려했는데,i는 for문 안에있다.
흠.

아래는 강사분이 제시해준 풀이!

1. 시작index와 끝 index를 잡는다.
2. 시작index가 끝index보다 작을때 아래 조건문을 계속 돌린다
3. 시작값과 끝값을 더한다.
3-a. 만약 0이라면, 시작값과 끝값을 리턴한다.
3-b. 만약 0보다크다면, 끝값의 index를 영원히 1 줄인다.(정렬되어있기때문에 큰수에서 작은수로 옮긴다)
3-c. 만약 0보다 작다면 시작값의 index를 영원히 1 늘린다 (위에서 조건들에 걸린것이 없으니 다음 시작값으로)
역시 for문으론 어려웠군. 확실히 변수를 밖으로 빼는게 좋아보였다.

문제2) countUniqueValues

오름차순으로 정렬된 숫자 배열이 주어질 때 고유한 숫자들의 갯수를 리턴.

이런식으로 말이다. 빈값은 0!

풀이1. 순진한(이번엔 나만의) 해결법

이번엔 내가 순진하게 풀어보겠다. Set자료구조를 사용해서 중복을 없애버리고 싶지만, 의도와 어긋난다.
또한 2중첩 for문은 이제 깔끔하게 보내줬다! 더이상 순진하기만 한 알고리즘이 아니다.

function countUniqueValues(arr) {
  if (!arr) return 0;
  let leftIndex = 0;
  let rightIndex = leftIndex + 1;
  let count = 1;
  while (leftIndex < arr.length - 1) {
    if (arr[leftIndex] === arr[rightIndex]) {
      rightIndex++;
    } else {
      count++;
      leftIndex = rightIndex;
      rightIndex = leftIndex + 1;
    }
  }
  return count;
}
console.log(countUniqueValues([1, 1, 1, 1, 1, 2]));

왼쪽 인덱스는 0, 오른쪽 인덱스는 왼쪽 인덱스에서 +1을 해준거다. 예외처리했기에 숫자는 하나가 기본으로 있을테니까 count는 1.
왼쪽 인덱스가 마지막 인덱스-1이 될때까지 굴려준다.
2-a. 왼쪽값과 오른쪽값이 같으면 오른쪽 인덱스를 늘려준다.(한칸 전진)
2-b. 전진하다가 값이 다르다면 고유한 값이니 count ++. 또한 왼쪽 인덱스를 오른쪽 인덱스값으로 치환(막 바뀐 고유한 값으로 또 비교를 해야함). 그리고 오른쪽 인덱스도 다시 왼쪽인덱스+1값으로 바꿔준다
done!

결과는 잘 나온다. 이제 강사분의 풀이를 보자!

풀이 2.

뭔가 더 깔끔하다.
1. 왼쪽 인덱스를 변수로 따로 뺀다.
2. 인덱스 1부터 for문을 돌린다.
2-a. 왼쪽값과 오른쪽값이 다르다면 오른쪽 인덱스에 1을 더하고, 그 자리를 왼쪽 값으로 치환한다(!)
=> 나는 인덱스를 치환했지만, 강사분은 값 자체를 치환했다. 비슷한 방식이지만 아직 뭐가 더 좋은지는 모르겠다. 코드가 깔끔한건 알겠음.
3. 넘어간 카운트만큼 i가 이동했으니 첫값을 더해 i+1을 리턴

slidig window

연속적인 데이터의 하위집합을 찾을때 유용하다. 창문을 미는것처럼 특정한 구간을 움직이는 느낌.
예제로 보자

문제1) maxSubArraySum

숫자로 이루어진 배열 arr과 자연수 n이 주어짐. 배열의 숫자들을 n번 연속 더한값이 경우의 수 중 최댓값일때 return.

풀이1. 순진한 풀이

업로드중..
아주 순진하다. 2중첩 for문으로 n개만큼 더하는 경우의수를 쭉쭉 밀고 나간다.
아주 느리군!

풀이2.

업로드중..

첫 인덱스부터 n개만큼 더해서 기준용 최댓값을 만든다(maxSum과 첫번째 for문)
tempSum에 MaxSum을 할당 후 for문(num-1까진 더했으니 i는 num부터~array.length까지)을 돌린다.
2-a. tempSum은 첫 값부터 n개의 값, 다시말해 인덱스 0부터 n-1까지 더했을 것이다.
=> 순회하면서 바로 전 인덱스값을 빼고, 바로 다음 인덱스값을 더한 Sum을 만든다.
2-b. maxSum과 tempSum을 Math.max메소드로 비교 후 maxSum에 값을 할당한다.
done!

Divde and Conquer

분할정복 알고리즘! 알고리즘들의 기본이 되는 알고리즘인 너낌?

김영현

모르는 것을 모른다고 하기

이전 포스트

알고리즘&자료구조 2편 - 문제 해결(1) 접근법

다음 포스트

알고리즘&자료구조 3편 - 문제해결(2) 패턴