본문 바로가기

전체 글

 (171)
[프로그래머스][2021 KAKAO BLIND RECRUITMENT][Python] 합승 택시 요금 [ 문제 ] 문제 풀러 가기 본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다. [출제 의도] 최단 경로 알고리즘 [ 문제 풀이 ] 먼저, 모든 노드에서 모든 노드로의 최단 경로를 구해야 합니다. Floyd-Warshal 알고리즘을 사용했습니다. cost[i][j] = i에서 j로 가는 최저 택시 요금 그다음, 어느 노드를 A와 B의 분기점으로 정할지 구해야 합니다. K를 분기점이라고 했을 때, S ~ K, K ~ A, K ~ B의 합이 최솟값일 때가 정답입니다. 문제에서 요구하는 답 = min(cost[s-1][k] + cost[k][a-1] + cost[k][b-1]) (단, k = 1 ~ n) Dijkstra 알고리즘을 사용하지 않은 이유는 비효율적이기 때문입니다. [ 정답 코드 ] #..
[BOJ] [Python] 1914: 하노이 탑 전형적인 하노이 탑 구현 문제이다. def honoi_tower(n, start, tmp, end): if n == 1: print(start, end) else: honoi_tower(n-1, start, end, tmp) print(start, end) honoi_tower(n-1, tmp, start, end) num = int(input()) print(2 ** num - 1) if num
[복잡도] 시간 복잡도와 공간 복잡도 시간 복잡도 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 알고리즘을 위해 필요한 메모리의 양

티스토리툴바