본문 바로가기
반응형

Problem Solving232

[카카오 기출] 광고 삽입 https://programmers.co.kr/learn/courses/30/lessons/72414?language=python3 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr def toNum(str1): hh, mm, ss = map(int, str1.split(':')) return hh*3600 + mm*60 + ss def toTime(num): str1 = '' hh = num//3600 if hh < 10: str1 += .. 2021. 9. 6.
[다이나믹 프로그래밍] 백준 17069번: 파이프 옮기기 2 / 골드 5 https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net dp 문제임을 깨달으면 접근할만 한데 어려운 이유는 dp임을 깨닫기가 쉽지 않다. 첫 시도를 bfs로 했었고 마지막 예제에서 시간 초과가 발생했다. 풀이 방법은, dp는 3차원 리스트로 만든다. n*n*3이다. 마지막이 3인 이유는 각 horizontal, vertical, diagonal 방향의 정보를 담고 있어야 하기 때문. 처음엔 모든 성분을 0으로 초기화해준다. 그.. 2021. 9. 5.
[다이나믹 프로그래밍] 백준 12865번: 평범한 배낭 / 골드 5 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 유명한 배낭 문제!! n, k = map(int, input().split()) items = [] for i in range(n): w, v = map(int, input().split()) items.append([w, v]) dp = [[0]*(k+1) for _ in range(n+1)] for i in range(1, n+.. 2021. 9. 4.
[카카오 기출] 합승 택시 요금 https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr import sys inf = sys.maxsize def solution(n, s.. 2021. 9. 2.
[카카오 기출] 순위 검색 https://programmers.co.kr/learn/courses/30/lessons/72412 2021. 9. 2.
[수학] 백준 2407번: 조합 / 실버 2 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net n, m = map(int, input().split()) dp = [[1]*(i+1) for i in range(n+1)] for i in range(2, n+1): for j in range(1, i): dp[i][j] = dp[i-1][j-1]+dp[i-1][j] print(dp[n][m]) 파스칼 삼각형의 원리를 이용하여 dp로 풀었다. nCr = n-1Cr-1 + n-1Cr 정답자 코드를 보니 그냥 팩토리얼로도 풀린다. 2021. 9. 2.
반응형

티스토리툴바