[2025-1주차] 배열&문자열 복습

팔랑이·2025년 10월 26일

문자열 배열 알고리즘 자료구조

자료구조/알고리즘

목록 보기

13/19

취준을 하며 코테, 면접을 앞두고 자료구조/알고리즘 복습을 위해 스터디를 하기로 했다.
기간은 전에 했던 것처럼 8주차로 나눴다. 👉🏻 8주치 계획표
새로 알거나 잊고 있었던 것 위주로 작성할 예정이다.

오늘의 주제

배열 (Array) & 문자열 (String)

기본 배열 조작 (삽입, 삭제, 탐색)

문자열 처리 알고리즘

투 포인터 기법

슬라이딩 윈도우

이전 게시글

배열, 연결 리스트, 스택, 큐에 대해 이전에 공부했던 게시글
python과 Swift의 문자열 처리 방식에 대해 다뤘던 이전 게시글

투 포인터, 슬라이딩 윈도우

1. 투 포인터 (Two Pointers)

: 두 개의 포인터로 배열/리스트를 효율적으로 탐색하는 기법

양 끝에서 시작: 정렬된 배열에서 두 수의 합
Fast/Slow: 연결 리스트 순환 감지
같은 방향: 중복 제거, 조건 만족 원소 이동

핵심: 정렬된 배열의 특성을 활용해 불필요한 탐색을 제거하여 시간복잡도를 개선

합이 작으면 → 왼쪽 포인터만 이동

합이 크면 → 오른쪽 포인터만 이동
👉🏻 중첩 반복문 불필요!

예시: 브루트 포스로 구할 경우 O(n^2)의 시간복잡도를 가지는데, 투포인터를 활용하면 O(n)이 될 수 있다.

# Brute Force: O(n²)
def two_sum_brute(arr, target):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] + arr[j] == target:
                return [i, j]

# 투 포인터: O(n)
def two_sum(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target: return [left, right]
        elif s < target: left += 1
        else: right -= 1

처음엔 예시만 대충 보고 '모든 경우의 수를 탐색하지는 못하는거 아닌가?' 했었는데, 그래서 저 배열 arr은 미리 오름차순으로 정렬된 상태여만 하는 게 킥이었던 것

2. 슬라이딩 윈도우 (Sliding Window)

: 연속된 부분 배열/문자열을 효율적으로 처리하는 기법

슬라이딩 윈도우의 두 가지 유형:

고정 크기: k개 원소의 최대합
가변 크기: 조건 만족하는 최적 구간

핵심: 이전 계산 결과를 재활용

매번 k개를 새로 계산하지 않고,

이전 합에서 빼거나 더함
👉🏻 중복 계산 제거!

예시: 브루트 포스로 구할 경우 매번 k개를 합산해야 해서 O(k*n)의 시간복잡도를 가지는데, 슬라이딩 윈도우를 활용하면 O(n)이 될 수 있다.

# Brute Force: O(n×k)
def max_sum_brute(arr, k):
    max_val = 0
    for i in range(len(arr) - k + 1):
        max_val = max(max_val, sum(arr[i:i+k]))  # 매번 k개 합산
    return max_val

# 슬라이딩 윈도우: O(n)
def max_sum(arr, k):
    window = sum(arr[:k])
    max_val = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i-k]  # 하나 빼고, 하나 더하기
        max_val = max(max_val, window)
    return max_val

새로 푼 문제

1. 문자열 슬라이싱: 열 개씩 끊어 출력하기

word = input()
slice_var = 0

while slice_var + 10 < len(word):
    print(word[slice_var:slice_var+10])
    slice_var += 10
print(word[slice_var: len(word)])

마지막 리스트의 개수를 맞추려고 저렇게 나눈건데,
다른 사람들 풀이를 보니까 파이썬의 슬라이싱은
예를 들어서 N = "happy" 일 때, print(N[0:30]) 을 해도 전혀 오류가 나지 않고 "happy"가 출력된다고 한다;; 해보니 진짜 됨 ~~(와중에 처음에 틀리게 풀었다가 이것덕분에 맞은건 안비밀ㅎ)~~

이걸 활용해서 코드를 더 효율화? 할 수는 있지만, 모든 언어에서 그런 것도 아니고 논리적으로 저렇게 하는게 더 맞지 않을까?? 싶어서 그냥 수정 안하고 놔뒀다.

2. 투 포인터: 두 수의 합

len_list = int(input())
num_list = list(map(int, input().split(" ")))
sorted_list = sorted(num_list)
target_num = int(input())

pointer_start = 0
pointer_end = len_list - 1

target_count = 0

while pointer_start != pointer_end :
    current_sum = sorted_list[pointer_start] + sorted_list[pointer_end]
    
    if current_sum == target_num:
        target_count += 1
        pointer_start += 1
        pointer_end -= 1
    elif current_sum < target_num:
        pointer_start += 1
    else:
        pointer_end -= 1

print(target_count)

3. 슬라이딩 윈도우: DNA 비밀번호

arr_len, target_len = map(int, input().split(" "))
arr = input()
min_count = list(map(int, input().split()))


dna_dict = {'A': 0, 'C': 1, 'G': 2, 'T': 3}

first = 0
last = target_len
count = 0

current_count = [0, 0, 0, 0]

for i in arr[first:last]:
    current_count[dna_dict[i]] += 1


def check_if_valid(current_count, min_count):
    for i in range(0, 4):
        if current_count[i] < min_count[i]:
            return False
    return True


while last <= arr_len:
    if check_if_valid(current_count, min_count):
        count += 1

    if last == arr_len:
        break

    current_count[dna_dict[arr[first]]] -= 1
    current_count[dna_dict[arr[last]]] += 1

    first += 1
    last += 1

    
print(count)