그리디24

• 

  [BOJ_1049] 기타줄 📌 문제 링크: https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: - 6개 묶음 패키지 가격과 낱개 가격을 각각 배열에 저장하고, 두 배열을 오름차순으로 정렬한다. - n이 값이 6보다 작거나 같은지 아니면 6보다 큰지 확인한다. - n의 값이 6보다 작다면, 패키지 가격의 최솟값과, 낱개 가격 * n개를 결괏값을 저장할 배열(answer)에 담는다. - n의 값이 6보다 크다면, 첨부한 코드의 .. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 30.

• 

  [BOJ_2828] 사과 담기 게임 📌 문제 링크: https://www.acmicpc.net/problem/2828 2828번: 사과 담기 게임 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 27.

• 

  [BOJ_1931] 회의실 배정 📌 문제 링크: https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 처음 제출한 코드에서는 중첩 for문을 사용해서 시간 복잡도가 O(n^2)으로 '시간 초과'로 인해 문제를 통과하지 못했다. 그래서 중첩 for문이 아닌 단일 for문으로 코드를 수정해서 문제를 해결할 수 있었다. 질문 게시판의 반례들이 항상 맞는 것은 아니다. 틀린 반례가 올려져 있는 경우도 있으니 주의해서 적용하자. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 27.

• 

  [BOJ_14916] 거스름돈 📌 문제 링크: https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 그리디 문제의 대표 유형인 거스름돈 문제이다. 입력값으로 주어진 N원을 2원과 5원의 동전으로 거슬러 줄 때, 거슬러 주는 돈의 개수를 최소한으로 만들어 반환해주면 되는 문제이다. 단순하게 생각해보면 5원의 개수를 최대한으로, 2원의 개수를 최소한으로 한다면 거슬러주는 동전의 개수를 최소한으로 만들 수 있다. (만약 입력값으로 10원이 주어졌다면 2원 동전 5개로 거슬러 줄 수도 있지만, 5원 동전 2개로 거슬러 주는 것이 더 적은 동전을 사용한다.).. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 21.

• 

  [BOJ_2839] 설탕 배달 📌 문제 링크: https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 그리디 알고리즘에 해당하는 유형의 문제지만, 설탕을 포장할 수 있는 경우를 모두 구하는 방법으로 풀이했다. 🚩 Idea: 1. 3kg의 봉지만 사용해서 포장할 수 있는 경우 2. 5kg의 봉지만 사용해서 포장할 수 있는 경우 3. 5kg의 봉지를 몇 개 사용하고, 나머지를 3kg의 봉지로 포장할 수 있는 경우 4. 3kg의 봉지를 몇 개 사용.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 10.

• 

  [BOJ_4796] 캠핑 📌 문제 링크: https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: - L, P, V의 값의 나눗셈을 통해 휴가 기간인 V에서 며칠 동안 캠핑장을 이용할 수 있는지 확인한다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 8.

• 

  [BOJ_2012] 등수 매기기 📌 문제 링크: https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net ❌ 내 풀이(Failure) : ✅ 내 풀이(Success) : 🧐 Review: 실패했던 풀이는 문제의 예제 입력처럼 변칙적이지 않은 데이터가 들어올 때는 정확히 값을 찾아낸다. 하지만 이 문제에서 학생의 수인 N의 범위는 1과 500,000 사이의 자연수 범위를 갖고, 예상 등수는 500,000 이하의 자연수이다. 그래서 학생의 수가 1명이지만, 본인이 예상 등수를 500,000까지도.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 7.

• 

  [BOJ_1541] 읽허버린 괄호 문제 링크: https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 내 풀이: Review: 약 20일 전에 주어지는 예시는 모두 통과했지만, 코드를 제출하면 런타임 에러가 발생하여 풀지 못했던 문제였다. 이 문제를 우연하게 다시 보게 되어 기존 코드의 어떤 부분에서 에러가 날지 생각해보고, 여러 가지 반례들을 대입해가며 코드를 수정하는 과정을 통해 문제를 해결할 수 있었다. 만약 이 문제를 풀며 런타임 에러가 발생한다면, '질문 검색' 게시판의.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 5. 8.

• 

  [BOJ_2217] 로프 문제 링크: https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 내 풀이: Review: 모든 로프를 사용하지 않아도 되기 때문에 하나의 로프를 사용하는 것부터 로프의 개수를 하나씩 늘려가며 최대로 견딜 수 있는 무게를 계산했다. 이때, 로프들의 정보를 입력받은 배열을 내림차순으로 정렬하여 견딜 수 있는 무게가 가장 큰 로프부터 개수를 셀 수 있도록 했다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 4. 13.

• 

  [BOJ_1026] 보물 문제 링크: https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 내 풀이: Review: 문제에서 요구하는 S의 값을 최소로 만들기 위해서는 A 배열에서 최댓값을 B 배열의 최솟값과 곱하고 그 결과를 더하는 과정을 통해 만들 수 있다. 문제의 조건에서 A 배열은 재배열을 하지만, B 배열을 재배열을 하면 안 된다는 조건이 있어서 A 배열만 역순으로 정렬을 하고, B 배열에서는 최솟값을 하나씩 꺼내 A 배열의 첫 번째 원소부터 곱하고 그 결과.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 4. 13.