태브로의 개발위키

출처 : https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) a = [0]*1000001 a[1],a[2] = 1, 2 for i in range(3,n+1): a[i] = (a[i-2]+a[i-1])%15746 print(a[n]) 풀이 : 그래서 피보나치 문제임을 확인했고 이게 재귀함수를 사용해서 풀었었는데 그렇게 풀면 메모리초과가 나기 때문에 위 풀이..

출처 : https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 풀이 : dp = [[[0]*(21) for _ in range(21)] for _ in range(21)] def w(a,b,c): if a 20 : return w(20,20,20) if dp[a][b][c]: # 0 이면 반환을 안함 return dp[a][b][c] if a < b < c : dp[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)..

출처 : https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 : t = int(input()) zero = [1,0,1] one = [0,1,1] def fibo(num): length = len(zero) if num >= length: for i in range(length, num+1): zero.append(zero[i-2]+zero[i-1]) one.append(one[i-2]+one[i-1]) print(f'{zero[num]} {one[num]}') for _ in range(t): fibo(int(input())) 문제 부터..

출처 : https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이: n = int(input()) ans = 0 row = [0]* n def right(x): for i in range(x): if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i) : return False return True def queen(x): global ans # 함수 안에서 ans 값이 변할 수 있도록 해줌 if x == n: ans..

출처 : 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 = int(input()) mat = [] A = [] B = [] for _ in range(n): mat.append(list(map(int, input().split()))) ans = float('Inf') def dfs(depth): global ans if depth == n//2: A_sum = 0 B_sum = 0 for i in range(n): if i not in A: B.appe..

출처 : https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이: n = int(input()) a = list(map(int, input().split())) ysj = list(map(int, input().split())) maximum = -1e9 minimum = 1e9 def dfs(depth, tot, plus, minus, multiply, divide): global maxi..

출처 : https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net a, b = map(int, input().split()) ans = [] def bts(start): if len(ans) == b : print(' '.join(map(str,ans))) return for i in range(start, a+1): ans.append(i) bts(i) ans.pop() start += 1 bts(1) 풀이: 이전과 똑같이 하면되는데 다만 함수에 변..

출처 : https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 a ,b = map(int, input().split()) ans = [] def bts(): if len(ans) == b: print(' '.join(map(str,ans))) return for i in range(1, a+1): ans.append(i) bts() ans.pop() bts() 첫 백트래킹 문제를 해결할 때 열심히 이해해서 몇 일이 지나도 코드를 쉽게 구현하고..

출처 :https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 : n, m = map(int, input().split()) s = [] def DFS(start): if len(s) == m : print(' '.join(map(str,s))) return for i in range(start, n+1): if i not in s : s.append(i) DFS(i+1) s.pop() DFS(1) 전문제와 푸는 방식은 비슷하다. 하지만 이문제..

DFS 가능한 모든 경로를 탐색하는 알고리즘. 백트래킹이란? 백트래킹은 DFS(Depth First Search; 깊이 우선 탐색)의 방식을 기반으로 불필요한 경우를 배제해가면서 답에 도달할 때까지 계속 탐색하는 전략이다. 즉 가지치기라고 할 수 있다. DFS를 기반으로 두기 때문에 스택을 이용해서 퇴각 하고 다음 탐색을 진행하기 때문에 백트래킹이라 불린다. 그래서 백준 15649의 풀이를 소개하며 정리하겠다. https://www.acmicpc.net/problem/15649 이 문제는 순열 문제로 4 2 가 주어진다면 [1 2] [1 3] [1 4] [2 1] ... [4 3] 이런식으로 중복되지 않게 하나씩 뽑아야한다. 이 때 바로 백트래킹을 쓰는것이 아주 적합하다. 두 가지 코드를 준비했다. 1...