Algorithm TIL (240918)

TIL

Algorithm TIL (240918)

wnwlals13 2024. 9. 18. 19:16

> [백준] 입국심사 (3079)

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

🔥다시 풀기

문제 풀이 과정

주어지는 m과 심사시간 t의 최대 범위가 1,000,000,000 이므로 이 범위를 모두 순회하면 시간초과가 날 것으로 예상, 이분탐색으로 추측
그러나 이분탐색 범위를 어떻게 설정해야 하는지 난감했다.
Pain Point : 심사시간 최댓값 * 인원수를 최대 범위로 생각하면, 시간초과가 날 것으로 생각했다. log(10억 * 10억) 은 10억으로 시간초과가 날것이라고 생각했기 때문이다.
그러나 시간초과가 나지 않는 이유 : log(1,000,000,000 * 1,000,000,000) 은 log10^18로 결과값은 18이다. 이 때 이분 탐색을 하면서 매번 n개의 심사대만큼 순회한다고 해도 18 * 100,000 = 1,800,000이므로 1초 내외로 연산처리된다.

동작 과정

start, end 를 입국 심사 시간 최저값, 최고값* 인원수로 설정한다.
start 가 end보다 작을 때까지 while문을 반복한다.
- mid를 구하고, n개의 입국심사대를 돌면서 mid 일 때, 각 심사대의 통과 인원의 수를 합한다.
합이 m보다 크거나 같다면, 상근이와 친구들 모두 통과하게 되므로 ans에 계속해서 작은 값을 갱신한다.
그렇지 않으면 mid를 증가시켜야 하므로 start를 mid + 1로 옮겨준다.

문제 풀이

python

n, m = map(int, input().split())
t = []
for i in range(n) :
    t.append(int(input()))

start, end = min(t), max(t) * m

ans = end
while start <= end :
    total = 0 # mid초까지 입국심사 통과한 사람의 수
    mid = (start + end) // 2 

    for i in range(n) :
        total += mid // t[i] # mid초를 각 t로 나눈 수를 더하면 total을 구할 수 있음
        
    if total >= m : # 상근이와 모든 친구들의 수만큼 입국심사를 통과했다면
        end = mid - 1
        ans = min(mid, ans)
    else :
        start = mid + 1
        
print(ans)

회고 및 느낀점

이분 탐색은 logN의 시간복잡도를 가진다. 문제를 잘 읽고 조건을 잘 부여한다면 풀 수 있을 것이다.

다음번에는 문제를 읽고 풀이 방법이 생각이 나도록 연습해야 겠다.

> [백준] 뒤풀이 (14575)

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

🔥다시 풀기

문제 풀이 과정

주어지는 T의 범위가 10억이므로 이분탐색으로 풀었다.
다만, 이문제에서 어려웠던 부분은 각 사람들은 주량인 L과 R 범위 내에서만 술을 마실 수 있는데, S 이하로만 마셔야 하므로 어느 조건을 만족할 때, answer에 S를 담아야 하는지가 어려웠다.
다른 코드를 참고해보니, 이분 탐색을 할 때 사람들의 주량을 확인하면서. 아래의 두 지표를 비교했다.
- 1) 전체 T - 모든 사람들이 최소 주량으로 마실 때의 값
- 2) 중간값 - 최소 주량 과 최대 주량 - 최소 주량을 비교하여 더 작은 범위의 값
2번이 더 클 경우, 아직 사람들이 더 마실 수 있기 때문에 mid의 값을 더 낮춰 마시는 술의 양을 늘려줌
1번이 더 클 경우, 마실수 없기 때문에 mid의 값을 높여 마시는 술의 양을 줄여줌

문제 풀이

python

n, t = map(int, input().split())
arr = []

ans = float('inf')
start, end = -1, -1
maxSum, minSum = 0, 0
for i in range(n) :
    l, r = map(int, input().split())
    arr.append([l, r])
    
    minSum += l
    maxSum += r
    
    if start < l : start = l # 최소 주량들 중 max부터
    if end < r : end = r # 최대 주량들 중 max까지

# 모든 사람들이 최대 주량으로 마셨을 때 t보다 작거나, 최소 주량으로 마셨을 떄 t보다 크면, t를 정확히
# 맞출수 없으므로 -1을 리턴한다.
if minSum > t or maxSum < t :
    print(-1)
    exit()

while start <= end :
    total = t
    more = 0
    mid = (start + end) // 2 
    
    for i in range(n) :
        l, r = arr[i]
        
        total -= l # 모든 사람을 최소의 주량으로 먹인다.
        more += min(mid-l, r-l) # 정해놓은 S에서 - 최소 주량과 최대주량 - 최소 주량중 더 작은 범위를 계산한다.
        # 최소 주량만큼 먹었을 때 각 사람들이 더 먹을 수 있는 술의 범위
            
    # 사람들이 더 마실 수 있다면, mid 값을 더 줄여 줌
    if more >= total :
        ans = min(ans, mid)
        end = mid - 1
    else :
        # 사람들이 감당할 수 없다면, mid 값을 늘려줌
        start = mid + 1
        
print(ans if ans != float('inf') else -1)

회고 및 느낀점

이분탐색은 로직 구성의 틀은 변하지 않지만, 그 조건을 어떻게 잘 세우는지가 문제 해결의 핵심 포인트인 것 같다.

아직 이 조건을 세우는 것이 어렵다. 이분탐색 문제를 더 많이 풀어봐야겠다.

> [백준] N과 M (1) (15649)

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

문제 풀이 과정

백트래킹 대표 문제
1 부터 N깍지의 수중에서 중복없이 M개 고른 수열 출력하기

⭐️ 백트래킹

정의 : 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
1부터 5까지의 수중에서 3개를 고른다고 할 때(중복 없이)
- 길이가 3인 배열에 [1, , ]을 넣고 1을 방문 처리한다. 그리고 배열의 다음 순번으로 이동
- [1,2, ] 을 넣고 2도 방문 처리 한다. 그리고 배열의 다음 순번으로 이동
- [1,2,3]을 넣고 3도 방문 처리 한다. 이 때 배열의 원소 모두 채워졌으므로 1 2 3을 출력한다.
- 그리고 그 다음 수인 [1,2,4]를 넣고 4도 방문 처리한다. 위와 동일하게 배열의 원소 모두 채워졌으므로 1 2 4를 출력한다.
- 이러한 과정을 반복한다.

문제 풀이

python

# 자연수가 주어졌을 때 그 중 M의 길이인 수열을 모두 구해라. => 대표적인 백트래킹 문제
# 백트래킹 문제는 재귀로 풀었다.
# 중복없이 M개를 고른다.
# 출력은 사전순으로 출력한다.

n, m = map(int, input().split())
arr = [0] * (m+1) # 1부터 n까지의 자연수 중에서 m개를 뽑아 만든 수열
issued = [False] * (n+1) # 1부터 n까지의 자연수 사용여부 체크

def func(k) : # 현재 k까지의 수를 택했음
    # base condition
    if k == m : # m개를 모두 택했으면
        for i in range(m) :
            print(arr[i], end=" ") # 현재 arr에 기록해둔 수를 출력
        print()
        return
    for i in range(1, n+1) : # 1부터 n까지의 수에 대해
        if not issued[i] : # 아직 i가 사용되지 않았으면
            arr[k] = i  # k번째 수를 i로 정함
            issued[i] = True # i를 사용되었다고 표시
            func(k+1) # 다음 수를 정하러 한 단계 더 들어감
            issued[i] = False # k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지 않았다고 명시함.
            
func(0) # 처음에는 빈리스트에서 시작

> [백준] N과 M (3) (15651)

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

문제 풀이 과정

N과 M(1) 과 비슷하지만 중복 가능하게 뽑는 문제이다.
동일하게 백트래킹을 사용하되, issued를 통해 사용여부를 체크하지 않았다.

문제 풀이

python

n, m = map(int, input().split())
arr = [0] * (m+1)

def func(k) :
    # base condition
    if k == m : # m개를 선택했다면 수열 반환
        for i in range(m) :
            print(arr[i], end=" ")
        print()
        return
    for i in range(1, n+1) : # 중복 허용이므로 한번 뽑인 숫자도 다시 뽑을 수 있음
        arr[k] = i
        func(k+1)

func(0)

> [백준] N과 M (5) (15654)

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

문제 풀이 과정

N 개의 자연수가 주어지고 이 자연수 배열 중에서 M개를 골라야 한다.
다만, 중복 가능하다.

✨ 시간 초과 났던 이유

백트래킹은 최악의 경우, 지수시간복잡도를 가진다!
그래서 재귀 함수 내에서 N의 범위만큼 순회하는 경우, 2^10,000 번 연산하게 되어 엄청나게 큰 연산을 해야한다.
이를 고려하지 않고 범위를 N으로 설정하여 시간초과가 났었다. 이후 주어진 N개의 범위 만큼만 순회하도록 수정하여 통과할 수 있었다.

문제 풀이

python

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))

# 중복 제거
maxNum = max(arr) + 1
nums = [0] * (m+1)
issued = [False] * maxNum

def func(k) :
    if k == m :
        for i in range(m) :
            print(nums[i], end=" ")
        print()
        return
    for i in arr :  # 백트래킹은 최악의 경우, 지수시간 복잡도를 가진다. 2^10,000의 연산을 한다면 엄청나게 큰수이므로 시간초과가 날 가능성이 있다.
        if not issued[i] :
            nums[k] = i
            issued[i] = True
            func(k+1)
            issued[i] = False

func(0)

회고 및 느낀점

백트래킹 문제를 오랜만에 풀어서 재귀 코드 구현하는 방법을 까먹었었다. 백트래킹은 현재 상황에서 가능한 한 모든 후보군을 따라 들어가며 탐색하는 알고리즘! 인 것을 잊지 말도록 하자. 때문에 N이 30만 되어도 10억의 연산횟수로 시간초과가 날 확률이 높다는 것 또한 명심!

코딩은 푸는 만큼 는다. 생각을 잃지 않도록 매일매일 문제를 풀어보자!

이제 추석도 다갔다... 정말 취뽀를 위해 달려보자..!