전체 글

문제 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 방법 멀티탭 구멍의 개수 N과 전기용품의 총 사용 횟수 K가 주어진다. 그 뒤 사용 순서대로 K 이하의 수가 K만큼 주어진다. 쉽게 말해서 두 번째 줄 i번째 입력의 값은 i에 사용하는 기기라는 뜻이다. 페이지 교체 알고리즘이 떠오르는 문제이며, 교체 횟수가 최소가 되는 알고리즘은 바로 가장 오랫동안 사용되지 않는 페이지를 교체하는 최적(Optimal) 알고리즘이다. 다만 실제로는 앞으..

문제 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차원 배열에 점을 찍고 그 점이 사각형을 이루는지 검사한다. 회전행렬에 대해서 인터넷을 찾..

문제 유형 문제는 알고리즘 + 객관식 + 주관식이 출제되었다. 알고리즘 탐색은 대충 알고 있는데, 구현이나 그리디 심화문제를 아직 잘 모르는 상태. 계속 문제를 풀어보면 될 것 같다는 생각이 들었다. solved.ac에서 프로필을 보면 다각형으로 어느 유형이 약한지 보여주는데, 약한 부분이 딱 문제로 나왔다. 객관식 및 주관식 특이하게도 컴투스는 알고리즘 문제에 객관식 & 주관식이 더해져 테스트가 진행되었다. 정보처리기사 수준의 문제, 게임 관련된 물리 문제, 렌더링 또는 그래픽 API에 관련된 문제가 출제되었다. 계산 문제도 좀 나왔는데 메모지 사용이 안되어서 머리로만 계산했다. CS는 나름 할만했지만 나머지는 최근에 공부한 적이 없어서 헷갈렸다. 공부해야할 것들을 정리해보면 게임 관련 알고리즘(A*,..