본문 바로가기

PS/백준

[백준 11651번] 좌표 정렬하기 2 (파이썬/python) 2021. 6. 14. https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 파이썬 정렬에 대해 미리 정리해놔서 풀 수 있던 문제 https://foameraserblue.tistory.com/102?category=481823 알고리즘용 파이썬 sorted 함수로 정렬하는 여러 방법들 파이썬으로 알고리즘을 풀다보면 정렬을 사용해야 되는 경우를 자주 본다. 알고리즘에서 많이 쓰이는 파이썬 자료형은 리스트, 이차원리스..
[백준 11729번] 하노이 탑 이동 순서 (파이썬/python) 2021. 6. 14. https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 자료구조 배울떄 배웠단 하노이탑 문제. 이런문제 풀면 재귀는 참 추상적이라는 생각이 들떄가있다. 별다른 해설은 없음... 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import sys input = sys.stdin.readline n = int(input()) li = [] def hanoi(x, f, b, t):..
[백준 1929번] 소수 구하기 (파이썬/python) 2021. 6. 14. https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 에라토스테네스의 체를 이용해 간단하게 풀 수 있다. 1은 소수가 아니기때문에 미리 False값을 넣어줘야함에 유의하자~! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import sys from math import sqrt input = sys.stdin.readline a, b = map(int, input().split()) li = [True for _ in range(..
[백준 10250번 ] ACM 호텔 (파이썬/python) 2021. 6. 14. https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 문제에 나온대로 구현만 하면 되는 간단한 문제였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import sys input = sys.stdin.readline t = int(input()) for _ in range(t): # 층수, 방수, 몇 번쨰 손님인지 h, w, n = map(int, input().split()) # 몇 층? a = n % ..
[백준 2609번] 최대공약수와 최소공배수 (파이썬/python) 2021. 6. 14. https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 유클리드 호제법을 이용해 최대공약수를 구할 수 있고 최소공배수는 두 값의 곱 / 최대공약수 임 https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95 갓무위키에 유클리드 호제법에 대한 내용이 참 정리가 잘 돼있습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import sys input = sys.stdin.rea..
[백준 1037번] 약수 (파이썬/python) 2021. 6. 14. https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 모든 약수가 주어지기때문에 오름차순 정렬 후에 0번 인덱스의 값과 맨 마지막 인덱스 값을 곱해주면 답이 나온다. 1 2 3 4 5 6 7 8 9 10 import sys input = sys.stdin.readline t = int(input()) arr = list(map(int, input().split())) arr = sorted(arr) n = arr[0]*arr[-1] print..
[백준 1436번] 영화감독 숌 (파이썬/python) 2021. 6. 14. https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 단순하게 완전탐색으로 풀면 되는 문제 메모리제한이 넉넉해서 666~ 300만까지의 리스트를 만들어서 666이 포함되어있는지 탐색해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 import sys input = sys.stdin.readline arr = [str(i) for i in range(666, 3000000)] n = int(input()) cnt = 0 for a..
[백준 2869번 ] 달팽이는 올라가고싶다 (파이썬/python) 2021. 6. 14. https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B > 이동횟수임 3. 만약 카운트가 0이라면 v-a가 a-b보다 작다는 뜻 ..
[백준 4948번 ] 베르트랑 공준 (파이썬/python) 2021. 6. 14. https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 처음에 제곱근만을 이용해 소수판별 하는 알고리즘을 짰다. 2번째 코드로 올리겠음 코드는 맞게 짰는데 시간초과가 난다... 소수판별 문제에서 시간초과를 안 나게 하라는건 결국 제곱근도 쓰면서 에라토스테네스의 체를 쓰라는말이랑 똑같다. 최대값인 123456 의 2배가 되는 인덱스까지 리스트를 만들고 에라토스테네스의 체를 활용해 소수를 구해주었다. 그 후 n값을 입력받을때 n+1 ~ 2n까지 소..

티스토리툴바