본문 바로가기

파이썬14

마방진:1307 2일차. 오늘도 마방진문제에 대하여서 풀고 있다. 그전에 무작정 논문에 나온 알고리즘을 분석하여 적용하려 했는데, 구현이 꽤나 까다로운 것 같아 방향을 틀었다. 일단 마방진을 구현하기 위해서 시간 분석도는 차차하고, n이 홀수일때, O(N^2)안에 수행되는 de la Loubère의 알고리즘을 이용하기로 했다. def make_odd_magicsquare(n): #n^2크기 배열 생성 arr = [[0 for _ in range(n)] for _ in range(n)] #초기 인덱스 첫번째 행의 가운데 위치 now를 설정 now = [n // 2, 0] #주어진 규칙으로 숫자를 n^2번 배정한다. for i in range(1, n**2 + 1): x, y = now arr[y][x] = i new_x = x +.. 2022. 6. 14.
1307:마방진 풀기 1일차. 먼저 문제에 대한 링크이다. https://www.acmicpc.net/problem/1307 1307번: 마방진 마방진이란 N*N의 격자의 각 칸에 1부터 N*N까지의 정수를 정확히 하나씩 채웠을 때, 모든 가로줄, 세로줄, 대각선의 합이 같은 배치를 말한다. 예를 들면, 다음은 3*3 마방진 중 하나이다. 가로줄, www.acmicpc.net 문제와의 첫만남 말그대로 마방진을 구현하는 심플(?..ㅎㅎ)한 문제이다. maximum값 은 300으로 n의 제곱 크기의 마방진을 구현해야 하므로, 시간복잡도 nlogn안에 해결해야 할 것 같다 내가 알고있는 기초지식은 문제에서 설명해준 것처럼, N*N의 격자의 각 칸에 1부터 N*N까지의 정수를 정확히 하나씩 채웠을 때, 모든 가로줄, 세로줄, 대각선의 합이 .. 2022. 6. 13.

티스토리툴바