아는게 없어서 쓰는 블로그 아는게 없어서 쓰는 블로그

1. 문제 9417번: 최대 GCD 첫째 줄에 테스트 케이스의 개수 N (1 < N < 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 양의 정수 M (1 < M < 100)개가 주어진다. 모든 수는 -231보다 크거나 같고, 231 -1보다 작거나 www.acmicpc.net 2. 해결방법 - 문제에서 큰 힌트를 직접 주었다. GCD 알고리즘을 이용하자 ! - 우선 우리가 구해야할 값은 두 쌍의 GCD의 최댓값이다. 각 테스트 케이스에서 주어진 수 중 2쌍씩 묶자 → 2중 for 문을 사용하고 중복은 제거해주었다. 묶은 2쌍들의 최대 공약수(GCD)를 구한 뒤 →유클리드 알고리즘 최댓값을 출력 ! 3. 코드 n = int(input()) numList = [list(map(int,i..

1. 문제 6219번: 소수의 자격 세 정수 A, B, D가 주어진다. www.acmicpc.net 2. 해결방법 N의 크기가 작았기에 에라토스테네스의 체 알고리즘을 사용하였다. [ 알고리즘/ Python ] 소수 구하기 : 에라토스테네스의 체 코테, 백준 문제를 풀다보면 '소수'를 구하는 문제가 꽤나 나온다. 소수를 사람의 손으로 풀기에는 다소 어려움이 있을 수 있다. 2,3,5,7 .. 정도는 괜찮지만 컴퓨터 암호화에 사용되는 아주 큰 소 0lrlokr.tistory.com 3. 코드 A = [False, False] + [True]*4000000 for i in range(2, 4000000): if A[i]: for j in range(i+i,4000000, i ): A[j] = False a,b..

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..