728x90 backtracking 썸네일형 리스트형 [백준알고리즘] 14888번: 연산자 끼워넣기 -Python [백준알고리즘] 14888번: 연산자 끼워넣기 -Python https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. www.acmicpc.net 백트래킹 문제이다. 왜지? 그냥 DFS 문제이다. 단계별 풀기에는 분명 백트래킹으로 되어있는데 페이지 밑에 알고리즘 분류에는 또 브포로 나와있다.. 주절주절했듯이 그냥 모든 경우를 찾아야한다. 가지치기(pruning)할 경우를 나눈다고 해.. 더보기 [백준알고리즘] 2580번: 스도쿠 -Python [백준알고리즘] 2580번: 스도쿠 -Python https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 2020.03.11 거의 유사하긴 하나, 새로 푼 코드를 아래에 추가했다. 와 이거 푸는.. 더보기 [백준알고리즘] 9663번: N-Queen -Java [백준알고리즘] 9663번: N-Queen -Java https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 드디어! BackTracking 분류에서 대표적인 백트래킹 문제인 N-Queen문제가 나왔다. 체스판에서 퀸은 가로, 세로, 대각선 방향으로 모두 길이 제한 없이 이동이 가능하다. 즉 각자의 가로, 세로, 대각선에 다른 퀸이 놓이지 않게 N X N 행렬 위에 N개의 퀸을 올리면 되는 문제이다. 이 문제를 처음에 주어진 것처럼 NxN행렬로 만들어서 구하다가 메모.. 더보기 [백준알고리즘] 15650번: N과 M (2) -Python [백준알고리즘] 15650번: N과 M (2) -Python https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 저번에 풀었던 N과 M (1)의 다음 문제이다. 조건을 보면 "고른 수열은 오름차순이다."가 추가되었다. 별로 추가된 것도 없고 그냥 풀었다. itertools를 쓰면서 이 추가된 조건을 처리하려 하는 것보다 그냥 짜는 게 훨씬 쉬워 보여서 그냥 짰다. 얼른 백 트랙킹 마무리 지어야겠다. import sys def testCa.. 더보기 [백준알고리즘] 15649번: N과 M (1) -Python [백준알고리즘] 15649번: N과 M (1) -Python https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 오랜만에 백준에 들어가니 BackTracking이 있었다. 예전에도 있었나 모르겠지만 처음 본 것 같아서 풀어봤다. 근데 1번째 문제라 그런지 백트랙킹 문제라기보다는 DFS 같았다. 그래서 그냥 DFS로 풀었다. :) 두 가지 방법으로 풀었는데 첫 번째는 DFS로 풀었고 두 번째 풀이는 itertools 모듈을 이용해서 풀었다.. 더보기 이전 1 2 다음
