이것저것 공부 기록하기

문제링크 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/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/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제설명 배열이 아니라 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬하는 문제이다. 정렬문제이므로 어차피 문자열로 처리해야 했기에 입력값을 int로 변환하지 않고 문자열 타입 그대로 받았다. 그 후 sorted() 를 취해 문자열을 정렬한 후, "".join() 을 사용했다. 참고 python에서 문자열 자체를 정렬하려면, s.sort()를 쓰면 안된다. string의 경우 첫글자의 주소값으로 참조를 하기에 원본이 변경되면 안되므로, str type에 sort() ..

문제링크 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제설명 홀수 N개의 값들에 대해 산술평균, 중앙값, 최빈값, 범위를 차례로 구하는 문제로 까다로운 조건이 없었다. 최빈값이 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력해야 하는 조건이 주어졌다. 이 조건에 대해서는 Counter의 most_common으로 2개까지만 구한 후 케이스를 구분하는 방식을 취했다. most_common으로 최빈값을 구한다면, 중앙값 뿐 아니라 최빈값에 대해서도..

문제링크 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제설명 시간 제한과 메모리 제한이 있는 문제이며, 특히 메모리 제한이 빡센 문제로 단순하게 sort로 풀고 PyPy3로 돌려서 해결되는 문제가 아니다. 앞에서 블로깅했던 수 정렬하기 2(https://www.acmicpc.net/problem/2751) 문제는 메모리 제한이 256MB 였지만, 이번 문제는 메모리 제한이 8MB이므로 정렬이라는 접근보다는 새로운 접근으로 풀어야 했다. '수 정렬하기 2' 처..