[Algorithm] 5주차 스터디 - 수학 / 이분탐색, 투포인터 / 해시

---

목차

1. 개념 정리

(1) 수학

(2) 이분탐색, 투포인터

(3) 해시

 

2. 5주차 필수 문제 풀이

(1) A - 베르트랑 공준 (백준 4948번)

(2) B - 게으른 백곰 (백준 10025번)

(3) C - 랜선 자르기 (백준 1654번)

(4) D - 어깨동무 (백준 27932번)

(5) E -  콰트로치즈피자 (백준 27964번)

---

1. 개념 정리

(1)  수학

1. 소수 판정법 
합성수 N에서 1을 제외한 가장 작은 약수는 ${\sqrt N}$
 ex) N = 18 → 2 ≤ $\sqrt 18$
 ex) N = 25 → 5 ≤ $\sqrt 25$
 ex) N = 21 → 3 ≤ $\sqrt 21$
즉, 2부터 $\sqrt N$까지의 수로 나누어지지 않으면 소수임을 알 수 있음. 시간 복잡도 $O(\sqrt N)$ 소요

2. 범위 내에서의 소수 판정법
(1) 범위 내의 각각 숫자들이 소수인지 판정
(2) 에라토스테네스의 체

• k를 제외한 k의 배수들을 모두 거르며 (False로 만든다.) 합성수를 제거해 나가는 방법

3. 최대 공약수

• 최대공약수(GCD): 두 자연수의 공통된 약수 중 가장 큰 약수
• 유클리드 호제법 - 두 수 A, B에 대해서 A를 B로 나눈 나머지를 r이라고 하면 GCD(A, B) = GCD(B, r)이다.
  ex) GCD(20, 12) = GCD (12, 8) = GCD(8, 4) = GCD(4, 0) = 4
• 최소공배수(LCM): A $\times$ B = GCD(A, B) $\times$ LCM(A, B)

4. 연립합동방정식

5. 이항계

[수학 연습 문제]

- 백준 1978번: 소수 찾기

- 백준 1929번: 소수 구하기

- 백준 11653번: 소인수분해

- 백준 6064번: 카잉달력 

- 백준 11050번: 이항계수1 

- 백준 11051번: 이항계수2

 

(2) 이분탐색, 투 포인터

1. 이분탐색(이진탐색)

• 오름차순 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법
• 선형탐색이 $O(N)$에 동작한다면, 이분탐색은 $O(logN)$에 동작한다.

2. Parametric Search

• 조건을 만족하는 최소/최댓값을 구하는 문제(최적화 문제)를 결정 문제로 변환해 이분 탐색을 수행하는 방법
• 이분탐색을 수행할 변수로 함수를 그렸을 때, 감소/증가함수여야 parametric search로 풀 수 있다.

3. 투 포인터

• 배열에서 원래 이중 for문으로 $O(N^2)$에 처리되는 작업을 2개의 포인터의 움직임으로 $O(N)$에 해결하는 알고리즘
• 투포인터와 이분탐색은 호환되는 문제가 많다.

[이분탐색 연습문제]

- 백준 1920번: 수 찾기

- 백준 10816번: 숫자 카드2

- 백준 18870번: 좌표 압축

- 백준 2295번: 세 수의 합

- 백준 1654번: 랜선 자르기

[투포인터 연습문제]

- 백준 2230번: 수 고르기

- 백준 1806번: 부분합

 

(3) 해시

해시: 키에 대응되는 값을 저장하는 자료구조로 insert, erase, find, update의 연산을 $O(N)$에 활용할 수 있다.

해시함수: 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수. 마치 카드 번호 16자리에서 뒷 4자리만 배열의 인덱스로 쓴 것과 같다.

충돌: 서로 다른 키가 같은 해시 값을 가지게 될 경우 발생하는 문제
ex) 5135에 Kim이 저장되어 있을 때, Kim이 0000 0000 0000 5135에 대응되는 Kim인지 9999 9999 9999 5135에 대응되는 Kim인지 알 수 없다.

충돌 회피 방안
1) Chaning: 각 인덱스마다 연결 리스트 (또는 C++ vector등의 동적 배열) 를 둬서 충돌 회피를 하는 방법
2) Open addressing: 각 인덱스에 바로 (키, 값) 쌍을 쓰는 방법으로, Linear Probing, Quadratic Probing, Double hashing 등을 활용한다.

C++을 사용할 경우, STL에 내장된 unordered_set, unordered_multiset, unordered_map 등을 활용하여 해시를 구현할 수 있다.

[해시 연습문제]

- 백준 7785번: 회사에 있는 사람

- 백준 1620번: 나는야 포켓몬 마스터 이다솜

---

2. 5주차 필수 문제 풀이

해당 주차는 Python을 사용했습니다.

 

(1)  A - 베르트랑 공준 (백준 4948번)

4948번: 베르트랑 공준

4948번: 베르트랑 공준

📢 풀이: 에라토스테네스의 체

✔️합성수 N에서 1을 제외한 가장 작은 약수는 $\sqrtN$ 이라는 효율적인 소수 판정법을 사용한다. 

✔️ 특정 구간의 소수를 구하는 것이므로 에라토스테네스의 체 알고리즘을 사용할 수 있다.

import sys

while True:
    n = int(sys.stdin.readline().strip())
    if n == 0:
        break

    cnt = 0

    for i in range(n+1, 2*n+1):
        if i == 1:
            continue
        elif i == 2:
            cnt += 1
            continue
        else:
            for j in range(2, int(i**(1/2))+1):
                if i % j == 0:  # i가 j로 나누어 떨어진다면
                    break       # i는 소수가 아님
            else:           # i가 나눠떨어지는 수가 없다면
                cnt += 1    # i는 소수임

    print(cnt)

참고: https://ji-gwang.tistory.com/218

(2)  B - 게으른 백곰 (백준 10025번)

10025번: 게으른 백곰

10025번: 게으른 백곰

📢 풀이: 투 포인터

✔️ 투 포인터의 응용인 슬라이딩 윈도우(구간의 크기가 일정할 때) 알고리즘을 사용할 수 있다.

✔️구간의 크기가 2k+1로 일정하기 때문에 두 개의 포인터가 아닌 하나의 포인터를 반복문과 함께 사용하여 해결한다.

import sys

n, k = map(int, sys.stdin.readline().rsplit())
ice = [0] * 1000001

for i in range(n):
    input = list(map(int, sys.stdin.readline().split()))
    amt = int(input[0])
    idx = int(input[1])

    ice[idx] = amt

next = 2*k + 1
window = sum(ice[:next])
result = window

for i in range(next, 1000001):
    window += (ice[i] - ice[i-next])
    result = max(result, window)

print(result)

참고: https://whwl.tistory.com/232

(3)  C - 랜선 자르기 (백준 1654번)

1654번: 랜선 자르기

1654번: 랜선 자르기

📢 풀이: 이분 탐색

✔️ 대표적인 parametric search 유형

✔️ N개를 만들 수 있는 랜선의 최대 길이(최적화 문제)를 랜선의 길이가 x일 때 랜선이 N개 이상인가 아닌가?(결정문제)로 바꾸어 풀 수 있다. 

import sys

k, n = map(int, input().split())

line = []
for _ in range(k):
    line.append(int(sys.stdin.readline().strip()))


def slove(x):
    cur = 0
    for i in range(k):
        cur += line[i] // x
    return cur >= n     # n개 이상 만들어지는지 아닌지 True-False로 반환


st = 1
en = 2 ** 31-1     # 0x7fffffff

while (st < en):
    mid = (st+en+1)//2  # st+en으로 하면, |st-en|=1 일 때 st가 계속 같을 수도 있음
    if slove(mid) == True:
        st = mid
    else:
        en = mid - 1

print(st)

(4)  D - 어깨동무 (백준 27932번)

27932번: 어깨동무

27932번: 어깨동무

📢 풀이: 정렬, 이분탐색

✔️사람들의 키 차이 h를 mid로 두고, 이분탐색을 수행하며 적당한 mid값 즉 h값을 찾을 수 있다.

import sys

n, k = map(int, input().split())
people = list(map(int, sys.stdin.readline().split()))
people.append(people[n-1])

result = sys.maxsize


def search(low, high):
    global result
    if low > high:
        return

    mid = (low+high) // 2
    count = check(mid)

    if k < count:
        search(mid+1, high)

    else:
        result = min(result, mid)
        search(low, mid-1)


def check(h):
    count = 0

    for i in range(n):
        me = people[i]

        if i == 0:
            after = people[i+1]

            if abs(after - me) > h:
                count += 1

        else:
            before = people[i-1]
            after = people[i+1]

            if abs(me - before) > h or abs(after - me) > h:
                count += 1

    return count


search(0, result)
print(result)

참고: https://velog.io/@lifeisbeautiful/백준-27932-어깨동무-Java

(5)  E -  콰트로치즈피자 (백준 27964번)

27964번: 콰트로치즈피자

27964번: 콰트로치즈피자

📢 풀이: 해시

✔️ 배열의 중복을 제거하기 위해 set 자료형을 사용한다.

✔️원소의 끝 6자리가 'Cheese'인지 확인하기 위해 음수 인덱싱을 활용한다.

import sys
from collections import Counter

n = int(input())
arr = sys.stdin.readline().split()

topping = list(set(arr))
cnt = 0

for item in topping:
    if item[-6:] == 'Cheese':
        cnt += 1

if cnt >= 4:
    print('yummy')
else:
    print('sad')

 

참고 자료 : 강좌 [실전 알고리즘] 0x12 ~ 0x15강 BaaaaaaaarkingDog