본문 바로가기

Problem Solving3

[백준] 9663번: N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹 문제이다. 어렵지 않아 보이지만 제한 시간을 맞추기가 너무나 힘들었다. n = int(input()) grid = [[0]*n for _ in range(n)] def attackable(r, c): for i in range(r): for j in range(n): if grid[i][j] == 1: if i == r or j == c or (r+c) == (i+j) or (r-c) == (i-j): .. 2022. 6. 30.
[백준] 2447번: 별찍기 - 10 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 풀이 작은 패턴들이 더 큰 패턴을 이루는, 전형적인 재귀 문제이다. N = int(input()) grid = [[' ']*N for _ in range(N)] def recursion(n, x, y): if n == 1: return d = int(n/3) for i in range(3): for j in range(3): if not(i==1 and j==1): re.. 2022. 4. 2.
[백준] 1238번: 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 출발지와 목적지 사이의 최단 왕복 시간을 구하는 전형적인 최단 경로 문제이다. 다만 한 정점에서만 출발하는 것이 아니라, N개의 정점 각각에서 출발했을 때의 최단 경로를 구하고, 그중에서 최대 값을 뽑아야 한다. 처음엔 문제를 대충 읽고, 단지 모든 정점에서의 최단 경로를 구해야한다는점 만을 고려해 플로이드 워셜 알고리즘으로 접근했다. import sys N, .. 2022. 3. 26.

티스토리툴바