백준

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 입력으로 주어지는 N개의 물건들은 각각 무게 W와 가치 V를 가진다. 배낭이 최대 K의 하중을 견딜 수 있다고 할 때, 무게의 합이 K를 넘지 않으면서 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구한다. 이 문제는 유명한 알고리즘 문제인 knapsack 문제이다. 브루트 포스로 풀 수도 있고 재귀를 사용할 수도 있는데, 당연하지만 DP를 사용하는 방법이 제일 시간복잡도가 낮은 방법이다. D..

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 스도쿠가 주어지면 빈칸을 채우는 문제이다. N-퀸 문제와 비슷하게 sudoku 함수와 중복이 없는지를 검사하는 check 함수를 만들어 백트래킹을 통해 풀었다. 먼저 배열에서 비어있는 셀을 찾는다. 비어있는 셀을 찾으면 그 셀에 대해 1부터 9까지 숫자를 대입해보며 check 함수로 유효한지 여부를 검사한다. 만약 행, 열, 한 칸에 대해 중복이 없다면 그 자리에 수를 쓴다. sudoku 함수를 재귀호출하면서 더 이상 비어있는 셀이 없을 때까지 반복한다. ..

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 정수 N이 입력으로 주어질 때, 크기가 N x N인 체스판 위에 퀸 N개를 놓을 수 있는 모든 경우의 수를 출력한다. N-queen 문제는 백트래킹으로 풀 수 있는 유명한 알고리즘 문제 중 하나이다. 백트래킹 (Backtracking) 상태공간트리란 문제 해결 과정에서 해를 포함하고 있는 트리이다. 해가 존재한다면 그 해는 반드시 상태공간트리의 어떤 노드에 해당하므로, 이 트리를 체계적으로 탐색하면 언젠가는 해를 구할 수 있다. 해를 찾기 위해 상태공간트리를 완전탐색해야만..

2447번: 별 찍기 - 10재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이www.acmicpc.net문제입력으로 3의 거듭제곱인 N이 주어질 때 N x N의 프랙탈 패턴을 출력하는 문제이다. 주어진 패턴을 보면 N = 3일 때의 패턴이 크기가 커지며 반복되고 있다는 것을 알 수 있다. 이는 가운데 부분이 뚫려 있는 네모난 도넛 모양을 이루고 있다. 자세히 보면 N = 9일 때는 N = 3일 때의 패턴을 8개 가져다 놓은 모양이다. 그리고 N = 27일 때는 N = 9일 때의 패턴을 8개 가져다 놓았다. 즉 N = 3^x의 패턴은 N = 3..

5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 입력으로 수행할 함수와 배열이 주어지면 배열에 주어진 함수를 차례대로 수행하여 그 결과를 출력하는 문제이다. 이때 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 배열의 첫번째 수를 버리는 함수이다. 만약 배열이 비어 있는 상태에서 함수 D가 실행될 경우 "error"를 출력한다. 풀이 처음에 아래와 같은 코드를 제출했더니 시간 초과가 났다. import sys from collections import deque t = int(sys.stdin.readline()) for i in range(t): ..