위상정렬

알고리즘 문제) BOJ 1637. 날카로운 눈 링크 : https://www.acmicpc.net/problem/1637문제 요약정수가 여러 개 모여있는 정수더미특정 정수 하나만 홀수개 존재 & 나머지 정수는 짝수개 존재이때 정수 더미에서 홀수개 존재하는 정수를 찾기시간 제한2초입력입력의 개수 N1 ≤ N ≤ 20000N개의 줄에 정수 A, C, B가 주어지는데,A, A+B, A+2B, …, A+kB (A+kB ≤ C) 정수들이 더미안에 존재함을 의미A, B, C는 1~ 2,147,483,647이하 정수N개의 입력이 나타내는 정수를 모두 포함출력홀수개 존재하는 정수와, 해당 정수가 몇 개 들어있는지 출력홀수개 존재하는 정수가 없다면 NOTHING접근법완전탐색으로 먼저 생각해보장..각 정수를 일일이 구하고..

알고리즘 문제) BOJ 1516. 게임개발 링크 : https://www.acmicpc.net/problem/1516문제 요약어떤 건물을 짓기 위해서는 다른 건물을 먼저 지어야할 수 있음N개의 건물이 완성되기까지 걸리는 최소 시간 구하기시간 제한2초입력건물의 종류 수 N(1 ≤ N ≤ 500)N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호건물의 번호는 1부터 N각 줄은 -1로 끝난다각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수출력N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력접근법위상정렬그러나 주어진 테케말고 또 다른 테케를 생각해야 한다.만약 아래와 같은 구조일때, 건물 C에 영향을 주는 시간은 뭐가 될까?부모 건물 A..

알고리즘 문제) BOJ 1513. 경로 찾기 링크 : https://www.acmicpc.net/problem/1513문제 요약N*M 직사각형 도시에 살고 있음(1,1)에서 출발해서 (N,M)으로 가려고 할 때,이동은 현재 위치가 (r, c) 일 때, (r+1, c) 또는 (r, c+1)로만 이동오락실은 번호가 증가하는 순서대로 가야함오락실을 0개 방문했을 때부터, C개 방문했을 때 까지 경우의 수를 출력하는 프로그램을 작성하시오.시간 제한2초입력N M C모두 50이하 자연수둘째 줄부터 C개의 줄에 1번 오락실부터 C번 오락실까지 위치가 차례대로 주어진다오락실의 위치가 (1,1) 또는 (N,M)일 수도 있다출력첫째 줄에 0개 방문했을 때, 1개 방문했을 때, ..., C개 방문했을 때 총 경로의 개수를 ..

알고리즘 문제) BOJ 3114. 사과와 바나나 링크 : https://www.acmicpc.net/problem/3114문제 요약R*C맵에 A나라와 B나라가 존재각 칸에는 A나무(사과) 개수, B나무(바나나) 개수가 주어짐(1,1)부터 시작해 (R,C)까지 불도저를 이동하면서 나무를 제거하고, 국경선을 만들려고함이때 국경선 아래는 A, 국경선 위는 B국가가 가지게 되는데,A나라는 사과를 좋아하고, B나라는 바나나를 좋아한다.따라서, 국경선 아래에 사과나무 개수 합과 국경선 위의 바나나 나무 개수 합이 최대가 되는 경우를 찾을 것시간 제한1초입력땅의 크기 R,C ( 2 ≤ R,C ≤ 1500)R개의 줄에 각 칸에 심어져 있는 나무 개수가 주어짐사과는 A, 바나나는 B이며 심어져 있는 나무 개수는 1~99..

알고리즘 문제) BOJ 14676. 영우는 사기꾼? 링크 : https://www.acmicpc.net/problem/14676문제 요약우주 전쟁건물을 짓는 순서가 정해져있음ex) 1번 건물을 지어야 2번, 3번 건설 가능 = 1번 건물이, 2,3,번에 영향을 미친다한 건물은 최대 3개 건물에게만 영향을 미칠 수 있으며, 중복 건설이 가능하다.치트키 ⇒ 원하는 건물을 마음대로 지을 수 있음주어진 정보를 보고 영우가 치트키를 사용했는지 안헀는지 파악하기시간 제한1초입력첫째 줄 : 건물 종류 개수 N, 건물 사이 관계 수 M, 영우의 게임 정보 개수 K1 ≤ N,M,K ≤ 10만다음 M개의 줄에 걸쳐 건물 관계인 X, Y가 차례대로 중복 없이 주어짐X를 건설해야 Y건설 가능1 ≤ X, Y ≤ N다음 줄부터 ..