본문 바로가기

코딩테스트/Python

 (225)
[Python] 백준 #11279 - 최대 힙 문제 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 풀이 import heapq import sys input = sys.stdin.readline n = int(input()) h = [] for _ in range(n): x = int(input()) if x==0: print(heapq.heappop(h)[1]) if h else print(0) else: heapq.heappush(h,(-x,x)) 파이썬에서 힙은 ..
[Python] 백준 #1904 - 01타일 문제 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 n = int(input()) d = [0]*(n+1) d[0]=1 d[1]=1 for i in range(2,n+1): d[i] = (d[i-1] + d[i-2])%15746 print(d[n]) d[3] d[2]의 숫자들의 마지막에 1을 붙인 것 d[1]의 숫자들의 마지막에 00을 붙인 것 => d[3] = d[2] + d[1] d[4] d[3]의 숫자들의 마지막에 1을 붙인 것 d[2]..
[Python] 백준 #1003 - 피보나치 함수 문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 d = [[0,0] for _ in range(41)] d[0]=[1,0] d[1]=[0,1] for i in range(2,41): d[i][0] = d[i-1][0] + d[i-2][0] d[i][1] = d[i-1][1] + d[i-2][1] T = int(input()) for _ in range(T): n = int(input()) print(" ".join(map(str,d[n]))) d[n]은 f(n)을 실행했을때 가지는 0의 개수와 1의 개수이다. d[0] = [1,0..
[Python] 백준 #9095 - 1, 2, 3 더하기 문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 d=[0]*11 d[1]=1 d[2]=2 d[3]=4 for i in range(4,11): d[i]=d[i-3]+d[i-2]+d[i-1] n = int(input()) for _ in range(n): m = int(input()) print(d[m]) d[4]를 구해보자. 3을 만들 수 있는 경우의 수에서 +1을 한 것, 2를 만들 수 있는 경우의 수에서 +2를 한 것, 1을 만들 수 있는 경우의 수에서 +3을 한 것을 합치면된다. 즉, d[4] = d[3] + d[2] + d[1..
[Python] 백준 #11727 - 2×n 타일링 2 문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 n = int(input()) d = [0]*1001 d[1] = 1 d[2] = 3 for i in range(3,1001): d[i] = (d[i-1] + 2*d[i-2])%10007 print(d[n]) 경우의 수를 다 구해보면된다. d[n-1]일떄는 2*1 타일이 붙을 수 있다. (d[n]+=d[n-1]) d[n-2]일때는 1*2 타일 2개, 2*2타일 두개가 붙을 수 있다. d[n-2]의 타일들에 *2를 해..
[Python] 백준 # 11726 - 2×n 타일링 문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 n = int(input()) d = [0]*(n+1) d[0]=1 d[1]=1 for i in range(2,n+1): d[i]=(d[i-2]+d[i-1])%10007 print(d[n]) d[2]를 구해주기 위해 d[0]을 1로 지정하였다. d[0]을 지정해주지 않고 d[1000]까지 먼저 다 계산 해놓고 d[n]을 구하는 방법도 있다. n = int(input()) dp = [0] * 1001 dp[1..
[Python] 백준 #1463 - 1로 만들기 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 n = int(input()) d=[0]*(n+1) d[1]=0 for i in range(2,n+1): arr=[] if i%3==0:arr.append(d[i//3]+1) if i%2==0:arr.append(d[i//2]+1) arr.append(d[i-1]+1) d[i] = min(arr) print(d[n]) 동적프로그래밍을 사용하였다. d를 만들어서 3으로 나누어질때, 2로 나누어질때를 구하고 -1을 할때도 구해준다. 이들 중에 최솟값을 구해준다. [다른사람 코드] - 백준 숏코딩 n = ..
[Python] 백준 #2667 - 단지번호붙이기 문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 import sys input = sys.stdin.readline def dfs(i,j): visited[i][j] = True # 방문한 곳을 True로 바꾸기 cnt[-1]+=1 # 바꾸고 cnt 1 증가 for p in range(4): # 상하좌우로 방문 cx = d[p][0] + i cy = d[p][1] + j if 0

티스토리툴바