모나오랭의 개발일지

https://www.acmicpc.net/problem/16566  철수가 낸 카드에 맞춰 민수는 효율적으로 카드를 내야 합니다. 우선 민수의 카드 배열을 오름차순으로 정렬해주고, 유니온 파인드(union-find)를 사용해주면 됩니다. 이때 부모 배열의 인덱스의 값을 카드의 숫자와 동일하게 초기화합니다. 즉 parent[i] = i 의 형태로 초기화합니다. 철수가 낸 카드보다 최소한으로 큰 카드를 내기 위해서 부모 배열을 업데이트할 때, 낸 카드의 부모를 오른쪽 숫자(인덱스)로 맞춰주면 됩니다. 이를 표로 통해 설명하자면, 다음과 같이 초기화를 완성한 상태입니다.인덱스1234567부모1234567 민수의 카드는 1부터 7까지 있고, 처음에 철수가 4를 냈다고 가정해봅시다. 그럼 민수의 카드 배열에서 ..

https://www.acmicpc.net/problem/30621  다이나믹 프로그래밍(DP)를 사용하여 문제를 풀어주면 됩니다. 시간 배열이 1차원이므로 형태가 복잡하진 않습니다. 문제의 DP 규칙은 다음과 같습니다. 1. dp[i] = dp[i - 1] -> i번째 시간에 '어'를 외칠 수 없는 경우2. dp[i] = confuse[i] -> i번째의 혼란이 이전 최종 혼란보다 큰 경우3. dp[i] = dp[index] + confuse[i] -> i번째 시간에 '어'를 외칠 수 있는 경우 3번째 규칙을 판단하려면 이전 dp값들 중 가장 큰 누적 혼란을 가진 index를 찾아야 하는데, 선형 탐색은 시간 복잡도가 크므로 이분 탐색(binary search)을 사용해줍니다. dp[index]보다 c..

https://www.acmicpc.net/problem/20303  유니온 파인드(Union-Find)와 다이내믹 프로그래밍(DP)을 이용하는 것이 큰 틀입니다. 처음에 DP를 사용하지 않고 문제를 풀어갔는데, 친구 그룹이 꼭 하나란 보장이 없기에 DP를 사용해야 되는 것을 깨달았습니다.. (ex. K = 8, 각각 3명, 4명씩 친구인 그룹의 총 사탕 합이 최대일 수 있음) 1. 아이들이 가지는 사탕 개수 배열, 유니온 파인드의 부모 배열, 루트를 중심으로 그룹에 속한 아이들의 수를 저장하는 사이즈 배열, 최대 사탕 수를 저장하는 dp 배열을 생성합니다. 2. 친구 관계를 입력받을 때마다 유니온 파인드를 통해 아이들의 관계를 정리합니다. 이때 하위 그룹을 귀속할 때 상위 그룹의 루트에 하위 그룹의 사..

https://www.acmicpc.net/problem/17404   문제와 흡사하게 다이나믹 프로그래밍(DP)을 사용하는 문제입니다.근접한 집들끼린 같은 색으로 칠하지 않아야 하는데, 추가로 처음 집과 마지막 집의 색도 달라야 합니다. 처음에 문제를 풀 때 첫번째 집의 색의 정보를 저장한 배열을 따로 만들어 DP를 실행할 때마다 새로 저장을 했습니다.  너무 복잡하고 연산이 뜻대로 되지 않았습니다. 다시 문제를 풀 때 dp[n - 1][i]의 처음 집 색을 구하고 n번째 집의 색을 다른 두 가지 중 cost가 낮은 색을 택하려고 했습니다. 하지만 처음 시도와 달리 첫 집의 색을 저장하지 않아 답이 안 나왔습니다. 그래서 처음부터 집 색을 하나 정하고, 그다음에 DP를 진행하여 마지막 집의 색을 처음 ..

https://www.acmicpc.net/problem/11729  하노이 탑의 이동 조건은 작은 원판 위에 큰 원판이 오지 않는 한에서 판을 이동시킬 수 있습니다.n개의 원판이 있을 때 반대 기둥으로 옮기는 움직임의 총횟수는 2^n - 1> 입니다. (원리는 생략...) 재귀 함수를 사용하여 문제를 풀 건데, 문제는 원판의 개수에 따라 이전 원판들이 이동하는 기둥이 달라집니다. 이를 해결하기 위해 각 함수마다 출발 기둥과 경유 기둥, 목표 기둥을 설정하여 각 원판마다 올바르게 움직임을 출력할 수 있도록 해줍니다.  #include void hanoi(int n, int start, int mid, int end) { if(n >= 2) { hanoi(n - 1, start, end,..

https://www.acmicpc.net/problem/2467  용액을 하나씩 정하여 합의 특성값이 0에 가장 가까운 페어 용액을 찾으면 됩니다. 이중 반복문으로 페어 용액을 탐색하기엔 시간 복잡도가 O(n^2)이 되므로 시간 초과가 뜰 것입니다. 이를 해결하기 위해 이분 탐색을 사용하면 되는데, 특정 페어 용액을 찾는 것이 아닌 합의 특성값이 최소가 되는 용액을 찾는다는 점에서 막혔습니다. 이를 해결할 방법으로 타겟 페어 용액을 특정 용액 * (-1)>으로 지정하고 이와 가장 가까운 페어 용액을 이분 탐색으로 찾아내면 됩니다.  #include #include int n;long double liq[100000];long double sum = 2000000000;long double l1, l2;..

https://www.acmicpc.net/source/83170616 카잉 달력의 수학적 규칙을 찾는다면 이 문제는 어렵지 않게 풀 수 있습니다. (하지만 그 규칙을 찾는게 제일 어렵..) 카잉 달력의 특징으로 에서 해가 지나면 x와 y가 동시에 증가한다는 점입니다. 즉 x따로, y따로 연산을 해도 상관이 없습니다. 저는 이 점을 이용해서 문제를 풀었습니다. x와 y는 임계값 m, n이 정해져 있기에 m, n의 내에서 숫자가 반복됩니다. 즉 x와 y는 연도를 각각 m과 n으로 나눈 나머지입니다. 따라서 특정 연도를 계산할 때 x를 만족시키는 임의의 연도 A가 y도 만족시킨다면 A가 우리가 찾는 특정 연도가 되는 겁니다. 연도를 계산하는 과정은 다음과 같습니다. 1. x를 만족하는 임의의 연도를 구한다...

https://www.acmicpc.net/problem/11286  지난 글에서 풀었던 1927번 "최소 힙" 문제와 거의 똑같습니다. 차이점은 출력하는 원소가 절댓값의 최소입니다. 이는 C언어의 stdlib 라이브러리의 함수 abs()를 통해 간단하게 판단할 수 있습니다. abs() 함수는 인자의 절댓값을 반환합니다. 근데 문제를 보면 절댓값이 같은 원소가 여러 개이면 그중 작은 수를 출력하고 제거한다고 합니다. 즉 음수가 있으면 음수를, 없으면 양수를 출력 후 제거하면 됩니다. 이는 힙 알고리즘에서 abs()로 절댓값을 비교하고, 둘의 값이 같다면 해당 key가 음수인 경우에 계속 정렬을 진행해주면 됩니다. key가 양수이면 비교하는 대상이 음수든 양수든 진행을 할 필요가 없습니다.  #includ..

https://www.acmicpc.net/source/83167848  값을 추가하고 힙을 정렬해주는 알고리즘과, 힙의 가장 작은 값을 제거하고 다시 힙을 정렬하는 알고리즘 두 가지가 필요합니다. 이는 힙의 기본적인 알고리즘으로 숙지해두면 좋습니다. 힙 정렬은 시간 복잡도가 O(nlogn)이기 때문에 bubble, insertion, selection sort보다 높은 성능을 보여줍니다. 최소 힙 or 최대 힙의 정렬과 첫번째 값 제거의 원리는 구글링, 자료를 참고하시면 됩니다(그리기가 복잡쓰..). 함수 ins()가 값을 추가하고 힙을 정렬하는 알고리즘입니다. 함수 del()가 가장 작은 값(힙의 가장 첫 인덱스값)을 제거하고 힙을 정렬하는 알고리즘입니다. 힙 원소의 개수가 0이면 0을 출력해야 하기..

https://www.acmicpc.net/problem/1931  회의의 개수를 최대로 하기 위해선 종료 시각이 빠른 회의를 먼저 진행하면 됩니다. 빨리 끝나야 그 다음 회의를 진행할 수 있는 가능성이 높아지기 때문이죠. 그리고 종료 시각이 같다면 시작 시각이 빠른 회의를 먼저 진행합니다. 그 이유는 시각에 따라 회의를 정렬할건데, 종료 시각이 빠른 회의가 끝나면 그 다음 시작 시각이 빠른 회의를 바로 진행할 수 있기 때문입니다. 따라서 회의를 정렬해주는게 이 문제의 선수과제입니다. C언어 내장함수인 qsort를 이용하여 시간 복잡도를 줄여줍니다. 정렬한 회의의 가장 첫번째 회의는 무조건 진행하는 회의이므로, 해당 회의가 끝나는 시각을 기점으로 다음 회의들의 시작 시각과 비교하여 더 빠르지 않다면 그 ..