[8주차] 알고리즘

 

 

<백준 2212번>

 

 

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

2212번: 센서

문제

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

입력

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.

출력

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

 

 

1. 센서의 좌표를 오름차순으로 정렬하면, 인접한 센서들 사이의 거리를 쉽게 계산할 수 있다.
2. 거리가 가장 먼 순서대로 K-1번째까지 선택하는 이유는, 첫 번째와 마지막 센서는 항상 집중국에 포함되어야 하기 때문이다.
3. 선택한 센서들 사이의 거리의 합이 집중국의 수신 가능 영역의 길이의 합이 되므로, 이 값을 출력한다.
4. 이 알고리즘의 시간 복잡도는 센서의 좌표를 정렬하는데 O(NlogN)이 소요되고, 거리를 계산하고 정렬하는데 O(NlogN)이 소요되므로, 전체적으로 O(NlogN)의 시간 복잡도를 갖는다. 이는 입력의 크기에 따라 효율적인 알고리즘이다.

 

O(NlogN)은 알고리즘의 시간 복잡도를 나타내는 표기법 중 하나입니다. 이 표기법은 알고리즘의 실행 시간이 입력 크기에 비례하여 어떻게 증가하는지를 나타낸다. N은 입력의 크기를 의미하는데, 이 경우에는 센서의 개수를 나타낸다. logN은 로그 함수의 밑이 2인 로그를 의미하고, 따라서 NlogN은 N에 로그를 취한 값과 곱하는 것을 의미한다. 시간 복잡도를 O(NlogN)로 표현한 알고리즘은 입력 크기 N에 비례하여 실행 시간이 증가하며, N이 증가할수록 실행 시간이 로그 증가한다. 따라서, N이 증가할수록 알고리즘의 실행 시간이 비교적 느리게 증가한다.

 

 

 

1. 센서들의 좌표를 오름차순으로 정렬한다.

 

2. 인접한 센서들 사이의 거리를 계산한다.

 

3. 거리가 가장 먼 순서대로 K-1번째까지 선택한다. (K-1번째까지 선택하는 이유는 첫 번째와 마지막 센서는 항상 집중국에 포함되어야 하기 때문이다.)

 

4. 선택한 센서들 사이의 거리의 합을 출력한다.

 

 

 

N = int(input())  //센서의 개수
K = int(input())  //집중국의 개수

sensors = list(map(int, input().split()))  # 센서의 좌표

sensors.sort()  //센서의 좌표를 오름차순으로 정렬

distances = []  //인접한 센서들 사이의 거리를 저장할 리스트

//인접한 센서들 사이의 거리 계산
for i in range(1, N):
    distances.append(sensors[i] - sensors[i-1])

distances.sort(reverse=True)  //거리를 내림차순으로 정렬

//선택한 센서들 사이의 거리의 합 계산
total_distance = sum(distances[K-1:])

print(total_distance)

 

 

 

<2293번>

 

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

2293번: 동전 1

 

 

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

 

 

이 문제는 문제가 짧아서 생각보다 쉬울 줄 알았는데 동전의 가치가 달라 생각할 부분이 많았다. 이 문제는 동전의 가치를 조합하여 합이 k원이 되도록 만드는 경우의 수를 구하는 문제고, 동전의 가치는 중복으로 사용할 수 있고, 순서만 다른 것은 같은 경우로 취급한다. 찾아보니 동적 계획법을 활용하여 해결할 수 있다고 한다. 동적 계획법이란 큰 문제를 작은 문제 여러 개로 나누어 해결하는 알고리즘 기법이다. 

 

 

<dp[i] = i원을 만들 수 있는 경우의 수>

1. dp 리스트를 생성하고 초기값을 0으로 설정한다. dp 리스트의 인덱스는 0부터 k까지의 값에 대응한다.
2. dp[0]을 1로 설정하여 0원을 만들 수 있는 경우의 수는 1가지이다.
3. 동전의 가치를 하나씩 확인하면서, dp 리스트를 업데이트합니다. 현재 가치의 동전을 사용하여 j원을 만들 수 있는 경우의 수는 dp[j]에 추가된다. 이때, dp[j]는 이전 단계에서 j-현재 가치의 동전을 만들 수 있는 경우의 수(dp[j-coin])와 더해진다.
4. dp[k]를 출력한다.
5. dp 리스트를 사용하여 작은 문제의 답을 저장하고, 이를 활용하여 큰 문제의 답을 구한다.
6. dp[i]는 i원을 만들 수 있는 경우의 수를 나타낸다.
7. dp[0]을 1로 설정하는 이유는 아무 동전도 사용하지 않아도 0원을 만들 수 있는 경우의 수는 1가지이기 때문이다.각 동전의 가치를 하나씩 확인하면서, dp 리스트를 업데이트한다.
8. 현재 가치의 동전을 사용하여 j원을 만들 수 있는 경우의 수는 dp[j]에 추가된다. 이때, dp[j]는 이전 단계에서 j-현재 가치의 동전을 만들 수 있는 경우의 수(dp[j-coin])와 더해진다.

 

n, k = map(int, input().split())  // n: 동전의 종류, k: 목표 금액
coins = []
for _ in range(n):
    coins.append(int(input()))  //각 동전의 가치

dp = [0] * (k + 1)
dp[0] = 1  //0원을 만들 수 있는 경우의 수는 1가지

for coin in coins:
    for i in range(coin, k + 1):
        dp[i] += dp[i - coin]

print(dp[k])