모나오랭의 개발일지

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를 이용하여 시간 복잡도를 줄여줍니다. 정렬한 회의의 가장 첫번째 회의는 무조건 진행하는 회의이므로, 해당 회의가 끝나는 시각을 기점으로 다음 회의들의 시작 시각과 비교하여 더 빠르지 않다면 그 ..

https://www.acmicpc.net/problem/1541  문제의 포인트는 괄호의 개수에 제한이 없다는 것입니다. 즉 식의 형태가 어떻게 되었든 '-'가 처음 나오면 그 뒷부분은 모두 음수의 합으로 표현이 가능합니다. 예시로 아무거나 2개를 적어보겠습니다 1. 10 + 20 - 30 + 40 + 50 -> 10 + 20 - (30 + 40 + 50) -> -90 2. 10 - 20 - 30 + 40 - 50 -> 10 - 20 - (30 + 40) - 50 -> -130 '-'가 나왔다는 것을 표시하기 위해 플래그를 사용해줍니다. 입력의 형태가 문자열이므로(C언어 기준) '+' 또는 '-'가 나왔을 경우 플래그가 1이면 숫자를 음수로 더해줍니다(빼줍니다). 숫자는 반복문을 통해 형태를 만들어줍니..

https://www.acmicpc.net/problem/2667  BFS를 이용해 단지 경로를 추적하고, 끝까지 이동할 수 없는 경우 이 경로를 하나의 단지로 간주합니다. 그다음 해당 단지의 집의 수를 저장하면 됩니다. 그러기 위해선 단지의 개수를 인덱스로 가지고 집의 수를 값으로 가지는 배열을 따로 추가해 주면 됩니다.  1. 지도를 입력받습니다. 지도의 숫자들이 붙어있으므로 문자열로 간주하고 반복문을 통해 하나씩 배열에 저장해줍니다. 2. 방문 여부 배열, 단지의 정보를 저장하는 배열을 생성합니다. 3. 너비 우선 탐색(BFS)을 이용해 지도를 탐색합니다. 시작 좌표를 기준으로 탐색을 실행하기에 시작 좌표를 인자로 받는 함수를 만들었습니다. 4. 더 이상 이동할 수 없는 경우, 단지 배열의 인덱스를..

https://www.acmicpc.net/problem/2630  백준 1074번 "Z" 문제과 비슷한 느낌이지만, 더 간단합니다. 색종이를 나누는 기준이 중간에 다른 색이 섞여있을 때잖아요? 그럼 한 영역을 탐색할 때 색이 한 종류면 더 이상 나누지 않고, 중간에 색이 다른 게 섞여 있으면 그 영역을 4등분해서 다시 탐색합니다. 만약 색이 촘촘히 섞여 있으면 영역의 크기가 1이 될 때까지 영역을 4등분 후 다시 탐색하게 될겁니다. 이는 재귀 함수를 통해 구현하면 됩니다. 함수는 탐색을 시작하는 배열의 시작 인덱스와 영역의 크기를 입력받도록 합니다. 그리고 그 영역 내의 종이 색이 한 종류면 해당 색의 종이 개수를 추가하고, 두 종류면 영역의 크기를 4등분 하여 함수를 호출합니다.  #include i..

https://www.acmicpc.net/problem/30804  과일을 앞뒤로 빼면서 최대 개수를 구하는 방법말고  다른 방식으로 접근해봤습니다. 문제의 조건은 "과일의 종류가 2가지 이하"인 상태에서 개수가 최대인 경우를 구하는 겁니다. 즉 임의의 두 종류의 과일이 서로 연속으로 붙어있는 개수가 가장 많은 경우가 문제의 답이 되는 겁니다. 따라서 반복문을 통해 과일의 번호 두 개가 서로 인접한 개수를 구하고, 그 중 최댓값을 구하면 됩니다.  #include #include int n;int fruits[200000] = {0,};int count_fruit[10] = {0,}; // 과일의 종류별 개수를 저장int main() { scanf("%d", &n); for(int i = 0..

https://www.acmicpc.net/problem/18111  노가다를 통해 최소 시간과 블록의 높이를 구하는 브루트포스 문제입니다.(변수가 은근히 많아 이름을 쓸 때 헷갈렸습니다..;) 별 다른 알고리즘을 쓰지 않아 문제 자체는 풀기 괜찮았습니다.  1. 입력받은 땅의 최고 높이와 최저 높이를 구합니다. 평탄화가 끝난 뒤 땅의 높이는 이 둘 사이의 값입니다. 2. 최대 높이와 최소 높이 사이에서 반복문을 통해 한 높이를 목표로 평탄화를 할 때, 쌓아야 하는 블록 개수와 파내야 하는 블록 개수를 구합니다. 3. 쌓아야 하는 블록 개수가 보다 많으면 해당 높이론 평탄화를 하지 못하므로 생략합니다. 4. 평탄화에 걸린 시간의 최솟값과 해당 높이를 구합니다. 시간이 같을 경우 높이가 더 높은 경우를 출..

https://www.acmicpc.net/problem/1389  플로이드-워셜(Floyd-Warshall) 알고리즘을 통해 우회하여 연결되어 있는 지를 확인하면 됩니다. 연결되어 있음을 저장하는 배열을 따로 만들 때, 플로이드 워셜 알고리즘을 사용하면서 초기화에 주의하면 됩니다.  1. 관계 배열을 입력받고, 베이컨 수를 저장하는 배열을 생성합니다. 2. 플로이드-워셜 알고리즘을 통해 베이컨 수를 업데이트합니다. 이 때 배열을 초기화하고 진행합니다. 3. 베이컨 수가 가장 작은 사람을(노드 번호) 출력합니다.  #include #include #define INF 1000000int n, m;int relation[101][101] = {0,};int bridge[101][101] = {0,};voi..