Ikjo's Technology blog

문제 설명 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 접근 방법 해당 문제는 DFS를 통한 백트래킹을 이용하여 해결할 수 있었습니다. 우선 로봇이 이동하는 평면을 나타내야 하는데, 로봇은 이 평면의 중심상에서 출발하여 동, 서, 남, 북 각각의 방향으로 이동할 수 있어야 합니다. 이때 이러한 평면의 전체 크기는 주어지는 정수 n의 크기와 규칙이 있었습니다. if n = 1, then 3 x 3 board if n = 2, then 5 x 5 board if n = 3, then 7 x 7 board...

문제 설명 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 접근 방법 해당 문제에서는 이진 트리 구조를 전위 순회한 결과를 순서대로 제공해주고 이 결과를 통해 해당 이진 트리 구조를 후위 순회한 결과를 요구하고 있습니다. 우선 해당 문제를 풀기 위해서는 전위 순회(루트 - 왼쪽 노드 - 오른쪽 노드 순 탐색)한 결과만으로 본래 이진 트리 구조를 만드는 것이 급선무였습니다. 이진 트리 구조는 단순하게 특정 노드를 추가할 때 루트 노드를 기준으로 작으면 왼쪽에, 크면 오른쪽에 배치하고 이후 부모 노드..

문제 설명 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근 방법 해당 문제에서는 n * n 체스판에서 n개의 퀸이 서로를 공격할 수 없도록 배치할 수 있는 경우의 수를 요구하고 있습니다. 직관적으로 n개의 퀸을 해당 체스판에 배칠할 수 있는 모든 경우의 수를 구하여 퀸들이 서로 공격하는 여부를 점검하고자하면 압도적인 시간초과가 발생합니다. 왜냐하면 n은 최대 15로, 15개의 퀸을 225칸의 배치할 수 있는 경우의 수가 엄청날 뿐만 아니라, 퀸 서로간 공격 유무를 점검하는 작업은 시간 복잡도 성능이 매우 떨어지기 때문입..

문제 설명 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 접근 방법 해당 문제에서는 전체 n명(짝수)의 사람과 i번 사람 및 j번 사람이 같은 팀에 속했을 때의 능력치가 주어졌을 때 그리고 n명의 사람이 반으로 나누어 팀을 이루었을 때 각 팀의 능력치 차이가 가장 적은 값을 요구하고있습니다. 처음 이 문제를 봤을 때 어떤 규칙성을 찾기 보다도 브루트포스 및 백트래킹을 이용해야겠다는 생각을 우선적으로 했습니다. 지금 생각해보면 어리석었지만 저는 각 팀원별 순서를 따지는 경우의 수인 순열을 이용하면서 모든 경우의 수를 따졌었습니다. ..

문제 설명 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 접근 방법 해당 문제에서는 각각의 CCTV의 동작별로 사무실을 감시했을 때 해당 사무실의 사각지대가 가장 최소일 때의 값을 요구하고 있습니다. 우선 5개의 CCTV별로 각각의 동작 방식들을 구현했습니다. 기본적으로 모든 CCTV는 동, 서, 남, 북 일직선 방향으로 감시를 할 수 있으므로 기본적인 동작들을 구현한 뒤 각각의 CCTV별로 이 동작들을 활용하도록 했습니다. 이후 사무실 데이터를 입력받을 때 CCTV 정보들을 List에 저장시켰습니..