본문 바로가기

# Foundation

 (88)
# Foundation/백준풀이 [이분탐색] 백준 1654 :: 랜선 자르기 랜선 자르기 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB283735211337318.668%문제집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm 은 버려야 한다.(이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 ..

2019. 6. 25. 17:13
# Foundation/알고리즘 동적 계획법(Dynamic Programming) 알고리즘 동적 계획법 이름의 유래수학, 컴퓨터 공학, 경제학에서 사용되는 문제풀이 방법. 리처드 벨만이 처음 이 단어를 사용했으며,그의 자서전 '태풍의 눈'에서 다음과 같이 설명했다. 어떤 문제가 다단계로 이루어져 있으며, // sub-structure시간에 대해 가변적이고, // time-varying동적이다. // dynamic 시간에 대해 가변적이라는 특성은, 특히 경제학에서 주로 다뤄지는 것 같다. 동적 계획법이란?하나의 복잡한 문제를, 동일한 구조의 간단한 문제들의 합으로 푸는 방법. 하나의 문제를, 그것과 동일한 형태의 작은 문제들로 나눈 뒤.작은 문제들을 풀어내어 최종적인 문제에 접근하는 것이 그 목적이다. 또한 어떤 문제를 푸는 도중에, 작은 문제들의 결과값이 필요하다면,작은 문제를 푸는 과정으로 ..

2019. 6. 25. 16:16
# Foundation/백준풀이 [동적계획법] 백준 1003 :: 피보나치 함수 피보나치 함수 성공시간 제한메모리 제한제출정답맞은 사람정답 비율0.25 초 (언어별 추가 시간 없음)128 MB66959146351165829.096%문제다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.1234567891011int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }}fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.fibonacci(2)는 fibonac..

2019. 6. 24. 02:46
# Foundation/백준풀이 [동적계획법] 백준 1463 :: 1로 만들기 1로 만들기 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB74952244731562832.094%문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.예제 입력 1 복사2 예제 출력 1 복사1 예제 입력 2 복사10 예제 출력 2 복사3 힌트10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다. 문제 ..

2019. 6. 24. 01:25
# Foundation/백준풀이 [이분탐색] 백준 7453 :: 합이 0인 네 정수 합이 0인 네 정수 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초256 MB7483159794720.196%문제정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.출력합이 0이 되는 쌍의 개수를 출력한다.예제 입력 1 복사6 -45 22 42 -16 -41 -27 56 30 -36 53 -37 77 -36 30 -75 -46 26 -38 -10 62 -32 -5..

2019. 5. 28. 01:48
# Foundation/백준풀이 [이분탐색] 백준 1072 :: 게임 게임 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB7700138198019.549%문제김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.게임 기록은 다음과 같이 생겼다.게임 횟수 : X이긴 게임 ..

2019. 5. 27. 23:04
# Foundation/백준풀이 [이분탐색] 백준 10816 :: 숫자카드 2 숫자 카드 2 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB96382832194833.633%문제숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정..

2019. 5. 26. 21:32
# Foundation/백준풀이 [이분탐색] 백준 2512 :: 예산 예산 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB114833528261531.362%문제국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 14..

2019. 5. 26. 20:48

티스토리툴바