주발이의 개발새발

1. 문제 https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 2. 해결방법 코알라 강의를 듣고난 후 푼 문제이다. 사실상 해결방안을 미리 알고 푼 문제 .. - 처음엔 누적합을 이용해보았다. obstacle이라는 배열을 두고 장애물을 모두 받은 뒤, imos배열에 (imos방식은 아닌데 왜 배열이름이 imos인가에 대해서는 너그럽게 양해해주시길 바란다.. ) 높이가 i일 때 obstacle이 몇개인지를 각각 알아보았지만 시간초과 ! - 이제 imos..

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

코테, 백준 문제를 풀다보면 '소수'를 구하는 문제가 꽤나 나온다. 소수를 사람의 손으로 풀기에는 다소 어려움이 있을 수 있다. 2,3,5,7 .. 정도는 괜찮지만 컴퓨터 암호화에 사용되는 아주 큰 소수는 판별하기 어렵다. 그럼 컴퓨터에게 이 소수를 구하라고 시키는 프로그램을 작성해보자 ~ 1. 소수 1과 그 수 이외의 자연수로는 나눌 수 없는 자연수 소수는 2,3,5,7...에서 볼 수 있듯 약수가 2개라는 특징을 가진다. 이러한 특징 때문에 1은 소수가 될 수 없다. import math n = int(input()) def isPrime(n): if n

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. 다이나믹 프로그래밍(DP)이란 ? 큰 문제를 작은 문제로 나누어 푸는 알고리즘 다이나믹 프로그래밍, 동적계획법은 문제를 어떤 형태로 변형시켜 쉽게 푸는 방법을 의미한다. * 여담이지만 '동적(Dynamic)'은 멋있어보여서 붙은 이름이라고 한다. 처음에 이 사실을 모르고 Dynamic에 집중해서 이 알고리즘을 보았는데 .. 계속 어느 부분이 동적으로 작동한다는 거지? 라고 생각했었다. 이 사실을 알고 나서는 '계획법'을 집중해서 보게 되었다.. ! 2. DP의 2가지 필수 조건 1) Overlapping Subproblem 같은 문제는 항상(구할 때 마다) 정답이 같다. 큰 문제가 작은 문제로 세분화될 수 있고, 같은 방법으로 풀릴 때 ex. 피보나치 수 - Fib(n-1) = Fib(n-2) + ..

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. 완전탐색 알고리즘이란 ? 컴퓨터의 빠른 계산능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 알고리즘 - 완전탐색 알고리즘 = Brute-force 알고리즘(무식하게 풀기) - 즉, 무식하게 모든 경우의 수를 다 따져가며 정답을 찾는 방식이다. 하지만 직관적이며 이해하기 쉽고 문제의 정확한 결과를 얻을 수 있는 가장 기초적인 방식이다. 예시를 한번 살펴 보자 4자리의 암호로 구성된 자물쇠를 풀려고 시도한다. 이 때, 자물쇠가 정상적으로 작동한다면 반드시 해결할 수 있는 문제이다. 0000~9999까지 모든 경우의 수를 다 입력할 수 있기 때문이다. 물론 사람의 손으로 작동시킨다면 아주 오랜 시간이 걸릴 것이다. 하지만 우리에게는 위대한 발명품이 있다. 바로 연산속도가 매우 빠른 컴퓨터 ..