close
프로필 배경
프로필 로고

Brynn Park

Algorithm/BOJ ・2025. 3. 20. fullscreen 넓게보기

[BOJ] 3273번: 두 수의 합 (two-pointer) / sliding window, hash set

728x90

 

문제 링크

https://www.acmicpc.net/problem/3273

 

 

 

TIL

  • 너무 쉬운 문제는 의심해보자 >> 효율성을 따지는 문제일 가능성 높음
    • 특히 범위가 100,000이 넘어간다면 무조건 시간 효율성 문제 !!! >> 무조건 O(NlogN) 이여야함

 

[ 투 포인터 (Two-pointer) ]

  • 투 포인터(Two-pointer) 알고리즘은 두 개의 포인터(pointer)를 사용하여 배열이나 리스트를 탐색하는 효율적인 알고리즘
  • 이 알고리즘은 정렬된 배열에서 특정 조건을 만족하는 요소를 찾거나, 최적화 문제를 해결할 때 유용함

✅ 투 포인터의 핵심 원리

  • 정렬된 배열에서 사용 !!!
    • 왜 정렬을 하는가?
    • 투 포인터 기법의 핵심은 두 개의 포인터(left, right)를 조정하여 목표 값을 빠르게 찾는 것입니다.
      정렬이 되어 있으면, 특정 조건을 만족하지 않는 경우 불필요한 탐색을 건너뛸 수 있습니다.
  • 배열의 두 개의 위치(포인터)를 설정하여, 특정 조건을 만족하도록 움직인다.
  • 일반적으로 왼쪽 포인터(left)와 오른쪽 포인터(right)를 사용하여 탐색을 최적화한다.
  • 정렬된 배열에서 활용하면 한 번의 순회(O(n)) 만으로 원하는 값을 찾을 수 있다.

 

📌 투 포인터의 주요 유형

1️⃣ 서로 다른 방향에서 이동하는 투 포인터 (Two Pointers from both ends)

  • 정렬된 배열에서 두 개의 포인터를 양 끝에서 시작하여 서로 중앙으로 이동하며 조건을 만족하는 값을 찾는다.
  • 주로 두 수의 합 문제, 특정 구간 찾기 문제에서 사용된다.

[ 예제 코드 ] - 💡 예제: 두 수의 합 문제

def two_sum_two_pointer(arr, x):
    arr.sort()  # 배열을 정렬해야 투 포인터 사용 가능
    left, right = 0, len(arr) - 1  # 양 끝에서 시작
    count = 0

    while left < right:
        total = arr[left] + arr[right]
        if total == x:
            count += 1
            left += 1  # 다음 조합을 위해 포인터 이동
            right -= 1
        elif total < x:
            left += 1  # 합이 작다면 left를 오른쪽으로 이동
        else:
            right -= 1  # 합이 크다면 right를 왼쪽으로 이동

    return count

arr = [1, 2, 3, 5, 7, 9, 10, 12]
x = 12
print(two_sum_two_pointer(arr, x))  # 결과: 3 (쌍: (3,9), (5,7), (2,10))

 

2️⃣ 같은 방향으로 이동하는 투 포인터 (Sliding Window)

  • 두 개의 포인터를 같은 방향으로 이동시키면서 특정 조건을 만족하는 구간을 찾는다.
  • 주로 최대 길이 연속 부분 배열, 최적의 구간 찾기 문제에서 사용된다.

[ 예제 코드 ] - 💡 예제: 연속 부분합이 x 이하인 최대 길이 구하기

def longest_subarray(arr, x):
    left = 0
    total = 0
    max_length = 0

    for right in range(len(arr)):
        total += arr[right]

        while total > x:
            total -= arr[left]
            left += 1  # left를 오른쪽으로 이동

        max_length = max(max_length, right - left + 1)

    return max_length

arr = [1, 2, 3, 4, 5]
x = 8
print(longest_subarray(arr, x))  # 결과: 3 (연속 부분배열: [1,2,3] 또는 [2,3,4])

 

🔥 투 포인터를 언제 사용할까?

  1. 정렬된 배열에서 특정 합을 찾는 문제 (두 수의 합)
  2. 연속된 부분 배열에서 최적의 값을 찾는 문제 (슬라이딩 윈도우)
  3. 두 배열을 비교하며 특정 조건을 만족하는 경우 (병합 정렬, 교집합 문제)
  4. 두 개의 리스트에서 공통 요소 찾기 (예: 두 개의 정렬된 배열에서 공통된 숫자 찾기)

 

[ 슬라이딩 윈도우 (Sliding Window) ]

  • 슬라이딩 윈도우(Sliding Window)는 배열이나 리스트에서 특정 구간(부분 배열, 서브스트링)의 최적해를 찾을 때 사용되는 효율적인 기법
  • 이 기법을 사용하면 불필요한 중복 연산을 줄이고 O(n) 시간 복잡도로 문제를 해결할 수 있음

✅ 슬라이딩 윈도우의 핵심 원리

  • 연속된 부분 배열 (Subarray) 또는 부분 문자열 (Substring)을 다룰 때 사용.
  • 윈도우의 크기를 조정하며 필요한 정보를 재활용하여 효율적으로 탐색한다.
  • 투 포인터(Two-pointer) 기법과 유사하지만, 고정 크기 또는 가변 크기의 윈도우를 유지하면서 문제를 해결한다.

📌 슬라이딩 윈도우의 유형

1️⃣ 고정 크기 (Fixed-size Sliding Window)

  • 윈도우의 크기가 고정된 경우, 주어진 크기의 연속된 요소들을 살펴보며 최적해를 찾는다.
  • 주로 평균 계산, 최대합, 최솟값 찾기 등의 문제에서 사용됨.

[ 예제 코드 ] - 고정 크기 슬라이딩 윈도우 (Fixed-size)

def max_subarray_sum(arr, k):
    n = len(arr)
    if n < k:
        return None  # 윈도우 크기가 배열보다 크면 계산 불가

    # 첫 번째 윈도우 합 계산
    window_sum = sum(arr[:k])
    max_sum = window_sum

    # 슬라이딩 윈도우 시작
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]  # 새로운 요소 추가, 왼쪽 요소 제거
        max_sum = max(max_sum, window_sum)

    return max_sum

arr = [2, 1, 5, 1, 3, 2]
k = 3
print(max_subarray_sum(arr, k))  # 출력: 9 (부분 배열: [5,1,3])

 

2️⃣ 가변 크기 (Variable-size Sliding Window)

  • 윈도우 크기가 변동되는 경우, 조건을 만족하는 가장 긴(혹은 짧은) 부분 배열을 찾는 데 사용된다.
  • 주로 연속된 부분 배열(Substring) 중 조건을 만족하는 최장 길이 찾기 문제에서 사용됨.

[ 예제 코드 ] - 주어진 배열에서 합이 x 이하인 가장 긴 연속 부분 배열의 길이를 구하라.

def longest_subarray(arr, x):
    left = 0
    total = 0
    max_length = 0

    for right in range(len(arr)):
        total += arr[right]  # 새로운 요소 추가

        while total > x:  # 조건을 초과하면 left를 이동하여 합을 줄임
            total -= arr[left]
            left += 1

        max_length = max(max_length, right - left + 1)  # 최대 길이 갱신

    return max_length

arr = [1, 2, 3, 4, 5]
x = 8
print(longest_subarray(arr, x))  # 출력: 3 (부분 배열: [1,2,3] 또는 [2,3,4])

 

 

🎯 슬라이딩 윈도우를 언제 사용할까?

  1. 연속된 부분 배열(서브어레이)에서 최댓값 또는 최솟값을 찾을 때
  2. 특정 조건을 만족하는 가장 긴(혹은 짧은) 부분 배열을 찾을 때
  3. 고정된 크기의 구간에서 값을 계산할 때 (예: 이동 평균, 최대합)
  4. 문자열에서 연속된 부분을 검사할 때 (예: 아나그램, 서브스트링 매칭)

 

 

[ 해시셋 (Hash Set) ]

  • 해시셋(Hash Set은 중복을 허용하지 않는 데이터 저장 구조로, 빠른 검색, 삽입, 삭제를 가능하게 하는 해시 테이블(Hash Table) 기반의 자료구조
  • Python에서는 set 자료형이 해시셋 역할을 함

🔍 해시셋의 핵심 특징

  1. 중복이 허용되지 않는다 → 동일한 값을 여러 번 추가해도 한 번만 저장됨.
  2. 순서가 없다 (Unordered) → 원소가 삽입된 순서를 유지하지 않음.
  3. 검색, 삽입, 삭제 속도가 빠름 → 평균 O(1) (최악의 경우 O(n))
  4. 해시 함수를 사용하여 값의 위치를 결정 → 충돌(충돌 시 O(n))을 최소화하여 빠른 접근을 보장.

🛠 해시셋 사용법 (Python set)

# 해시셋 생성
my_set = set()

# 값 추가 (중복 불가)
my_set.add(1)
my_set.add(2)
my_set.add(3)
my_set.add(1)  # 중복된 값 추가 → 무시됨

print(my_set)  # 출력: {1, 2, 3}

# 값 제거
my_set.remove(2)  # 존재하는 값 제거 (없으면 KeyError 발생)
print(my_set)  # 출력: {1, 3}

my_set.discard(10)  # 존재하지 않는 값 제거 → 에러 발생하지 않음

# 값 존재 여부 확인 (O(1))
print(1 in my_set)  # 출력: True
print(5 in my_set)  # 출력: False

 

 

🎯 해시셋 활용 예제

 

1️⃣ 중복 제거하기 (O(n))

💡 리스트에서 중복을 제거하고 고유한 값만 저장할 때 사용

nums = [1, 2, 2, 3, 4, 4, 5]
unique_nums = set(nums)
print(unique_nums)  # 출력: {1, 2, 3, 4, 5}

 

2️⃣ 특정 값 존재 여부 빠르게 확인 (O(1))

💡 리스트에서는 O(n)이 걸리지만, 해시셋에서는 O(1)로 빠르게 확인 가능

nums = {10, 20, 30, 40, 50}
print(30 in nums)  # 출력: True (O(1))
print(60 in nums)  # 출력: False (O(1))

 

3️⃣ 두 배열의 교집합 찾기 (O(n))

💡 리스트로 찾으면 O(n²), 해시셋을 사용하면 O(n)으로 최적화 가능

a = [1, 2, 3, 4, 5]
b = [3, 4, 5, 6, 7]

# 교집합 찾기 (O(n))
intersection = set(a) & set(b)
print(intersection)  # 출력: {3, 4, 5}

 

4️⃣ 배열 내 두 수의 합 찾기 (Two Sum 변형, O(n))

💡 해시셋을 사용하면 O(n)으로 최적화 가능!

def two_sum_hashset(arr, x):
    seen = set()
    count = 0

    for num in arr:
        if (x - num) in seen:
            count += 1  # 쌍 찾음
        seen.add(num)

    return count

arr = [1, 2, 3, 5, 7, 9, 10, 12]
x = 12
print(two_sum_hashset(arr, x))  # 출력: 3 (쌍: (3,9), (5,7), (2,10))

 

 

🔥 해시셋을 언제 사용해야 할까?

 

✅ 리스트에서 중복을 제거할 때 → set(list)
✅ 어떤 값이 존재하는지 빠르게 확인할 때 → if x in set:
✅ 두 리스트의 교집합을 찾을 때 → set(a) & set(b)
✅ 빠르게 데이터 추가/삭제할 때 → set.add(x), set.remove(x)
✅ 두 수의 합(Two Sum) 문제를 O(n)으로 해결할 때

 

💡 정렬된 순서가 필요하면 리스트, 빠른 검색과 중복 제거가 필요하면 해시셋! 🚀

 

 

 

 

[ 총 정리 : 투 포인터 vs. 해시셋 vs. 슬라이딩 윈도우 ]

 

 

 

[ 처음 코드 ] - 시간초과 (시간 초과날 줄 알았음,,) >> O(N^2) 이니까 ~

n = int(input())
numbers = list(map(int, input().split()))
target = int(input())

cnt = 0
for i in range(n):
    for j in range(i, n):
        if numbers[i]+numbers[j]==target:
            cnt += 1
print(cnt)

 

 

 

 

Code

투포인터 - O(NlogN)

def count_pairs_two_pointer(n, arr, x):
    arr.sort()  # 정렬 (O(n log n))
    left, right = 0, n - 1
    count = 0

    while left < right:
        total = arr[left] + arr[right]
        if total == x:
            count += 1
            left += 1
            right -= 1
        elif total < x:
            left += 1  # 합이 작으므로 더 큰 수를 선택해야 함
        else:
            right -= 1  # 합이 크므로 더 작은 수를 선택해야 함

    return count

# 입력 받기
n = int(input())
arr = list(map(int, input().split()))
x = int(input())

# 결과 출력
print(count_pairs_two_pointer(n, arr, x))

 

해시셋 - O(N)

def count_pairs(n, arr, x):
    seen = set()
    count = 0
    
    for num in arr:
        if (x - num) in seen:
            count += 1
        seen.add(num)
    
    return count

# 입력 받기
n = int(input())  # 수열 크기
arr = list(map(int, input().split()))  # 수열
x = int(input())  # 목표 합

# 결과 출력
print(count_pairs(n, arr, x))

 

 

 

 

'Algorithm > BOJ' 카테고리의 다른 글

[BOJ] 15683번: 감시 (DFS+백트래킹)  (0) 2025.03.21
[BOJ] 1253번: 좋다  (0) 2025.03.21
[BOJ] 2138번: 전구와 스위치 (Greedy)  (0) 2025.03.20
[BOJ] 2631번: 줄세우기 (LIS) / LIS 알고리즘 문제  (0) 2025.03.20
[BOJ] 1967번: 트리의 지름 (DFS)  (0) 2025.03.19
Algorithm/BOJ 관련 글
더 보기

티스토리툴바