문제 설명https://www.acmicpc.net/problem/9663 성능 요약메모리: 14468 KB, 시간: 6084 ms 분류백트래킹, 브루트포스 알고리즘 문제 설명N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N이 주어진다. (1 ≤ N 출력첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 문제 풀이보드가 이차원 배열이기 때문에 배열을 받을 때 2차원 배열로 해도 되지만, 1차원 배열로도 가능하다.각 원소의 index를 행이라고 생각하고, 원소값을 열이라고 생각하면 1차원 배열로도 가능하다.예를 들어, arr = [1, 3, 0..
백트래킹
백트래킹현재 상태에서 가능한 모든 선택지를 따라 들어가며 탐색하는 알고리즘 DFS와 헷갈릴 수도 있지만, 백트래킹 = DFS가 아니라 백트래킹 방법 중의 하나가 DFS인 것이다. DFS는 깊이 우선 탐색으로 모든 경우의 수를 다 탐색하지만,백트래킹은 조건에 맞지 않는다면 그 부분은 탐색하지 않고 탐색을 중지한 다음 그 이전으로 돌아가서 다른 경우를 탐색한다.연습 문제[백준`15649] N과 M (1)문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되..
문제 설명 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 성능 요약 메모리: 31120 KB, 시간: 388 ms 분류 백트래킹, 브루트포스 알고리즘, 구현 제출 일자 2024년 3월 28일 02:34:44 문제 설명 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번..
문제 설명 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 성능 요약 메모리: 31120 KB, 시간: 6464 ms 분류 백트래킹, 브루트포스 알고리즘 제출 일자 2024년 3월 19일 02:14:35 문제 설명 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱..
문제 설명 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 풀이 시간초과 때문에 힘들었던 문제.. 이게 파이썬의 한계인가 처음에는 count가 n일 때 route 배열에 있는 순서대로 cost를 더해주면서 값을 구하고, 총 비용과 minCost를 비교하는 방법으로 코드를 짰었는데 시간초과가 걸렸다 파라미터로 cost를 더하면서 넘겨주고 minCost와 파라미터로 넘어온 cost를 비교해서 더 낮..
