코딩(137)
-
백준 1463번
def solve(): n = [int(x) for x in input().split()] arr = [0, 0, 1, 1] for i in range(5, n+1): one, two, three = math.inf, math.inf, arr[i-1] if i % 3 == 0: one = arr[i//3] if i % 2 == 0: two = arr[i//2] value = 1 + min(one, two, three) arr.append(value) print(arr[n]) solve() #f(n) = 1 + min(f(n/3), f(n/2), f(n-1)) https://roamingman.tistory.com/12 백준 1463번 문제(1로 만들기) 파이썬(Python) 풀이 [로밍맨] 문제 링크 w..
2022.08.23 -
백준 10773번
def solve(): n = int(input()) arr = [] for _ in range(n): a = int(input()) if a != 0: arr.append(a) else: arr.pop() print(sum(arr)) solve() https://roamingman.tistory.com/47 백준 10773번 문제(제로) 파이썬(Python) 풀이 [로밍맨] 문제 링크 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정.. roamingman.tistory.com 이번에도 로밍맨님의 도..
2022.08.23 -
백준 2579번
참고했습니다. https://roamingman.tistory.com/72 백준 2579번 문제(계단 오르기) 파이썬(Python) 풀이 [로밍맨] 문제 링크 https://www.acmicpc.net/problem/2579 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-host="www.acmicpc.net" data-og-source-url="https://www... roamingman.tistory.com
2022.08.23 -
다익스트라 알고리즘
https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#s-1 https://youtu.be/611B-9zk2o4 매상황에서 가장 비용이 적은 노드를 선택 -그리디 알고리즘의 한 종류 -특정 노드 출발, 다른 모든 노드로 가는 최단 거리 동작 과정 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블 갱신 5. 3,4번 반복
2022.08.19 -
플로이드 워셜 알고리즘
https://youtu.be/9574GHxCbKc -모든 노드에서 다른 모든 노드까지의 최단 경로 계산 -단계별로 거쳐 가는 노드를 기준으로 수행 -2차원 테이블에 최단 거리 정보 저장 -다이나믹 프로그래밍의 한 종류 기본 점화식: D(ab) = min(D(ab), D(ak) + D(kb)) *테이블 출발 /도착 1 2 3 4 1 0 4 무한 6 2 3 0 7 무한 3 5 무한 0 4 4 무한 무한 2 0 출발 /도착 1 2 3 4 1 0 4 11 -> 8 6 2 3 0 7 9 3 5 9 0 4 4 7 11 2 0 (i) k=1: 1번 노드를 거쳐감: D(24) = D(21) + D(14) D(32) = D(31) + D(12) (ii) k = 2: 2번 노드를 거쳐감: D(13) =D(12) + D(..
2022.08.19