분류 전체보기
-
백준 11049(행렬 곱셈 순서)전공/알고리즘 2020. 7. 15. 14:56
https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같� www.acmicpc.net 오랜만의 알고리즘 컨디션이 너무 안좋아져서.. 아무튼 이 문제를 보면 대충 감이 안온다. 어떻게든 풀 수는 있을것 같은데.. 처음에는 행값이 큰 거 순서대로 연산횟수를 줄이면 어떨까 싶었지만, 진행방법이 떠오르지 않아서 스킵하고, 스터디에서 진행하는 dp식으로 문제를 접근하였다. dp를 적용시키려면 문제의 부분 뭉텅이도 전체처럼 풀수 있을때 적용시키는 것 같다. 뭔가 부분문제도 전체..
-
백준 11780(플로이드 2)전공/알고리즘 2020. 7. 10. 15:44
https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n(1≤n≤100)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 www.acmicpc.net https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 � www.acmicpc.net 이 문제에서 훨씬 더 어려운 조건..
-
백준 1865(웜홀)전공/알고리즘 2020. 7. 10. 00:21
https://www.acmicpc.net/problem/1865 1865번: 웜홀 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀 www.acmicpc.net 운동하려고 노트북 켰다가 학교 학회의 갓 906bc의 답변을 받고 깨달았다. 그래서 지금 정리하지 않으면 내일 또 귀찮아 할까봐 지금 쓰게되었다. 이 문제는 사이클이 존재하냐 안 하냐의 문제이다. 과연 사이클은 어떻게 알 수 있을까? 다수 vs 다수 최단거리를 구하는 걸 두번하면 되지 않을까 생각을 한다. 결론은 플로이드 와샬을 두번? 사용하면 어떨까. 만약에 그러니깐, 최단 거리로 가려고 하는..
-
백준 1738(골목길) 벨만포드전공/알고리즘 2020. 7. 9. 18:05
https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 �� www.acmicpc.net 벨만포드 알고리즘을 알고 있으면 딱 봐도 벨만포드 알고리즘을 사용하는 문제같다. 왜냐하면 음수간선이 존재하고, 사이클이 존재하는지도 확인을 해야하는 문제이기 때문. 문제에서 지나갈 때마다 계속해서 돈을 줍고, 잃는다고 하니 그냥 일반 최단거리 문제처럼 풀 수 있다. 아 그런데 여기서 돈을 최대한 적게 뺏기고, 많이 얻어야 하므로, 최대거리를 구하는 문제가 된다. 역시 ..
-
백준 11657(타임머신)전공/알고리즘 2020. 7. 3. 17:29
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 개빡대가리였었던 문제 N개의 도시가 있고, M개의 이동경로가 있다. 만약 1번의 도시에서 나머지 도시까지 최단경로로 갈때, 그 최단거리를 구하는 문제. 다익스트라 하지만 다 익스트라에서는 음수의 간선을 사용할 수 없다. 왜냐하면 일단 다익스트라는 순환구조가 불가능하기 때문이다. 그렇기 때문에 음수의 간선이 들어가면 계속해서 순환하는 경우..
-
백준 1068(트리)전공/알고리즘 2020. 7. 1. 15:18
https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 어떤 트리에서 어떤 index이하의 subtree를 모두 제거 했을때 리프노드의 갯수를 구하자 리프노드는 트리에서 자식이 없는 노드를 리프노드라고 한다. 그렇다면 트리를 구성해서, root부터 자식 노드를 방문, 만약에 자식 노드가 없는 경우 +1 하면 된다. 그리고 어떤 index의 subtree를 제거해야 하므로 index를 방문하면 그냥 스킵. 여기서 두가지 상황이 나온다. 만약에 제거..
-
백준 2263(트리의 순회)전공/알고리즘 2020. 7. 1. 12:57
https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net https://xkdlaldfjtnl.tistory.com/44 백준 4256(트리) https://www.acmicpc.net/problem/4256 4256번: 트리 문제 이진 트리는 매우 중요한 기본 자료 구조이다. 아래 그림은 루트 노드가 유일한 이진 트리이다. 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며 xkdlaldfjtnl.tistory.com 이 문제와 완벽하게 동일한 문제. 단지 차이점은 문제의 예시가 좀..