개발하는 시나몬

> 깊이/넓이 우선탐색(DFS, BFS) 활용 (DFS 편) 📖 문제 : 알파코드 철수와 영희는 서로의 비밀편지를 암호화해서 서로 주고받기로 했다. 그래서 서로 어떻게 암호화를 할 것인지 의논을 하고 있다. 영희 : 우리 알파벳 A에는 1로, B에는 2로 이렇게 해서 Z에는 26을 할당하여 번호로 보내기로 하자. 철수 : 정말 바보같은 생각이군!! 생각해 봐!! 만약 내가 “BEAN"을 너에게 보낸다면 그것을 암 호화하면 25114이잖아!! 그러면 이것을 다시 알파벳으로 복원할 때는 많은 방법이 존재하는 데 어떻게 할건데... 이것을 알파벳으로 바꾸면 BEAAD, YAAD, YAN, YKD 그리고 BEKD로 BEAN말고도 5가지나 더 있군. 당신은 위와 같은 영희의 방법으로 암호화된 코드가 주어지면 그것..

> 깊이/넓이 우선탐색(DFS, BFS) 활용 (DFS 편) 📖 문제 : 동전 분배하기 N개의 동전을 A, B, C 세명에게 나누어 주려고 합니다. 세 명에게 동전을 적절히 나누어 주어, 세 명이 받은 각각의 총액을 계산해, 총액이 가장 큰 사람과 가장 작은 사람의 차가 최소가 되도록 해보세요. 단 세 사람의 총액은 서로 달라야 합니다. 입력설명 첫째 줄에는 동전의 개수 N(3

> 깊이/넓이 우선탐색(DFS, BFS) 활용 (BFS 편) 📖 문제 : 섬나라 아일랜드 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대 각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요. 만약 위와 같다면 입력설명 첫 번째 줄에 자연수 N(3

> 깊이/넓이 우선탐색(DFS, BFS) 활용 (BFS 편) 📖 문제 : 미로의 최단거리 통로 7*7 격자판 미로를 탈출하는 최단경로의 경로수를 출력하는 프로그램을 작성하세요. 경로수는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다. 출발점은 격자의 (1, 1) 좌표이고, 탈 출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 도로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면 위와 같은 경로가 최단 경로이며 경로수는 12이다. 입력설명 7*7 격자판의 정보가 주어집니다. 출력설명 첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1를 출력한다. 입력예제 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 1..

> 깊이/넓이 우선탐색(DFS, BFS) 활용 (BFS 편) 📖 문제 : 사과나무 현수의 농장은 N*N 격자판으로 이루어져 있으며, 각 격자안에는 한 그루의 사과나무가 심어저 있다. N의 크기는 항상 홀수이다. 가을이 되어 사과를 수확해야 하는데 현수는 격자판안의 사 과를 수확할 때 다이아몬드 모양의 격자판만 수확하고 나머지 격자안의 사과는 새들을 위해서 남겨놓는다. 만약 N이 5이면 아래 그림과 같이 진한 부분의 사과를 수확한다. 현수과 수확하는 사과의 총 개수를 출력하세요. 입력설명 첫 줄에 자연수 N(홀수)이 주어진다.(3

> 깊이/넓이 우선탐색(DFS, BFS) 활용 (BFS 편) BFS는 레벨 탐색 ! => 큐 사용 📖 문제 : 송아지 찾기 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아 지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성 하세요. 입력설명 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000 까지이다. 출력설명 점프의 최소횟수를 구한다. 입력예제 1 5 14 출력예제 ..

> 깊이/넓이 우선탐색(DFS, BFS) 활용 (DFS 편) 📖 문제 : 동전 바꿔주기(DFS) 명보네 동네 가게의 현금 출납기에는 k가지 동전이 각각n1, n2, ... , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다.예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은4가지 방법으로 교환할 수 있다. 20 = 10×2 20 = 10×1+5×2 20 = 10×1+5×1+1×5 20 = 5×3+1×5 입력으로 지폐의 금액 T, 동전의 가지수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1,2,...,k) 지폐를 동전으로 교환하..

> 깊이/넓이 우선탐색(DFS, BFS) 활용 (DFS 편) 📖 문제 : 양팔 저울 무게가 서로 다른 K개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0 으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 물의 무게를 그릇에 담고자 한다. 주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고, 각 추의 무게가 {1, 2, 6}이 면, S=9이고, 양팔저울을 한 번만 이용하여 1부터 S사이에 대응되는 모든 무게의 물을 다음과 같이 그릇에 담을 수 있다. X는 그릇에 담는 물의 무게이고, ⎕은 그릇을 나타낸다. 만약 추의 무게가 {1, 5, 7}이면 S=13이고, 그릇에 담을 수 있는 물의 무게는 {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}이고, ..

> 깊이/넓이 우선탐색(DFS, BFS) 활용 (DFS 편) 📖 문제 : 휴가 카운셀러로 일하고 있는 현수는 오늘부터 N+1일째 되는 날 휴가를 가기 위해서, 남은 N일 동안 최대한 많은 상담을 해서 휴가비를 넉넉히 만들어 휴가를 떠나려 한다. 현수가 다니는 회사에 하루에 하나씩 서로 다른 사람의 상담이 예약되어 있다. 각각의 상담은 상담을 완료하는데 걸리는 날 수 T와 상담을 했을 때 받을 수 있는 금액 P로 이루어져 있다. 만약 N = 7이고, 아래와 같이 예약이 잡혔있다면 1일에 잡혀있는 상담은 총 4일이 걸리며, 상담했을 때 받을 수 있는 금액은 20이다. 만약 1일 에 예약된 상담을 하면 4일까지는 상담을 할 수가 없다.하나의 상담이 하루를 넘어가는 경우가 많기 때문에 현수는 예약된 모든 상담을..

> 깊이/넓이 우선탐색(DFS, BFS) 활용 (DFS 편) 📖 문제 : 최대점수 구하기 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.) 입력설명 첫 번째 줄에 문제의 개수N(1