이것저것 공부 기록하기

문제링크 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제설명 push, pop 을 해가며 pop을 이용해 입력 받은 수열을 만드는 문제이다. 문제의 예시를 살펴보자. 8 4 3 6 8 7 5 2 1 과 같이 입력을 받을 때, 수열 리스트 = [4,3,6,8,7,5,2,1] 이 된다. 우선 push를 4번 하면 스택에 다음과 같이 수가 담긴다. s = [1,2,3,4] 여기서 입력 받은 수열과 같게 하려면 pop을 두 번 해..

문제링크 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/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제설명 앞서 풀이했던 N과 M 시리즈 문제(위 링크 참고)와 유사하다. [Algorithm] 1일1솔 - 백준 15649 N과 M (1) (python3) 문제링크 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분..

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