조용하지않는개발Blog

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 소수!-> 소수 문제는 에라토스테네스의 체 문제라는 것을 인지해두자 그냥 for문으로 풀면 시간초과가 나오니 에라토스테네스의 체로 소수를 찾고 문제를 풀면 쉽게 풀 수 잇는 문제이다. import sys input = sys.stdin.readline start, end = list(map(int,input().split())) n_list = [False,False]+[True]*(end-1..

https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 소수!-> 소수 문제는 에라토스테네스의 체 문제라는 것을 인지해두자 그냥 for문으로 풀면 시간초과가 나오니 에라토스테네스의 체로 소수를 찾고 문제를 풀면 쉽게 풀 수 잇는 문제이다. import sys input = sys.stdin.readline while True: n = int(input()) if n==0: # 종료 시키기 break n_lis..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 연속된 몇개의 수를 더해서 큰 합을 구하는 문제이다. 입력을 통해 n이 최대 10만인것을 보아 n^2은 하면 안될것으로보인다. 그렇다면 dp(다이나믹 프로그래밍)문제일 것이라고 생각을하고 접근하였다. dp를 담을 리스트를 생성하고 임의의 수열에 처음부터 하나씩 비교하며 큰값을 dp에 작성하며 접근한다. 예제 문제를 통해 처음에 있는 10은 dp[0]에 10을 입력하고 이어..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 보았을때 동전의 총 n종류가 있고 그 가치의 합이 k로 만드는 문제인데 이때 필요한 동전의 개수를 최소로 하는 문제이다. 또한 동전의 가치 a가 오름차순으로 되어있다고한다. 오름 차순으로 되어있따는 것은 큰 값을 먼저 확인하고 k안에 포함이 된다면 빼주면서 계산하면 최소의 개수를 찾을 수있다..

https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 최소로 몇번 점프하는 문제여서 dp문제라고 파악하고 풀기 시작했다. n이 최대 1000번까지 있으니 빅오가 n2까지는 상관없을것으로 보인다. 이렇게 생각을하고 어떻게 하면 최대로 많이 이동하면서 할수있을까 고민을 했는데 맨뒤에서부터 끝까지 갈수있는 값을 찾게 하였다. 이동을 했다면 이동한 곳까지는 지우고 다시 최대로 갈수있는 곳을 찾게한다. 이렇게 반..

풀이 문제를 보았을때 알수있는 힌트 n개의 랜선이 있는데 k개의 똑같은 길이의 랜선을 만들려고한다. 이때 최대 길이를 구하라 k는 10,000이하 n은 1,000,000이하의 정수이다. 이를 보았을때 어떻게 하면 최대 길이를 찾을수있을까? 최대길이에서 1씩 하나씩 빼가며 확인한다? 결과는 나오겠지만 시간 초과가 될것같다. 그러면 좀더 빠르게 찾기 위해서는 어떻게 할까? 이진탐색을 통해 O(log n)으로 해결할 수 있다. 최소와 최대를 정하고 가운데에서 초과하면 가운데를 최대로 바꾸고 그렇지 않으면 가운데를 최소로 변경하여 최대길이를 찾을수있다. import sys input = sys.stdin.readline k,n=list(map(int,input().split(" "))) lenline=[] fo..

풀이 문제를 보았을때 알수있는 힌트 이친수? 0,1로 이루어진 이진수 중 다음 조건이 성립한다. 1. 0을로 시작하지 않는다. 2. 1이 연속 되면 안된다. 1