본문 바로가기
반응형

코딩테스트/파이썬68

[백준] [스택] 제로 10773 (파이썬) (시간 초과 방지 코드) 시간 초과가 안되게 주의 해야한다. 2021.03.14 - [Programming/Python] - [파이썬] 코딩테스트 시간 초과시 해결 방법 sys.stdin.readline().rstrip() 코드 # 제로 import sys input = sys.stdin.readline k = int(input()) st = [] for _ in range(k): num = int(input()) if num == 0: st.pop() else: st.append(num) print(sum(st)) 2021. 3. 14.
[백준] [조합] 다리놓기 1010 (파이썬) 스케치 코드 다리가 교차한다는 건 순서를 고려하겠다는 순열이라고 생각하면된다 문제에서는 다리가 교차되면 안된다 하였으니 조합식으로 풀면 된다. itertools 라이브러를 활용해서 풀어 보고 싶었으나 단순 개수를 구하는 문제이므로 시간 초과가 났다. 팩토리얼 함수, 조합 함수를 만들어서 코드를 구현하였다. # 다리 놓기 (조합을 구해야하는데 시간이 0.5초) # 1 itertools 라이브러리 이용 시간 초과실패 # from itertools import combinations T = int(input()) def factorial(n): result = 1 for i in range(1, n+1): result *= i return result def combinations(a,b): result = .. 2021. 3. 14.
[백준] [조합] 이항계수 11050 (파이썬) 코드 이항계수는 조합문제라고 할 수 있다. 이항계수 k 분의 n 인 분수가 있으면 조합 nCk 와 동일하다. # 이항 계수1 # recursion 재귀 에러 난다... def factorial(n): if n 2021. 3. 14.
[백준] 최소공배수 1934 (파이썬) 코드 유클리드 호제법을 사용하여 쉽게 구할 수 있다. 2021.03.14 - [Algorithm & Data structure] - [알고리즘] 유클리드 호제법 (최대공약수, 최소공배수) [알고리즘] 유클리드 호제법 (최대공약수, 최소공배수) 유클리드 호제법 유클리드 호제로 최대 공약수 구하기 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 한다. 이때 A와 B의 최대공약수는 B와 R의 최대 공약수와 같다 최소공배수 = 두 seongbindb.tistory.com # 최소 공배수 # a > b 를 만족해야 한다. def gcd(a,b): if a % b == 0: return b else: gcd(b, a % b) t = int(input()) for _ in range(t): x.. 2021. 3. 14.
[백준] 약수 1037 (파이썬) 스케치 코드 n = int(input()) arr = list(map(int,input().split())) arr.sort() # 약수가 무작위로 주어질 수 있기 때문에 sort가 필요하다 if len(arr) == 1: print(arr[0] ** 2) else: print(arr[0] * arr[-1]) 2021. 3. 14.
[백준] [그리디] ATM 11399 (파이썬) 코드 # ATM # 돈을 인출하는데 필요한 시간의 합의 최솟값 # 최소 시간이 걸리려면 돈을 빨리 뽑을 수 있는 사람 순으로 줄을 서야한다. # 대기 시간이 최소화 되어야한다. n = int(input()) time_table = list(map(int,(input().split()))) time_table.sort() time = 0 for i in range(n): time += time_table[i] for j in range(i): time += time_table[j] # for i in range(n): # for j in range(i+1): # time += time_table[j] # 이런식으로도 구현가능 print(time) 2021. 3. 14.
[백준] [그리디] 동전 0 11047 (파이썬) 코드 # 각각의 동전들이 Ai 는 Ai-1의 배수 이기 때문에 그리디가 적용이 가능하다. n, k = map(int, input().split()) coins = [] for _ in range(n): coins.append(int(input())) coins.sort(reverse=True) count = 0 for coin in coins: if coin 2021. 3. 14.
[백준] [DP] 정수 삼각형 1932 (파이썬) 스케치 코드 # 정수 삼각형 n = int(input()) arr = [] # 입력 받은 데이터를 저장할 배열 for _ in range(n): data = list(map(int,input().split())) arr.append(data) # dp 테이블 초기화 (할필요 없이 입력받은 테이블을 dp테이블로 생각한다.) # dp = [ [0]*(i+1) for i in range(n) ] # dp[i][j] = i 번째 층에서 j인덱스의 수를 선택한 경우의 합 # dp[0][0] = arr[0][0] for i in range(1, n): for j in range(0, i+1): # 1층이면 index가 0,1 필요 if j == 0: arr[i][j] += arr[i-1][j] elif j == i.. 2021. 3. 14.
[백준] [DP] RGB 거리 1149 (파이썬) 스케치 문제 접근은 하였으나 코드로 구현하는 것이 어려웠다 코드 # rgb거리 구하기 혼자 해결하지 못함 n = int(input()) # n이 2다 arr = [] for _ in range(n): arr.append(list(map(int,input().split()))) # (26, 10, 5) # 모든 집을 칠하는 최솟값을 구할 테이블 dp = [[1001]*3 for i in range(n)] #n 행 3열 테이블 for i in range(n): if i == 0: # 첫번 째 집이다 dp[i][0] = arr[i][0] # r 의 비용 dp[i][1] = arr[i][1] # g 의 비용 dp[i][2] = arr[i][2] # b 의 비용 else: dp[i][0] = arr[i][0] +.. 2021. 3. 14.
[백준] [DP] 파도반 수열 9461 (파이썬) 스케치 규칙이 발견되면 dp로 간단하게 해결 할 수 있다. # 9:16 ~ 9:32 # 파도반 수열 T = int(input()) for _ in range(T): n = int(input()) d = [0]* 101 d[1] = 1 d[2] = 1 d[3] = 1 d[4] = 2 d[5] = 2 # 6번째 부터 규칙이 발견 for i in range(6, n+1): d[i] = d[i-1] + d[i-5] print(d[n]) 2021. 3. 14.
[백준] [DP] 신나는 함수 실행 9184 (파이썬) 스케치 DP를 이용해서 푸는 문제이다. MAX = 21 # 20이 맥스 값이므로 맥스 값 설정 # w(a,b,c)의 값을 저장하는 dp 테이블 초기화 dp = [[[0]*MAX for i in range(MAX)] for _ in range(MAX)] # list index out of range를 방지하는 함수 def inRange(a, b, c): return 0 2021. 3. 14.
[백준] 베르트랑 공준 4948 (파이썬) 코드 에라토스테네스의 체를 이용하면 간단하게 해결 가능하다. import math while True: n = int(input()) if n == 0: break count = 0 check = [True]* (2 * n + 1) # 모든 수가 소수 라고 가정 for i in range(2, int(math.sqrt(2*n) + 1)): if check[i]: j = 2 while i * j 2021. 3. 12.
[백준] 설탕배달 2839 (파이썬) 스케치 코드 # 설탕 배달 출처다국어분류 # 시간 제한메모리 제한제출정답맞은 사람정답 비율 # 1 초128 MB153230484253831732.797% # 문제 # 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. # 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. # 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 .. 2021. 3. 12.
[백준] 수 정렬하기 2 2751 (파이썬) # 수 정렬하기 2 성공분류 # 시간 제한메모리 제한제출정답맞은 사람정답 비율 # 2 초256 MB113187292801987330.064% # 문제 # N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. # 입력 # 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. # 출력 # 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. # 예제 입력 1 # 5 # 5 # 4 # 3 # 2 # 1 # 예제 출력 1 # 1 # 2 # 3 # 4 # 5 import sys input = sys.stdin.readl.. 2021. 3. 12.
[백준] 카드2 2164 (파이썬) 코드 큐 자료구조를 이해하면 쉽게 풀 수 있는 문제 # 카드2 from collections import deque n = int(input()) q = deque() for i in range(n): q.append(i+1) while len(q) > 1: if (len(q) == 2): q.popleft() break q.popleft() # 제일 위에 있는 카드를 바닥에 버린다 q.append(q.popleft()) # 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. print(int(q.pop())) # 마지막에 있는 카드를 뽑는다. 2021. 3. 12.
반응형

티스토리툴바