본문 바로가기

분류 전체보기158

[목표] 2021 군장병 공개SW 해커톤 참여 https://osam.kr/hackathon/main 국방오픈소스아카데미 osam.kr 1차 목표 (해커톤 참여) 1. 온라인 교육 이수 App(Dart기초, Flutter 초급, 중급, 튜토리얼) (대략 25시간), git, github, 공개 sw강의 수강 (대략 5시간) 2. 코딩 테스트 준비 (난이도 별 4문제 출제) (파이썬으로 백준 문제 꾸준히 풀기) (9/6~9/7) 2021. 6. 28.
20210625#(49) 백준 15988 1, 2, 3 더하기 3 (다이나믹 프로그래밍) https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net import sys n=int(sys.stdin.readline()) dp=[0,1,2,4] for i in range(4,1000001): dp.append((dp[i-3]+dp[i-2]+dp[i-1])%1000000009) for i in range(n): testcase=int(input()) print(dp[testcase]) 기존 1,2,3 더하기 문제에서 n의 범위가 늘어나고 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 .. 2021. 6. 25.
20210625#(48) 백준 2579 계단 오르기 (다이나믹 프로그래밍) https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net n=int(input()) nlist,dp=[0 for i in range(301)],[0 for i in range(301)] for i in range(n): nlist[i]=int(input()) dp[0]=nlist[0] dp[1]=nlist[0]+nlist[1] dp[2]=max(nlist[1]+nlist[2],nlist[0]+nlist[2]) for i in range(3,n): dp[i]=max(.. 2021. 6. 25.
20210622#(47) 백준 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()) dp=[0,1,2,3] for i in range(4,n+1): dp.append(dp[i-1]+dp[i-2]) print(dp[n]%10007) 문제를 천천히 읽어보고 규칙을 찾는다면 어렵지 않게 점화식을 구해 풀 수 있는 문제! 2021. 6. 22.
20210622#(46) 백준 9095 1, 2, 3 더하기(다이나믹 프로그래밍) https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net #1 n=int(input()) dp=[0,1,2,4] for i in range(4,11): dp.append(dp[i-3]+dp[i-2]+dp[i-1]) for i in range(n): testcase=int(input()) print(dp[testcase]) #2 함수이용(이해하기에 좀 더 쉬울수도 있음) num=int(input()) def sol(n): if n==1: return 1 elif n==2: return 2 elif n==3: return 4 else: return sol.. 2021. 6. 22.
20210622#(45) 백준 14501 퇴사 (다이나믹 프로그래밍) https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net n=int(input()) t,p=[0 for i in range(n+1)],[0 for i in range(n+1)] for i in range(n): a,b=map(int,input().split()) t[i]=a p[i]=b dp=[0 for i in range(n+1)] for i in range(n-1,-1,-1): if t[i]+i>n: dp[i]=dp[i+1] else: dp[i]=max(p[i]+dp[i+t[i]],d[[i+1]]) print(dp[0]) 다이나믹프로그래밍 공부를 위해 풀어본 문제.. 제목이 재밌어보여서.. 2021. 6. 22.
20210621#(44) 백준 1003 피보나치 함수(다이나믹 프로그래밍) https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net n=int(input()) zero=[0]*100 one=[0]*100 m=[0,0,0] summ=[] zero[0]=1;one[0]=0;zero[1]=0;zero[2]=1;one[1]=1;one[2]=1 for i in range(n): mnum=int(input()) m.append(mnum) for i in range(3,m[i+3]+1): zero[i]=zero[i-1]+zero[i-2] one[i]=one[i-1]+one[i-2] m=m[3:] for i in m: print(zero.. 2021. 6. 21.
20210620#(43) 백준 1463 1로 만들기(다이나믹 프로그래밍) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net #1 메모리200680kb 시간168ms N=int(input()) dp=[0,0,1,1] for i in range(4,N+1): dp.append(dp[i-1]+1) if i%2 == 0: dp[i]=min(dp[i//2]+1,dp[i]) if i%3 == 0: dp[i]=min(dp[i//3]+1,dp[i]) print(dp[N]) #2 메모리133180kb 시간128ms N=int(input()) dp=[0 for _ in range(N+1)] for i in range(2,N+1): dp[i]=dp[i.. 2021. 6. 20.
20210618#(42) 백준 11650 좌표 정렬하기 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 N=int(input()) xy=[] for i in range(N): [a,b]=map(int,input().split()) xy.append([a,b]) xy=sorted(xy) for i in range(N): print(xy[i][0], xy[i][1]) 2021. 6. 18.

티스토리툴바