본문 바로가기

Algorithm

 (17)
[백준 11501] 주식 백준 11501번 : 주식 www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net /* 문제 설명 */ 매일, 세가지 행동 중 하나를 한다. 1. 주식을 하나 산다. 2. 원하는 만큼 가지고 있는 주식을 판다. 3. 아무것도 안한다. 이 때, 최대 이익이 어떻게 되는지 구하시오. /* 해결 방안 */ 주가가 낮을 때는 주식을 사야되고, 높을 때는 팔아야 된다. 따라서 최고점일 때 최대한 많이 팔 수 있도록, 최고점보다 낮은 주가를 만날 경우에는 무조건 ..
[백준 1311] 할 일 정하기1 백준 1311번 : 할 일 정하기1 www.acmicpc.net/problem/1311 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net /* 문제 설명 */ N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. Dij를 i번 사람이 j번 일을 할 때 필요한 비용이라고 했을 때, 모든 일을 하는데 필요한 비용의 최솟값을 구하여라. /* 해결 방안 */ N명의 사람들과 N개의 일이 있고, 각각의 사람들이 j번 일을 할 때 필요한 비용이..
[백준 2170] 선 긋기 백준 2170번 : 선 긋기 www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net /* 문제 설명 */ 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없을 때, 그려진 선들의 총 길이를 구하시오. (선이 여러 번 그려진 곳은 한 번씩만 계산한다.) /* 해결 방안 */ 겹쳐진 선분들끼리 한 구간으로 합쳐나가다가, 마지막에 구간들의 길이만 세서 더해주자! → Sweeping /* 구현 과정 */ 1. 왼쪽 좌표를 기준으로 선을 ..
[백준 20058] 마법사 상어와 파이어스톰 백준 20058번 : 마법사 상어와 파이어스톰 www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net /* 문제 설명 */ 2N × 2N 격자의 얼음판을 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸의 얼음을 -1 해준다. 위의 행동을 Q번 할 때, 모든 파이어스톰을 시전한 후에 남아있는 얼음 A[r][c]의 합과 남아있는 얼음..
[백준 20040] 사이클 게임 백준 20040번 : 사이클 게임 www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net /* 문제 설명 */ n개의 점이 있고 m개의 쿼리가 있을 때, 사이클의 생성 유무를 구하시오.(n ≤ 500,000 , m ≤ 1,000,000) /* 해결 방안 */ m개의 쿼리에 대해서 매번 사이클 유무를 판별하기 위해서 BFS, DFS를 수행한다면 시간초과가 난다.따라서 다른 방법을 생각해봐야하는데, 'A와 B의 선분을 이어주는 것'을 'A가 포함된 집합에 B집합을..
[백준 20057] 마법사 상어와 토네이도 백준 20057번 : 마법사 상어와 토네이도 www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net /* 문제 설명 */ 토네이도가 움직이면서 모래를 일정한 비율로 흩날린다. 이 때, 격자 밖으로 나간 모래의 양을 구하시오. /* 해결 방안 */ 전형적인 구현 문제로, 크게 두 단계로 나눌 수 있다. 1. 토네이도의 움직임을 구현하기 2. 흩날리는 모래를 계산하기 우선 1번(토네이도의 움직임)부터 구현하기위해, 토네이도의 움직임을 잘..
[백준 1450] 냅색 문제 백준 1450번 : 냅색 문제 www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. www.acmicpc.net /* 문제 설명 */ N개의 물건과 최대 C만큼의 무게를 넣을 수 있는 가방이 있을 때 가방에 물건을 넣을 수 있는 방법의 수를 구하시오. (N은 30보다 작거나 같은 자연수) /* 해결 방안 */ 풀이로 완전탐색이 떠오르지만, N=30인 경우 2^30이 되어 시간초과가 난다. 그렇다면, 2^30을 줄이려면 어떻게 해야할까? → 문제를 절반으로 나누어 생각한다. (Meet I..

티스토리툴바