728x90 반응형 백준 알고리즘55 [백준 10473][파이썬] 인간 대포 (우선순위 큐를 사용하지 않는 다익스트라) https://www.acmicpc.net/problem/10473 10473번: 인간 대포 입력은 한 개의 길찾기 문제를 표현한다. 첫 줄에는 두 개의 실수가 입력되며 각각은 당신이 현재 위치한 X, Y좌표이다. 두 번째 줄에는 목적지의 X, Y좌표가 실수로 입력된다. 이어지는 줄에는 대 www.acmicpc.net 다익스트라 알고리즘을 사용하는 문제이다. 우선 이 문제는 그래프를 주지 않았기 때문에 우리가 직접 그래프를 만들어야 한다. 주어진 정점은 시작점, 도착점, n개의 대포이다. 이 정점들의 모든 pair가 그래프의 간선이 된다. 즉 간선의 개수는 (n+2)의 제곱이 되는 것이다. 지금 이 생각까지 코드로 나타내보자. import sys INF=1e9 input=sys.stdin.readline.. 2023. 6. 29. [백준 11657][파이썬] 타임 머신 (벨만 포드) https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 음의 간선을 포함하고 있기 때문에 다익스트라가 아닌 벨만 포드 알고리즘을 사용한다. 무조건 음의 간선을 포함한다고 문제가 생기는 것은 아니다. 정확히는 음의 간선이 포함된 사이클이 최단 거리를 - ∞로 만들 때 문제가 발생한다. 다음과 같은 음의 사이클은 문제가 되지 않는다. 사이클을 반복하면 비용이 증가하기 때문에 최단 거리를 구하는 .. 2023. 6. 13. [백준 4485][파이썬] 녹색 옷 입은 애가 젤다지? (다익스트라) https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net https://growth-coder.tistory.com/200 위 포스팅에서 다익스트라 기본 문제를 풀어보았다. 알고리즘 자체는 거의 동일하나 보완할 필요성을 느껴서 기록을 해보려고 한다. 우선 이 문제는 그래프로 표현하기보다는 2차원 배열 그대로 보는 편이 좋다. 연결된 노드들은 동서남북으로 정해져 있기 때문에 동서남북으로 돌면서 체크하는 편이 좋다. 우선 이 문제는 위 포.. 2023. 6. 9. [백준 2042][파이썬] 구간 합 구하기(펜윅 트리) https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net https://growth-coder.tistory.com/162 이전 포스팅에서 펜윅 트리(BIT, 이진 인덱스 트리)의 사용법에 대해서 공부하였다. 이 펜윅 트리를 사용하면 구간 합 문제를 쉽게 구현할 수 있다. 우선 갱신 함수이다. def update(i, num): arr[i]+=num while i0: res+=tree[i] i-.. 2023. 4. 26. 이전 1 2 3 4 5 6 7 ··· 14 다음 728x90 반응형
