whatasame's algorithm

  • 신규 아이디 추천

    2023년 12월 28일 • String • Programmers

    📋 문제 정보

    문제 요약

    주어진 7단계의 과정을 구현하기

    🤔 아이디어

    정규식을 사용하든 반복문과 조건문을 사용하든 구현만 하면 되는 문제다. 다만 문제를 푸는 과정에서 Python 정규식과 인덱스에 대한 내용이 헷갈려서 정리한다.

    💭 생각 정리

    Python에서 정규식

    Java에서 정규식을 많이 다뤘기에 정규식을 생각하는 것은 별로 어렵지 않았다. 그러나 Pattern을 컴파일하고 사용해야하는 Java와 달리 Python에서는 패턴을 직접 리터럴로 사용할 수 있었다.

    # 컴파일 후 사용
pattern = re.compile(r'[^a-z\d\-\_\.]')		    
new_id = re.sub(pattern, '', new_id)

# 리터럴 사용
new_id = re.sub('[^a-z\d\-\_\.]', '', new_id)

    List index 정리

    Python에서 마지막 원소에 접근하는 -1 인덱스는 원소가 없으면 런타임 에러가 발생한다.

    ""[-1] # out of index

    그러나 슬라이싱의 경우 해당 인덱스가 존재하지 않더라도 가능한 범위까지 적용되고 런타임 에러는 발생하지 않는다.

    "abcde"[:1000] # "abcde"

    📄 소스 코드

    import re

def solution(new_id):
    # 1단계
    new_id = new_id.lower()
    
    # 2단계
    new_id = re.sub('[^a-z\d\-\_\.]', '', new_id)

    # 3단계
    new_id = re.sub('\.+', '.', new_id)
    
    # 4단계
    new_id = re.sub('^\.|\.$', '', new_id)
    
    # 5단계
    if not new_id:
        new_id = "a"
    
    # 6단계
    new_id = new_id[:15]
    if new_id[-1] == ".":
        new_id = new_id[:-1]
    
    # 7단계
    while len(new_id) <= 2:
        new_id += new_id[-1]
    
    return new_id

  • 디스크 컨트롤러

    2023년 12월 25일 • Heap • Programmers

    📋 문제 정보

    문제 요약

    응답시간의 평균이 가장 작을 때 평균을 소수점을 버려서 반환

    🤔 아이디어

    핵심 알고리즘

    현재 시간에 들어온 요청이 있다면 모두 최소힙에 저장한다. 이때, 최소힙의 기준은 소요시간이다. 소요 시간이 가장 짧은 요청부터 처리해야 후보의 수를 최대한 줄일 수 있기 때문이다.

    현재 힙에 후보가 5개 있을 경우 단순히 계산하면 1초당 응답 시간이 5초씩 늘어난다. 따라서 후보의 수를 빠르게 줄일 수 있도록 소요시간이 짧은 요청부터 처리한다.

    의사 코드

    # jobs를 시작 시간 순으로 정렬

# jobs 혹은 heap을 모두 소모할 때까지
    # 현재 처리할 수 있는 요청 모두 힙에 넣기
    # 힙이 비어있다면 1초 째깍
    # 힙 소모
        # 현재 시간 갱신
        # 응답 시간 갱신

    시간 복잡도

    단계별 시간 복잡도는 다음과 같다.

    • jobs 정렬: $O(nlogn)$
    • 전부 소모: $O(n)$

      • 현재 처리할 수 있는 요청 모두 힙에 넣기: $O(k)$

        $k$: jobs에 남아있는 $n$의 수

      • 1초 째깍: $O(1)$
      • 힙 소모: $O(log(n-k))$

    따라서 전체 시간 복잡도는 $O(nlogn)$이다.

    🖨️ 입출력 분석

    시간 복잡도 분석

    • 사실 $n$이 500이하이므로 힙을 사용하지 않고 시간 복잡도가 더 큰 풀이도 가능하다.

    추가 테스트 케이스

    [[2, 7]]
-> 7

    [[0, 1], [0, 3], [0, 5]]
-> (1 + 4 + 9 = 14) / 3 = 4

    [[1, 3], [11, 33], [50, 5]]
-> (3 + 33 + 5 = 41) / 3 = 13

    [[1, 9], [2, 5], [3, 4]]
-> (9 + 17 + 11 = 37) / 3 = 12

    💭 생각 정리

    힙을 하나만 소모해야한다

    처음에 짠 코드는 한 번의 while문에서 모든 힙을 소모했다. 그러나, 한 번에 하나만 소모해야한다. 예를 들어 7초에 다음과 같은 요청이 힙에 있다고 가정하자.

    [[7, 10], [7, 20]]

    이때 [8, 1]이라는 요청이 있다면 어떨까? 한 번에 모두 소모한 경우 다음과 같이 동작한다.

    [7, 10] -> [7, 20] -> [8, 1]

    의사 코드에서 의도한 대로라면 가장 짧은 요청부터 처리해야하는데 그렇지 못하다. 따라서, 한 번에 하나씩 소모한 후 힙을 업데이트해야한다.

    📄 소스 코드

    from heapq import *

def solution(jobs):
    n = len(jobs)
    
    # jobs를 시작 시간 순으로 정렬
    heapify(jobs)    
    
    heap = []
    now, res = 0, 0
    # jobs 혹은 heap을 모두 소모할 때까지
    while jobs or heap:
        # 현재 처리할 수 있는 요청 모두 힙에 넣기
        for req, time in find_targets(jobs, now):
            heappush(heap, (time ,req))
            
        # 힙이 비어있다면 1초 째깍
        if not heap:
            now += 1
            
        # 힙 소모
        if heap:
            time, req = heappop(heap)
            
            # 현재 시간 갱신
            now += time
            
            # 응답 시간 갱신
            res += now - req
    
    return res // n

def find_targets(jobs, time):
    if not jobs:
        return []
    
    targets = []
    while jobs:
        if jobs[0][0] > time:
            break
        targets.append(heappop(jobs))
        
    return targets

  • 17425번: 약수의 합

    2023년 11월 23일 • Prefix sum • BOJ

    📋 문제 정보

    문제 요약

    길이가 K인 구간의 합 중 가장 큰 값을 출력

    🤔 아이디어

    핵심 알고리즘

    nums가 [2, 3, 5]일 때 문제의 출력값을 구하기 위해선 다음과 같이 계산한다.

    • g(2) = f(1) + f(2)
    • g(3) = f(1) + f(2) + f(3)
    • g(5) = f(1) + f(2) + f(3) + f(4) + f(5)

    볼드로 강조된 부분들이 중복으로 계산되는데 이를 누적합으로 줄일 수 있다.

    \[g(n) = g(n - 1) + f(n)\]

    의사 코드

    divided_sums[num]: num의 약수들의 합

for num in [0, ..., 1_000_000]:
	divided_sums에 100만이하의 num의 배수를 더한다.
	누적합 갱신

return [divided_sums[num] for num in nums]

    시간 복잡도

    • 100만 이하의 num의 배수 덧셈: $O(logn)$
    \[n + \frac{n}{2} + \frac{n}{3} + ... + \frac{n}{n} = n(1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n})\] \[1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n} = O(logn)\]
    • 누적합 갱신: $O(1)$

    최종 시간 복잡도: $O(nlogn)$

    🖨️ 입출력 분석

    시간 복잡도 분석

    • n이 최대 100만이므로 효율적으로 약수를 구하는 알고리즘을 사용하더라도 $O(\sqrt{n})$이므로 $O(T*\sqrt{n})$은 100,000,000으로 시간 초과가 발생한다. 따라서 모든 수에 대하여 일일히 약수를 구하는 방법은 안된다.

    💭 생각 정리

    python3으로 제출하면 시간 초과

    pypy3으로 제출해야 시간초과가 발생하지 않는다.

    📄 소스 코드

    import sys

input = sys.stdin.readline
t = int(input())
nums = [int(input()) for _ in range(t)]

def solution(nums):
    divided_sums = [0 for _ in range(1_000_001)]

    for num in range(1, 1_000_001):
        for times in range(num, 1_000_001, num):
            divided_sums[times] += num

        divided_sums[num] += divided_sums[num - 1]

    return [divided_sums[num] for num in nums]

print("\n".join(map(str, solution(nums))))

  • 2559번: 수열

    2023년 11월 23일 • Prefix sum • BOJ

    📋 문제 정보

    문제 요약

    길이가 K인 구간의 합 중 가장 큰 값을 출력

    🤔 아이디어

    핵심 알고리즘

    7개의 숫자가 있을 때 구간의 크기가 5인 경우 구간은 다음과 같다.

    • 1, 2, 3, 4, 5
    • 2, 3, 4, 5, 6
    • 3, 4, 5, 6, 7

    이때 볼드체로 표시된 부분의 계산의 중복을 누적합으로 개선할 수 있다.

    의사 코드

    # 누적합: sums[i] = nums[0] + ... + nums[i]
sums = [0] * (n + 1)
nums = [0] + nums # index 패딩

# 누적합 계산
for idx in range(1, n + 1):
	sums[idx] = sums[idx - 1] + nums[idx]

# 모든 구간 중 가장 큰 값 구하기
for start in 구간이 가능한 곳:
	# start부터 k개의 구간합: sums[start + k - 1] - sums[start - 1]

    시간 복잡도

    • 누적합 계산: $O(n)$
    • 가장 큰 구간 계산: $O(n)$

    최종 시간 복잡도: $O(n)$

    🖨️ 입출력 분석

    시간 복잡도 분석

    • 수열의 원소 개수가 최대 10만개이므로 $O(nlogn)$이하의 알고리즘 사용

    유의사항

    • k = 3이고 구간의 시작은 start이면 구간의 끝은 start + 3 - 1이다. start + 3이 아니다.

    추가 테스트 케이스

    5 3
1 2 3 4 5
-> 12

    💭 생각 정리

    누적합을 구할 때 앞에 0을 패딩하는 이유

    누적합의 정의는 다음과 같다.

    sums[i] = nums[0] + ... + nums[i]

    누적합으로 구간합을 구하려면 다음과 같다.

    section(start, end) = sums[end] - sums[start - 1]

    이때, sums를 0부터 시작하면 sums[0 - 1] = sums[-1]이 발생한다.

    이러한 상황을 쉽게 처리하기 위해 앞에 0을 하나 패딩한다.

    구간이 가능한 곳의 범위

    1번째 수부터 n번째 수는 range(1, n + 1)로 표현할 수 있다.

    이때, k개의 원소를 가질 수 있는 start의 범위는 range(1, n + 1 - (k - 1))이 된다.

    range(1, n + 1 - k)는 start로부터 k개 떨어진 곳들의 모음을 나타내므로 다르다.

    📄 소스 코드

    import sys

input = sys.stdin.readline
n, k = map(int, input().split())
nums = list(map(int, input().split()))

def solution(n, k, nums):
    nums = [0] + nums
    sums = [0 for _ in range(n + 1)]

    # 누적합 구하기
    for idx in range(1, n + 1):
        sums[idx] = sums[idx - 1] + nums[idx]

    # 모든 구간 중 가장 큰 값 구하기
		answer = float("-inf")
    for idx in range(1, n + 1 - (k - 1)):
        result = sums[idx + k - 1] - sums[idx - 1]
        answer = max(result, answer)

    return answer

print(solution(n, k, nums))