본문 바로가기

분류 전체보기65

백준 1307:마방진 코드수정 마방진 에서 데코레이터 부분 및 타입 어노테이션, 독스트링등을 작성하였다. map에 들어가는 함수에 parameter가 두개가 필요한데, 하나만 쓰는 방법만 알고 여러개를 사용하는 방법을 몰라서 새로 공부해서 적용해 보았다. functools.partial에서 d를 고정으로 적용하였더니 작동했다. def iterize(function): def wrapper(x, d): if isinstance(x, list): return list(map(functools.partial(wrapper, d=d), x)) else: return function(x, d) return wrapper @iterize def magic_plus(x, d): return x + ((N // 2) ** 2) * d import .. 2022. 6. 19.
1307:마방진 풀기 3, 4일차 결론적으로 풀었다! 그런데 아직 해야할 문제가 많이 남아있다.. 일단 코드가 너무 길고, 성능이 엄청 딸리진 않는데, 개선의 부분이 있을 것 같다. 제대로 만드려면 모든 마방진을 구현할 수 있는 알고리즘이 필요한데 그게 의문이다. 현재로써는 단순히 n을 넣으면 n * n에 해당하는 마방진 단 하나가 나오는데, 4 * 4는 880개의 마방진이 존재하고, 5 * 5 는275,305,224개가 존재한다니 참으로 엄청날 수가 없다. 모든 경우의 수를 제공 할 순 없겠지만, 100개정도는 랜덤으로 제공해야 제대로 된 알고리즘이 될거라고 생각한다. 아니면 차원을 높여서 3d구조의 마방진을 만드는것도 나쁘지 않을 것 같다. 그리고 1일차에 소개한 논문의 strachey 알고리즘이 끝까지 소개되어 있지 않은 상태였다... 2022. 6. 16.
마방진: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.

티스토리툴바