문제 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 방법 멀티탭 구멍의 개수 N과 전기용품의 총 사용 횟수 K가 주어진다. 그 뒤 사용 순서대로 K 이하의 수가 K만큼 주어진다. 쉽게 말해서 두 번째 줄 i번째 입력의 값은 i에 사용하는 기기라는 뜻이다. 페이지 교체 알고리즘이 떠오르는 문제이며, 교체 횟수가 최소가 되는 알고리즘은 바로 가장 오랫동안 사용되지 않는 페이지를 교체하는 최적(Optimal) 알고리즘이다. 다만 실제로는 앞으..
프로그래밍/Algorithm
문제 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 풀이 방법 센서를 점으로 보면 다음과 같이 해석된다. 일직선상에 N개의 점이 있을 때 이들을 다 포함하는 길이의 합이 최소가 되는 K개의 선분을 만든다. 선분 사이의 K-1개의 공간이 생기게 되는데, 이 공간들을 가장 크게하면 선분 길이 합이 최소가 된다. 점들을 오름차순으로 정렬한다. 인접한 점들 간 거리(선분 길이)를 내림차순으로 정렬한다. 인접한 점들 간 거리를..
문제 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 풀이 방법 처음의 대략적인 생각은 다음과 같다. 시작점 좌표와 두 번째 좌표를 리스트에 넣는다. 3~4를 세대 g만큼 반복한다. 끝점 기준으로 기존 좌표들을 회전시켜 새로운 좌표를 만든다. (회전은 회전행렬을 사용한다.) 만들어진 좌표를 리스트에 넣는다. 리스트를 순회하면서 2차원 배열에 점을 찍고 그 점이 사각형을 이루는지 검사한다. 회전행렬에 대해서 인터넷을 찾..
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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 #include #define MAX_SIZE 30 int getSize() { int n = 0; while (1) { printf("n 입력(홀수, 최대 %d): ", MAX_SIZE); scanf("%d", &n); if (n > MAX_SIZE) { printf("%d보다 큰 수를 입력하셨습..
