본문 바로가기

알고리즘 온라인 저지

 (48)
BOJ 1002번 터렛 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 두 원의 중심과 반지름이 주어졌을때, 두개의 원의 위치관계를 묻는 문제이다. 두 원의 관계에서 접점의 갯수는 무한개, 0개, 1개, 2개, 로 4가지가 있을 수 있다. 무한개는 두 원의 중심이 같고, 반지름도 같은 경우가 있으며 0개인 경우는 반지름이 다른 동심원(A), 작은원이 큰원의 내부에 위치했을때(B), 두 원이 닿지 않는 거리에 있을때(C) 1개인 경우는 두 원이 내접했을때(D), 외접했을때(E) 2개인 경우는 그 외의 상황(F) 으로 정리가 가능하다. 먼저 두 원이 일치하는 경우는 중심좌표가 같고, 반지..
BOJ 1753번 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 그래프의 간선에 가중치가 존재할 때, 최소 / 최대 비용을 구하는 알고리즘 중 하나인 다익스트라(Dijkstra) 알고리즘을 아는지 묻는 문제이다. 다만 다익스트라 알고리즘은 간선의 가중치가 양수 영역에 있어야 한다. 음수 가중치를 가지는 그래프의 최단거리 탐색 문제는 벨만 포드 알고리즘을 이용하도록 하자. 벨만 포드 알고리즘 문제도 조만간 하나 풀어야겠다. 문제의 예시를 그래프로 나타내면 오른쪽과 같다. 커다란 블록은 노드..
BOJ 1644 소수의 연속합 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 간단한 내용을 어렵게 설명한 문제라는 생각이 들었다. 요약하면 주어지는 자연수 N 이하의 소수를 모두 구한 뒤, 그 소수들의 구간합을 구해서 N이 되는 구간이 몇 개인지를 세는 문제이다. N이하의 소수를 구하는 것은 에라토스테네스의 체 를 이용하여 구할 수 있으니 결국 구간합을 여러 번 구하는 문제인 셈이다. N이하의 소수를 구하는 내용은 인터넷이나 바로 전 글을 참고하여 해결했다 가정하자. BOJ 4948 베르트랑 공준 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 ..
BOJ 4948 베르트랑 공준 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net BOJ 상으로는 수학 카테고리에 있는데 이게 왜 수학 카테고리에 있는지는 모르겠는 문제, 에라토스테네스의 체를 쓸 수 있다면 매우 간단한 문제이다. 임의의 자연수 n ~ 2n 사이의 소수의 개수를 구하는 문제이다. 그런데 문제 하나에 1~123456 사이의 임의의 값이 입력되기도 하고, 한 번에 여러 개의 질문이 들어온다. 때문에 1~246912 사이의 모든 소수를 구해놓고, 구간 안에 들어있는 소수 개수를 세는 방식으로 해결한다. 알고리즘은 간단하다. ..
BOJ 1715번 카드 정렬하기 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제가 복잡해 보이지만 사실 문제를 단순화하면 리스트 내의 가장 작은 두 수의 합 을 반복적으로 구하는 문제이다. 처음에는 삽입 정렬을 이용해서 처리하려 했으나 시간이 초과되어 우선순위 큐를 이용해야 한다는걸 뒤늦게 깨닳은 문제였다. 우선순위 큐는 평소 힙을 이용해서 구현하나, 최초에 삽입정렬로 구현하는 탓에 구현시간이 몇분 남지 않아 그당시 바로 떠올랐던 멀티셋을 이용해 구현했다. 구현은 너무나도 간단하다. (입력 함수를 나누고, 의미없는 개행을..
BOJ 1931번 회의실 배정 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 회의실에서 소화 가능한 회의의 개수의 최댓값을 묻는 문제이다. 회의 시간이 아닌 회의 개수 이므로 임의의 시점에서 회의실에 들어갈 수 있는 회의 중 가장 빨리 끝나는 회의를 탐욕적으로 선택하면 끝. 심지어 회의 번호를 기억할 필요도 없이 단순 횟수만 출력하면 되기 때문에 비교적 간단하게 구현할 수 있다. 위의 BOJ 예시를 그래프로 나타내면 아래와 같다. 이 그래프를 이용하여 설명을 진행한다. 몇 가지 규칙을 정하고 그 규칙 대로만 (=알고리즘) 이 문제를 해결하기로 한다. (규칙 A) 현재시간 커서 이후에 시작 예정인 회의 중 가장 빠르게 종료 예정인 회의를 회의실에 투입한다..
BOJ 1005번 ACM Craft 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 특정 건물의 선행 건물의 제한이 없으며, 후행 건물 또한 제한이 없기 때문에 단순 트리로는 해결이 불가능하다. 그래프를 이용해야 하며 그래프의 노드가 1000개, 간선이 100000개 이므로 완전 탐색을 한번 돌려도 시간은 충분하다. 즉 완전 탐색을 한번 돌면서 각 노드에 소요시간을 저장해 두기만 해도 해결 가능한 정석에 가까운 문제라는 생각이 들었다. 처음에는 단방향 그래프와 너비 우선 탐색을 이용해 구현하였으나, 이후 포스팅을 준비하면서 내 설명 능력에..
BOJ 5638번 수문 5638번: 수문 첫째 줄에 수문의 개수 n이 주어진다. (1 ≤ n ≤ 20) 다음 n개 줄에는 각 수문 Gi의 유량 (m3/hour) Fi와 피해 비용 Ci가 주어진다. 다음 줄에는 테스트 케이스의 수 m (1 ≤ m ≤ 50)이 주어진다. 다음 m개 www.acmicpc.net 각 수문의 유랑과 비용을 이용해, 조합 가능한 유량의 최소비용을 테이블에 저장하여 풀 수 있는 문제였다. 다만 약간의 함정이 2곳에 있었다. 수문의 정보가 다음과 같이 주어진다면, 배출 가능한 유량과 비용의 테이블을 만들 수 있다. 여기서 요구되는 배출 가능 유량이 4000이라면? 첫 번째 함정이라고 느낀 부분이다. 이 부분은 당연히 200 비용으로 처리되어야 하고, 실제 구현을 해보면 간단하게 처리할 수 있다. (cpp 1..

티스토리툴바