Show 큰 수의 법칙저자:Kyeongsik Choi 큰 수의 법칙(Law of Large numbers)은 야코프 베르누이(Bernoulli; 1654~1705)의 “추측술”이라는 책 안에 소개한 내용이다. 큰 수의 법칙은 다음과 같다. 큰 수의 법칙어떤 시행에서 사건 A가 일어날 수학적 확률이 p이고, n번의 독립시행에서 사건 A가 일어나는 횟수를 X라고 할 때, 임의의 양수 h에 대하여 n의 값이 한없이 커질수록 확률 이다. 탐구 1지오지브라에서 확률 계산기를 실행하여 이항분포와 정규분포 곡선의 차이를 관찰해 봅시다. 특히 n의 값이 커질 때마다 두 분포 사이의 차이가 어떻게 되는지 관찰하고 토의해 봅시다. [문제1] 큰 수의 법칙#[문제] 큰 수의 법칙 : 문제 설명#
[문제] 조건#
아이디어#
law_of_large_number.py#
LawOfLargeNumber.java#
이 자료는 나동빈님의 이코테 저서를 보고 정리한 자료입니다. 큰 수의 법칙다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙. 단 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다. 예를 들어 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때, M이 8이고, K가 3이라면 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 => 46 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 예를 들어 순서대로 3, 4, 3, 4, 3 으로 이루어진 배열이 있을 때 M이 7이고, K가 2라고 가정하자 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 => 28 입력 조건
출력 조건
입력 예시5 8 3 출력 예시46 풀이맨 처음에는 각 인덱스의 수를 K번만 더할 수 있다고 생각해서 풀었는데, 알고보니 아니었다..! 문제 조건을 다시 읽어보니, K번을 초과하여 중복으로 더할 수 없는 것이지, K번 더한 후 다른 수를 한번 더한 후 다시 더할 수 있었던 것이다. 따라서 입력받은 배열에서 가장 큰 수와 두번째로 큰 수만 있으면 문제를 해결할 수 있다. 추가하여필자의 처음 짠 코드를 올리기 보다는, 이후 책에 나와있는 아이디어를 사용한 코드를 올리겠다. 아이디어는 이러하다. while을 사용하여 수를 계속 더해가는 방법은 M이 10000 이상의 큰 수를 입력받으면 시간초과가 발생할 가능성이 높다. 이 문제를 해결하기 위해 다음과 같은 아이디어를 제시한다. 우선 N이 5이고 다음과 같은 배열이 주어졌다고 가정한다.
이때 가장 큰 수와 두 번째로 큰 수는 6과 5이다. 이때 M이 8이고, K가 3이라면 다음과 같이 더했을 때 합이 최대이다. { 6, 6, 6, 5 } { 6, 6, 6, 5 } 이 문제를 풀려면 가장 먼저 반복되는 순열에 대해서 파악해야 한다. 가장 큰 수와 두번째로 큰 수가 더해질 때는 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있다. 이때 반복되는 수열의 길이는 어떻게 될까? 바로 (K + 1)로 위의 예시에서는 4가 된다. 따라서 M을 (K + 1)로 나눈 몫이 수열이 반복되는 횟수가 되며, 여기에 K를 곱해주면 가장 큰 수가 더해지는 횟수가 된다. 그런데 M이 (K + 1)로 나누어 떨어지지 않는 경우도 있다. 그럴 때는 M을 (K + 1)로 나눈 나머지를 추가로 더해주면 가장 큰 수가 등장하는 횟수가 된다. 가장 큰 수가 더해지는 횟수 : [{M / (K + 1)} * K] + {M % (K + 1)} 코드
📔 Reference[이것이 취업을 위한 코딩 테스트다 - 나동빈] GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. - GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소 github.com |