난이도 : 골드 2 문제 이진 탐색 트리 복원하기 문제 바로가기 1부터 N까지의 모든 정수를 한 번씩 포함하고 있는 수열 A1, A2, ..., AN이 있다. 값이 A1인 노드를 루트로 하는 트리에 A2, A3, ..., AN 을 순서대로 삽입하려 한다. N-1개의 노드를 삽입할 때마다 루트에서 그 노드에 도달하기 위해 거쳐야 하는 간선의 수, 즉 노드의 깊이가 주어질 때 A1, A2, ..., AN을 구하는 프로그램을 작성하시오. 풀이 값 받으면서 2N(n-1)children.size() > 0) { // 왼쪽 자식 존재 Inorder(head->children[0]); } result[head->index] = idx++; if (head->children.size() > 1) { // 오른쪽 자식 ..

난이도 : 골드 3 문제 ㄷㄷㄷㅈ 문제 바로가기 정점이 네 개 이상 있는 임의의 트리에 대해, 그 트리에서 정점 네 개로 이루어진 집합을 고르자. 전체 트리의 간선들 중 집합에 속한 두 정점을 잇는 간선만을 남겼을 때, 네 개의 정점이 하나의 트리 형태로 이어지게 된다면 ‘ㄷ’ 모양이거나 ‘ㅈ’ 모양일 것이다. 트리에서 ‘ㄷ’의 개수와 ‘ㅈ’의 개수를 각각 트리에서 ‘ㄷ’ 모양, ‘ㅈ’ 모양을 이루는 정점 네 개짜리 집합의 개수라고 하자. 이제, 동현이는 세상의 모든 트리를 다음과 같은 세 종류로 나누었다. D-트리 : ‘ㄷ’이 ‘ㅈ’의 3배보다 많은 트리 G-트리 : ‘ㄷ’이 ‘ㅈ’의 3배보다 적은 트리 DUDUDUNGA-트리 : ‘ㄷ’이 ‘ㅈ’의 정확히 3배만큼 있는 트리 신이 난 동현이는 트리만 보..

난이도 : 골드 4 걸린 시간 : 40분 문제 알파벳 문제 바로가기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 49866 15734 9600 29.155% 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 풀..

난이도 : 골드 5 걸린 시간 : 1시간 반 이상 (오류 찾기) 문제 최단경로 문제 바로가기 풀이 다익스트라 기본 구현을 이용해서 푼다. 다익스트라 개념 바로가기 코드 #include #include #include using namespace std; int main() { // 입력 // v, e는 10^5, 10^6이하 int V; int E; cin >> V >> E; int start; // 시작 정점 cin >> start; vector edge(V+1, vector(0)); for (int i = 0; i > from >> to >> val; edge[from].push_back(make_pair(to..

문제 : 백준 17836번 _ 공주님을 구해라! https://www.acmicpc.net/problem/17836 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 2465 566 431 21.923% 문제 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다. 마왕은 용사를 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈 하고 ..

달팽이 리스트 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 597 219 175 40.984% 문제 영진이는 달팽이를 좋아한다. 달팽이를 너무너무 좋아하기 때문에 특정한 모양의 단방향 연결리스트에 달팽이 리스트라는 이름을 붙여주었다. 일반적인 선형 단방향 연결리스트의 각 노드 번호를 연결된 순서대로 1, 2, ..., N이라 하자. 이때 N번 노드는 아무 노드도 가리키지 않는데, 여기서 N번 노드가 1번 노드를 제외한 임의의 노드를 가리켜 사이클을 이루게 되는 리스트를 달팽이 리스트라고 한다. 달팽이 리스트는 각 노드당 하나의 정수를 저장한다. 즉, 달팽이 리스트는 다음과 같이 생긴 연결리스트이다. 노드 안의 수는 저장된 값을 뜻한다. "달팽아 달팽아 1번 노드부터 한 칸씩..