https://www.acmicpc.net/problem/14567 접근 방법 간단한 위상정렬 문제이다. Queue를 넣을 때 Level이라는 속성을 넣어주면 쉽게 풀 수 있다. Need Know 위상 정렬 전체 코드 ( Java ) import java.io.*; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedW..

https://www.acmicpc.net/problem/2056 접근 방법 문제에서 작업을 하는데에 있어서 순서가 있다고 하였다. 작업을 하기 전에 끝내야 할 것이 있으므로 위상 정렬을 사용하기로 했다. degree 가 0 ( 선행 조건을 다 수행을 하였다 ) 이 된 값 들을 queue에 넣어주는 방법. 그리고 tmp 배열을 사용한 이유는 각 작업을 끝내기 위해 필요한 누적 소요 시간을 저장을 따로 해줘야 되기 때문이다. Need Know 위상 정렬 전체 코드 ( Java ) import java.io.*; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokeni..

위상 정렬이란? 어떤 일을 하는 순서를 찾는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 위상 정렬의 특징 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서라고 한다. 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중단되고 이러한 그래프로 표현된 문제는 실행이 불가능한 문제가 된다. 위상 정렬 이용하는 방법 진입 차수가 0인 정점(즉, 들어오는 간선의 수가 0)을 선택을 하고 Queue에 모두 넣는다. 진입 차수가 0인 정점(즉, 들어오는 간선의 수가 0)을 선택 선택되어진 정점을 Queue에서 제거 선택된 정점에 속해있는..

https://www.acmicpc.net/problem/17070 접근 방법 간단하다. 그냥 재귀 함수를 통해서 현재 상태값과 현재의 위치에서 갈 수 있는 모든 것들을 넣어주 면 된다. 물론 나의 코드는 dp를 사용해서 반복되는 구간을 처리하고 있지 않지만 시간 초과가 일어난다면 DP 를 사용해야 할 것이다. ( 제 친구가 pypy를 쓰는데 시간초과가 났다고 함... ) Need Know 재귀함수 필요에 의하면 동적프로그래밍 (DP) 전체 코드 ( Java ) import java.io.*; import java.util.StringTokenizer; class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(Syst..

https://www.acmicpc.net/problem/2437 접근 방법 아이디어만 있다면 풀 수 있는 문제이다. 물론... 그 기발한 아이디어가 없어서 질문 검색을 통해 그 아이디어를 얻게 되었다. 아이디어는 이러하다. 먼저 n번째 까지의 누적값을 Sn 이라 해보자. 그리고 배열에서 n번째 값을 An 이라 하자. 그리고 S(n-1) 보다 만약 (An)-1값이 크면 S(n-1) ~ A(n-1) 의 값은 만들지 못한다. 따라서 만들 수 없는 최솟값은 S(n-1) 이 된다. 내가 생각하는 증명은 이러하다. Sn은 1부터 시작할 것이다. 왜냐하면 첫번째 원소가 2라면 제일 최솟값인 1을 만들지 못하기 때문이다. 그럼 이제 차근차근 값들이 더 해가지면서 만들 수 있는 조합들이 무수하게 많아질 것이다. 하지만..

https://www.acmicpc.net/problem/3671 접근 방법 먼저 문제를 보았을 때 배열에 대한 순열이 필요하다는 것을 알았다. 하지만 여기서 평범하게 순열을 쓰면 { 1, 1, 1 } 에서 1번째 1 + 2번째 1 → 11 / 2번째 1 + 3번째 1 → 11 두 개의 값은 다르다고 인식을 할 것이다. 그렇기 위해 나는 어떠한 장치를 걸기로 하였다. 맨 처음에는 단순히 Visit을 배열로 생성하고 boolean타입으로 한 번 들렸다면 true값을 반환하게 만들었었다. 하지만 문제의 메모리 제한은 128 MB 이다. 그래서 메모리 초과가 발생하게 된다. ( 10000000 boolean타입이 두개 이기 때문에 ) 해결방법은 3번, 4번 을 읽기를 바란다. Decimal_arr (에라토스테..