본문 바로가기

전체 글

 (191)
Degree Bounded Minimum Spanning Tree( BOJ 20927 ) 문제 : https://www.acmicpc.net/problem/20927 20927번: Degree Bounded Minimum Spanning Tree 제약에 맞는 Spanning Tree가 존재한다면 첫 번째 줄에 YES를 출력하여라. 이후 해당 Spanning Tree 의 간선을 $N-1$개의 줄에 걸쳐 출력한다. 간선을 출력하는 순서는 상관없으며, 각 간선을 출력할 때는 www.acmicpc.net 문제 파악하기 N개의 정점을 모두 연결하는 트리 중 가중치의 값이 가장 작은 트리의 모양을 찾는 문제입니다. 얼핏 보면 Spanning Tree 알고리즘 문제처럼 보이지만 이 문제는 한 가지 조건이 더 주어집니다. 바로 각각의 노드가 가질 수 있는 차수가 제한되어 있습니다. 그렇기에 기존의 크루스칼..
Pizza( Atcoder 238-B ) 문제 : https://atcoder.jp/contests/abc238/tasks/abc238_b B - Pizza AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제 파악하기 pizza를 주어진 각도만큼 회전시키고 잘랐을 때, 가장 큰 피자의 각도를 구하는 문제입니다. 피자의 각도는 0˚ ~ 359˚까지 있으며, 동일한 위치를 다시 자르지 않는다는 점을 고려하면 문제를 해결할 수 있습니다. 문제 해결하기 동일한 위치를 다시 자르지 않기에 우리는 0˚ ~ 359˚까지 배열을 사용해서 잘린 적이 있는지 확인하면 됩니다. ..
소수 판별법(밀러-라빈 소수판별법) 알고리즘 설명 연습 문제 : https://www.acmicpc.net/problem/5615 5615번: 아파트 임대 첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 231-1이하인 양의 정수이다. www.acmicpc.net 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include #define NMAX 7 #define lint uns..
Optimization is Freaky Fun( BOJ 17417 ) 문제 : https://www.acmicpc.net/problem/17417 17417번: Optimization is Freaky Fun 첫 번째 줄부터 Q개의 줄에 걸쳐, 교준이의 프로그램의 출력 결과를 출력한다. www.acmicpc.net 문제 파악하기 입력받은 Q개의 쿼리를 처리하는 문제입니다. 쿼리는 N, S, E를 입력받으며, 구간 [S, E] 사이의 모든 자연수 i를 N으로 나눈 값([N/i])의 합을 구하는 문제입니다. 입력되는 N, S, E 자체가 최대 1012이기 때문에 단순한 반복문으로는 해결할 수 없습니다. 또한, 각각의 서브태스크의 조건이 다르기 때문에 시간에 맞춰 문제를 해결하기 위해서는 입력되는 쿼리의 특징에 따라 다른 알고리즘이 필요합니다. 예를 들어 서브태스크 2와 4를 ..
Celebrity( BOJ 23259 ) 문제 : https://www.acmicpc.net/problem/23259 23259번: Celebrity 첫째 줄에 아름다운 별의 수를 출력한다. www.acmicpc.net 문제 파악하기 주어진 N개의 그래프 중 동형인 그래프가 없이 유일한 모양인 그래프의 개수를 찾는 문제입니다. N은 최대 10,000개이지만 다행히 입력되는 모든 그래프의 정점은 항상 5개이기 때문에 모든 경우의 수를 확인하여 문제를 해결할 수 있습니다. 문제 해결하기 우선, 그래프가 동형인지 아닌지 확인하는 방법부터 찾아야 합니다. 그래프가 서로 동형이란 의미는 연결된 정점의 상태가 동일하다는 의미입니다. 문제에서 확인할 수 있듯이 별 A와 별 B는 달라보이지만 잘 보면 정점 간 연결된 상태가 똑같습니다. 이처럼 정점 간 연결된..
타일 채우기 2( BOJ 13976 ) 문제 : https://www.acmicpc.net/problem/13976 13976번: 타일 채우기 2 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000,000,000,000)이 주어진다. www.acmicpc.net 문제 파악하기 3xN 크기의 벽을 1x2 크기의 타일로 채우는 경우의 수를 구하는 문제입니다. 2xN 크기의 벽을 채우는 문제의 심화된 버전이라고 할 수 있습니다. 하지만 문제를 해결하는 과정은 2xN 크기의 벽을 채우는 문제와 동일한 방식으로 해결할 수 있습니다. 이전 상태를 사용할 수 있는 경우가 총 몇 가지인지 확인해서 점화식을 세우면 문제를 해결할 수 있습니다. 문제 해결하기 이렇게 타일을 채우는 문제는 가장 작은 경우부터 하나씩 확인해보면 됩니다. 여기서 중요한 점은 사용하..
거스름돈( BOJ 14916 ) 문제 : https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제 파악하기 2원과 5원을 사용해서 N원을 만드는 방법 중 동전을 가장 적게 사용하는 방법을 찾는 문제입니다. 아쉽게도 5원부터 먼저 사용하는 방법으로는 문제를 풀 수 없습니다. 예를 들어 6원 같은 경우, 5원을 먼저 사용하는 방법으로는 해답을 찾을 수 없습니다. 따라서, 그리디 방식이 아닌 모든 경우를 고려하는 동적 프로그래밍이 필요합니다. 문제 해결하기 N원을 만들기 위해서는 2가지 조건 중 하나만 만족하면 됩니다. (N-2)원을 만들 수 있거나 (N-5)원을 만들 수 있으면 됩니다. 따라서, 우리는..
백설공주와 난쟁이( BOJ 2912 ) 문제 : https://www.acmicpc.net/problem/2912 2912번: 백설공주와 난쟁이 첫째 줄에 난쟁이의 수 N과 모자 색상의 수 C가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ C ≤ 10,000) 둘째 줄에는 각 난쟁이가 쓰고 있는 모자의 색상이 줄을 서 있는 순서대로 주어진다. 셋째 줄에는 사진 www.acmicpc.net 문제 파악하기 구간 [a, b]사이의 숫자 중 절반 이상의 개수를 가진 숫자가 있는지 없는지 판단하는 문제입니다. 데이터의 개수는 총 300,000개이며 쿼리의 개수는 10,000개이기에 각 쿼리 당 효율적인 알고리즘이 요구되는 문제입니다. 이 문제를 풀기 위해서는 우선, 절반 이상의 개수를 가지기 위해서 필요한 조건을 생각해보아야 합니다. 문제 해결하..

티스토리툴바