본문 바로가기

알고리즘90

Algorithm - 사과나무(BFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [사과나무(BFS)] 현수의 농장은 N*N 격자판으로 이루어져 있으며, 각 격자안에는 한 그루의 사과나무가 심어져있다. (단, N은 항상 홀수) 가을이 되어 사과를 수확해야 하는데, 현수는 격자판 안의 사과를 수확할 때 다이아몬드 모양의 격자판만 수확하고 나머지 격자 안의 사과는 새들을 위해서 남겨놓는다. 만약, N이 5이면 아래 그림과 같이 진한 부분의 사과를 수확한다. 현수가 수확하는 사과의 총 개수를 출력하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에 자연수 N(3 ≤ N ≤ 20, 홀수)이 주어진다. 두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연.. 2022. 1. 8.
Algorithm - 송아지 찾기(BFS : Breadth First Search) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [송아지 찾기(BFS)] 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 직선상의 좌표점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 현수는 스카이 콩콩을 타고 이동하는데, 한 번의 점프로 앞으로 1칸 or 뒤로 1칸 or 앞으로 5칸을 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지를 구하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표점은 1부터 10,000까지이다. *출력 .. 2022. 1. 7.
Algorithm - 알파코드(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [알파코드(DFS)] 철수와 영희는 서로의 비밀편지를 암호화해서 서로 주고받기로 했다. 그래서 서로 어떻게 암호화를 할 것인지 의논을 하고 있다. 영희 : 우리 알파벳 A에는 1로, B에는 2로 해서 Z에는 26을 할당하고 번호로 보내기로 하자. 철수 : 생각해봐!! 만약 내가 "BEAN"을 너에게 보낸다면 그것을 암호화하면 "25114"이잖아? 그러면 이것을 다시 알파벳으로 복원할 때는 많은 경우의 수가 존재하게 돼.. 실제로 "25114"을 알파벳으로 바꾸면 "BEAAD", "YAAD", "YAN", "YKD", "BEKD"로 "BEAN" 말고도 5가지의 경우.. 2022. 1. 5.
Algorithm - 동전 분배하기(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [동전 분배하기(DFS)] N개의 동전을 A, B, C 세명에게 나누어 주려고 한다. 세 명에게 동전을 적절히 나누어 주어, 세 명이 받은 각각의 총액을 계산한 후 총액이 가장 큰 사람과 가장 작은 사람의 차가 최소가 되도록 만들고자 한다. (단, 세 사람의 총액은 서로 달라야 함) 위의 조건을 모두 만족하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에는 동전의 개수 N(3 ≤ N ≤ 12)이 주어진다. 그 다음 줄부터 각 동전의 금액이 주어진다. *출력 설명 총액이 가장 큰 사람과 가장 작은 사람의 최소차를 출력한다. 풀이(Python) 답안 import .. 2022. 1. 4.
Algorithm - 동전 바꿔주기(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [동전 바꿔주기(DFS)] 명보네 동네 가게의 현금 출납기에는 k가지의 동전이 각각 n(1), n(2), ... , n(k)개씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔주려고 한다. 이 때, 동전 교환방법은 여러가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있으면 20원 짜리 지폐를 다음과 같이 4가지 방법으로 교환할 수 있다. 입력으로 지폐의 금액(T), 동전의 가지수(k), 각 동전 하나의 금액(p)와 개수(n)이 주어질 때, 지폐를 동전으로 교환하는 방법의 수를 출력하는 프로그램.. 2022. 1. 3.
Algorithm - 양팔저울(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [양팔저울(DFS)] 무게가 서로 다른 K개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0이다. 양팔저울을 한 번만 이용하여 원하는 물의 무게를 그릇에 담고자 한다. 주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고 각 추의 무게가 {1, 2, 6}이면 S=9이고 양팔저울을 한 번만 이용하여 1부터 S사이에 대응되는 모든 무게의 물을 다음과 같이 그릇에 담을 수 있다. 참고로, X는 그릇에 담는 물의 무게이고 □는 그릇을 나타낸다. 만약, 추의 무게가 {1, 5, 7}이면 S=13이고 그릇에 담을 수 있는 물의 무게는 {.. 2022. 1. 3.

티스토리툴바