Algorithm/BOJ (13) 리스트형 [백준 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.. 이전 1 2 다음