Python/Coding Test

2749 피보나치 수 3

문제 https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 접근 문제에서 주어지는 N의 범위가 매우 크기 때문에, 피보나치 수들에 어떠한 주기가 있을 것으로 판단하고 구글 검색 후 피사노 주기라는 개념을 알게 되었다. 피사노 주기 def) In number theory, the nth Pisano period, written as π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats. 즉, 주기를 p라고 했을 때, n번째 피보나..

21939 문제 추천 시스템 Version 1

문제 https://www.acmicpc.net/problem/21939 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 접근 처음 생각한 방법은 딕셔너리에 난이도별로 문제를 저장하려 했으나, 난이도별로 관리할 필요가 없다는 생각이 들어서 우선순위큐로 바꿨다. 가장 어려운 문제와 가장 쉬운 문제를 추천해야 하므로 우선순위큐 2개를 사용했고, 푼 문제들을 저장하기 위해 딕셔너리를 사용했다. solve 연산을 수행할 때마다 저장된 문제를 갱신하는 방법으로 풀었으나 시간초과가 발생해서 ..

13334 철로

문제 https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 접근 가장 처음 시도한 방법은 정렬과 스위핑을 사용해서 철도의 구간과 구간에 들어가는 경로의 개수를 갱신해나가는 방법으로 풀이했으나 틀림 -> 반례가 무엇인지 못찾겠다... 다른 방법으로 정렬된 전체 경로들(시작점과 끝점이 철도의 길이 d보다 작거나 같은 경로들)에 대해, 철도의 길이 d에 함께 포함될 수 있는 경로들을 따로 저장(q)해놓고..

2485 가로수

문제 https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 접근 모든 가로수의 간격이 같으려면 주어진 가로수의 간격의 최대공약수를 구해야 한다고 생각해서 유클리드 호제법을 이용했다. 각 간격을 저장하고 저장된 모든 간격에 대한 최대공약수를 계산한 후, 각 간격을 최대공약수로 나눈 몫 - 1을 합해서 정답을 구한다. 풀이 def gcd(x, y): if x % y == 0: return y return gcd(y, x % y) n = int(i..

19235 모노미노도미노

문제 https://www.acmicpc.net/problem/19235 19235번: 모노미노도미노 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 접근 문제에 주어진 대로 구현하면 되는 시뮬레이션 문제 어떻게 풀어야 간단할까?? 초록색 보드와 파란색 보드에 대한 처리를 함수 하나로 구현하면 편하기 때문에 파란색 보드를 시계방향으로 90도회전시켜서 생각한다. 풀이 1. 블록 처리 1번 블록: 초록색 보드와 파란색 보드 모두 1번 블록으로 처리 2번 블록: 초록색 보드는 2번 블록으로 파란색 보드는 3번 블록으로 처리 3번 블록: ..

16960 스위치와 램프

문제 https://www.acmicpc.net/problem/16960 16960번: 스위치와 램프 첫째 줄에 스위치의 수 N, 램프의 수 M이 주어진다. 둘째 줄부터 N개의 줄에는 스위치에 대한 정보가 주어진다. 스위치 정보의 첫 번째 정수는 그 스위치와 연결된 램프의 수이고, 이후 연결된 램 www.acmicpc.net 접근 N개의 스위치마다 해당 스위치를 누르지 않았을 때 M개의 모든 램프를 켤 수 있는지 확인한다. 한 스위치에 M개의 램프가 연결된 경우에는 항상 N-1개의 스위치로 모든 램프를 켤 수 있기 때문에, 실제 시간 복잡도는 이론상 계산한 O(N^2 * M) 보다 훨씬 작을 것이다. 풀이 각 스위치에 연결된 램프를 저장하기 위해 딕셔너리 사용 각 스위치를 누르지 않았을 때 N-1개의 스..

1781 컵라면

문제 https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 접근1 (틀림) 가장 먼저 생각한 방법은 딕셔너리를 사용해서 데드라인 별로 얻을 수 있는 컵라면을 리스트 형태로 저장한 후 정렬해서 각 데드라인 일자마다 문제 풀이가 가능한 갯수만큼 더하는 방법으로 작성 But, 많은 컵라면을 얻을 수 있는 문제의 데드라인 값이 큰 경우, 해당 문제를 풀기 전 데드라인 값이 작은 문제들을 먼저 풀어버려서 많은 컵라면을 얻을 수 있는 문제는 못 풀게될 가능성) 접근2 ..

17175 피보나치는 지겨웡~

문제 https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 접근 출력을 1000000007로 나눈 나머지로 하라는 것은 피보나치 함수 호출의 숫자가 1억보다 큰값이 존재한다는 뜻이므로, 실제로 피보나치 함수를 구현해서 호출 횟수를 세는 방법은 시간초과가 난다. (제한시간 1초) 어떠한 값 i에 대한 피보나치 함수 호출 횟수는 i-1의 피보나치 함수 호출 횟수와 i-2의 피보나치 함수 호출 횟수의 합이므로 다이나믹 프로그래밍으로 접근 풀이 dp[i]를..

15918 랭퍼든 수열쟁이야!!

문제 https://www.acmicpc.net/problem/15918 15918번: 랭퍼든 수열쟁이야!! 세 자연수 n, x, y가 주어진다. (2 ≤ n ≤ 12, 1 ≤ x < y ≤ 2n, 1 ≤ y-x-1 ≤ n) www.acmicpc.net 접근 비슷한 문제를 풀었던 적이 있어서 바로 백트래킹으로 접근 풀이 먼저 x와 y 사이에 숫자가 몇개(diff) 들어가는지 계산해서, 결과 배열의 x번째와 y번째를 diff로 채우고 시작 결과 배열의 idx를 기준으로 1부터 n까지의 숫자 중 이전에 사용하지 않았던 숫자(i)에 대해 idx번째와 idx+i+1번째에 해당 숫자를 집어넣을 수 있는지 확인하고, 집어넣을 수 있으면 결과 배열에 숫자를 채우고 idx+1로 넘어간다. 만약 해당 idx번째에 이미 ..