난이도 : 골드 4 걸린 시간 : 40분 문제 가장 가까운 공통 조상 문제 바로가기 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다. 예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다. 루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요..

난이도 : 골드 4 걸린 시간 : 20분 문제 전화번호 목록 문제 바로가기 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 풀이 b+tree 사용 코드 #include #include #include #include using namespace ..

난이도 : ? 걸린 시간 : 1시간 반 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다. x x x x 말 x x x x 근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포함되지 않는다. 이제 원숭이..

난이도 : 골드 1 걸린 시간 : 많이 문제 달이 차오른다 가자 문제 바로가기 민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다. 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨) 벽 : 절대 이동할 수 없다. (‘#’) 열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f) 문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F) 민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0) 출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1) 달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려..

난이도 : 골드 2 걸린 시간 : 1시간 문제 트리의 높이와 너비 문제 바로가기 이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다. 한 열에는 한 노드만 존재한다. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다. 이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 ..

난이도 : 골드 2 걸린 시간 : 1시간 문제 퍼즐 문제 바로가기 3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다. 1 2 3 4 5 6 7 8 어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 풀이 최단 경로 문제이므로 bfs 이용 memo 해야 똑같은 경로 다시 탐색 x memo는 전체 map의 상태를 저장해야함 string으로 저장 코드 #include #include #include #include #include using namespace std; int map[..

난이도 : 골드 5 걸린 시간 : 1시간 30분 문제 DSLR 문제 바로가기 풀이 DSLR이라는 4가지 경로가 있다고 생각하고 bfs 코드 #include #include #include using namespace std; struct point { int prev; char state; int visited = -1; }; char dslrArr[4] = { 'D', 'S', 'L', 'R' }; int dslrResult(int type, int num) { int tmp; switch (type) { case 0 : return (num* 2) % 10000; case 1 : if (num == 0) return 9999; else return num - 1; case 2 : tmp = num /..

난이도 : 골드 3 걸린 시간 : 30분 문제 다리 만들기 문제 바로가기 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 가장 짧은 다리의 길이 == 가장 가까운 두 점 사이의 최단 거리 모든 섬 사이의 최단 거리를 구해야 함 각 섬에 속한 점들로부터 다른 섬의 점들까지의 최단 거리 계산 가중치 없으므로 bfs 이용 각 섬에 속하는 점들은 bfs로 따로 찾기 코드 #include #include using namespace std; int map[101][101]; int direction[4][2] = { ..