본문 바로가기

알고리즘이야기/백준10

6588번 골드바흐의 추측 문제 출처 : https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. www.acmicpc.net 바로 이전문제가 하나하나 소수를 찾았던 코드를 짠 문제였는데 바로 에라토스테네스의 체를 사용한 문제가 나왔다. 이 문제는 이전처럼 코드를 짜면 시간초과가 난다..! 그래서 에라토스테네스의 체를 사용하여 문제를 풀었더니 바로 성공했다! import sys result=[] s=[True]*1000001 for k in range(2,1000001): if s[k]==True: fo.. 2020. 6. 25.
1978번 소수 찾기 문제 출처 : https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 에라토스테네스의 체를 사용하지 않고 하나하나 찾아주는 코드를 짜보았다. 물론 에라토스테네스의 체를 알기 전 풀었던 문제이다 ㅎㅎ,, 하지만 이렇게 풀면 시간초과 날 확률이 매우 크기 때문에 에라토스테네스의 체를 사용하는 것을 무척이나 추천드립니다..!!! import sys T=int(input()) result=[] for _ in range(T): A=list(map(int, sys.stdin.readline().split())) for i in .. 2020. 6. 25.
1934번 최소공배수 문제 출처 : https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있� www.acmicpc.net 이전 최대공약수, 최소공배수와 비슷한 유형이다. 직접 찾아주는 코드를 짰고, 더 간단한 코드로 만들어야겠다,, 그리고 이전에도 말했듯이 백준에서 시간을 좀 더 줄이기 위해 항상 import sys를 사용한다..! import sys def solve(A): for i in range(1,min(A)+1): if not A[0]%i: if not A[1]%i: r.. 2020. 6. 25.
2609번 최대공약수와 최소공배수 문제 출처 : https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 정말 문제제목 그대로 최대공약수를 구하고 구한 최대공약수(max(result))를 이용해서 최소공배수를 구했다. 아직 내 머리에서는 주어진 문장 그대로? 해석해서 푸는게 덜 어려운가보다,, 나중엔 최대공약수, 최소공배수를 함수로 쉽게 구해야지ㅠ_ㅠ import sys A=list(map(int, sys.stdin.readline().split())) result=[] for i in range(1,min(A)+1): if not A[0]%i: if .. 2020. 6. 10.
1260번 DFS와 BFS 문제 출처 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 내가 제일 어려워하고 시도조차 하지 않(못)했던 BFS와 DFS,,,,,,,, 진짜 관련 문제 나올때마다 자연스럽게 쓰루~,,,,,, ㅎㅎㅎ,, 근데 이젠 정말 정면돌파 해야할 것 같아서 블로그마다 개념을 다시 찾아보고 코드를 이해하려고 노력했다. 그래서 많은 코드와 방법 중 제일 이해가 잘 되었던 바로 아래의 코드..! 내 방식대로 조금 변형했.. 2020. 6. 10.
10430번 나머지 문제 출처 : https://www.acmicpc.net/problem/10430 10430번: 나머지 첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000) www.acmicpc.net 음,, 이번 문제는 딱히 풀이할 게 없는 것 같다,, 하지만 더 빠른 방법이 있을거같다..! import sys A,B,C=map(int, sys.stdin.readline().split()) print((A+B)%C) print(((A%C) + (B%C))%C) print((A*B)%C) print(((A%C) * (B%C))%C) 2020. 6. 2.
10828번 스택 문제 출처 : https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 � www.acmicpc.net import sys N=int(input()) result=[] for i in range(N): M=sys.stdin.readline().split() if M[0]=='push': result.append(M[1]) elif M[0]=='top': if len(result)!=0: print(result[-1]) else: print(-1) elif M[0].. 2020. 5. 30.
2751번 수 정렬하기2 문제 출처 : https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net import sys N=int(input()) M=[] for i in range(N): M.append(int(sys.stdin.readline())) M.sort() for i in M: print(i) 이전 포스팅에서 말했던 sys를 사용했다! 2020. 5. 30.
2750번 수 정렬하기 문제 출처 : https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net N=int(input()) M=[] for i in range(N): M.append(int(input())) M.sort() for i in M: print(i) 간단한 정렬문제인데 일반적인 input()보다는 sys.stdin.readline()이 시간적으로 더 빠를것이다..! 2020. 5. 30.