모나오랭의 개발일지

https://www.acmicpc.net/problem/1058  노가다 느낌으로 두 사람을 기준으로 나머지 사람들을 탐색해 서로 친구먹고 있으면 2-친구로 간주하면 되겠다고 생각했는데, 후에 보니 플로이드-워셜(Floyd-Warshall) 알고리즘이었더군요.. (아니 지지난달에 학교에서 배운건데 그새 까먹었네)  1. 입력에 따라 이차원 배열을 저장합니다. 이 때 Y이면 1, N이면 inf 를 저장합니다. inf 는 구분이 가능한 아주 큰 숫자나 음수로 설정하면 됩니다. 2. 반복문을 통해 서로 공유하는(?) 친구가 있으면 배열의 값을 바꿉니다. 이 때 inf 를 제외하면 2가 최대입니다. (직접 친구면 이미 1, 경유해서 친구면 2) 3. 각 사람마다 2-친구의 수를 저장하고, 이 중 최댓값을 구합..

https://www.acmicpc.net/problem/11650  문제 자체는 매우 간단하나, 시간 제한이 1초이기에 C언어 내장 함수 qsort를 사용했습니다. 구조체도 qsort를 사용해 쉽게 정렬할 수 있기에 qsort 사용 요령을 잘 익혀야겠습니다. 1. 좌표를 구조체로 정의하여 배열에 저장합니다. 2. qsort를 이용해 배열을 정렬합니다. #include #include typedef struct {        int x;        int y;}point;int compare(const void *a, const void *b) {        point* p1 = (point*)a;        point* p2 = (point*)b;        if(p1->x != p2->x) ..

https://www.acmicpc.net/problem/1057  사실 서로 대결을 안 할 일이 없기 때문에 -1 출력 부분을 따로 작성하진 않았습니다.처음에 홀수가 라운드를 진행할 때 부전승 때문에 복잡하게 생각을 했는데, 그냥 (번호 + 1) / 2 를 하니까 모두 감안하여 계산이 되더군요. 이걸 알고 나니 코드가 훨씬 간결해졌습니다.  1. 라운드 횟수를 추가하며, 총 번호 개수와 둘의 번호를 절반으로 줄입니다. 2. 둘의 번호가 같아지면 같은 라운드를 진행했다는 뜻이므로 종료합니다.  #include int count = 0;void game(int n, int k, int l) { if(k == l) return; count++; game(n/2, (k+1..

https://www.acmicpc.net/problem/1015  문제를 이해하는게 제일 어려운 부분입니다. 진짜 간단하게 요약하자면, 입력한 숫자가 몇 번째로 큰 지 구하는 겁니다..ㅋㅋ 예제 입력 2로 설명하자면, 수열 A 을 작은 순위로 나타내면 입니다. 이게 P 입니다. 서로 같은 숫자일 땐 오른쪽 애가 더 큰걸로 간주합니다(사전순이기 때문!).  1. 행렬을 저장합니다. 2. 순위를 저장하는 행렬에, 반복문을 통해 비교하여 해당 인덱스의 숫자가 얼마나 큰지 저장합니다.  #include int p[50] = {0,};int main() { int n; scanf("%d", &n); int a[n]; for(int i = 0; i

https://www.acmicpc.net/problem/1913   1학년 때 C언어 과목 기말고사 1번 문제로 나온 것이 기억납니다. 그 땐 손도 못댔는데 금방 규칙이 보이더군요.  1. 아래, 오른쪽, 위, 왼쪽 순서로 인덱스 이동을 하는데, 한 바퀴를 돌면 안쪽도 똑같이 진행해주면 됩니다. 2. 인덱스의 행 부분을 ridx, 열 부분을 cidx 로 놓았습니다. 그리고 한 바퀴를 돌 때 한 방향으로 n - 1 만큼 진행합니다. (이 때 n은 정사각형의 한 변 길이) 3. 한 사이클의 첫 시작은 따로 숫자를 저장하고, 아래 오른쪽 위 방향은 n - 1 만큼 진행, 왼쪽은 n - 2 만큼 진행합니다. 그리고 ridx++ 를 하여 다음 사이클을 시작합니다. 이 때 찾는 숫자가 나오면 해당 ridx, ci..

https://www.acmicpc.net/problem/18110  상위 15%와 하위 15%를 계산한 후 마지막 절사평균을 계산할 때 C언어 라이브러리의 round 함수를 사용하면 됩니다.round 함수는 변수의 소수점을 반올림하는 함수입니다. 상하위 %를 인덱스로 쉽게 가리기 위해 정렬을 하는데, C언어 내장 함수인 qsort 함수를 사용했습니다. qsort의 시간복잡도는 O(nlogn)이기에 시간 초과 방지에도 좋습니다.  1. 난이도를 배열에 저장합니다. 2. 배열을 정렬합니다. 오름차순이냐 내림차순이냐는 크게 상관없습니다. 이후 사용자들의 의견의 개수에 따른 상하위 15%의 값을 구합니다. 3. 상하위 15%의 값에 따라 난이도의 평균을 구합니다. 이 때 round 함수를 사용합니다.  #in..

https://www.acmicpc.net/problem/1932  배낭 문제와 원리가 같은 다이나믹 프로그래밍(DP) 문제입니다. 최댓값을 구하는게 그나마 다른 점...?밑으로 진행할 수록 경우의 수가 하나씩 증가하는데, N번째 줄에서 연산하는 인덱스가 N - 1 을 넘지 않으므로 따로 초기화할 필요 없이 N * N 크기의 배열을 이용하면 됩니다.  1. 문제에서 입력받는 숫자들을 저장하는 2차원 배열과 합의 경우의 수를 줄마다 저장하는 2차원 배열 dp[][] 를 생성합니다. 2. 경우의 수를 저장하는 2차원 배열에 합을 저장할 건데, 이 때 저장하는 방법으로 이전 줄의 왼쪽과 오른쪽 숫자 중 그동안 누적 합이 더 큰 부분을 고른 후 현재 줄의 숫자를 더합니다. 다시 말해 더 큰 숫자를 고르는 것이 ..

https://www.acmicpc.net/problem/22940  처음으로 플레티넘 문제를 풀어서 기분이 아주 좋았습니다ㅋㅋㅎㅎㅋㅋ (2학년이 끝나서야..ㅠㅠ)사실 선형대수학을 공부하셨다면, 문제 조건이 해가 모두 자연수이므로 구상 자체는 어렵지 않을 겁니다.하지만 가우스 소거법이 생소하다면 막막할 수 있습니다. 원리만 알면 문제를 풀 수 있으므로 가우스 소거법에 대해 알아보겠습니다.코드는 설명 밑에 있습니다. 가우스 소거법 (Gauss Elimination)  가우스 소거법이란, 위의 문제처럼 선형 연립 방정식이 주어졌을 때 해를 구할 때 사용하는 방법입니다. 이 때 선형 방정식이란 최고 차항의 지수가 1인 방정식을 말합니다. 중학생 때 처음 함수를 그리면 일차 함수의 경우 직선을 그리잖아요? 그래..

https://www.acmicpc.net/problem/12919 처음엔 BFS로 S에 A 또는 B를 붙이면서 경우의 수를 늘려가 T와 같아지는 순간이 생기면 1을 출력하고 프로그램이 종료되는  방식을 구상하였으나 문자열이기도 하고, 뒤집는 경우도 생각해야 하기에 잘 풀리지 않았습니다.그러다 반대로 T를 기준으로 A 또는 B를 없애면서 S와 같아지는 순간을 찾는 방식이 훨씬 간단하다는 것을 깨달았습니다.이 때 위의 예시 1번을 보면 T가 인 경우, S가 일 때와 일 때 각각 알파벳 제거 과정이 마지막에 달라집니다.  두 경우를 모두 감안하여 두 경우 각각 재귀 함수를 돌려야 합니다.  1. 재귀 함수의 결과를 올바르게 출력하기 위해 출력 변수 check를 전역 변수로 0으로 선언합니다. 2. T의 맨 ..

https://www.acmicpc.net/problem/2805  나무 배열을 따로 정렬할 필요 없이 가장 높은 나무의 높이를 기준으로 시작해서 기준을 하나씩 낮추며 자를 수 있는 나무 높이의 총합을 구하면 됩니다. 그래서 그냥 단순하게 반복문을 중복해서 썼더니 시간 초과...시간 복잡도가 O(n^2)이면 시간 초과가 뜨므로 O(nlogn)인 이진 탐색을 이용하여 풀었더니 맞았습니다. 기준 높이를 0에서부터 시작하기에 더 직관적입니다. 1. 나무 배열을 순서대로 입력받습니다. 이후 가장 높은 나무의 높이를 구합니다.2. 기준 높이를 0에서 시작하여 이진 탐색을 통해 계속 조정하면서 자른 나무의 총합을 M과 비교합니다.  #include int main() { int n, m; scanf("%..