전공/알고리즘
-
백준 1937(욕심쟁이 판다)전공/알고리즘 2020. 7. 17. 14:20
https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 무슨 문젠지 모르겠는 문제 그냥 dp인걸 알아서 풀었다 정도? ㅈ 같은 판다 아무튼 생각을 진짜 많이 했다. 집중해서 계속 하다보니깐 떠오른 사실이 있었다. 가장 큰 값 순서대로 처리하면 꼬일 일이 없다. 여기서 말하는 꼬일 일이란 내가 만약에 큰 값대로 처리를 하는데 어떤 값 처리 후에 그 값의 dp변화가 생기는 것이다. 예제에서 가장 큰 값인 16을 먼저 처리해보자. 16 상 하 좌 ..
-
백준 2213(트리의 독립집합)전공/알고리즘 2020. 7. 16. 16:10
https://www.acmicpc.net/problem/2213무 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 �� www.acmicpc.net 먼저 이 문제를 dp문제라고 생각하자. 요즘 dp스터디라서 dp인걸 알고 풀고 있음. 문제 이해부터 하자면 트리가 있을때, 인접한 정점은 고르지 못한다. 이 조건을 만족하면서 고른 정점들의 가중치 합이 최대가 되는 값과 그 고른 정점들을 구하려는 문제이다. 결론부터 얘기하면 subtree로 나눈다. subtree들이 모여서 그 위의 부모트리의 값을 결정한다...
-
백준 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를 방문하면 그냥 스킵. 여기서 두가지 상황이 나온다. 만약에 제거..