제레미 베러미의 타임라인

문제스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.유사문제백준 25870번은 문제 이름까지 똑같은 문제이며, 같은 소스코드 제출로도 통과가 가능하다.해설백트래킹을 활용해 풀 수 있는 대표적인 문제다.생각의 흐름만..

문제 서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.  그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. 에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.   정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수..

체스판에서 대각선 경로를 구할 때 어떻게 구현을 해야 할까?간단하게 보일 수도 있지만 막무가내로 구현하면 코드가 상당히 더러워질 수 있다. 백준 N-queen(9963), 비숍(1799) 문제에서 유용하게 활용할 수 있는 대각선 경로 판정 팁을 공유해본다.# 보드판 사이즈SIZE_X = 8SIZE_Y = 8def Diagonal(x, y, board): for i in range(SIZE_Y): for j in range(SIZE_X): if abs(i-y) == abs(j-x): board[i][j] = 1board = [[0]*SIZE_X for _ in range(SIZE_Y)]Diagonal(3, 3, board) # x, y 위치..

문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.해설 다이나믹 프로그래밍을 활용해 풀 수 있는 문제다. '연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합' 을 구해야 한다. 따라서 DP[i] 는 'i번째까지의 수열에서 구할 수 있는 최대 연속합' 을 저장하게끔 만들어야 한다. 연속합이 만들어지는 경우는 다음 세 가지 경우이다.이전 최장 연속합과 연결자신 바로 앞 원소(i-1)와 연결자신 그 자체아래..

문제n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.해설얼핏 보면 그리디를 활용하는 것처럼 보일수도 있지만 다이나믹 프로그래밍을 활용한 문제이다. 상위 가치의 동전이 하위 가치의 동전들의 합으로 구성될 수 있기 떄문이다. (1원, 5원이 있을 경우 1원x5개로 구성 가능) 동전들을 조합해 k원의 가치를 만드는 경우의 수를 모두 구해야 한다. 따라서 DP[n]은 'n원의 가치를 만들 수 있는 모든 경우의 수'가 된다. 동전 DP 문제는 표를 그려보면 쉽게 이해할 수 있다. 아래는 n = ..

문제크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 24 1 3 5 6주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (x, y) 이다. 가장 처음에 주사위에는 모든 면에 0이 적혀져 있다.지도의 각 칸에는 정수가 하나씩 쓰여져 있다. 주사위를 굴렸을 때, 이동한 칸에 쓰여 있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다. 0이 아닌 경우에는 칸에 쓰여 있는 수가 주사위의 바닥면으로 복사되며, ..