Coder's Cattitude

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 문제에서 주어진 숫자 S를 서로 다른 자연수들을 N개 더해서 만드는데 N의 개수의 최댓값을 구하는 것이다. 쉽게 생각하면 작은 수인 1부터 2, 3,,, 차례로 더해가면 N이 최대가 된다 는 것을 생각하면 된다. 그래서 생각해낸 풀이 방법이 등차가 1인 등차 수열을 생각해서 등차수열의 합 공식을 사용하는 것이었다. temp = 1 + 2 + 3 +,,, + n까지 더한 값은 temp = n * (n + 1) / 2 로 구할 수 있다. 이 temp 값이 S값 커졌을 때의 n 값에서 1을 뺀 것이 바로 답이다. 1을 빼주는 이유는 200을 예를 들어서 설명하겠다 200에 가장 가까운 200보다 큰 temp 값은 n이 20인 210이다. temp가 210일 때 n값..

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 예외 ex1) 1 131 -1 ex2) 1 1111 5 📌 풀이 문제를 찬찬히 보면 A -> B를 만든다기보다는 B -> A를 만드는 것이 쉽다. 그래서 규칙을 찾아보면, [규칙] B의 일의 자리 수가 1이면, B에 B를 10으로 나눈 몫을 저장한다. B를 2로 나누었을 때 나머지가 0이면, B에 B를 2로 나눈 몫을 저장한다. 3. B를 2로 나누었을 때 나머지가 0이 아니면, ans에 -1을 저장하고 ans를 출력한다. while문을 탈출하는 방법은 3개이다. 3번 조건을 생각안해서 틀렸었다 [while문 탈출] A와 B가 같아졌을 때 B가 A보다 작아졌을 때 A로 B를 만들 수 없을 때 2번, 3번은 답이 -1이다. 🔑 python 코드 # A -> B impor..

Greedy (탐욕법) 1. 탐욕법 (Greedy) 탐욕 : 현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘 -> 매 순간 가장 좋아 보이는 것 을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 예외) 다익스트라 알고리즘 - 암기가 필요 그리디 알고리즘의 경우 많은 유형을 접해보고 문제를 풀어보며 훈련해야함 => 창의력 즉, 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함 => 단순히 현재 상황에서 가장 좋아보이는 것만을 선택해도 문제를 출 수 있는지를 파악할 수 있어야 함 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘임 => 문제에서 가장 큰 순서대로 혹은 가장 작은 순서대로 ..

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 1. 책의 위치를 받은 배열을 음의 정수(minus_loca)와 양의 정수(plus_loca) 두 개의 배열로 나눈다. 2. 음의 정수들을 배열에 넣을 때, 계산하기 편하게 -1을 곱해서 넣는다. 3. -1을 곱한 음의 정수와 양의 정수를 내림차순으로 배열에 넣는다. => 가장 큰 보폭인 애들끼리 묶어서 최대한 많은 양을 옮기기 위해 4. 음의 정수와 양의 정수 각각을 M칸씩 건너 뛰면서 새로운 배열(minus_step, plus_step)에 저장한다. => 최대로 들 수 있는 책의 개수만큼 옮길 책들의 묶음을 나눠줌 5. steps를 계산해준다. 5-1. minus_step의 인수 수가 0 인 경우, plus_step의 가장 큰 값은 steps에 한번만 더해..

🔒 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다. 신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가? ⌨ 입력 첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다. 두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다...

🔒 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 2..

🔒 문제 민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. ⌨ 입력 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어..

🔒 문제 지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다. 각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오. ⌨ 입력 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 ..

🔒 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. ⌨ 입력 첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000) 🖨 출력 상근이가 배달하는 봉지의 최소 개수를 출력한다...