전체 글

스도쿠 빈칸을 채우는 문제다. 0이 있는 곳에 1부터 9까지 대입하면서 정답이 되지 않는 수이면 다시 후퇴하는 식으로 코드를 짰다. 일단 0이 있는 곳의 인덱스를 zero에 넣어준다. 그런 뒤 zero에서 하나씩 빼서 정답이 될 수 있는지 확인해준다. isRight는 가로줄, 세로줄, 3X3 정사각형에 확인하려는 숫자가 있으면 False를 반환해준다. 만약 True가 반환이 되면 sudoku배열에 정답을 넣어주고 index를 증가시켜 재귀 함수를 호출하고 다음 zero의 값을 똑같이 비교해준다. ##함수 선언 부분 import sys def SDK(index): if index == len(zero): for i in range(9): for j in range(9): print("%d" % (sudok..

N X N 체스판에서 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. 밑의 그림은 이 문제를 풀 때 어떤 식으로 백트래킹하는 지를 보여준다. 이를 구현하기 위해 N개의 행 or 열과 우상향 대각선과 우하향 대각선을 구현해줄 배열이 필요하다. 각 행 or 열에는 한개의 퀸만 들어갈 수 있기 때문에, 행 or 열 배열은 하나만 선언해주면 된다. 또한 left와 right 배열은 각각 index와 col의 합과 index와 col의 차가 같다는 점을 이용한다. 만약 index와 col의 합이 같으면 같은 우상향 대각선 상에 위치한다는 뜻이므로 퀸이 올 수 없다. ##함수 선언 부분 def Queen(index): global cnt_Queen if index == N: cnt_Queen += 1 return ..

완전 탐색중의 한 방법인 백트래킹 알고리즘에 대한 문제이다. 백트래킹의 특징은 탐색과정 중에 정답이 될 수 없는 조건에 해당되면 가지치기(Pruning)하여 효율을 높일 수 있다는 점이다. DFS와 유사하지만 DFS는 불필요한 경로를 사전에 차단할 수 없기 때문에 경우의 수를 줄이지 못한다. 백트래킹 문제는 트리를 그리면서 풀면 이해가 더 잘 된다. 예제 입력 2의 경우에, 각 숫자(부모 노드)에는 자식노드 1,2,3,4가 있는데, 정답이 아닌 조건(자기 자신 ex) 1 1 , 2 2,..)이면 다시 되돌아가서 진행(가지치기)해준다. 1부터 N까지 돌면서 M만큼 출력을 해줘야 한다. 그러므로 M 만큼의 배열을 선언해서 하나씩 넣어준 뒤 출력하고 다시 빼주는 식으로 코드를 짜면 되겠다. s는 탐색하면서 a..

6이 3개이상 연속으로 들어가는 수를 찾는 문제다. 무한 루프 반복문을 돌려서 6이 3개이상 연속으로 들어가는 수를 cnt해주면서 구하려는 값이 되면 반복문을 탈출해주면 되겠다. i를 1부터 계속 증가시켜주고 i를 문자열로 바꾼 뒤 그 문자열에 666이 있으면 cnt를 1씩 더해주는 식으로 풀면 되겠다. 파이썬은 다양한 기본 함수가 있어서 find함수를 써서 쉽게 풀 수 있었다. 예전에 C로 풀었던 코드를 보면, 666부터 시작해서 1씩 증가시켜주면서 연산을 위한 End_safe에 값을 넣어주고 End_safe를 나눠주면서 cnt가 3이면(6이 연속 3번 나오면) right를 1씩 더해주는 식으로 코드를 짰다. #파이썬 코드 ##변수 선언 부분 cnt = 0 is_right = 0 ##메인 함수 부분 i..

체스판을 차례차례 대보면서 가장 적게 칠하는 경우를 구하는 문제이다. 모든 경우를 돌려봐야하는 브루트 포스 문제다. 일단 8X8 체스판을 만들어 놓고 이동하면서 칠해야하는 개수를 세줘야 하기 때문에, 처음이 검은색으로 시작하는 체스판과 처음이 흰색으로 시작하는 체스판 두 개를 만들어놔야 한다. 일단 나는 8X8크기의 2차원 배열을 각각 모두 'W' 혹은 'B'로 초기화해서 만들고, 2중 for문으로 체스판을 만들었다. 하나하나 옮겨가면서 비교하려면 총 몇번을 비교할지가 중요하다. 길이가 8이기 때문에, 행을 따라서 N-7만큼 반복하고 열을 따라서 M-7만큼 반복해주면 된다. 그리고 8X8만큼 반복을 해주면서 미리 만들어둔 판과 다른 색이면 cnt를 1씩 더해준다. 최솟값을 구하기 위해서 min_cnt에 ..

N = 3 에서 N = 4, 5정도까지 직접 옮겨보면 대충 어느 부분에서 재귀를 사용해야 할 지 감이 온다. N = k 일 때 k-1개의 블럭을 2번으로 옮긴 뒤 k번째(가장 큰 블럭) 블럭을 3번으로 옮기고 k-1개의 블럭들을 (3번에 k번째 블럭이 없다고 생각하고) 3번으로 옮겨주면 된다. k-1개의 블럭들을 옮기는 작업이 반복이 되기 때문에, 이 부분을 재귀함수를 이용해서 구현하면 되겠다. 주의해야 할 점은 k의 짝홀수 여부에 따라 옮기는 곳이 다르다는 점이다. 예를 들면, k = 4일 때는 3개를 2로 옮기는데, 3개를 2로 옮길 때는 2개를 2가 아닌 3으로 옮겨야 한다. 그러므로 단순히 Hanoi(N-1, 1, 2)로 쓰는 것이 아니라, 변수를 사용해서 재귀가 호출 될 때 목적지가 달라지게 해..

기본적인 패턴이 반복이 되는 별 찍기 문제이다. N = 3일때의 기본 형태가 N이 커짐에 따라 반복이 되는 형태이다. 기본 형태는 9개의 별에서 가운데 하나가 빠진 8개로 이루어져있다. NXN크기의 2차원 배열을 0으로 초기화한다. 0은 별이 찍히지 않음을 의미한다. 문양을 만들기 위해서는 기본 형태를 계속해서 찍어주면 되는데 그러기 위해서는 좌표가 필요했다. star함수에는 N과 시작 좌표인 0,0을 전달해 준다. 그리고 N을 3으로 나누어 주면서 다시 호출해주면서 별을 찍어주면 되겠다. N이 계속 호출되며 결국 1이 될 때 좌표에 별을 찍어주면 된다. 그렇다면 어떻게 좌표를 찍어야 할까? 생각보다 간단하다. 좌표는 N이 9라고 가정하면, (0,0) ~ (2,2), (0,3) ~ (2,5), (0,6)..

두 원의 중심 좌표와 반지름을 줄 때 교점의 개수를 구하는 문제이다. 겉보기에는 쉬운 문제이지만, 조건문을 짤 때 실수를 많이하는 문제이다. 조건문을 나눠줄 때 크게 두가지 경우로 나눈 뒤 세부적으로 들어가는 것이 좋을 것 같아서 두 원의 중심이 같을 때와 다를 때로 나누었다. 중심이 같을 때는 두 원이 일치하는 경우와 한 원이 다른 원을 포함할 때 두가지 경우가 있다. 중심이 다를 때는 밑의 사진의 경우 처럼 한 점에서 접하는 경우, 두 점에서 만나는 경우, 만나지 않는 경우로 나뉘는데, 한 점에서 접할 때는 (1) 각 반지름의 합이 좌표사이의 거리와 같을 때 (2) 각 반지름의 차가 좌표사이의 거리와 같을 때이다. 제곱근 계산의 번거로움 때문에 제곱을 한 값을 사용해서 비교를 해주면 되겠다. 두 점에..