이마닷의 블로그

0. 문제 https://www.acmicpc.net/problem/15954 15954번: 인형들 첫 번째부터 세 번째까지의 인형을 선택하면 표준편차는 2/3의 양의 제곱근이 되고, 이 때 표준편차가 최소가 된다. 두 번째부터 네 번째까지의 인형을 선택하는 경우와, 세 번째부터 다섯 번째 www.acmicpc.net 1. 문제분석 - 주어진 최소 개수 이상의 크기 만큼 순차적으로 표본집합을 만들어 분산 및 표준편차 값을 구하는 비교적 단순한 브루트 포스(Brute Force) 문제이다. 2. 주의할 점 - 값이 double 또는 float으로 이루어지다 보니, 소수점 이하의 값이 처리 도중 잘못 바뀌는 상황에 유의하며 문제를 풀어야 한다. 특히 위 수식 중 두번째 수식처럼 곱하기, 나누기의 연산이 더 ..

0. 문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제분석 - N개의 퀸을 체스판에 배치하는 모든 경우의 수에 대해 판단해야 하므로 Brute Force방식으로 각 좌표에 queen이 있는 상황을 다 따져보아야 한다. - N개의 queen이 있는 상황에 대해 조건 만족을 판단하기 위해 체스판을 설정한 뒤에는, 다시 또 다른 경우의 수를 판단하기 위해 체스판의 설정을 되돌려놓은 후 다른 경우의 수를 탐색해야 한다. 따라서 BackTracking 알..

0. 문제 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 1. 문제분석 - 처음에는 맨 처음 숫자를 눌러 가장 가까운 채널로 이동해 +, - 버튼에 따라 목표지점에 도달하는 최단 거리만 구하면 된다고 생각해서 BFS로 쉽게 풀 수 있을 것이라 생각했다. 하지만, 가장 가까운 채널로 이동하기 위해 가장 가까운 채널을 구하는 방법이 꽤나 복잡해져서 포기했다. 결국에는 이동 가능한 모든 채널로 이동해보고 해당 채널에서 목표지점까지 ..