0과 1의 쉼터

풀이 트리로 주어지는 목차의 정보를 글머리 번호 형태로 바꾸면 되는 문제다. 아래 조건에 따라 변환할 수 있다. i 번째 수가 i - 1번째 수보다 작다면, 상위 글머리 번호부터 변환해주어야 한다. i 번째 수가 i - 1번째 수보다 크다면, 글머리 번호 형태에 따라 1로 변해야 한다. i 번째 수가 i - 1번째 수와 동일하다면, 이미 존재하는 목차이므로 i - 1번째 수의 글머리 번호 형태 + 1로 변해야 한다. 먼저 i번째 수가 i - 1번째 수보다 작은 경우다. 상위 글머리 번호부터 변환해주어야 하기에 이전에 기록된 하위 글머리 번호에 대해 누적된 수들을 0으로 초기화 하는 과정이 시간초과의 원인이 되었다. 이번 기회에 알게 된 사실인데, 문제를 틀렸거나 부분점수를 얻은 경우 '내 제출' 란에서 ..

풀이 주어진 트리에 대해 트리의 지름을 구하면 되는 문제다. [백준 1967] 트리의 지름 [Python] 에서 더 많은 정점을 입력받는 동일한 문제이지만, 이전 글의 풀이와 동일한 방법으로 문제를 해결할 수 있다. 다른 점이라 하면, 입력이 양방향 그래프로 주어지기 때문에 따로 처리하지 않아도 된다. 소스코드 소스코드 보기 출처 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net

풀이 주어진 트리에 대해 트리의 지름을 구하면 되는 문제다. 트리의 지름이란, 트리에서 임의의 두 정점을 연결하는 간선의 가중치 합이 최대가 되는 값을 의미한다. 즉, 문제에 나온 이미지처럼 임의의 두 정점을 길게 당길 때 가장 큰 원을 만들 수 있는 간선의 합이 트리의 지름을 의미한다. 그렇다면 임의의 두 정점을 연결하는 간선의 가중치 합이 최대가 되는 정점은 어떻게 찾을까? 임의의 두 정점(x, y)과 간선의 가중치의 합이 최대가 되는 정점(v1, v2)의 관계에 있어 다음과 같다. (x, y) 두 정점 모두 (v1, v2)와 일치할 때 : 한 번의 탐색으로 정답을 구할 수 있다. (x, y) 중 하나의 정점(x)만 (v1, v2)의 (v1)과 일치할 때 : 한 번의 탐색으로 (v1)를 구할 수 있다..

풀이 조건에 맞게 값을 넣어줄 수 있는 Binary Search Tree를 구현하는 문제이다. 소스코드 #include #include typedef struct node{ int data; struct node *left, *right; }*pNode; void postorder(pNode root){ if (root == NULL) return; postorder(root->left); postorder(root->right); printf("%d\n", root->data); } pNode make_tree(pNode root, int data){ if (root == NULL){ root = (pNode)malloc(sizeof(pNode)); root->data = data; root->left..