Lee 코딩 Lee 코딩

: 배낭에 들어갈 수 있는 무게가 주어지고, 물건들의 무게와 가치가 주어진 후 총 가치가 최대가 되도록 하는 방법을 구하는 문제 1) 물건들을 쪼갤 수 있다고 가정하는 문제 -> 그리디 알고리즘을 사용해서 풀이 2)물건들을 쪼갤 수 없다고 가정하는 문제 -> DP를 이용해서 풀이 (브루트포스를 이용해서 각 물건들을 넣을 때와 안 넣을 때를 모두 고려해서 풀이할 수도 있지만 이 경우 O(2^N)의 시간복잡도를 가지기 때문에 시간초과가 발생한다.) 배낭 알고리즘 p[i,w]를 i개의 보석이 있고 무게의 한도가 w일 때 최적의 가치라고 하자. i번째 물건이 배낭에 들어갈 수 없다면 : i-1개의 물건이 배낭에 들어갔을 때의 최적 가치 값 -> 즉 p[i-1][w] i번째 물건을 배낭에 넣을 수 있다면 : i-..

이동하기 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 25141 14683 10410 57.734% 문제 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다. 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오. 입력 첫째 줄에 ..

카드 정렬하기 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 32520 10927 8502 33.784% 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교..

잃어버린 괄호 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 50569 25609 20497 50.293% 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출..

해킹 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 256 MB 9855 3941 2799 38.853% 문제 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다. 최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대..

ACM Craft 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 512 MB 55074 13138 8811 25.856% 문제 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다. 위의 예시를 보자. 이번 게임에서는 다음과 같이 건설 순서 규칙이 ..

미로만들기 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 8912 4846 3595 55.299% 문제 n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다. 시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다. 아래 그림은 n=8인 경우의 한 예이다. ..

2252번: 줄 세우기 (acmicpc.net) 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static ArrayList graph = new ArrayList(); static int[] indegree; static int n; pub..