덧칠하기
어느 학교에 페인트가 칠해진 길이가 n미터인 벽이 있습니다. 벽에 동아리 · 학회 홍보나 회사 채용 공고 포스터 등을 게시하기 위해 테이프로 붙였다가 철거할 때 떼는 일이 많고 그 과정에서 페인트가 벗겨지곤 합니다. 페인트가 벗겨진 벽이 보기 흉해져 학교는 벽에 페인트를 덧칠하기로 했습니다.
넓은 벽 전체에 페인트를 새로 칠하는 대신, 구역을 나누어 일부만 페인트를 새로 칠 함으로써 예산을 아끼려 합니다. 이를 위해 벽을 1미터 길이의 구역 n개로 나누고, 각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호를 붙였습니다. 그리고 페인트를 다시 칠해야 할 구역들을 정했습니다.
벽에 페인트를 칠하는 롤러의 길이는 m미터이고, 롤러로 벽에 페인트를 한 번 칠하는 규칙은 다음과 같습니다.
- 롤러가 벽에서 벗어나면 안 됩니다.
- 구역의 일부분만 포함되도록 칠하면 안 됩니다.
즉, 롤러의 좌우측 끝을 구역의 경계선 혹은 벽의 좌우측 끝부분에 맞춘 후 롤러를 위아래로 움직이면서 벽을 칠합니다. 현재 페인트를 칠하는 구역들을 완전히 칠한 후 벽에서 롤러를 떼며, 이를 벽을 한 번 칠했다고 정의합니다.
한 구역에 페인트를 여러 번 칠해도 되고 다시 칠해야 할 구역이 아닌 곳에 페인트를 칠해도 되지만 다시 칠하기로 정한 구역은 적어도 한 번 페인트칠을 해야 합니다. 예산을 아끼기 위해 다시 칠할 구역을 정했듯 마찬가지로 롤러로 페인트칠을 하는 횟수를 최소화하려고 합니다.
정수 n, m과 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section이 매개변수로 주어질 때 롤러로 페인트칠해야 하는 최소 횟수를 return 하는 solution 함수를 작성해 주세요.
제한사항
- 1 ≤ m ≤ n ≤ 100,000
- 1 ≤ section의 길이 ≤ n
- 1 ≤ section의 원소 ≤ n
- section의 원소는 페인트를 다시 칠해야 하는 구역의 번호입니다.
- section에서 같은 원소가 두 번 이상 나타나지 않습니다.
- section의 원소는 오름차순으로 정렬되어 있습니다.
입출력 예
| n | m | section | result |
|---|---|---|---|
| 8 | 4 | [2,3,6] | 2 |
| 5 | 4 | [1,3] | 1 |
| 4 | 1 | [1,2,3,4] | 4 |
입출력 예 설명
입출력 예 #1
예제 1번은 2, 3, 6번 영역에 페인트를 다시 칠해야 합니다. 롤러의 길이가 4미터이므로 한 번의 페인트칠에 연속된 4개의 구역을 칠할 수 있습니다. 처음에 3, 4, 5, 6번 영역에 페인트칠을 하면 칠해야 할 곳으로 2번 구역만 남고 1, 2, 3, 4번 구역에 페인트칠을 하면 2번 만에 다시 칠해야 할 곳에 모두 페인트칠을 할 수 있습니다.
2번보다 적은 횟수로 2, 3, 6번 영역에 페인트를 덧칠하는 방법은 없습니다. 따라서 최소 횟수인 2를 return 합니다.
입출력 예 #2
예제 2번은 1, 3번 영역에 페인트를 다시 칠해야 합니다. 롤러의 길이가 3미터이므로 한 번의 페인트칠에 연속된 3개의 구역을 칠할 수 있고 1, 2, 3번 영역에 페인트칠을 하면 한 번에 1, 3번 영역을 모두 칠할 수 있습니다.
따라서 최소 횟수인 1을 return 합니다.
입출력 예 #3
예제 3번은 모든 구역에 페인트칠을 해야 합니다. 롤러의 길이가 1미터이므로 한 번에 한 구역밖에 칠할 수 없습니다. 구역이 4개이므로 각 구역을 한 번씩만 칠하는 4번이 최소 횟수가 됩니다.
따라서 4를 return 합니다.
🥨 나의 풀이
롤러로 칠해줄 수 있는 범위를 section에 맞게 업데이트를 해주고 싶었는데
잘 안되었다. 참고 풀이를 보니 그리디로 풀면 된다고 함
function solution(n, m, section) {
var answer = 0;
//answer 에 담아주기
// let wall = n / n
//return answer;
for(let i = 1; i <= n; i++){
// const roller = Math.floor(i / m)
console.log(i)
if(m >= section[section.length - 1]){
answer = 1
}
}
return answer
}🌿 정답 풀이
그리디 접근법
function solution(n, m, section) {
let answer = 0;
let check = section[0] + (m-1);
for (const val of section) {
if (val <= check) continue;
else {
check = val + (m-1);
answer++;
}
}
return answer + 1;
//반복이 종료되면 마지막 덧칠하는 것을 세지 못하므로 정답에 추가로 +1을 해주어서 반환
}function solution(n, m, section) {
let answer = 0;
let max = 0;
section.forEach((s) => {
if (s > max) {
answer++;
max = s + m - 1;
}
});
return answer;
}function solution(n, m, section) {
let answer = 0;
// 현재까지 칠한 구역
let part = 0;
// section을 forEach() 메서드로 하나씩 확인한다.
section.forEach((a) => {
// 현재 구역이 현재까지 칠한 구역보다 크다면
if (a > part) {
// 구역을 칠해주고 현재까지 칠한 구역을 업데이트 시켜준다.
part = a + m - 1;
// 페인트를 칠했으니 1증가 시킨다.
answer++;
}
});
return answer;
}🥥 Greedy algorithm
Greedy Algorithm(탐욕 알고리즘)은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 탐욕 알고리즘으로 문제를 해결하는 방법은 다음과 같이 단계적으로 구분할 수 있다.
- 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
- 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
- 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.
탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식이다. 그러나 항상 최적의 결과를 보장하지는 못한다는 점을 명심해야 합니다.
따라서 두 가지의 조건을 만족하는 "특정한 상황" 이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못한다. 탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립하여야 한다.
- 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다.
짐나르기 문제
김코딩과 박해커는 사무실 이사를 위해 짐을 미리 싸 둔 뒤, 짐을 넣을 박스를 사왔다. 박스를 사오고 보니 각 이사짐의 무게는 들쭉날쭉한 반면, 박스는 너무 작아서 한번에 최대 2개의 짐 밖에 넣을 수 없었고 무게 제한도 있었다.
예를 들어, 짐의 무게가 [70kg, 50kg, 80kg, 50kg]이고 박스의 무게 제한이 100kg이라면 2번째 짐과 4번째 짐은 같이 넣을 수 있지만 1번째 짐과 3번째 짐의 무게의 합은 150kg이므로 박스의 무게 제한을 초과하여 같이 넣을 수 없다.
박스를 최대한 적게 사용하여 모든 짐을 옮기려고 합니다.
짐의 무게를 담은 배열 stuff와 박스의 무게 제한 limit가 매개변수로 주어질 때, 모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 return 하도록 movingStuff 함수를 작성하세요.
function movingStuff(stuff, limit){
let count = 0; //옮긴 횟수
let sortedStuff = stuff.sort((a,b) => a - b);
while (sortedStuff.length !== 0){
if(sortedStuff[0] + sortedStuff[sortedStuff.length-1] <= limit){
//가장 가벼운 것 + 가장 무거운 것
count++;
sortedStuff.shitf(); //shift() 메서드는 배열에서 첫 번째 요소를 제거하고,
//제거된 요소를 반환합니다.
//이 메서드는 배열의 길이를 변하게 합니다.
sortedStuff.pop();
}else{
count++;
sortedStuff.pop(); //가장 무거운 걸 나른다.
}
}
return count;
}그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 "가장 큰 순서대로", "가장 작은 순서대로"와 같은 기준을 알게 모르게 제시해줌 -> 정렬 알고리즘과 짝을 이뤄 주로 출제
⛑ 거스름돈 -> 동전의 최소 개수
해당 문제는 큰 단위가 작은 단위의 배수 형태일 때만 가능
화폐의 단위가 무작위 -> 다이나믹 프로그래밍으로 해결
n =1260
count = 0
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count = count + n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수
n = n % coin # n %= coin
print(count)👯♀️ 어떤 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 그래도 찾을 수 없다면, 다이나믹 프로그래밍이나 그래프 등 고민하기
큰 수의 법칙
M의 크기가 100억 이상처럼 커진다면 시간 초과 판정을 받음
n, m, k = map(int,input().split())
data = list(map(int,input().split()))
data.sort() # 오름차순 정렬
first = data[n -1] # 가장 마지막이 큰 수
second = data[n - 2]
result = 0
while True:
for i in range(k):
if m == 0:
break
result += first
m -= 1
if m == 0:
break
result += second
m -= 1
print(result) n, m, k = map(int,input().split())
data = list(map(int,input().split()))
# 5 8 3
#2 4 5 4 6
data.sort() # 오름차순 정렬
first = data[n -1] # 가장 마지막이 큰 수
second = data[n - 2]
# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k + 1)) * k
count += m % (k +1)
#count = 6
result = 0
result += (count) * first #가장 큰 수 더하기
#result = 36
result += (m - count) * second # 두 번째로 큰 수 더하기
#result = 10
print(result) # 46 숫자 카드 게임
n , m = map(int,input().split())
result = 0
for i in range(n)
data = list(map(int, input().split()))
min_value = min(data)
result = max(result, min_value)
print(result)1이 될 때까지
# 25 5
n, k = map(int, input().split())
while n >= k:
while n % k != 0:
n = n - 1
result += 1
n = n // k
result += 1
while n > 1:
n -= 1
result += 1
print(result) 