주발이의 개발새발

1. 문제 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 해결 사실 해결 방법은 단순했다. - DP를 사용해자. - [ 알고리즘 ] 다이나믹 프로그래밍(DP) - 개념 - 문제에서 '구하라는 값'에 집중하자 → 나머지 값을 메모이제이션에 넣어보자 ~ 3. 코드 n = int(input()) dp= [0,1,1] for i in range(3,n+1): dp.append((dp[i-1]+dp[i-2])%1000000007) print(dp[n]) 4. 잊지말자 많이 헤멨던 문제다. DP를 배우기 전 그냥 재귀호출로만 풀다가 시간초과, 런타임 에러를 띄우고.. DP를 배우고 다시 돌아왔다. 하지만 메모리 ..

1. 문제 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 mCn을 구하면 답이다 ~~ ! ** 문제의 제한 덕분에 가능했던 것 같다. n,m

1. 문제 3040번: 백설 공주와 일곱 난쟁이 매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다. www.acmicpc.net 2. 해결 - 완전탐색 (Brute-Force)를 사용하여 풀었다. - 우선 아홉난쟁이 중 합이 100인 난쟁이 7명을 찾아야하는데 7명을 찾기보다는 아닌 2명을 제외하는 것이 더 간단해보인다. - (전체 합 - 아닌 두명의 숫자 합)을 통해서 구할 수 있다. - 나머지 2명이 중복되지 않게 2중 for 문을 사용해주었다. (아래에 예시 코드를 작성하였다) - 완전탐색을 하며 i,j를 찾아도 9C2 = 36으로 충분히 작은 수가 나오므로 완전..

1. 문제 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 2. 해결 - 우선 문제이해를 위해 666이 포함된 수열을 순서대로 써보았다. [666, 1666, 2666, 3666, 4666, 5666, 6660, 6661, 6662, 6663, 6664, 6665, 6666, 6667, 6668, 6669, 7666.. ] 처음에는 6660~6665를 놓치고 6666 6667 순서대로 작성하였다. 문제를 정말 꼼꼼하게 살펴보아야 할 것 같다. - 수열 앞 뒤로 배열을 넣어 정렬하려고 했다. 하지만 완전 탐색..

1. 문제 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 글만 읽어봤을 땐 이게 뭔말인고 .. 싶었다. 그래서 예제를 적어보고 스스로 답을 찾아보는 과정에서 알고리즘에 대해서 떠올랐다. 브론즈에서는 그냥 무작정 코드를 짜면 풀리는 문제가 많았는데 실버단계 문제부터는 이해가 중요한 문제가 많이 나오는 것 같다. 스스로 예제에 대한 답을 내려보는 과정을 습관들여야겠다. 2. 해결 해결방법을 떠올리는 것은 어렵지 않다. X1, X2, ... 을 배열로 두고 ** 중..

1.문제 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 2. 해결 - 고민이 많이 되었던 문제이다. 버블 정렬을 통해 하나씩 정렬해볼까도 생각해봤는데 .. - 계속 안되다가 힌트를 보고 BruteForce를 이용해보아야겠다 .. ~ 고 생각했다. ** BruteForce Algorithm -비교대상 문자열을 처음부터 끝까지 모두 순회하면서 비교하는 알고리즘 그렇다 .. n개의 덩치들(?)을 나머지 n-1개와 비교해서 본인보다 큰 덩치의 수를 알면 끝나는 문제.. ! 3. 코드 n = int(in..

1. 문제 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 2. 해결 - 소수의 조건을 생각해보았다. 소수는 약수가 2개인 수이다. 소수의 약수는 1과 자기자신인 수인데.. - 주어진 수(num)이 소수임을 확인하기 위해서는 num을 2부터 num-1까지 하나하나 나누어보면서 나머지가 0이 아님을 보이면 되겠다! - for문 if문을 적절히 사용하고 - cnt를 통해 탐색하고 있는 수(num)이 소수일 때 +1씩 해주면 되겠다 ! 3. 코드 n = int(input()) nums = list(map(int,input().split())) def isPrime(num): if n..

1. 문제 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 2. 해결 - 우선 얻은 금메달, 은메달, 동메달 수의 순서대로 리스트를 정렬한다. - sort, lambda함수를 이용하여 정렬하였다. - 등수를 찾을 때 for 문을 돌며 n과 함께 주어진 국가번호 k의 index(정렬한 리스트의 등수 -1) 를 찾는다. - 등수가 중복되는 국가의 공동 등수를 지정하기 위해 for문을 돌며 k국가의 모든 메달 수 가 같은 국가가 나오면 그 국가의 (index+1)등이므로 출력해준다. 3. 코드..

1. 문제 14593번: 2017 아주대학교 프로그래밍 경시대회 (Large) 아주대학교 프로그래밍 경시대회(Ajou Programming Contest, APC)는 2009년 제1회를 시작으로 2014년 제6회까지 개최된 아주대학교 학생들을 위한 프로그래밍 경시대회이다. 2017년, 다른 학교에서 활발히 www.acmicpc.net 2. 해결방법 3개의 정수를 입력받고 각각 내림차순, 오름차순, 오름차순으로 정렬하여 풀어야한다. 만약 람다함수를 몰랐다면 중복 체크때문에 코드가 조금 더 길어졌을 것 같다. 3.코드 n = int(input()) playes = [] for i in range(n): play = list(map(int,input().split())) playes.append(play) p..

1. 문제 15905번: 스텔라(STELLA)가 치킨을 선물했어요 경인지역 6개대학 연합 프로그래밍 경시대회 shake! 는 아주대학교, 경희대학교, 성균관대학교, 인하대학교, 한국항공대학교, 한양대학교ERICA가 함께하는 대학교 자체 연합 대회이다. shake! 는 매 www.acmicpc.net 2. 문제해결 정렬문제이다. 문제는 정렬해야할 대상이 2개라는 것 이때 문제해결을 쉽게 할 수 있는 함수가 바로 람다함수이다. 람다함수에 대해서는 아래 자세하게 설명하겠다 생각해본 알고리즘 - 입력받은 참가자들의 해결한 문제 수와 패널티 총 합을 입력받고 playes(이중 리스트)에 넣기 - playes를 해결한 문제 수 내림차순, 패널티 총 합 오름차순으로 정렬하기 - playes에서 5등의 해결한 문제 수..