돌이 코딩하는 방

문제 태그 : https://www.acmicpc.net/problem/2162 문제 소개 만나는 선분끼리 싹다 그룹을 만들어서 그룹의 갯수와 최대 그룹의 크기를 출력하는 문제 문제 풀이 선분 교차 알고리즘을 이용해 만나는 선분을 판별하고, union & find를 이용하여 그룹을 만들어 주는 문제. 출력처리는 조상의 번호별로 갯수를 세면 간단하게 할 수 있는 것 같다. 선분교차와 union&find를 모른다면 각각 이글과 이글을 참고하자. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52..

문제 태그 : https://www.acmicpc.net/problem/15647 문제 소개 간선의 가중치가 있는 트리가 주어진다. 1번 노드 부터 N번 노드까지 각 노드에 대해서 다른 모든 노드에서 그 노드까지의 거리의 합을 출력하시오. 문제 풀이 처음에는 하나당 O(logN)에 구하는 방법을 생각했다. HLD나 centriod decomposition을 떠올렸지만, 잘 모르는 쪽이기 때문에 더 이상 풀이를 떠올릴 수 없었다. 분명히 centriod를 활용해 풀 수 있을 것 같긴하다. 그래서 전체를 O(N)으로 구하는 방식으로 바꾸었다. Tree DP를 이용하는 방식이다. F[i] = 내 서브트리의 노드들이 i번 노드까지 오는데 걸리는 거리의 합 cnt[i] = 내 버스트리의 노드 수 dp[i] = 내..

문제 태그 : https://www.acmicpc.net/problem/18292 문제 소개 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. 문제 풀이 숫자가 작고 인접한 칸을 고르지 않는다는 조건. Bit를 활용한 DP가 풀이로 바로 떠오른다. 한 줄에 대해서 0~2^m 까지를 고르는 경우를 모두 고려 해주면 된다. 각 숫자별로 켜져 있는 비트가 골라진 칸 이라고 생각하면 된다. dp[i][j][k]= i 번째 줄까지 j 개의 칸을 선택했으며, 마지막 (i번째) 줄 의 선택된 모양이 k일때 최댓값이다. 총 테이블의 크기는 O(NK 2^M)이고, ..

문제 태그 : https://www.acmicpc.net/problem/17955 나한테 잘 맞는 문제였다. 정말 좋은 문제라고 생각한다. 문제 소개 n,m이 주어진다. 이후 1 이상 m 이하의 수 n개가 주어진다. n개의 숫자는 원형으로 이루어져 있다. 이후 2가지 행동을 할 수 있다. 1. 어떤 한 칸을 골라 그 수를 max(원래 숫자, 왼쪽의 숫자, 오른쪽 숫자)로 바꾼다. 2. 어떤 한 칸을 골라 그 수를 min(원래 숫자, 왼쪽의 숫자, 오른쪽 숫자)로 바꾼다. 원형으로 이루어진 n개의 숫자를 모두 (1,2,3,...m)으로 만드는데 필요한 최소 행동의 횟수를 각각 구하시오. 만약 만들 수 없다면 -1을 출력한다. 문제 풀이 스포 주의! Step1. 문제 관찰 문제의 예제를 봄으로써 몇가지 사실..

문제 태그 : https://www.acmicpc.net/problem/1006 앞에서 순서대로 푸는 사람들이 절망할만한 문제이다. 1000~1005 보단 확실히 난이도가 있다. 문제 설명 원형 2열로 배치된 2n 개의 칸을 최소 그룹의 갯수로 묶어야 한다. 그룹에는 조건이 있다. 최대 2개가 같은 그룹일 수 있으며, 배치 상에서 연속된 칸이어야 하고, 두 칸의 값의 합이 m을 넘지 않아야 한다. 2칸이 한 줄이고 n줄이 있다고 생각하면 된다. 문제 풀이 DP를 쓰고 싶은 느낌이 들었다. 어떤 줄까지 다 채우는데 사용된 최소 그룹의 갯수를 이용해 다음 줄까지 채우는데 사용된 최소 그룹의 갯수에 영향을 준다고 생각할 수 있기 때문이다. 하지만 문제가 있다. 어떤 칸을 채울 때에는 이전 칸을 완벽히 채운 상..

문제 태그 : https://www.acmicpc.net/problem/1520 문제 설명 문제 풀이 (사고의 흐름) (1,1)에서 (n,m)으로 갈 수 있는 경우의 수 찾기. 경우의 수를 찾는 것이고, 어떤 칸까지 갈 수 있는 경우의 수는 그 칸으로 올 수 있는 경우의 수의 합으로 표현된다. 따라서 이 문제는 2차원 DP로 해결 할 수 있다. 2차원 필드에서 진행되는 보통의 간단한 DP 문제 같은 경우에는 오른쪽 혹은 아래로 밖에 움직이지 못한다. 따라서 (i,j)는 (i-1,j)와 (i,j-1)로 표현이 된다. 하지만 이 문제는 그렇지 않다. 어떤 (i,j)의 칸으로 올 수 있는 칸은 주위의 4칸 중 (i,j)보다 숫자가 큰 칸이다. 따라서 (i,j)에 대한 경우의 수를 확실하게 구하기 위해서는 주변..

문제 태그 : https://www.acmicpc.net/problem/4243 문제 설명 문제 풀이 (사고의 흐름) 일단 DP라는 것을 어느정도 바로 생각할 수 있었다. 직선에서 하는 DP인데 N이 작기 때문에 N^2이라고 생각을 했고, 이러면 보통 DP[i][j]는 i에서 j까지 ~~~ 라고 생각했다. 여기서 우리는 i 부터 j까지 다 들렀다면 당연히 최종위치는 i또는 j라는 것을 알 수 있다. 들르는데 걸리는 시간은 0이기 때문에 중간에 띄고 건널 이유가 아예없다. 그래서 관찰한 사실을 토대로 DP[state][i][j]는 state의 방향에 있으면서 i부터 j까지 들리는데 기다림의 합의 최소라고 생각할 수 있다. 하지만 이러면 문제가 있다. 지금까지 대기시간의 총합이 최소가 되는 경우가 지금까지 ..

문제 태그 : https://www.acmicpc.net/problem/1848 다익스트라에 관해 포스팅을 하다가 백준 다익스트라 문제들을 살펴보았는데, 한 문제 시도하다가 틀린 흔적을 발견했다. 그래서 그 문제를 풀게 되었는데, 굉장히 좋다고 생각하여, 풀이도 저장할겸 포스팅을 하게 되었다. 문제 설명 양 방향 그래프가 주어지는데 일반적인 양방향 그래프와 다른 점은 A점에서 B점으로 갈 때의 비용과 B점에서 A점으로 갈 때의 비용이 다르다는 것이다. 이때 목적은 1번 정점에서 출발하여 1번 정점으로 다시 돌아오는 최단거리를 구하는 것이다. 이때 한 번 지난 간선은 역으로도 다시 올 수 없다는 것이다. 즉 다시 말해, 1->3->1의 경로로 이동하는 것은 안된다는 것이다. 문제 풀이 (사고의 흐름) 일단..

문제 태그 : https://www.acmicpc.net/problem/1753 문제 설명 이 문제에서 요구하는 것은 방향그래프에서 특정 정점이 주어졌을 때 그 점으로부터 모든 점까지의 거리를 각각 구하는 것이다. 이는 다익스트라 알고리즘이 하는 일과 정확히 일치한다. 맞다. 다익스트라를 한번 연습해보라는 뜻이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include using namespace std; typedef long long int ll; typedef pair pii; #define ff first #define ss..

문제 태그 : https://www.acmicpc.net/problem/1260 문제 설명 사실 풀이라고 할 것은 딱히 없다. 문제의 제목 부터 내용까지 DFS와 BFS를 한 번 해보시오 라는 뜻의 연습문제이다. DFS와 BFS에 대한 개념을 알아야지 풀 수 있으며, 알 면 풀 수 있다. DFS와 BFS에 대한 설명은 여기에 나와있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include using namespace std; int vid[10101]; int vib[10101]; vector ed..