부품 찾기
전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유 번호가 있다. 어느날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 견적서를 요청했다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성하자.
문제
- 첫째 줄에 정수 N이 주어진다. (1 <= N <= 1,000,000)
- 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.
- 셋째 줄에는 정수 M이 주어진다. (1 <= M <= 100,000)
- 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다.
- 첫째 줄에 고백으로 구분하여 각 부품이 존재하면 yes, 없으면 no를 출력한다.
접근방법
다량의 데이터 검색은 이진 탐색 알고리즘으로 효과적으로 처리할 수 있다. 먼저 N개의 부품을 정렬한다. 그 다음 M개의 부품이 존재하는지 검사하면된다. 이렇게 문제를 풀면 최악의 경우 시간 복잡도 \(O(M * LogN)\) 의 연산이 필요해 이론산 최대 200만 번의 연산이 이루어 진다고 분석할 수 있다. 반면 N개의 부품을 정렬하기 위한 시간복잡도는 \(O(N * LogN)\) 으로 이론적으로 최대 약 2,000만의 연산이 필요하다. 결과적으로 이진 탐색을 사용하는 문제 풀이 방법의 경우 시간 복잡도는 \(O( (M+N) * LogN )\)이다.
코드1 (binarysearch)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| # 이진 탐색 소스코드 구현(반복문)
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) //2
#찾은 경우 중간점 인덱스 반환
if array[mid] == target:
return mid
# 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
elif array[mid] > target:
end = mid - 1
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
start = mid+1
return None
# N(가게의 부품 개수) 입력
n = int(input())
# 가게에 있는 전체 부품 번호를 공백으로 구분하여 입력
array = list(map(int, input().split()))
array.sort() # 이진 탐색을 수행하기 위해 사전에 정렬 수행
#M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인요청한 부품 번호를 공백으로 구분하여 입력
x = list(map(int,input().split()))
# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
# 해당 부품이 있는지 확인
result = binary_search(array,i,0,n-1)
if result != None:
print('yes',end=' ')
else:
print('no',end=' ')
|
1
2
3
4
5
| 5
8 3 7 9 2
3
5 7 9
no yes yes
|
코드2 (계수 정렬)
모든 원소의 번호를 포함할 수 있는 크기의 리스트를 만든 뒤에, 리스트의 인덱스에 직접 접근하여 특정한 번호의 부품이 존재하는지 확인한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| # N(가게의 부품 개수) 입력
n = int(input())
array = [0] * 1000001
# 가게에 있는 전체 부품 번호를 입력 받아서 기록
for i in input().split():
array[int(i)] = 1
# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력
x = list(map(int, input().split()))
# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
# 해당 부품이 존재하는지 확인
if array[i] == 1:
print('yes', end=' ')
else:
print('no', end=' ')
|
1
2
3
4
5
| 5
8 3 7 9 2
3
5 7 9
no yes yes
|
코드3 (집합 자료형 자료)
단순히 특정한 수가 한번이라도 등장했는지 검사하면 되므로 집합 자료형을 사용 가능하다. set()함수는 집합 자료형을 초기화할 때 사용한다. 단순히 특정 데이터가 존재하는지 검사할 때 효과적으로 소스코드가 간결하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
# N(가게의 부품 개수) 입력
n = int(input())
# 가게에 있는 전체 부품 번호를 입력 받아서 집합(Set) 자료형에 기록
array = set(map(int, input().split()))
# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력
x = list(map(int, input().split()))
# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
# 해당 부품이 존재하는지 확인
if i in array:
print('yes', end=' ')
else:
print('no', end=' ')
|
1
2
3
4
5
| 5
8 3 7 9 2
3
5 7 9
no yes yes
|
떡볶이 떡 만들기
떡 절단기에 높이 H를 지정하면 줄지어진 떡을 한번에 절단한다. 높이가 H보다 긴 떡은 H위의 부분이 잘리고 낮은 떡은 잘리지 않는다. 예를 들어 높이가 19, 14, 10, 17 cm인 떡이 나란히 있고 H를 15cm로 지정하면 잘린 떡의 길이는 4, 0, 0, 2 cm이며 손님은 6cm의 길이를 가져간다. 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큰의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
문제
- 첫째 줄에 떡의 개수 N과 요청한 길이 M이 주어진다. (1 <= N <= 1,000,000, 1 <= M <= 2,000,000,000)
- 둘째 줄에 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.
- 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력해야한다.
접근방법
전형적인 이진 탐색이자 파라메트릭 서치(Parametric Search) 유형이다. 파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 사용된다. 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다.
이 문제의 아이디어는 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해 조정하는 것이다. ‘현재 높이로 자르면 조건을 만족하는가?’를 확인한 뒤에 조건의 만족 여부에 따라서 탐색 범위를 좁혀서 해결할 수 있다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| # 떡의 개수(N)와 요청한 떡의 길이(M)을 입력
n, m = list(map(int, input().split(' ')))
# 각 떡의 개별 높이 정보를 입력
array = list(map(int, input().split()))
# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)
# 이진 탐색 수행 (반복적)
result = 0
while(start <= end):
total = 0
mid = (start + end) // 2
for x in array:
# 잘랐을 때의 떡볶이 양 계산
if x > mid:
total += x - mid
# 떡볶이 양이 부족한 경우 더 많이 자르기 (오른쪽 부분 탐색)
if total < m:
end = mid - 1
# 떡볶이 양이 충분한 경우 덜 자르기 (왼쪽 부분 탐색)
else:
result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
start = mid + 1
# 정답 출력
print(result)
|
Comments