제레미 베러미의 타임라인

문제세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다해설  흔한 유형의 그래프 문제로, 이미 방문한 알파벳을 지나지 않으면서 갈 수 있는 최장거리를 구하는 것이 목표다. 예를 들어, 예제 입력 3의 경우는 다음 그림과 같이 10칸을 이동할 수 있..

문제스도쿠는 매우 간단한 숫자 퍼즐이다. 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이 아닌 경우에는 칸에 쓰여 있는 수가 주사위의 바닥면으로 복사되며, ..

개인에 의해 작성된 답입니다. 오류 발견시 댓글을 통해 알려주세요. + 과제는 스스로 하기! 1. 이름을 물어보고 입력받은 이름을 사용하여 아래의 예시와 같이 대답하며 인사해주는 프로그램을 작성하시오. name = input("당신의 이름은 무엇인가요? ") print("하이", name, "씨 만나서 반가워요") 2. 고향을 물어보고 입력받은 고향에 대하여 아래의 예시와 같이 답해주는 프로글매을 작성하시오. hometown = input("당신의 고향은 어디인가요? ") print("당신은 아름다운", hometown, "에서 왔군요.") 3. 좋아하는 숫자를 물어 본 후 좋아하는 숫자에 10을 더한 값을 말해주는 프로그램을 작성하시오. number = int(input("당신이 좋아하는 숫자는? ")..

개인에 의해 작성된 답입니다. 오류 발견시 댓글을 통해 알려주세요. + 과제는 스스로 하기! 1. 2020이라는 정수가 메모리에 2진수로 어떻게 표현되는지 확인해보자. 해당 숫자를 변수에 입력한 후 bin 함수를 활용하면 된다 정수 = 2020 print(bin(정수)) 2. 중국 여행에 앞서 우리나라 돈을 중국 돈(위안)으로 환전하고자 한다. 1위안은 165원이라고 할 떄, 150만원을 위안으로 환전한 결과를 구해보자. 가진돈 = 1500000 위안환율 = 165 가진돈_위안 = 가진돈 / 위안환율 print("환전결과 :", 가진돈_위안) 3. 지름이 30 cm인 피자를 1/4 등분하였다. 이 조각 피자의 넓이를 구해보자. 지름 = 30 반지름 = 지름 / 2 원넓이 = 3.14 * 반지름 * 반지름..

개인에 의해 작성된 답입니다. 오류 발견시 댓글을 통해 알려주세요. + 과제는 스스로 하기! 1. 쉘 모드에서 intro라는 변수에 자신을 소개하는 내용을 2줄 이상 입력한 후 화면에 출력하시오. >>> print("안녕하세요, 제 이름은 제러미 베러미라고 합니다\n만나서 반갑습니다.") 2. 코드 편집기 모드에서 자신에 대한 소개(이름, 고향, 취미)를 1초 간격으로 화면에 출력되도록 하는 프로그램을 만드시오. import time print("안녕하세요, 제 이름은 제러미 베러미입니다.") time.sleep(1) print("제 고향은 서울입니다.") time.sleep(1) print("취미는 프로그래밍입니다.") time.sleep(1) 3. 2번 문제에서 작성한 소스코드를 1초 간격으로 '삑'..