태브로의 개발위키

문제 ) 1 4 5 6 7 9 11 16 43 59 의 오름차순이 있을 때 7의 위치는? lt = 0, rt = n-1 을 설정 while lt

출처 : https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 풀이 : def solution(answers): answer = [] c1 = [1,2,3,4,5] c2 = [2,1,2,3,2,4,2,5] c3 = [3,3,1,1,2,2,4,4,5,5] cnt = [0, 0, 0] for i in range(len(answers)) : if answers[i] == c1[i % 5]: cnt[0] += 1 if a..

출처 : https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net import sys n, k = map(int, input().split()) bag = [[0,0]] dp = [[0 for _ in range(k+1)] for _ in range(n+1)] for _ in range(n): bag.append(list(map(int, input().split()))) for i in ..

출처 : https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 : n = int(input()) line = [] for _ in range(n): line.append(list(map(int,input().split()))) line.sort() dp = [1 for i in range(n)] for i in range(n): for j in range(i): if line[i][1] > line[j][1]: dp[i] = max(dp[i], dp[..

출처 : https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 : n = int(input()) a = list(map(int, input().split())) inc = [1 for i in range(n)] for i in range(n): for j in range(i): if a[i] > a[j]: inc[i] = max(inc[i], inc[j]+1) dec = [1 for i in range(n)] for i in range(n-1, -1, -1): f..

출처 : https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 : n = int(input()) dp = [[0] * 10 for i in range(n+1)] for i in range(1,10): dp[1][i] = 1 for i in range(2, n+1): for j in range(10): if j == 0 : dp[i][j] = dp[i-1][j+1] elif j == 9 : dp[i][j] = dp[i-1][j-1] else : dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] print(sum(dp[n]) % 1000000..

출처 :https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 : n = int(input()) a = [0]* (n+1) for i in range(2,n+1): a[i] = a[i-1] + 1 if i % 3 == 0 : a[i] = min(a[i], a[i//3]+1) if i % 2 == 0 : a[i] = min(a[i], a[i//2]+1) print(a[n]) 다이나믹 프로그래밍의 정석인 문제가 아닐까 생각한다. 하지만 못 풀었다... 조금 이런 접근이 낯설었다. 우선 다이나믹 프로그램에서는 무엇을 미리 배열을 정할지를 생각해야한다. 지금까지 문제..

출처 : https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 : t = int(input()) sol = [0] * 101 sol[1], sol[2], sol[3] = 1, 1, 1 for _ in range(t): n = int(input()) for i in range(4,n+1): sol[i] = sol[i-3] + sol[i-2] print(sol[n])

출처 : https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) a = [0]*1000001 a[1],a[2] = 1, 2 for i in range(3,n+1): a[i] = (a[i-2]+a[i-1])%15746 print(a[n]) 풀이 : 그래서 피보나치 문제임을 확인했고 이게 재귀함수를 사용해서 풀었었는데 그렇게 풀면 메모리초과가 나기 때문에 위 풀이..

출처 : https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 풀이 : dp = [[[0]*(21) for _ in range(21)] for _ in range(21)] def w(a,b,c): if a 20 : return w(20,20,20) if dp[a][b][c]: # 0 이면 반환을 안함 return dp[a][b][c] if a < b < c : dp[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)..