본문 바로가기

전체 글219

Algorithm - 사다리 타기(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [사다리 타기(DFS)] 현수와 친구들은 과자를 사먹기 위해 사다리 타기를 한다. 사다리 표현은 2차원 리스트에 0과 1로 채워지며, 0은 평면을 의미하고 1은 사다리를 의미한다. 현수는 특정 도착지점으로 도착하기 위해 몇 번째 열에서 출발해야 하는지를 알고 싶어한다. 여기서 특정 도착지점은 2로 표기된다. 위의 조건을 모두 만족하는 프로그램을 작성하시오. 참고로, 사다리의 지도가 10 * 10이면 아래와 같이 2차원 리스트로 표현된다. 위의 조건들을 고려하여, 특정 도착지점인 2에 도달하려면 7번째 열에서 출발하면 된다. 단, 사다리 타기의 특성 상 네 방향(상.. 2022. 1. 18.
Algorithm - 토마토(BFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [토마토(BFS)] 현수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤의 네 방향에 있는 토마토를 의미한다. 참고로, 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며 토마토가 혼자 저절로 익는 .. 2022. 1. 17.
Algorithm - 안전영역(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [안전영역(DFS)] 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음 해당 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어지는지를 조사하려고 한다. 이 때, 문제를 단순화하기 위해 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며, 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 이제 N=5인 지역에 많은 비가 .. 2022. 1. 14.
Algorithm - 섬나라 아일랜드(BFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [섬나라 아일랜드(BFS)] 섬나라 아일랜드의 지도가 격자판의 정보로 주어진다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다이다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에 자연수 N(3 ≤ N ≤ 20)이 주어진다. 두 번째 줄부터 격자판 정보가 주어진다. *출력 설명 첫 번째 줄에 섬의 개수를 출력한다. 풀이(Python) 답안 import sys from collections import deque sys.stdin = open('AA/input_68.txt', 'rt') dx.. 2022. 1. 13.
Algorithm - 단지 번호 붙이기(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [단지 번호 붙이기(DFS)] 그림 1과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 참고로, 대각선상에 집이 있는 경우는 연결된 것이 아니다. 그림2는 그림1을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에는 지.. 2022. 1. 12.
Algorithm - 등산 경로(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [등산 경로(DFS)] 등산을 매우 좋아하는 철수는 마을에 있는 뒷산에 등산경로를 만들 계획을 세우고 있다. 마을 뒷산의 형태를 나타낸 지도는 N*N 구역으로 나뉘어져 있으며, 각 구역에는 높이가 함께 나타나 있다. N=5이면, 마을 뒷산의 형태를 나타낸 지도는 아래와 같이 표현된다. 어떤 구역에서 다른 구역으로 등산을 할 때에는 그 구역의 위, 아래, 왼쪽, 오른쪽 중 더 높은 구역으로만 이동할 수 있다. 등산로의 출발지는 전체 영역에서 가장 낮은 곳이고, 목적지는 가장 높은 곳이다. (단, 출발지와 목적지는 유일함) 지도가 주어지면 출발지에서 도착지로 갈 수 .. 2022. 1. 11.

티스토리툴바