이것저것 공부 기록하기

문제링크 https://www.acmicpc.net/problem/1904 문제설명 문제에 재귀 함수 코드가 주어져 있고, 그대로 구현하면 값을 구하는 데 시간이 매우 오래 걸린다는 힌트도 주고 있다. 문제풀이 a, b, c가 모두 같을 경우 a, b, c가 0 이하가 될 때까지 재귀를 돌게 되어 시간이 매우 오래 걸리므로, 메모이제이션을 활용하여 풀이했다. n = int(input()) dp = [0] * 1000001 dp[1], dp[2] = 1,2 for i in range(3, n+1): dp[i] = (dp[i-1] + dp[i-2]) % 15746 print(dp[n])

문제링크 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제설명 문제에 재귀 함수 코드가 주어져 있고, 그대로 구현하면 값을 구하는 데 시간이 매우 오래 걸린다는 힌트도 주고 있다. 따라서 메모이제이션으로 풀어야 함을 알 수 있고, 이 때 0 이하인 수는 1, 20 초과인 수의 경우는 모두 w(20,20,20) 이므로 초기값은 20까지 설정해두면 된다. 문제풀이 a, b, c가 모두 같을 경우 a, b, c가 0 이하가 될 때까지 재귀를 돌게 되..

문제링크 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제설명 문제풀이

문제링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제설명 짝수 N명의 사람들을 스타트 팀과 링크 팀으로 나누었을 때, 팀 간 능력치를 최소화하는 문제이다. S는 팀의 i번 사람과 j번 사람이 같은 팀에 속했을 때의 능력치를 담은 2차원 배열이며, S_ij 와 S_ji 는 다르게 취급되므로 그 경우를 각각 따져주기 위해 이중 for 문으로 각 능력치를 구하여 팀 전체의 능력치에 더해줬다. 문제풀이 combinations 를 활용해서 팀 조합을 만들고, 스타트..

문제링크 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제설명 N개로 이루어진 수열과 N-1개의 연산자가 주어질 때, 수식을 만들어 최댓값과 최솟값을 구하는 문제이다. 이 때 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 하며, 나눗셈은 정수 나눗셈으로 몫만 취한다. 또한, 음수를 양수로 나눌 때에는 양수로 바꾼 뒤 몫을 취한 후 그 몫을 음수로 바꾸어야 한다. 예를 들어..

문제링크 https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제설명 앞서 풀이했던 15649번: N과 M(1), 15650번: N과 M(2) 문제와 유사하며, 문제의 조건이 약간 변형되었다. '같은 수를 여러 번 골라도 된다' 는 조건이 추가되었다. 이 조건으로 인해 해당 문제는 백트래킹으로 풀이하면 pruning 과정이 따로 필요없이 dfs로 경우의 수를 탐색해주면 된다. 또한, 경우의 수로 풀이하는 경우에는 중복순열을 이용해서 풀 수 있다...

문제링크 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제설명 앞서 풀이했던 15649번: N과 M(1) 문제와 유사하며, 문제의 조건이 약간 변형되었다. '고른 수열은 오름차순이어야 한다' 는 조건이 추가되었다. 백트래킹으로 풀이하면 pruning 과정에서 해당 조건을 추가해주면 된다. 또한, 경우의 수로 풀이하는 경우에는 오름차순 조건을 충족시킨다는 건 순서 상관없이 같은 수열로 취급한다는 의미이므로, 조합을 이용해서 풀 수 있다. 문..

문제링크 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제설명 자연수 N과 M이 주어졌을 때, '1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열' 조건을 만족하는 길이가 M인 수열을 모두 구하는 문제이다. 문제 분류는 백트래킹으로 되어있지만, 중복 없이 일정한 개수의 자연수가 담긴 수열을 구하며, 순서를 상관하여 수열을 다르게 취급한다는 점에서 순열을 이용해서 풀이할 수도 있다. 문제풀이 1. 순열 이 문제에서는 수열을 순서가 다..