본문 바로가기

전체 글219

Algorithm - 미로 탐색(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [미로 탐색(DFS)] 7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하시오. 격자판의 움직임은 상하좌우로만 움직이며 미로가 아래와 같다면 위의 지도의 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다. 참고로, 격자판의 1은 벽이고 0은 통로이다. *입력 설명 7*7 격자판의 정보가 주어진다. *출력 설명 첫 번째 줄에 경로의 가지수를 출력한다. 풀이(Python) 답안 import sys sys.stdin = open('AA/input_65.txt', 'rt') dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] .. 2022. 1. 11.
Algorithm - 미로의 최단거리 통로(BFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [미로의 최단거리 통로(BFS)] 7*7 격자판 미로를 탈출하는 최단경로의 수를 출력하는 프로그램을 작성하시오. 단, 경로의 수는 출발점에서 도착점까지 가는데 이동한 횟수를 의미하며 출발점은 격자의 (1, 1) 좌표이고 탈출 도착점은 (7, 7) 좌표이다. 또한, 격자판의 1은 벽이고 0은 도로이다. 참고로, 격자판의 움직임은 상하좌우로만 움직이며 미로가 아래와 같다면 다음의 경로가 최단경로(12)이다. *입력 설명 7*7 격자판의 정보가 주어진다. *출력 설명 첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 단, 도착할 수 없는 경우에는 -1을 출력한다. 풀.. 2022. 1. 9.
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.

티스토리툴바