computer_study

문제 : www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. �� www.acmicpc.net 문제 해결 아이디어 1. 열의 순서는 inorder traversal 기준으로 탐색이 된다. 2. inorder로 탐색을 하며, 해당 노드의 column값을 저장해주고( column_cnt ), 각 level별로 최대값( level_max[] ) 최소값( level_min[])을 계속 저장해준다. 3. 탐색은 항상 가장 윗 노드부터 시작해야되므로, root를 찾기위하여 paren..

문제 : www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 문제 해결 아이디어 1. class나 구조체를 사용하여 node를 생성 후, 값들을 저장하고 탐색한다. python class Node: def __init__(self, data, left_node, right_node): self.data = data self.left_node = left_node self.right_node = right_node def preorder(node): prin..

문제 : www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 문제 해결 아이디어 1. 중량제한 C의 범위가 10억이므로, 이진탐색을 사용하여 중량의 최대값을 구한다. 2. 해당 중량을 목적지까지 옮길 수 있는지 여부는 BFS를 통해 판단한다. 예제입력 3 3 1 2 2 3 1 3 2 3 2 1 3 다음 입력이 주어졌다면, 1이 시작점 3이 끝점으로 하여 다음과 같이 그릴 수 있다. 현재 최대 무게가 2( middl..

문제 : www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 문제 해결 아이디어 1. 좌표의 최대 수가 10억이므로, 이진 탐색을 통해 공유기 사이의 거리를 구하여야된다. 2. 집의 개수가 N 좌표가 X라 할 때, 최대 O( N log(X) )가 걸린다. 3. 인접한 공유기 사이의 거리를 변수로 두고, 그 값을 이진탐색을 통해 바꾸어가며, 인접한 공유기 사이의 거리의 최대값을 구한다. 예제입력 5 3 1 2..

문제:www.codeground.org. , practice/회문인 수의 합/ codeground Codeground is a real-time coding website open to those interested in software development and algorithms. www.codeground.org 1번 아이디어(실패) 현재 수와 가장 가까운 회문의 수를 찾는 방법은, 두 수를 비교하여 작은 수를 그 자리에 대체하는 것으로 생각했었다. #include #include #include using namespace std; int cnt; vector result; void calculate(vector num, int num_int){ int check = 0; int Palindro..

문제 : www.codeground.org/practice/practiceProblemView 우주정거장 문제는, 삼각형을 이루는 모양을 제거할 수 있다는 것이 핵심인듯 보였다. 때문에, 처음 했던 생각은 삼각형의 개수를 세는 것이었다. (이는 틀린 방법이었다.) 위와같은 모양이 주어졌다면 1. 먼저 입력받은 연결선들의 값들을 모두 순차적으로 정렬한다. (시간초과를 방지하기 위해, 간선들을 한번씩 탐색하는 동안 모든 검사를 끝내도록 한다.) 2. 연결선의 개수만큼 반복문을 돌며, 삼각형이 있는지 찾는다. 3. 1과 3이 연결되어있다면 삼각형이 하나 존재한다는 얘기이기 때문에, 노드 하나를 제거할 수 있다. 4. 총 노드의 개수에서 제거 한 노드를 빼서 답을 구한다. (답:2) 같은 방법으로 다음도 생각할..

문제 : www.codeground.org/practice/practiceProblemViewNew 처음은 큐를 이용하여 문제를 해결하려 하였다. (이는 시간초과가 발생하였다.) 1. 선수들의 실력을 오름차순으로 정렬하여 순서대로 큐에 넣는다. 2. 큐가 비워질 때 까지 순회하며, 현재 가장 작은 수 부터 시작해서, k 초과로 차이나는 선수들을 하나의 버스에 태운다. 예를들어 k=3이고, 실력이 1, 5, 3, 7, 9인 선수들을 태운다고 하면 이러한 방법으로 버스 두대로 나누어 태울 수 있다. #include #include #include using namespace std; int Answer; unsigned int k; int main(int argc, char** argv) { int T, t..

문제 : www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 문제 해결 아이디어 1. python에선 dictionary, c++에선 map함수를 이용하여, key값과 value값을 설정하고 문제를 해결한다. 2. 입력값들을 순회하며, 같은 값이 나올 때 마다 value값을 증가시켜, 마지막에 그중 최대값을 출력한다. python n = int(input()) books = {} for _ in range(n): book = input() if book ..