https://www.acmicpc.net/problem/14244 14244번: 트리 만들기 n과 m이 주어졌을 때, n개의 노드로 이루어져 있고, m개의 리프로 이루어져 있는 트리를 만드는 프로그램을 작성하시오. 항상 정답이 존재하는 경우만 입력으로 주어진다. 트리는 사이클이 없는 www.acmicpc.net 난이도는 쉽지 않아보이는데 의외로 쉽다. 알고리즘 분류에 나와있듯 트리를 이용한 구성적인 문제다. 트리가 어떻게 구성되는지 일반화 될 수 있는 규칙을 찾아 문제를 풀면 된다. 문제 조건에 의해 리프노드는 항상 최소 2개이고, 답이 항상 존재한다. 리프노드가 2개인 경우는 딱 한가지다. 모든 노드가 일직선으로 연결되면 된다. 리프노드가 3개 이상인 경우는 하나의 중심 노드에 대해 리프노드를 3개 ..
https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net class5 문제를 풀면서 만났던 생 수학 문제. 두 정수가 주어질 때, 두 정수를 포함하는 범위의 모든 정수를 이진수로 변환했을 경우 1의 개수를 모두 세는 문제이다. 곧이곧대로 구하면 수의 범위가 커서 시간초과를 받는다. 나는 다음과 같은 풀이를 떠올렸다. 1. 누적합 [a, b] 구간의 모든 정수의 이진수의 1의 개수를 직접 구하기보다 [1, a] 구간의 이진수의 1..
문제 소개 https://www.acmicpc.net/problem/2376 2376번: 단말 정점들의 거리 첫째 줄에 단말 정점의 개수 n(2≤n≤1,000)이 주어진다. 다음 n-1개의 줄에는 차례로 1, 2번 단말 정점 사이의 거리, 2, 3번 단말 정점 사이의 거리, …, n-1, n번 단말 정점 사이의 거리가 주어진다. 다 www.acmicpc.net 이진트리와 인오더의 개념을 이용한 단순 구현 문제입니다. 규칙을 찾는다는 점에서 구성적 문제이기도 합니다. 문제를 어떻게 풀어야 할지는 알겠는데, 구현을 어떻게 할 지 감이 안잡히는 느낌으로 풀었던 문제입니다. 풀이 아이디어 풀이 아이디어는 생각보다 간단합니다. 문제에서 주어진 조건들을 하나씩 살펴보겠습니다. 1. n개의 단말 정점을 갖는 루트가 ..
