알고리즘 문제풀이

백준 1715번 - 카드 정렬하기 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2초 128MB 21083 7277 5732 35.092% 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40..

백준 15992번 - 1,2,3 더하기 7 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 0.25초 512MB 912 482 383 55.267% 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n과 m이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 단, 사용한 수의 개수는 m개 이어야 한다. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n과 m이 주어진다. n은 양수이며 1,000보다 작거나 같다. m도 양수이며, n보다 작거나 같다. 출력..

백준 10749번 - Superbull 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1초 512MB 201 113 86 52.439% 문제 Bessie and her friends are playing hoofball in the annual Superbull championship, and Farmer John is in charge of making the tournament as exciting as possible. A total of N (1 > N; vector id(N); for(int i=0; i> id[i]; } // 최적 부분 구조 priority_queue PQ; for(int i=0; i

백준 13334번 - 철로 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 512 MB 3652 1374 903 38.590% 문제 집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 d로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다. 양의 정수 d와 n 개의 정수쌍, (hi, oi), 1 ≤ i..

최소 공통 조상? 트리에서 임의의 두 노드(u, v)에서의 최소 공통 조상은 "u와 v의 공통 조상노드들 중 가장 깊이가 깊은(=루트로 부터 거리가 먼)노드"로 정의할 수가 있다. 최소 공통 조상은 여러가지 분야에서 응용될 수 있지만, 트리 상에서 두 노드의 거리를 구할 때 많이 이용되는 알고리즘이다. 아래와 같은 트리가 있다고 가정해보자. 트리의 최상위 루트 노드는 루트노드를 제외한 모든 노드들의 조상 노드임을 알 수 있다. 깊이가 다른 노드 3과 6의 조상 노드들은 무엇이 있을까? (0, 1)번 노드가 3,6의 공통 조상일 것이다. 그 중, 최소 공통 조상은 공통 조상 중 depth가 가장 깊은 1이 된다. 다음으로는 깊이가 같은 4,5번 노드의 최소 공통 조상은 무엇이 있을까? 최상위 루트 노드인 ..

백준 3015번 - 오아시스 재결합 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 7690 1864 1333 24.925% 문제 오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다. 이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다. 두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다. 줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든..