파이썬
[정렬] 수 정렬하기(?)
2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 두 가지 방법으로 풀었는데, 나름 참신하다고 생각한 방법이 python 내장 정렬이랑 시간이 비슷하게 걸려서 놀랐다. 아래 104ms가 걸린 방법은 기존 정렬 알고리즘이랑 다르게 풀어보고 싶어서 내 나름대로 생각해서 해본 방식이다. length = int(input()) EMPTY = "EMPTY" dummy = [EMPTY] * 2001 for i in range(length): num = int(input()) + 1000 dummy[num] = num resul..
[브루트 포스] 영화감독 숌
1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net n = int(input()) res = [] count = 0 target = '666' while True: if target.find('666') != -1: count = count + 1 if count == n: print(target) break target = str(int(target) + 1)
[재귀] 하노이 탑
11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 첫 공부를 할 시점에 이 문제를 접했던 기억이 난다. 아무리 생각해도 모르겠어서 이 길이 내 길이 아닌지 심각하게 고민했던 시기가 있었는데... 지금에는 보고 쉽게 풀지만 그 당시에는 정말 내 앞을 가로막은 거대한 벽으로 느껴졌었다. count = int(input()) def move(now, target, empty, c): if c == 1: print(now, target) return move(now, empty, target, c - 1) ..
[기본 수학2] 베르트랑 공준
www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 기존에 만들어 놓은 소수 구하는 함수를 돌렸더니 시간초과가 나서 잠시 당황했다. 매번 소수를 구하는 방식으로는 테스트케이스 갯수대비 짧은 제한시간(1초)을 통과할 수 없을 것 같아서... 테스트케이스에 나올 수 있는 소수의 범위 2*123456 내에 있는 소수를 다 구하고 인덱싱 하는 방식으로 전환했다. import math from sys import stdin test_case_list = [] wh..
[기본수학 2] 소인수분해, 소수 구하기
11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 소인수 분해 문제는 굳이 소수를 구하는 방식으로 풀어야 하나? 하는 생각이 들어서 그냥 쉽게 작성했다. import sys from sys import stdin test = int(stdin.readline()) def get_factorization(no: int): for i in range(2, no): if no % i == 0: print(i) return ge..
[기본수학2] 소수
2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 소수찾기 문제랑 사실상 같다. [기본수학 2] 소수 찾기 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 시간 절약을 위해 10 이하 소수를 배열에 넣고 시작 nookpi.tistory.com 설명은 생략 from sys import stdin import math test_min = int(stdin.readline()) test_max = i..
[기본수학 2] 소수 찾기
1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 시간 절약을 위해 10 이하 소수를 배열에 넣고 시작했다. 소수 (수론) 위키백과, 우리 모두의 백과사전. 좌측은 소수, 우측은 합성수. 소수란 자신보다 작은 두 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 소수(素數, 발음: [소쑤], 문화어: 씨수, 영어: prime nu ko.wikipedia.org from sys import stdin import math test_count = int(stdin.readline()) test_case = list(map(int, stdin.readline().split(" ")..
[기본수학1] Fly me to the Alpha Centauri
1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 이동 거리의 변화는 +1 , 0 , -1 중에서 일어나고 맨 마지막 이동거리는 1이기 때문에, 작동시기별 최대 이동거리에 도달하기 위한 요소들이 생기게 된다. 최대 이동거리가 5라면 1 2 3 4 5 4 3 2 1 의 형태가 기본적으로 존재하게 된다는 뜻. 이 형태의 합을 구하면 n^2 이 된다. 전체 이동거리에서 n^2 로 나올 수 있는 형태를 빼고 나머지를 통해서 잔여 횟수를 더해주면 끝. 잔여 횟수는 0 또는 1..
[기본수학1] 설탕 배달
2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 제출코드 from sys import stdin kg = int(stdin.readline()) def get_container_count(kg: int): total_max = kg // 3 # 나올 수 있는 토탈 최대값 total_min = kg // 5 # 나올 수 있는 토탈 최소값 if kg % 5 == 0: return total_min for i in range(0, total_max + 1): three_rest = (kg - (3 * i)) if three_..
[기본수학1] 부녀회장이 될테야
2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 제목이 굉장히 귀여운 문제였다. 이렇게 사람이 많이 살고있는 아파트의 부녀회장이 되려면 쉽지 않을 것 같다. 예제를 바탕으로 몇 번 그려보면 규칙성을 쉽게 발견할 수 있었다. 재귀적으로 풀어봤다. 제출코드 from sys import stdin test_count = int(stdin.readline()) test_case = [] for i in range(0, test_count): case_k = int(stdin.readline()) case_n = int(stdin.readline()) tes..