시나위

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 요약 스도쿠 정답을 찾으면된다. 행과 열, 3X3 안에 1~9가 중복없이 들어가야한다. 접근 1. Brute-force 숫자를 넣어야하는 자리수는 최대 81개이고 1부터 9까지 모든 값을 넣어서 확인하려면 981 이 된다. O(232) 는 대충 42초 정도 걸리는데 이 값보다 크므로 이 방법으로 풀수 없다. 물론 0인 위치에서만 확인하면 되지만 찾아야하는 위치가 9개 이상이면 3초가 넘으므로 입력값을 알지 못하면 풀수 없다. 2. Backtracking 백..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 손님들이 주문한 단품 메뉴로 코스요리(조합)를 만든다. 코스 요리는 단품 두개 이 상으로 이루어져있다. 코스 요리의 길이(단품 메뉴의 개수)를 보고 그 중에 가장 많이 선택된 조합을 반환한다. 접근 모든 손님들이 주문한 단품 메뉴로 모든 조합을 만들어야한다. 조합을 만들 때 반복문, 라이브러리, 백트래킹으로 구현할수 있다. 1. 조합만들기 - 반복문 반복문을 중첩해서 사용하면 쉽게 조합을 만들수 있다. 예를 들면 ABCDE에서 3개의 원소를 가지는 조합을 만들기 위해선 다음과 같이 짜면 된다. st..

https://www.acmicpc.net/problem/10597 10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net 백트래킹 문제이다. 한글자, 두글자씩 읽어서 확인하고 마지막까지 순회했을 때 (포커의 스트레이트 같이) 모든 값이 이어지는지 확인한다. # import sys; input = sys.stdin.readline def backtrack(ind, limit): global s, stack if ind == limit: max_v = max(stack) for i in range(1..

https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹 연습을 위한 쉬운 문제 # import sys;input = sys.stdin.readline def backtrack(ind=0, cnt=0): global n, m, nums, ans_set, visit if cnt == m: tmp = tuple([nums[i] for i, v in enumerate(visit) if v]) if tmp not in ans_set: ans_..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 백트래킹과 그래프 탐색 알고리즘을 모두 사용해야하는 문제이다 3개의 벽을 설치할 땐 백트래킹을 설치한 이후 바이러스가 전파되는 것은 그래프 탐색(BFS를 사용했다)을 하면된다. 바이러스 전파가 끝나면 이차원 배열에서 안전한 구역을 찾으면 된다. # import sys; input = sys.stdin.readline from collections import deque def bfs(): global N, M..

https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹이 너무 부족해서 쉬운문제부터 다시 시작... def backtrack(ind, limit, prev): global nums, answer, visit if ind == limit: tmp = tuple([nums[i] for i, v in enumerate(visit) if v]) if tmp not in answer: print(*tmp) answer.add(tmp) return ..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 전형적인 백트래킹 문제이다. import sys; input = sys.stdin.readline def is_correct(value, r, c): global sudoku, find_list # 1 check row for i in range(9): if value == sudoku[r][i]: return False # 2 check col for i in range(9): if val..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 시뮬레이션과 백트래킹으로 모든 조합을 만들면 된다. i번째가 i번째로 가는 시뮬레이션 부분은 어렵지 않지만 백트래킹으로 조합을 만들때 중복되는 거 없이 수를 최소한으로 줄여야 통과할수 있었다. #include #include using namespace std; int N, M, H; int ladder[32][12]; int answer; bool check() { int i, r, c; fo..

https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹이 조금 부족한거 같아서 푼 문제 2 # N & M (8) import sys; input = sys.stdin.readline def backtrack(lst=None, prev=0): global N, M, nums if lst is None: lst = [] if len(lst) == M: print(*[nums[i] for i in lst]) return for i in r..

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹이 조금 부족한거 같아서 푼 문제 # N & M (5) import sys; input = sys.stdin.readline def backtrack(ind, limit, size, nums, visit, lst=None): if lst is None: lst = [] if ind == limit: print(*[nums[i] for i in lst]) return for i in..