전체 글351 [백준 1072] 게임 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 투포인터 문제이다. 코드는 어렵지 않지만 투포인터를 떠올리긴 쉽진 않은거 같다 ㅠ while문을 돌리면 TLE가 발행한다. 이 문제의 또다른 포인트는 롱롱과 인트 범위라고 생각하는데 승률을 구하는 경우 소수점 아래는 버림하므로 먼저 100을 곱하고 시작하는 게 맞다. 이 경우 분자의 최댓값이 10^9이므로 100을 곱하면 INT 범위를 넘어선다. 따라서 N과 D는 롱롱이 되어야 한다. in.. 2021. 6. 20. [백준 1948] 임계경로 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 위상정렬 + 역추적 문제이다. 문제이해가 어려웠으나 요약하면 1. 시작점->목적지까지 도달하는데 가장 오래 걸리는 시간 구하기 2. 1만큼의 시간이 소요되는 경로에 속한 도로들의 수 구하기 이다. 1분도 쉬지 않는다는 의미가 2라는 걸 이해하지 못했다... 1을 푸는 것은 위상정렬 + dp를 결합하면 어렵지 않게 해결할 수 있으나 문제는 2였다. 2에 대해 set으로 풀.. 2021. 6. 19. [백준 11779] 최소비용 구하기 2 www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 알고리즘과 역추적을 하는 문제이다. eazymean.tistory.com/384 [알고리즘] 최단 경로 역추적 다익스트라 알고리즘과 플로이드 와샬을 사용한 최단거리 찾기 문제에서 종종 출제되는 경로 역추적 문제이다. 최단 거리와 그 경로를 찾는 문제로 다익스트라 알고리즘과 플로이드 와샬의 역 eazymean.tistory.com 다익스트라에서의 역추적은 비교적 단순하다.. 2021. 4. 11. [백준 11780]플로이드2 www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드를 사용하는 경로 역추적 문제이다. eazymean.tistory.com/384 [알고리즘] 최단 경로 역추적 다익스트라 알고리즘과 플로이드 와샬을 사용한 최단거리 찾기 문제에서 종종 출제되는 경로 역추적 문제이다. 최단 거리와 그 경로를 찾는 문제로 다익스트라 알고리즘과 플로이드 와샬의 역 eazymean.tistory.com 경로 cost를 long long까진 안했어도 됐던 것 같다. 플로이드는.. 2021. 4. 11. [알고리즘] 최단 경로 역추적 다익스트라 알고리즘과 플로이드 와샬을 사용한 최단거리 찾기 문제에서 종종 출제되는 경로 역추적 문제이다. 최단 거리와 그 경로를 찾는 문제로 다익스트라 알고리즘과 플로이드 와샬의 역추적 접근 방법이 약간 다르다. 공통점 최단 거리가 업데이트 될 때 경로 역시 업데이트 한다. 다익스트라 path[NODE] = PREV NODE에 도착하기 전 거쳐야 하는 노드가 PREV 경로 초기화 for (int i = 1; i dist[curNode] + a.first) { ... path[a.second] = curNode; } 경로를 추적할 땐 dst -> src까지 거꾸로 내려간다. vector answer; int x = dst; while (x != path[x]) { answer.push_back(x); x .. 2021. 4. 11. 이전 1 2 3 4 5 6 ··· 71 다음