2주차 프리코스 과제는 자동차 경주를 구현하는 문제였다. 각 자동차별 이동이 랜덤을 활용해 구현해야 했고 진행 과정과 결과에 대한 출력이 모두 동반되는 문제였다. 1주차 과제보다 구현만 생각하면 더 쉬운 과제라고 생각이 됐지만 좋은 설계에 대한 고민에서는 더 어려운 과제였던 것 같다. 구현 링크 1. 애플리케이션 아키텍처 설계 이전 과제...

1주차 프리코스 과제는 문자열 덧셈 계산기를 구현하는 문제였다. 정상적인 입력에 대한 구현은 크게 어렵지는 않다고 느꼈지만, 비정상적인 입력에 대한 처리는 제법 까다로운 과제라는 생각이 들었다. 어떤 입력까지는 정상적인 입력으로 간주하고 어떤 입력부터는 비정상적인 입력으로 간주할 지 개발자의 판단에 맡긴다는 느낌이 들었고 스스로 기준을 정해서 구현했다...

문제 링크 문제 풀이 자연수 $N$ 과 정수 $K$ 에 대한 이항 계수를 $M$ 으로 나눈 나머지를 구해야 하는데, $N$ 이 최대 $10^{18}$ 이며 $K$ 는 최대 $N$ 인 음이 아닌 정수, $M$ 은 2,000이하의 소수이다. 매우 큰 수로 이루어진 이항 계수를 계산하는 것은 단순한 다이나믹 프로그래밍으로는 불가능한데 $M$ 이...

문제 링크 문제 풀이 자연수 $N$ 과 정수 $K$ 에 대한 이항 계수를 1,000,000,007로 나눈 나머지를 구해야 하는 문제다. 단순한 다이나믹 프로그래밍으로는 해결할 수 없는데 페르마의 소정리와 분할 정복을 이용한 거듭 제곱을 적용하면 해결할 수 있다. 이항 계수의 경우 분모를 모듈러 곱셈 역원으로 바꾸면 아래와 같이 된다.(p...

문제 링크 문제 풀이 백준 11050번 - 이항 계수 1 해당 문제에서 $N$ 과 $K$ 의 범위가 더 커졌고, 이항 계수를 10,007로 나눈 나머지를 구해야 하는 문제다. 이항 계수는 팩토리얼 연산 때문에 수가 기하급수적으로 커지며 연산량도 많아져서 다이나믹 프로그래밍을 활용해서 효율적으로 구해야 한다. 또한 계산 중간에 기본 타입의...

문제 링크 문제 풀이 자연수 $N$ 과 정수 $K$ 가 주어졌을 때 이항 계수를 구하는 문제로 파스칼의 항등식을 활용한 재귀나 다이나믹 프로그래밍으로 해결할 수 있다. 파스칼의 삼각형을 통해 알 수 있는 파스칼의 항등식은 아래와 같다. [\binom{n}{r} \binom{n-1}{r} + \binom{n-1}{r-1}] 1. 재귀 ...