알고리즘 문제풀이

백준 22253번 - 트리 디자이너 호석 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1초 1024MB 241 105 82 41.837% 문제 트리를 너무나 사랑하는 효성이는 트리 분재 전문가이다. 효성이가 기르는 모든 트리는 정점과 간선으로 이루어져 있다. 정점은 $1$번부터 $N$번 정점까지 존재하며, 간선은 서로 다른 두 정점을 연결해준다. 정점의 개수는 간선의 개수보다 정확히 한 개가 많으며, 사이클을 이루지 않는다. 트리의 뿌리는 정점 중 하나로, 모든 정점 중 가장 낮은 높이에 존재한다. 항상 1번 정점이 트리의 뿌리임이 보장되고, 이파리란 연결된 간선이 1개 이하인 정점을 의미한다. 정점이 뿌리에 가까울수록 낮은 높이에 존재하며, 멀수록 높은 높이에 존재한다. 효성이가 기르는 트리는..

백준 6087번 - 레이저 통신 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1초 128MB 8352 2869 1976 32.135% 문제 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. 아래 그림은 H = 8, W = 7인 경우이고, 빈 칸..

백준 1507번 - 궁금한 민호 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2초 128MB 4674 2331 1832 48.775% 문제 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다. 도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다. 강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다. 예를 들어, 예제의 경우에 모든 도시 사이에 강호가 구한 값을 가지는..

[TOC] 백준 2933번 - 미네랄 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1초 128MB 8504 2296 1463 24.750% 문제 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다. 동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다. 창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 ..

[프로그래머스 코딩테스트 고득점 Kit] - 이분탐색 입국 심사 - level 3 문제 제한사항 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다. 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다. 심사관은 1명 이상 100,000명 이하입니다. 문제의 조건대로 시뮬레이션을 통해 최적해를 찾는 방법은 시간 제한 내에 문제를 해결할 수 없다는 것을 입출력의 제한사항으로 파악할 수 있다. 입국심사를 기다리는 사람의 최대 수가 $10^9$이라는 것을 고려한다면, $O(N)$으로도 해결하기 힘들다. 다른 관점에서 문제를 생각해보아야한다. 결정론적인 방법으로 생각해보자, 함수 $F(k)$ 를 다음과 같이 정의해보자. $F(k)$ : $k$시간..

프로그래머스 코딩테스트 고득점 Kit - 완전 탐색 모의고사 - level1 문제 1번, 2번, 3번 수포자가 찍는 방식에서 일정 주기를 가지고 반복되는데, 이 주기를 찾아서 배열에 저장한다. 이 후, answers를 순회하며 정답과 1대 1비교를 통하여 각각의 수포자가 맞힌 문제의 개수를 계산하여 비교한다. #include #include using namespace std; vector solution(vector answers) { vector answer; vector v(3); v[0].assign({1,2,3,4,5}); v[1].assign({2,1,2,3,2,4,2,5}); v[2].assign({3,3,1,1,2,2,4,4,5,5}); int scores[3] = {0, }; for(in..