본문 바로가기

파이썬

 (17)
이코테 Chapter 09 최단 경로 - 전보 문제 어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메세지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메세지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내려면 도시 X -> Y로 가는 통로가 설치되어 있어야 한다. 어느 날 C라는 도시 C에서 위급 상황이 발생해 최대한 많은 도시로 전보를 보내야 한다. 메세지는 도시 C에서 출발해 각 도시 사이에 설치된 통로를 거쳐 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 정보로 주어졌을 때, 도시 C에서 보낸 메세지를 받게 되는 도시의 개수는 총 몇 개 이며 도시들이 모두 메세지를 받는 데까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성해라. 입력조건 첫째 줄에 도시의 개수 N, 통로의 개수..
이코테 Chapter 09 최단경로 - 미래 도시 문제 방문 판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있다. 공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하려 한다. 공중 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다. 또한 연결된 2개의 회사는 양방향으로 이동할 수 있다. 이 때, 다른회사로 이동하기 위한 시간은 정확히 1만큼의 시간이 소요된다. 또한 오늘 A씨는 소개팅에도 참여해야 한다. 소개팅의 상대는 K번 회사에 존재한다. 방문 판매원 A는 X번 회사에 물건을 팔러 가기 이전에 소개팅 상대의 회사에 가서 함께 커피를 마실 예정이다. 따라서..
알고리즘 정리 <최단 경로> 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 일반적으로 컴퓨터공학과 학부 수준에서 사용하는 최단 거리 알고리즘은 다익스트라 최단 경로알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 이렇게 3가지이다. 오늘은 이 중에서 다익스트라 최단 경로와 플로이드 워셜 알고리즘 유형을 다룰 것이다. 1. 다익스트라 최단 경로 알고리즘 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. - 기본 원리 - 1) 출발 노드를 설정한다. 2) 최단 거리 테이블을 초기화한다. 3) 방문하지 않은 노드중에서 최단 거리가 가장 짧은 노드를 선택한다. 4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하..
이코테 Chapter 08 - 개미 전사 문제 개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있ㄷ으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자. {1, 3, 1, 5} 이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을..
이코테 Chater 08 - 바닥 공사 문제 문제가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다. 이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000) 출력 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최솟값을 출력한다.첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다. 접근법 & 풀이 (의식의 흐름) 1. 일단 N이 1, 2, 3일때 경우의 수를 계산하고 그림으로 그려봄 2. 그리면서 어떻게 점화식을 유추해낼까 생각하다가 포기...ㅜㅜ [소스 코드] n = int..
알고리즘 정리 <다이나믹 프로그래밍> 다이나믹 프로그래밍 다이나믹 프로그래밍이란 다양한 알고리즘 문제를 푸는 상황에서 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘이다. 쉽게 말로 표현하자면 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘이다. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로는 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 1 1 2 3 5 8 13 21 34 55 89 이를 점화식으로 나타낼 수 있는데 an+2 = an+1 + an과 같이 표현할 수 있고 프로그래밍으로 표현하면 다음과 같다. [소스 코드] def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(..
이코테 Chapter 07 - 떡볶이 떡 만들기 문제 동빈이네 떡볶이 떡은 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 예를 들어, 높이가 19, 14, 10, 17 cm인 떡이 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 그리고 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm가 된다. 이 때 손님은 잘린 떡의 길이의 총 합인 6cm의 길이를 가져간다. 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오 입..
이코테 chapter 07 이진 탐색 - 부품 찾기 문제 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N=5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다. M=3 [5, 7, 9] 이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다. 입력 첫째 줄에 정수 N이 ..

티스토리툴바