All77 [백준 알고리즘] 1149번(RGB거리) - 관련 : DP문제 백준 알고리즘 오늘 풀어본 문제는 다이나믹 프로그래밍과 관련된 문제입니다.알고리즘이 아직 생소해서 그런지 문제를 이해하는데 시간이 걸렸습니다.특히 오늘은 어이없는 실수를 했습니다. 어떤 실수를 했는지는 밑에 있습니다.참 부끄럽네요 이런 실수는.... 동적 계획법(Dynamic Programming)혹시나 아직 개념을 모르시는 분이 있을까봐 설명을 드립니다.일반적으로 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것입니다.각 하위 문제의 해결을 계산하고 그 계산 값을 다른 곳에 저장해 두었다가 같은 문제가 나왔을 경우 저장된 값을 가지고와서 불필요한 것들을 줄이고 계산을 빨리 할 수 있도록 도와줍니다.더 자세한 내용은 이 곳에서 확인 하세요(출처 : 위키 백과) .. 2017. 9. 5. [백준 알고리즘] 2407번(조합) [백준 알고리즘] 지난 번에 팩토리얼에 대해 풀었고 이번에는 조합에 대한 문제입니다. 조합에 대한 문제는 예전에 제가 이항계수 때 풀어놓은 것이 있어서그것을 이용하여 문제를 해결했습니다.이번에 조금 다른 것이 있다면 범위 입니다. 조합 조합에 대해 모르는 사람은 없을 것이라고 생각하지만혹시나 조합에 대해 모르는 사람이 있을 수도 있다고 생각하기에간단한 설명을 드리겠습니다.조합은 영어로 Combination이라고 하며 기본적인 원리는 이렇습니다.n개에서 r개를 고를 수 있는 경우의 수입니다.(중복 X)예를 들어 보겠습니다.A / B / C / D / E 라는 사람 중에 2명 씩 짝을 이룰수 있는 경우를 구해보겠습니다.AB / AC / AD / AE / BC / BD / BE / CD / CE / DE 이렇.. 2017. 9. 1. [백준 알고리즘] 1676번(팩토리얼 0의 개수) [백준 알고리즘] 팩토리얼 문제에 이어서 팩토리얼에 관련된 문제를 하나 더 풀어보았습니다. 문제 해석 일단 이것을 어떻게 풀 것인가 생각을 해보았습니다. 너무 깊게 생각하다가 자꾸 이상하게 풀어서 쉽게 보자 생각했습니다.그래서 다시 한번 보니까 문제는 생각보다 간단했습니다.일단 한번 문제를 봅시다. N! 까지 뒤에서 부터 0이 아닌 숫자가 나올 때 까지 0의 갯수를 구하는 것 입니다.그렇다면 0이 나오려면 어떻게 해야할까요? 10이 나온다면 0이 나오게됩니다. 00이 나오려면 10*10이 되면 됩니다.다시 말하면 10이 몇 번 곱해지는지에 따라 0의 갯수가 정해집니다. 예를 들어봅시다.5! = 1 x 2 x 3 x 5 = 30 (0이 1번)6! = 1 x 2 x 3 x 5 x 6 = 180 (0이 1번).. 2017. 8. 31. [백준 알고리즘] 10872번(팩토리얼) [백준 알고리즘] 오늘도 기본 중에 기본인 팩토리얼 알고리즘을 짜보았습니다.일단 팩토리얼에 대해 설명하겠습니다. 팩토리얼(n!) 계승이라는 이름과 팩토리얼이라는 이름 두 가지를 가지고 있습니다. 우리는 팩토리얼이 더 친숙합니다.1에서 n까지 양의 정수를 모두 곱한 값을 n 팩토리얼 또는 n계승이라고 합니다.단, 0!는 0으로 약속합니다. 문제 사실 문제는 정말 간단합니다.그냥 n팩토리얼을 구하는 알고리즘을 작성하시면 됩니다. 코드 123456789101112131415161718192021222324252627import java.util.Scanner; public class Beak10872 { public static void main(String[] args) { Scanner sc = new S.. 2017. 8. 31. [백준 알고리즘] 11051번(이항 계수Ⅱ) [백준 알고리즘] 이항 계수 문제를 하나씩 풀다 보니 내가 몰랐던 것이 너무 많다는 것을다시 한번 알게 되었습니다. 그래서 공부 더 열심히 하려고 합니다힘냅시다 이전에 이항계수를 구하는 것은 재귀함수를 써서 구했습니다.그리고 시간복잡도 같은 것은 잘모르기도 하고 별 신경을 안쓰고 짰었습니다.하지만 저번부터 피보나치도 그렇고 이번에 이항 계수도 그렇고 앞으로도 그럴 것 같습니다.시간이 점점 중요해지고 있다는 것을요 그리고 점점 생각할 것이 많아 진다는 것도요... 여튼 이번에 풀어본 문제는 이항계수 관한 문제입니다.그리고 여기에서 우리에게 원하는 것은 동적 계획법 / 메모이제이션 으로 풀으라는 것입니다. 그렇습니다 다시 공부해야합니다. 동적 계획법(Dynamic Programming) / 메모이제이션 (출.. 2017. 8. 28. 이전 1 ··· 7 8 9 10 11 12 13 ··· 16 다음
