본문 바로가기
728x90
반응형

그리디5

Leetcode 135 - Candy (Javascript) 1-pass 방식으로 풀기 https://leetcode.com/problems/candy/description/ 문제 난이도는 hard지만 기본 풀이법은 그다지 어렵지 않은 문제라고 생각햇다... 초기 풀이법(2-pass)1. 캔디 배열 1로 초기화 -> 무조건 1개는 받아야함2. 오른쪽으로 이동하면서 1차순회3. 다시 왼쪽으로 이동하면서 캔디 개수를 업데이트/** * @param {number[]} ratings * @return {number} */var candy = function(ratings) { let candies = Array(ratings.length).fill(1) for(let i = 0; i 0; i--) { if(ratings[i] a+b, 0)}; 근데 loop를 2번을 한다는.. 2025. 4. 22.
백준 16953 - A → B ( Python ) https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 그리디 알고리즘의 일종이라고도 볼 수 있는 것 같다 풀이 1. b가 짝수인 경우 2로 나눌 수 있음 2. 1로 끝나는 경우 1제거 3. 짝수이면서 1로 끝나는 경우는 없으므로 if ~ elif로 작성 풀이 방식을 떠올리는 건 어렵지 않았다. 하지만 1로 끝나는 경우 1제거하는 방식을 문자열로 치환후 slice하였는데 다른 사람 풀이를 확인해보니 10으로 나눈 나머지로 분기를 정할 수 있었다.. 문제의 전제가 숫자였으니 이런 방식도 떠올려야하는데 아직 알고리즘 풀이가 많이 부족하다ㅠ 힘내자... a, b = map(int,.. 2023. 1. 14.
백준 2217 - 로프 ( Python ) https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 예제풀이 n: 2 10 15 2개의 로프가 각각 10 15를 들 수 있음. 10인 로프는 10이 넘어가는 순간 끊어짐 예제의 최대 무게는 20이된다. n: 5 3 7 1 10 5 이런경우에는 줄을 5개를 쓰는 것이 불필요하다 1이 5개인 경우엔 고작 5까지밖에 못들지만 최대가 10이므로 하나를 쓰는게 더 나은 경우다 내림차순으로 정렬해보자 모든 경우의 수를 생각해보면 10 -> 10 7 .. 2022. 12. 1.
백준 5585 - 거스름돈 ( Python ) https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 그리디 알고리즘의 대표격이라고 할 수 있는 문제인 것 같다 제한시간: 10분 1. 모든 동전을 내림차순으로 정렬 2. 정렬한 배열을 순회하며 거스름돈을 해당 동전으로 나눈 몫을 카운팅 3. 나눈 몫 * 동전 를 거스름돈에서 빼준다. coins = [500, 100, 50, 10, 5, 1] pay = int(input()) change = 1000 - pay count = 0.. 2022. 11. 29.
백준 2839 - 설탕 배달 ( Python ) 2839 - 설탕 배달 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 예제 풀이 1. 18인 경우 18 -> 5로 나누어 떨어지지 않음 -3 count += 1 15 -> 5로 나누어 떨어짐 15 // 5 count += 3 count 4 2. 4인 경우 나누어 떨어지는 경우가 없으므로 -1 3. 6인 경우 6 -> 5로 나누어 떨어지지 않음 -3 count +=1 3 -> 5로 나누어 떨어지지 않음 -3 count +=1 0 -> 종료 count 2 4. 9인 경우 9 -> 5로 나누어 떨어지지 않음 -3 count.. 2022. 11. 17.
728x90
반응형

티스토리툴바