본문 바로가기

문제 노트

 (157)
천상용섬( BOJ 12758 ) 문제 : https://www.acmicpc.net/problem/12758 12758번: 천상용섬 테스트케이스마다 승균이가 벨 수 있는 모든 경우의 수를 출력한다. 출력은 개행으로 구분되어야 한다. 정답이 커질 수 있으니 \(1,000,000,007\)로 나눈 나머지를 출력한다. www.acmicpc.net 문제 파악하기 제시된 N개의 약수를 오름차순으로 나열하는 경우의 수를 구하는 문제입니다. N의 개수는 300개라서 많지 않지만 입력되는 숫자가 최대 1,000,000이기 때문에 단순히 모든 숫자를 비교하기에는 너무 오랜 시간이 필요합니다. 그렇기에 우선, 빠르게 구할 수 있는 값부터 먼저 구해봅시다. 어떤 수(K)의 약수를 구하기 위해서는 1부터 K까지의 수를 모두 비교할수도 있지만, 1부터 √K까..
주식( BOJ 11501 ) 문제 : https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 문제 파악하기 주식을 어느 날에 팔아야 최고 이익이 나는지 파악하는 문제입니다. 입력 값이 최대 1,000,000개이기 때문에 왠만하면 단순 반복문으로 알고리즘을 설계해야 한다는 점에 유념한다면 어렵지 않게 문제를 풀 수 있습니다. 문제 해결하기 문제를 풀기 위해서는 언제 주식을 팔아야 하는지 알아야 합니다. 최고의 이익을 내기 위해서는 가장 주가가 비싼 날에 판매를 해야합니..
오목( BOJ 2615 ) 문제 : https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 문제 파악하기 바둑판의 모습이 주어질 때, 흑/백의 승패여부를 판단하는 문제입니다. 종목이 오목이기에 가로, 세로, 대각선 방향으로 연결된 같은 색의 돌이 딱 5개여야하며, 만약 6개 이상 돌이 연결되어 있다면 인정되지 않습니다. 바둑판은 19*19로 이루어졌기에 2차원 배열을 사용하여 바둑판의 모습을 충분히 저장할 수 있으며, 5목인지 판단하면 되기에 놓여진 모든 바둑돌을 하나씩 검사해..
체인( BOJ 2785 ) 문제 : https://www.acmicpc.net/problem/2785 2785번: 체인 희원이는 그의 다락방에서 N개의 체인을 찾았다. 각각의 체인은 몇 개의 고리로 연결되어 있는데, 각각의 고리는 최대 두 개의 인접한 고리를 가질 수 있다. 각각의 고리는 열고 닫을 수 있다. 그 www.acmicpc.net 문제 파악하기 N개의 체인을 하나로 연결하기 위해 필요한 고리의 최소 개수를 구하는 문제입니다. 각각의 고리는 분리되어 다른 체인들을 연결할 수 있으며, 최대 2개의 체인을 연결할 수 있습니다. 문제를 분석해보면 결국 체인, 즉 숫자와 숫자 사이를 연결하기 위해 사용되는 고리의 개수를 구하는 문제입니다. 따라서, 연결에 사용되는 고리의 개수를 줄이기 위해서는 하나의 체인을 전부 다른 체인을 연..
문자열 장식( BOJ 1294 ) 문제 : https://www.acmicpc.net/problem/1294 1294번: 문자열 장식 첫째 줄에 단어의 개수 N이 주어진다. N은 최대 20이다. 둘째 줄부터 N개의 줄에 단어가 주어진다. 단어는 최대 1,000글자이고, 공백은 없이 알파벳 대문자로만 구성되어 있다. www.acmicpc.net 문제 파악하기 N개의 문자를 적절하게 분해해서 사전순으로 가장 앞에 있는 하나의 문자를 만드는 문제입니다. 모든 문자의 순서를 맞춰야 하기 때문에 앞에서부터 하나씩 가져와야합니다. 문제를 처음 보면 사전순으로 가장 빠른 문자를 마냥 선택하면 될듯 하지만 aaa / aab 와 같이 동일한 문자가 반복될 때, 어떤 문자에서 a를 가져오는지에 따라 결괏값이 달라지기에 좀 더 세밀한 조건이 필요합니다. 문..
Escaping( BOJ 20041 ) 문제 : https://www.acmicpc.net/problem/20041 20041번: Escaping 첫 번째 줄에는 경찰의 수 N이 주어진다. 단, 1 ≤ N ≤ 500,000이다. 그 다음 N 개의 줄에는 각 경찰의 초기 위치의 좌표 (xi, yi)가 공백을 사이에 두고 주어진다. 다음 줄에는 도둑의 초기 위치의 좌 www.acmicpc.net 문제 파악하기 N명의 경찰이 1명의 도둑을 잡을 수 있는지 여부를 파악하는 문제입니다. 정답이 Yes / No로 나오는 대표적인 결정 문제라고 할 수 있습니다. 경찰과 도둑은 항상 상하좌우 인접한 격자 점으로 이동하며, 번갈아 가며 한 칸씩 움직일 수 있기 때문에 경찰이 먼저 도달하거나 도둑과 함께 동시에 도달하는 위치에서는 항상 경찰이 도둑을 잡을 수 ..
보석( BOJ 2492 ) 문제 : https://www.acmicpc.net/problem/2492 2492번: 보석 첫째 줄에 4개의 정수 N, M, T, K가 빈칸을 사이에 두고 주어진다. N은 지도의 너비를 나타내고, M은 지도의 높이를 나타낸다(1 ≤ N, M ≤ 1,000,000). T는 금강석의 개수를 나타내고, K는 정사각형의 크 www.acmicpc.net 문제 파악하기 가장 많은 금광석을 포함하고 있는 K*K 크기의 정사각형 위치를 구하는 문제입니다. 지도의 크기인 N과 M의 범위는 크지만 묻혀있는 금광석의 개수는 최대 100개이기 때문에 탐색할 범위만 잘 설정하면 충분히 완전탐색으로도 해결할 수 있습니다. 그럼 탐색할 범위는 어떻게 구할 수 있을까요? 탐색할 범위를 구하기 앞서, 탐색할 영역이 정사각형이라는 점..
나무 막대( BOJ 7344 ) 문제 : https://www.acmicpc.net/problem/7344 7344번: 나무 막대 목공소에 n개의 나무 막대가 있고, 각 막대의 길이와 무게가 주어져 있습니다. 이 막대들은 기계를 이용해 하나 하나 가공 처리 과정을 거치게 됩니다. 이때, 각 막대를 처리할 수 있도록 기계를 www.acmicpc.net 문제 파악하기 N개의 나무 막대를 가공하기 위해 필요한 세팅 횟수를 구하는 문제입니다. 나무 막대는 길이(l)와 무게(w)를 가지고 있으며, 이전에 가공했던 나무 막대보다 길이와 무게 모두 크거나 같다면 세팅할 필요가 없습니다. 따라서, 한번 세팅하면 더 이상 세팅할 필요가 없는 나무 막대들을 찾는 알고리즘이 필요합니다. 알고리즘을 통해 세팅이 필요없는 나무 막대들을 골랐다면, 해당 나무 ..

티스토리툴바