https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 3 16을 예로 들어보자. 3부터 16까지 검사하면서 현재 숫자가 소수이면 출력해주는 구조인데, 그냥 구하면 시간초과가 발생할 것이다. 그리고 1은 좀 특별하게 예외처리를 해주어야 한다. 왜냐?? 1은 소수가 아니지만, 소수 판별 알고리즘에 걸리지 않아 소수로 판별되기 때문이다! 2부터 n의 제곱근까지 i를 증가시키면서 혹시 딱 나눠 떨어지는 수가 있다면, 소수가 아니므로 False를 반환하고, 검사에 걸리지 않았다면 True를..
https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net x,y 좌표쌍을 여러 개 입력 받고, 정렬하는 문제이다. x좌표에 대해 오름차순으로 정렬하고, 만약 x좌표 값이 동일하다면 y좌표 값을 기준으로 오름차순 정렬해주면 된다. 사실 파이썬 정렬의 기본값은 오름차순이라, 아래 코드처럼 정렬 기준을 정해주지 않아도 되지만 쓸 경우가 반드시 있을 것이라 생각하므로 알아두면 좋을 것 같다! Key가 의미하..
https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 각 배열을 처음부터 끝까지 탐색하면 시간초과가 나도록 유도하는 문제이다. O(log n)의 시간복잡도를 가지는 이분탐색을 활용해야한다. 상근이가 가지고 있는 숫자카드가 비교할 배열보다 작으니까, 숫자카드에서 수를 하나 뽑아서 상근이의 숫자카드 목록에 있는지 찾아주면 된다. import sys def binary_search(arr, num,left,right): wh..
https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 풀이는 다음과 같다. 예시로는 200을 들겠다! 200 = 1 + 199이다. 199 = 2 + 197이다. (이미 1을 위에서 써버렸으므로 수를 1증가시키면서 사용) 197= 3 + 194이다. ... 계속하다보면 수가 계속 줄어들어서 45 = 18 + 27 까지 오게 되고 27 = 19 + 9가 되면서 뭔가 이상한 순간이 생긴다. 9는 아까 써버렸는데 또 9가 나온다. 27을 더이상 쪼갤 수 없으므로, 200은 1~18 그리고 27까지해서 총 19개의 자연수로 나눌 수 있다! 즉, 200을 덧셈으로 쪼개나가면서..
https://www.acmicpc.net/problem/2163 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿 www.acmicpc.net 이 문제는 그림으로 설명하겠다. 5 x 3 초콜릿의 경우, 우리는 실제 자를 때 4 + 2번만 자르면 된다. (최대한 한번에 자르려고 하기 때문) 하지만, 이 문제는 그렇지 않기 때문에 조각조각에 대해 따로따로 잘라줘야한다. 그래서 곱해주는 것! a와 b는 바뀌어도 된다. 가로 먼저 자르냐, 세로 먼저 자르냐 차이일뿐! input = __import__('sys').stdin.readline..
https://www.acmicpc.net/problem/2588 2588번: 곱셈 첫째 줄부터 넷째 줄까지 차례대로 (3), (4), (5), (6)에 들어갈 값을 출력한다. www.acmicpc.net 파이썬으로 주 사용언어를 바꿔보려고 한다. (사실 C++도 애착이 깊은 언어라, 둘 다 잘하고 싶은 마음이 크다) 그래서 백준에 있는 파이썬 길라잡이 문제집을 통해 파이썬을 연습하는 중이다. 두 정수를 int형이 아닌 str형으로 받아서 인덱스를 이용해 곱하기 해주면 금방 풀리는 문제이다. import sys a = input() b = input() ans=0 ans = int(a) * int(b[2]) print(ans) ans = int(a) * int(b[1]) print(ans) ans = i..
