본문 바로가기

Algorithm8

[Problem Solving] 왕실의 나이트 문제 : 왕실의 나이트 행복 왕국의 왕실 정원은 체스판과 같은 8 x 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 말을 타고 있으므로 이동을 할 때는 L자 형태로만 이동가능하고 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다. 1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 2. 수직으로 두 칸 이동한 두에 수평으로 한 칸 이동하기 이처럼 8 x 8 좌표 평명상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 구하여라. 행 위치의 표현은 1부터 8로 표한하고, 열 위치를 표현할 때는 a부터 h로 표현한다. 첫째 줄에 8 x 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문.. 2021. 2. 1.
[Problem Solving] 상하좌우 이번에는 구현에 대한 알고리즘을 공부하였다. 구현 알고리즘 "상하좌우"에 들어가기에 앞서 간단한 사방 탐색으로 시작해볼까 한다. 아래의 코드는 순서대로 우, 상, 좌, 하 순서대로 1, 2, 3, 4를 차례대로 채우는 예제이다. 특히 2차원 배열을 초기화할 때는 반드시 리스트 컴프리 헨션을 이용해 주어야 한다. 그렇지 않으면 데이터를 넣거나 하는 등의 과정에서 문제가 생길 수 있다. n = 3 m = 3 array = [[0] * m for _ in range(n)] # 리스트 컴프리 헨션을 이용한 2차원 배열 초기화 # 방향 벡터 이용 dx = [0, -1, 0, 1] # 행, row dy = [1, 0, -1, 0] # 열, column x, y = 1, 1 # 3 X 3 크기의 2차원 배열에서 1,.. 2021. 2. 1.
[Problem Solving] 큰 수의 법칙 문제 : 큰 수의 법칙 첫째 줄에 N(2 2021. 1. 18.
[Problem Solving] 거스름돈 그리디 알고리즘 : 단순하지만 강력한 문제 해결 방법. 다른 말로 탐욕법이라고도 함. 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘. 탐욕적? '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 매 순간 가장 좋아 보이는 것을 선택하되, 현재의 선택이 나중에 미칠 영향에 대해서 고려하지 않는다. 문제 : 거스름돈 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재. 거슬러 줘야 할 돈이 N원일 때 최소 동전의 개수? (단, N은 항상 10의 배수) n = int(input()) # 거스름돈 n을 정수로 입력받는다. count = 0 # 최소 동전의 개수 coin_types = [500, 100, 50, 10] # 큰.. 2021. 1. 18.

티스토리툴바