2024년 01월 01일 월요일

간단한 문제 풀이 테크닉

• skills
• algorithm
• data_structure

들어가며

이번에는 간단한 문제 테크닉에 대해서 배워보고자 합니다.

문제 테크닉이라니 벌써부터 두근두근 거리지 않나요?

이제부터는 앞에서 표현한 것보다 좀 더 어려운 예제들이 나오게 됩니다.

다만, 알고리즘과 문제풀이법에서 배웠던 것처럼 차근차근 풀다보면 의외로 쉽게 풀릴거에요!

어떤 테크닉을 배울 것인가?

이번 장에서 다룰 테크닉은 3가지입니다.

• 빈도수 세기
• 슬라이딩 윈도우
• 투 포인터

슬라이딩 윈도우와 투 포인터는 어떻게 보면 비슷한 면도 있어요.

그리고 이름이 거창할 뿐이지 사실 다들 일상생활에서 잘 사용하고 있는 테크닉들이랍니다?

그럼 이제부터 하나씩 살펴볼까요?

빈도수 세기

빈도수 세기란 무엇일까요? 말 그대로 빈도수를 세는 문제들에 대한 접근법을 말합니다.

알고리즘이란 뭐라고 했죠? 문제를 푸는 방식입니다.

그렇기에 다소 추상적일 순 있지만, 그래도 문제를 푸는 방법 혹은 문제에 접근하는 방법이라고 생각하며 바라보시면 좋을 듯 합니다.

하나 문제를 내볼게요.

Q. 문제 "djdyaac"에서 각 알파벳이 몇 번 나왔는지 출력하시오. 이때, 출력 양식은 다음과 같습니다. (출력 시 알파벳은 정렬하지 않아도 됩니다.)

<출력> d:2 j:1 y:1 a:2 c:1

이와 같은 문제가 있다고 해봅시다.

어떻게 접근할 수 있을까요?

문제에 대한 분석

잠깐 앞에서 배웠던 것을 적용해서 해석해볼까요?

먼저 입력은 무엇이고 출력은 무엇일까요?

입력은 "djdyaac"와 같은 알파벳으로만 이루어진 문자열이겠죠?

출력의 경우는 알파벳:횟수 로 각 줄에 하나씩 내보내는 겁니다.

그러면 이 문제를 어떻게 단순화 할 수 있을까요?

잠깐! 아래 글을 읽기전에 한번 생각해보시겠어요?

저라면 문자열을 "d", "j", "d", "y", "a", "a", "c" 이렇게 나눠서 볼 것 같아요.

그러면 문자열을 다루는 문제에서 문자를 여러번 다루는 문제로 바뀔 수 있어요!

문자 하나를 셀려면 어떻게 하면 될까요?

우리는 머리로 바로 알지만 컴퓨터는 하나하나 다 무엇을 해야하는지 풀어서 설명을 해줘야하죠?

그러면 그렇게 지정을 해 봅시다.

문자를 세는 문제로 쪼갰으니, 많이 생각하지 말고 문자 하나만 놓고 봐요!

그러면 위 문제를 다시 정리하면,
입력은 문자열 하나, 출력은 그 문자열에 대한 횟수를 반환한다고 생각해볼 수 있겠죠?

이를 컴퓨터에게 시키면 어떻게 할까요?

입출력을 분석했고, 쪼개서 단순화 시켰으니 이제 할일은 의사코드를 작성해보는 겁니다. 컴퓨터가 이해할 수 있도록 우리가 재구성한다고 생각하면 되요!

잠시 여기서 한번 생각해보시겠어요?

저는 아래와 같이 해볼 것 같아요.

1. 함수를 선언한다.
   
2. 선언한 함수에 횟수를 저장할 변수를 선언한다.
   
3. 입력은 문자열을 받는다.
   
4. 이때, 공백(' ')도 문자열이나, 본 문제에는 해당이 되지 않으므로 예외로 처리하며, 영문을 세는 것이므로 그 외의 입력은 예외로 처리한다.
   
5. 문자열이 들어오면 횟수를 저장할 변수에 + 1을 한다.
   
6. 횟수를 저장한 변수를 리턴한다.

이렇게 작성해볼 것 같아요.

그리고 코드로 옮기면 문자 하나에 대한 카운트 함수가 만들게 된 것이죠.

그러면 이를 확장해보는 겁니다.

여러개의 문자에 대해서 반복하면 되지 않을까?
그리고 단순히 +1만 할게 아니라, 전역 변수 등을 선언해서 각 문자에 맞춰서 해당 변수의 값을 변경하면 되지 않을까?

여러가지 해결법이 있겠지만, 이런식으로 확장해서 풀 수 있을 거에요.

여러가지 방법 중에서, 배열이나 전역변수 선언 같은 방법 말고 조금 더 테크닉적인 것을 다룰려고 해요.

이에 대해서 이제 알아볼까요?

값을 저장하는 방법

언어마다 다르긴 한데, 보통 이런 문제에 대해서는 key-value 쌍으로 이루어진 HashMap이라는 것을 이용해서 구하곤 합니다.

하지만, 이는 나중에 배울 내용으로 당장 이에 대해서 다루고자 하는 것은 아니니까 걱정하지 않아도 되요.

그러면 어떻게 값을 저장하면 될까요?

방법은 되게 단순해요. 값과 1:1로 매칭되는 무언가를 만들어두고, 그것을 +해서 반환하면 되요.

전역변수여도 좋고, 배열이어도 좋아요.

절차지향이라면 C를 기준으로 알파벳이 대문자 26개, 소문자 26개이니 대소문자를 구별한다고 하면 크기 52의 배열을 선언해서 전부 0을 넣고,
0~25번 원소를 A~Z라고 생각하고, 26~51번 원소를 a~z라고 생각해서 각각의 문자가 나올 때 해당 원소를 +1을 해주면 되죠.

객체지향 언어라고 한다면, 객체를 이용하면 됩니다!
외부에 별도로 값을 저장하는 변수를 선언하고 각 알파벳에 대응하는 속성을 생성한 후에, 객체의 속성의 값을 +해주는 것이죠.

참고로 속성은 객체에서 사용하는 변수를 가리킨다고 생각하시면 돼요!

javascript

{
    a: 0,
    b: 0,
    c: 0,
    ...
    x: 0,
    y: 0,
    z: 0
}

앞서서 문자열을 쪼갠 문자를 다룰 때, 함수안에 횟수를 저장할 변수를 선언했었잖아요?

이에 대한 내용을 위 객체의 프로퍼티를 +1 해주는 방향으로 구현하면 횟수를 셀 수 있겠죠?

방법의 차이는 있을 뿐 이처럼 값과 1:1로 대응하는 형태로 구현하는 게 빈도수 세기의 핵심입니다.

다만 여기까지 말하면, 단순 무식해보이잖아요?

이것의 매력은 어떻게 값을 저장할 것인가?하는 부분에서 발생해요.

가령, "djdyaac"를 다룬다고 하면 실제로 쓰이는 문자는 "d", "j", "y", "a", "c"로 5개 잖아요? 그런데, 여기에 쓰이지도 않는 "b", "d", "e"...와 같은 문자를 위해서 공간을 할당할 필요가 있을까요?

주어진 문자에 맞춰서 이를 셀 수 있게 만드는 게 빈도수 세기의 핵심입니다!

C와 같은 언어라면, 동적할당과 같은 방법을 통해서 주어진 값에 따라서 저장하는 공간을 변화하게 할 수 있겠죠?

객체 지향의 경우라면, 프로퍼티 생성을 동적으로 해서 값을 넣어볼 것 같아요.

javascript

const count = {};

if (count["문자"] !== undefined) count["문자"] = 1;
else count["문자"] += 1;

자바스크립트 같은 경우는 배열의 원소를 동적으로 할당할 수 있어서, 위와 같이 짤 수 있겠죠?
자바나 파이썬 같은 언어라면 별도로 프로퍼티를 추가하는 방식으로 해서 구현하면 되요!

이에 대한 의사코드는 아래와 같답니다.

객체의 프로퍼티에 문자 세기와 관련된 요소가 없으면 문자 프로퍼티를 생성하고 1로 초기화한다.
객체의 프로퍼티에 문자 세기와 관련된 요소가 있으면 +1을 해준다.

한번 동적으로 할당해서 구현해보시겠어요?
그리고 이렇게 하는 방법에 익숙해지시면 된답니다!

생각보다 자주 쓰는 기본 테크닉이면서, 매우 중요한 테크닉이에요. 코딩 테스트를 보거나 프로그램을 작성하면 공간 복잡도, 즉 프로그램이 동작하면서 얼마나 메모리 용량을 차지하느냐도 중요하거든요!

근데 별거 없죠? 하지만 이 역시 빈도수나 횟수를 세는 문제 풀이 방법 중 하나이기에, 알고리즘이랍니다. ㅎㅎ.

각자 언어에 구현에 맡기지만, 참고를 위해 자바스크립트로 문자에 대한 횟수를 세는 부분에 대한 코드를 작성해둘게요! 참고하셔서 직접 위의 문제에 대한 답을 구현해보시면 될 것 같아요!

자바스크립트를 사용하는 분들을 위해서, 이렇게도 작성할 수 있다는 것을 보여주기 위해 제가 작성하는 방법대로 작성해둘게요!

javascript

const count = {};

function countWord(word) {
  count[`${word}`] ? (count[`${word}`] += 1) : (count[`${word}`] = 1);
  return count[`${word}`];
}

문자열 포매팅과, 삼항 연산자를 사용했으니, 참고하세요!

예제 풀이

원리에 대해 알았으니 직접 구현을 해봐야곘죠?

다음을 풀어보시겠어요?

Q. 문제
일종의 말장난으로 어떠한 단어의 문자를 재배열하여 다른 뜻을 가지는 다른 단어로 바꾸는 것을 애너그램(Anagram)이라고 한다.
예시로, chaos를 구성하는 문자의 순서를 바꾸어 애너그램하면 shaco가 되고, neo를 애너그램하면 one이 된다.
어떤 두 문자열이 주어졌을 때, 둘이 애너그램의 관계에 있는지를 보이는 코드를 작성해라.

• 예시1. 입력 : shaco, chaos / 출력 : true
  예시2. 입력 : neo, coe / 출력 : false

추가로 이와 관련된 백준 문제도 있어서 첨부하니 백준으로 풀어도 괜찮아요!
백준 문제 링크

슬라이딩 윈도우

두번째로 배워볼 테크닉이자 알고리즘은 슬라이딩 윈도우(Sliding Window)입니다.

이에 대해서는 하나의 예제를 통해서 알아볼까요?

Q. 문제
3, 2, 1, 5, 4, 2, 6, 1 라는 연속된 숫자들이 주어질 때, 연속적인 3개의 숫자의 합이 최대가 될 때, 이때의 최대값은 무엇인가?

뒤의 내용을 읽기 전에 한번 풀어보시겠어요?

이에 대한 문제를 어떻게 풀 수 있을까요?

단순한 접근

반복문을 사용해서 풀 수 있지 않을까요?

$3 + 2 + 1$을 하고, 값을 저장해둔다음,
한칸을 이동해서 $2 + 1 + 5$를 하고
$1 + 5 + 4$를 하면서

앞에서부터 차근차근 더해서 더 큰 값을 저장 후 반환하는 것이죠.

코드로 한번 구현해보시겠어요? 그 전에 의사코드로 먼저 구현을 해보고 코드로 옮겨보세요!

하셨나요?

아래는 제가 구현한 의사코드와 자바스크립트로 작성한 코드입니다! 참고하시면 좋을 듯 해요.

의사코드

1. 최대값을 저장할 변수를 선언한다. 그리고 이를 0으로 초기화한다.
2. 3, 2, 1, 5, 4, 2, 6, 1을 [3, 2, 1, 5, 4, 2, 6, 1]과 같이 배열로 생각한다.
3. 반복 계수를 i로 두고, 0번 인덱스부터 (배열의 길이 - 3)번 인덱스까지 1씩 늘려가며 반복한다. 배열의 끝에 도달하면 반복을 종료한다.
4. 각 반복에서, (i번째 값) + (i+1번째 값) + (i+2번째 값)을 더한다.
5. 더한 값을 최대값 변수와 비교해서 더한 값이 더 큰 경우 최대값 변수에 저장한다.
6. 최대값 변수에 저장된 값을 반환한다.

코드

javascript

function calMax(numbers) {
  let max = 0;
  for (let i = 0; i < numbers.length - 2; i++) {
    const sum = numbers[i] + numbers[i + 1] + numbers[i + 2];
    if (sum > max) max = sum;
  }
  return max;
}

calMax([3, 2, 1, 5, 4, 2, 6, 1]);

위와 같이 표현할 수 있을 것 같아요!

단순한 표현의 문제점

위는 3개의 쌍을 구하니까 위처럼 표현했는데

배열의 길이가 백만(1,000,000)이라고 생각하고, 100개씩 더했을때 최대값을 구한다고 하면 어떻게 짤까요?

$$(i 번째 값) + (i + 1번째 값) + (i + 2번째 값) + ... + (i + 98번째 값) + (i + 99번째 값)$$

이렇게 구현을 해야할 것이에요.

천만일때 1000개씩 더한단면...?

어마어마하게 힘들것이고, 자원의 낭비도 심해지죠.

매번 루프를 돌때 덧셈을 1000번 반복하는 거니까요!

어떻게 해결할 수 있을까요?

발상의 전환

앞선 3, 2, 1, 5, 4, 2, 6, 1 문제 풀이에서, 어떻게 더해지는 지 다시한번 살펴볼까요?

[3, 2, 1], 5, 4, 2, 6, 1
3, [2, 1, 5], 4, 2, 6, 1
3, 2, [1, 5, 4], 2, 6, 1
3, 2, 1, [5, 4, 2], 6, 1
3, 2, 1, 5, [4, 2, 6], 1
3, 2, 1, 5, 4, [2, 6, 1]

위와 같이 진행되면서 값을 비교하는 것을 확인할 수 있었죠.

여기서 어떠한 규칙을 발견 할 수 있나요?

잠깐 글 읽는 것을 멈추고 생각해보세요! 이를 앞에서부터 하나씩 더했던 기존 방법 말고, 어떻게 생각해볼 수 있을까요?

잘 보면

[i, i+1, i+2] -> [i+1, i+2, i+3] -> [i+2, i+3, i+4]

이렇게 되는 것을 볼 수 있지 않나요?

즉, 제일 왼쪽의 것이 1개 빠지고, 뒤의 것이 1개 들어오는 것이지요.

더해야하는 수의 개수가 3개든, 100개든 1000개든 위와 같다는 게 보이시나요?

무엇이 되었든 제일 왼쪽의 값을 빼고, 오른쪽 값 1개를 더해주면 되는 것이지요.

이게바로 슬라이딩 윈도우 기법입니다.

[i, i+1, i+2]와 같이 순서대로 이동하는 경우, 다음에 나올 것과 교집합적인 요소를 공유하고, 그외는 빼거나 더해주면서 진행하는 방식을 슬라이딩 윈도우 기법이라고 합니다.

그러면 이제 3, 2, 1, 5, 4, 2, 6, 1 문제를 가지고 슬라이딩 윈도우를 써서 의사코드와 코드를 작성해보시겠어요?

작성하셨나요? 마찬가지로 제가 작성한 의사코드와 코드를 공유할테니 한번 해보세요!

의사코드

1. 주어진 숫자들의 집합을 numbers라는 배열로 간주한다.
2. 최대값을 저장할 변수를 선언한다. 이를 max라고 한다.
3. 합을 저장할 변수를 선언한다. 이를 sum이라고 한다.
4. numbers[0] + numbers[1] + numbers[2] 한 값을 sum과 max에 저장한다.
5. i를 1씩 증가하면서 1부터 (배열의 길이 - 3)까지 반복한다. 이때, i는 배열의 원소를 가리키는 인덱스가 된다.
6. 반복 안에서, sum = sum - numbers[i-1] + numbers[i+2] 를 해준다.
7. sum과 max를 비교해서 더 큰 값을 max에 저장한다.
8. max를 반환한다.

코드

javascript

function calculateMaxSum(numbers) {
  let sum = numbers[0] + numbers[1] + numbers[2];
  let max = sum;

  for (let i = 1; i < numbers.length - 2; i++) {
    sum = sum - numbers[i - 1] + numbers[i + 2];
    max = sum > max ? sum : max;
  }

  return max;
}

calculateMaxSum([3, 2, 1, 5, 4, 2, 6, 1]);

위와 같이 풀 수 있어요!

예제 풀이

이제 위의 테크닉을 알았으니 예제를 한번 풀어봐야겠죠?

백준 사이트의 21921번: 블로그 문제입니다.

백준 문제

한번 풀어보세요!

투포인터

미리 말하지만, C언어 에서의 포인터나, 이중포인터를 말하는게 아닙니다!

문제풀이 기법을 다룰거에요!

투포인터(two pointer), 더블포인터(double pointer) 등으로 불리는 기법입니다.

앞에서 배운 슬라이딩 윈도우가 일정한 구간을 옆으로 이동시키는 방법이었다면,

투 포인터는 리스트나 배열에 순차적으로 접근해야하는 경우에, 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 방법을 말해요.

즉 둘의 차이점은 구간의 길이가 변하냐 안변하냐의 차이이지요.

이 역시 문제를 통해서 확인해볼까요?

Q. 문제
3, 2, 1, 5, 11, 2, 6, 1 에서 연속된 수의 합이 18이 되는 경우를 찾아 리턴하시오. 값이 없는 경우 null을 리턴하시오

한번 풀어보시겠어요??

단순한 접근

어떻게 풀어보셨나요?

그러면 이제 같이 한번 풀이를 해볼까요?

제일 처음 접근할 수 있는 방법은 슬라이딩 윈도우 때와 동일하게 처음부터 하나씩 반복문을 통해서 풀어보는 거에요.

이중 반복문을 이용해서 푸는 것이지요.

제가 이 방식에 대해서 이야기 하기 전에, 이중 반복문으로 한번 풀어보시겠어요?

풀어보셨나요?

이제 그러면 같이 살펴봐요!

의사코드

1. 입력을 numbers라는 배열로 생각한다.
2. 합을 저장할 sum 변수를 선언한다.
3. 반복 변수 i를 0부터 (배열의 길이 - 2)번 인덱스 까지 1씩 증가시키면서 반복한다.
4. sum을 numbers[i]로 초기화한다.
5. 반복변수 j를 (i + 1)번 인덱스부터 (배열의 길이 - 1)번 인덱스까지 1씩 증가시키면서 반복한다.
6. sum에 numbers[j]를 더해준다.
7. 만약 sum이 18인 경우, i부터 j번 인덱스까지의 수를 배열에 담아서 리턴한다.
8. 만약 sum이 18보다 큰 경우 해당 루프를 벗어난다.
9. null을 리턴한다.

코드

javascript

function findSubarrayWithSum(numbers, targetSum) {
  for (let i = 0; i < numbers.length - 1; i++) {
    let sum = numbers[i];
    for (let j = i + 1; j < numbers.length; j++) {
      sum += numbers[j];
      if (sum === targetSum) {
        return numbers.slice(i, j + 1);
      } else if (sum > targetSum) {
        break;
      }
    }
  }
  return null;
}

// 테스트
const numbers = [3, 2, 1, 5, 11, 2, 6, 1];
const targetSum = 18;
const result = findSubarrayWithSum(numbers, targetSum);

console.log(result); // [5, 11, 2]

단순한 접근의 문제점

위의 방식으로 진행할 때 문제점이 무엇일까요?

고려할 경우의 수가 너무 많아진다는 것입니다. 반복문 안에서 또 반복을 하기 때문에, 각각 도는 횟수를 $n, m$이라고 하면, $O(n * m)$이라는 시간 복잡도가 나오는 것이지요.

시간복잡도를 따지지 않더라도, 배열의 크기가 클 수록 오래 걸린다는건 짐작이 되시나요?

실제로 이런 방식으로 코딩테스트를 풀거나 하면 아마 시간초과 되는 일이 발생할거에요.

이런 류의 문제를 쉽게 풀기 위해서 나온 게 투포인터 알고리즘이랍니다.

그럼 이제부터 알아볼까요?

해결 방법 : 투포인터

한번 다른 방식으로 어떻게 풀 수 있는지 생각해보시겠어요?

생각해보셨나요?

이름과 앞에 설명에서 짐작은 해보셨겠지만, 투 포인터 방식은 두개의 포인터를 두고, 이를 이동해가면서 구하는 방식이에요.
말로 설명하는 것보다 그림으로 설명하는 게 나을 듯 해서 그림으로 그려서 보여드릴게요.

투 포인터 방식에서는 보통 start와 end라는 변수를 두어서 부분 배열의 시작과 끝을 가리키는 변수로 활용해요.
그리고 이들이 곧 배열의 인덱스를 가리키는 포인터가 되지요.

그리고 합이 18이 가는 연속적인 부분 배열이 나올때까지 움직여갑니다.

아래의 그림을 보시겠어요?

참고로 아래 그림에서 start는 빨간 화살표, end는 녹색 화살표로 표기할게요.

투포인터 그림 1

투 포인터 방식에서는 위처럼 2개의 변수를 두고 처음 위치를 가리키게 해요.

그리고 문제의 조건이 합이 18이 되는 경우이므로 합을 저장하는 변수를 따로 선언해둡니다.

투포인터 그림 2

처음에는 단순한 방법처럼 end를 움직여가면서 합을 구해요. 그리고 18보다 클 경우 end를 그만 옮기면 됩니다! 한번 아래에 표현해볼게요.

그림 3

투포인터 그림 3

그림 4

투포인터 그림 4

그림 5

투포인터 그림 5

그림 6

투포인터 그림 6

위와 같은 경우에 멈추면 됩니다.
그러면 이제 어떻게 할까요? 한번 생각해보시겠어요?

start(빨간 화살표)를 한칸 옮기고, 초록색을 빨간색의 위치부터 다시 위의 과정을 반복할 수 있을 거에요.
하지만 이 역시 이중 반복문을 사용해야하기 때문에 앞서서 확인한 단순한 접근의 문제점을 똑같이 갖고 있어요.

투 포인터에서는 이렇게 하지 않고, 뒤에서 하나씩 증가해서 목표한 값을 초과했으니, 이제는 빨간 화살표를 옮겨서 하나씩 빼줘요.
합이 18보다 작아질때까지 빨간 화살표를 계속 움직이시면 되요.

그림 7

투포인터 그림 7

그림 8

투포인터 그림 8

위에 보시면 합이 17로, 18보다 작아졌죠? 그러면 빨간 화살표의 이동을 멈추고 다시 18보다 큰 값이 될때까지 초록 화살표를 이동하는 겁니다.

투포인터 그림 9

한칸을 이동했더니 합이 18이 되었습니다. 이제, 정답인 [1, 5, 11, 2] 를 반환하면 됩니다.

어때요? 투 포인터가 조금 감이 오시나요?
이게 투 포인터입니다!

투포인터의 장점

그러면 왜 투 포인터를 별도로 배우는 것일까요? 어차피 반복문을 사용하는건 같지 않나요?

코드를 작성하면 투 포인터의 진가가 보입니다!

위의 과정을 이해하셨으면 앞선 문제를 푸는 코드를 한번 작성해보시겠어요?

앞에서 작성해보라는 코드를 다 스킵했어도, 이번것은 한번 꼭 작성해보는 것을 추천드릴게요.
그래야 제가 작성한 코드를 보았을 때 조금 더 와닿을 것이기 때문이죠.

작성하셨나요?

그러면 살펴봅시다.

의사코드

1. 입력을 numbers라는 이름을 가진 배열로 취급한다.
2. start, end 변수를 선언하고 각각을 0으로 초기화한다.
3. sum을 선언하고, number[0]로 초기화한다.
4. start 혹은 end가 배열의 끝에 도달할 때까지 반복한다
5. 만약, sum이 18보다 작으면 end를 + 1을 하고 sum에 numbers[end]를 더해준다.
6. 만약, sum이 18보다 크면 sum에서 numbers[start]를 빼고, start를 +1을 해준다.
7. 만약, sum이 18이면 start부터 end까지의 값을 배열에 담아서 반환한다.
8. null을 반환한다.

코드

javascript

function findArr(numbers) {
  let start = 0;
  let end = 0;
  let sum = numbers[0];

  while (start >= numbers.length || end >= numbers.length) {
    if (sum < 18) {
      end += 1;
      sum += numbers[end];
    } else if (sum > 18) {
      sum -= numbers[start];
      start += 1;
    } else {
      let arr = [];
      for (let i = start; i < end + 1; i++) {
        arr.push(numbers[i]);
      }
      return arr;
    }
  }

  return null;
}

위와 같이 구현할 수 있을 듯 해요.
배열을 담기 위해서 내부에 for문을 썼지만, 사실 이는 없어도 되는 로직이고, 따지고보면 while문 안에서 반복이 이루어지는 것을 볼 수 있어요.
즉, 반복문이 하나면 끝나는 것이지요.

시간 복잡도를 생각해볼까요?
최악의 경우는 start와 end 모두 배열의 끝에 도달하는 것인데, 이는 각각 $O(N)$으로 표기가 가능해요.
$O(N) + O(N) = O(2N)$ 이지만, 빅오 표기법에 따라 $O(N)$으로 표현이 되요.

그래서 시간 복잡도는 $O(N)$이라고 볼 수 있는 데, 이는 앞에서 표현한 단순한 방법이 $O(N * M)$이었던 데에 반해서 어마어마하게 줄어든 것을 알 수 있죠?

이게 바로 투 포인터의 매력이랍니다.

어때요? 이해가 되셨나요?

예제 풀이

그러면 이제 문제를 풀어봐야겠죠?

백준 2003 : 수들의 합

백준 1644 : 소수의 연속합

백준 1806 : 부분합

위의 문제들을 풀어보시겠어요?

정리입니다

3가지 알고리즘에 대해서 배워봤어요.

• 빈도수 세기
• 슬라이딩 윈도우
• 투 포인터`

어때요? 이 알고리즘을 잘 활용할 수 있겠나요?

알고리즘은 문제풀이 방법일 뿐이다를 보여주기 위해서, 그리고 실제로 바로 써먹을 수 있는 요소로 시작하고자 위 세 테크닉을 먼저 학습해봤습니다.

이제 다음은 재귀에 대해서 배워보고자 합니다.

그 전까지 해당 테크닉들이 몸에 익을 수 있도록 꼭 각각에 대해서 코드를 작성해보세요!

그럼, 화이팅입니다!