Coding Test

1. 문제 설명 https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 2. 아이디어 값의 범위가 크지 않아서 팩토리얼을 사용하면 간단하게 해결되는 문제다. 이항 계수가 무엇인지에 대한 설명은 따로 다루지 않겠다. 3. 코드 import sys sys.setrecursionlimit(100000) def factorial(nb): if (nb == 0 or nb == 1): return 1 return (nb * factorial(nb - 1)) def solution(): n, k = map(int, input().sp..

1. 문제 설명 https://www.acmicpc.net/problem/1790 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net 2. 아이디어 약간의 수학적 사고력을 필요로 하는 구현 문제다. 이 문제를 정직하게 풀려고 한다면 n만큼 수를 이어붙인 문자열에서 k번째 숫자를 찾아나서야 하는데 최악의 경우가 n == 100,000,000이고 k == 1,000,000,000이다. 데이터 1억개를 처리하는 시간이 대략 1초정도 걸리는데 이걸 다 이어붙이고, 문자열 1억 번째 위치를 찾으려 하면 당연히 타임에러가 발생한다. 이런 문제를 해결할 방..

1. 문제 설명 https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 2. 아이디어 당시에 이 문제를 풀 아이디어를 떠올리지 못해서 구글링을 통해 찾아낸 방법이 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)이었는데 애초에 다이나믹 알고리즘도 모르던 내가 이걸 100% 이해할 수 있었을리가 없다. 근데 난 왜 이걸로 문제를 풀어놨을까..? 분명한 건 구글링의 도움을 받아 문제를 풀었었다. 알고리즘에 대한 포스팅은 이후에 한 번에 정..

1. 문제 설명 https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 사실 나도 잊고 있었던 풀이법인데 다시 보니까 기억났다. 이래서 사람이 복습을 해야 돼 2. 아이디어 가장 처음에 떠오르는 무식한 방법은 a와 b값을 입력받고, 진짜 1111(4), 111(3)의 값을 저장하여 연산과정을 거치는 방법일 것이다. 문제를 어느정도 풀어보면 알겠지만, 이 방법은 절대 통과가 안 될 거라는 것을 짐작할 수 있다. (지금 생각해보니까 ..