요약
알고리즘 공부를 하면서 기억하고 싶은 이론들을 정리합니다.

목차

• 목차
• 병합정렬 (merge sort) - 개요 - 동작 원리 - 시간 복잡도
• 슬라이딩 윈도우 - 개요 - 동작 원리
• 투포인터 - 개요 - 동작 원리 - 시간 복잡도 - 문제 예시

병합정렬 (merge sort)

개요

• 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 전략을 사용.
• 배열을 작게 쪼갠 뒤 다시 합치면서 정렬을 완성.

동작 원리

분할 (Divide) 배열을 절반씩 나누어 더 이상 나눌 수 없을 때까지 분할 (원소가 1개가 될 때까지).

정복 (Conquer) 나눈 배열을 두 개씩 병합하면서 정렬된 상태로 합침.

결합 (Combine) 전체 배열이 정렬된 상태로 합쳐짐.

시간 복잡도

최선, 평균, 최악 모두: O(n log n) 병합 과정에서 추가 배열이 필요 → 공간 복잡도 O(n)

슬라이딩 윈도우

개요

• 배열이나 문자열에서 일정한 길이의 “창(Window)”을 좌우로 움직이며 문제를 해결하는 기법.
• 주로 연속 부분 배열/부분 문자열 문제에 사용됨.

동작 원리

1. 윈도우 크기 설정 문제에 맞게 고정 길이(k) 또는 가변 길이의 윈도우를 정한다.

2. 초기 윈도우 계산 처음 k개 구간의 합, 평균, 최대값 등 필요한 값을 구한다.

3. 슬라이딩 이동 윈도우를 오른쪽으로 한 칸 이동하면서,

4. 앞에서 빠지는 값 제거 새로 들어오는 값 추가

이 과정을 반복해 전체를 탐색한다.

투포인터

개요

투 포인터 기법은 두 개의 인덱스(pointer)를 사용해 배열이나 리스트를 탐색하는 알고리즘 기법이다.
주로 정렬된 배열에서 특정 조건을 만족하는 구간, 쌍(pair), 부분합 등을 효율적으로 찾을 때 사용한다. 일반적으로 브루트 포스(Brute Force) 방식이 O(n^2) 시간복잡도를 가지는 문제를 투 포인터로 O(N) 혹은 O(NlogN)으로 줄일 수 있다.

동작 원리

1. 포인터 초기화: 두 개의 포인터를 배열의 양 끝 혹은 시작 위치에 둔다.

• 예: 왼쪽 포인터(left), 오른쪽 포인터(right).

1. 조건 검사 및 이동:

• 두 포인터가 가리키는 값 또는 포인터 사이의 구간을 검사한다.
• 문제의 조건(예: 합, 길이, 정렬 여부 등)에 따라 포인터를 이동시킨다. -> 합이 목표보다 작으면 left를 이동. -> 합이 목표보다 크면 right를 이동.
• 조건을 만족하면 결과를 기록한 뒤 포인터 이동.

1. 종료 조건:

• 두 포인터가 교차하거나 배열 끝에 도달하면 탐색을 종료한다

시간 복잡도

• 일반적인 경우: 각 포인터가 배열을 한 번만 끝까지 이동하므로 O(N).

• 특정 변형 문제: 포인터 이동 과정에서 정렬이 필요하면 O(NlogN)이 추가될 수 있다.

  
  

문제 예시

hackerRank - Bear and Steady Gene