태브로의 개발위키

출처 : 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...

출처: https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 풀이 import sys n = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().split())) uni = list(sorted(set(a))) dic = {b : index for index, b in enumerate(uni)} for i in a: print(dic[..

출처: https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 풀이 import sys n = int(sys.stdin.readline()) member = [] for _ in range(n): member.append(list(sys.stdin.readline().split())) member.sort(key = lambda x : int(x[0])) for i in member: print(i[0], i[1]) 입출력은 늘 하던 방식이니 생략한다. 가..