SomeThing, Sum Thing

이번에 풀 문제의 알고리즘은 Greedy Algorithm이다. 정답률은 27.3%이다. https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 들어가기 전. 그리디(Greedy) 알고리즘은 최적의 해를 구하기 위해 사용되는 알고리즘 중 하나로, 여러 가지 경우 중 하나를 선택해야 할 상황이 올 때 그 순간에 최적인 것만 선택해 나가는 방식을 진행하여 최종적인 해답에 도달하는 알고리즘이다. 해결방법. 문제를 분석해보자. 받을 수 있는 값은 음수, 0..

이제부터 Greedy Algorithm을 중점으로 풀어보도록 하겠다. 정답률은 39.1%정도이다. https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 들어가기 전. 그리디(Greedy) 알고리즘은 최적의 해를 구하기위해 사용되는 알고리즘 중 하나로, 여러가지 경우 중 하나를 선택해야할 상황이 올때 그 순간에 최적인 것만 선택해 나가는 방식을 진행하여 최종적인 해답에 도달하는 알고리즘이다. 해결방법. 문제를 분석해보자. P일 중 L일을 사용할 ..

이번에는 브루트포스(Brute force)의 문제 블랙잭을 풀어보았다. 정답률은 45.6%정도로 다소 높은편이다. https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 들어가기 전. 브루트포스(Brute Force)는 조합 가능한 모든 경우를 대입하는 해결법을 말한다. 간단하게 4자리 비밀번호를 맞추기 위해서 0000~9999까지 모든조합을 대입하는 방법을 브루트포스라고 한다. 블랙잭이란 카드게임은 숫자카드에 쓰여있는..

이번에는 기본 수학 1에 관련된 문제에서 제목이 'ACM 호텔'로 되어있는 문제를 풀었다. 정답률이 34%대이다. https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 호텔에서 사람을 배정하는 방식은 엘레베이터에서 가까운 호수에서 아래층부터 사람들을 배정하기 시작한다. 즉 엘리베이터를 바닥에 눕힌 형태로 본다면 우측 하단부터 좌측으로 하나씩 놓고 다 놓았다면 다시 우측에서부터 한 칸씩 쌓는다고 생각하면 편하다. 문제에서 방의 번호는 YX..

이번에는 기본 수학 1에 관련된 문제에서 제목이 '설탕 배달'로 되어있는 문제를 풀었다. 정답률이 33%대이다. https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 이 문제를 읽어보면 특정 N에 대한 무게가 들어오면 3KG과 5KG으로 나누어서 최소한 배달할 수 있는 개수를 출력하는 문제이다. 이 문제를 접근하는 방식이 다양하겠지만, 나는 최솟값을 구하는 것을 중점으로 풀었다. 최솟값을 구하기 위해서는 최대한 많은 양을 5KG으로 나누고 나머지를 3KG으로 ..

이번에는 기본 수학 1에 관련된 문제에서 제목이 '달팽이는 올라가고 싶다'으로 되어있는 문제를 풀었다. 정답률이 28%대이다. https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 코딩에 들어가기 앞서 관계식을 따져보자. 나무 막대 길이를 V라고 하고 달팽이가 낮에 올라가는 길이를 A 밤에 미끄러지는 B 라고 하고, 달팽이가 올라간 수를 n이라고 하자. 이때 달팽이가 n일만큼 올라갔다고 했을 때 나오는 관계식은 다음과 같다. $$A*n - B*(n-1)$$ n에 관련된 식으로 정리한 후 나무 막대 길이 부등..

이번에는 기본 수학 1에 관련된 문제에서 제목이 '손익분기점'으로 되어있는 문제를 풀었다. 정답률이 25%대이다. https://www.acmicpc.net/problem/1712 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 www.acmicpc.net 바로 코딩에 들어가기 전, 수식을 구해보자. 고정 가격은 a 가변 가격은 b 물품 가격은 c 판매대수를 n이라고 한다면, 손익분기점에 관련된 식은 다음과 같다. $$ a+b*n 0$$ 항상 부등호가 성립하지 않는 경우, 즉 좌변이 항상 0보다 작거나 같을 때 일 것이다. 그리고 n이 점점 ..

이번에 푼 문제는 백준 코딩 테스트 4344번 문제, '평균은 넘겠지'이다. 정답 비율이 낮아서 푼 문제인데 생각보다 그렇게 어렵진 않았다. 나도 오답이 한 번 떴었는데, 소수점 때문에 오답이 났었다. https://www.acmicpc.net/problem/4344 4344번: 평균은 넘겠지 대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. www.acmicpc.net 문제 유형은 리스트에 관련된 문제이다. def i_can_over_mean(): #테스트하는 숫자를 받는다. test_count = int(input()) #테스트 결괏값을 저장하는 리스트이다. result_arr = [] #테스트 횟수를 range를 통해 반복한다. for ..

https://www.acmicpc.net/problem/10818 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net 최소 최대 문제를 python3로 해결했다. def findmaxmin(): size = int(input()) maxnumber = None //null로 지정 minnumber = None //null로 지정 numArr = input().split() //받아온 값들을 numArr의 리스트로 저장 for i in numArr: //최소값이 null 이거나 ..