Algorithm

[백준 / Python 파이썬] 2670번 - 연속부분최대곱

[Silver IV] 연속부분최대곱 - 2670 문제 링크 분류 브루트포스 알고리즘, 다이나믹 프로그래밍 문제 설명 N개의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면, 색칠된 부분의 곱이 최대가 되며, 그 값은 1.638이다. 입력 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 같고, 9.9보다 작거나 같다. 출력 계산된 최댓값을 소수점 이하 넷째 자리에서 반올림하여 소수점 이하 셋째 자리까지 출력한다. import sy..

[백준 / Python 파이썬] 15489번 - 파스칼 삼각형

[Silver IV] 파스칼 삼각형 - 15489 문제 링크 분류 조합론, 다이나믹 프로그래밍, 수학 문제 설명 파스칼 삼각형은 아래와 같은 모양으로 이루어져 있다. 양 끝을 제외한 각 수는 자신의 바로 왼쪽 위의 수와 바로 오른쪽 위의 수의 합으로 되어있다. 이때 R번째 줄, C번째 수를 위 꼭짓점으로 하는 한 변이 포함하는 수의 개수가 W인 정삼각형과 그 내부를 생각하자. 정삼각형의 변과 그 내부에 있는 수들의 합을 구하고 싶다. 예를 들면, 3번 째 줄, 1번 째 수를 꼭짓점으로 하고 한 변이 포함하는 수의 개수가 4인 정삼각형과 그 내부에 있는 수의 합은 1+(1+3)+(1+4+6)+(1+5+10+10) = 42 이다. 주어진 R, C, W에 대해서 그에 해당하는 합을 구하는 프로그램을 작성하여라..

[백준 / Python 파이썬] 13699번 - 점화식

[Silver IV] 점화식 - 13699 문제 링크 분류 다이나믹 프로그래밍 문제 설명 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n ≤ 35에 대하여 t(n)을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 n (0 ≤ n ≤ 35)이 주어진다. 출력 첫째 줄에 t(n)을 출력한다. N = int(input()) DP = [1, 1] for i in range(2, N + 1): answer = 0 for ..

[백준 / Python 파이썬] 25601번 - 자바의 형변환

[Silver I] 자바의 형변환 - 25601 문제 링크 분류 자료 구조, 그래프 이론, 그래프 탐색, 해시를 사용한 집합과 맵, 트리 문제 설명 자바의 클래스끼리는 상속을 통해 자신의 기능 일부를 다른 클래스에게 이식할 수 있다. 여기서 상속을 받은 클래스는 자식 클래스, 상속을 한 클래스는 부모 클래스가 된다. 클래스를 이용해서 만든 객체는 다른 클래스로 형태를 변환할 수 있는데, 이를 형변환(Casting)이라고 한다. 만약 자식 클래스에서 부모 클래스로 변환한다면 업캐스팅(Upcasting), 부모 클래스에서 자식 클래스로 변환한다면 다운캐스팅(Downcasting) 이라고 부른다. 즉, 자식 클래스와 부모 클래스 관계에 놓여있다면 형변환이 가능하다. Downcasting의 경우 런타임에 문제를..

[백준 / Python 파이썬] 2257번 - 화학식량

[Silver II] 화학식량 - 2257 문제 링크 분류 자료 구조, 스택, 문자열 문제 설명 우리가 널리 사용하는 H2O(물), CH3COOH(아세트산)과 같은 화학식은 알파벳과 숫자, 그리고 괄호로 구성된다. 먼저 알파벳은 원자를 나타내는 것으로 H는 수소(Hydrogen), C는 탄소(Carbon), O는 산소(Oxygen) 원자를 뜻한다. 또한 원자를 나타내는 알파벳 뒤에 따르는 숫자는 그 원자가 몇 개 포함되어 있는지를 뜻한다. 따라서 COOHHH 분자는 CO2H3로 나타낼 수 있다. 이 문제에서, 숫자는 항상 2 이상 9 이하로만 입력으로 주어진다. 따라서 CO23과 같이 숫자가 두자리인 경우는 없다. 물의 화학식을 보고 물은 두 개의 수소 원자와 한 개의 산소 원자로 이루어졌음을 알 수 있..

[백준 / Python 파이썬] 21735번 - 눈덩이 굴리기

[Silver III] 눈덩이 굴리기 - 21735 문제 링크 분류 백트래킹, 브루트포스 알고리즘 문제 설명 눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다. 앞마당의 길이는 N이고 위치 11부터 위치 N 까지만 눈이 쌓여있다. 위치 i에 눈이 ai만큼 쌓여있다. 대회 규칙은 해당 앞마당에서 M초 동안 눈덩이를 굴려 눈사람을 만드는 것이다. 눈덩이의 시작 크기는 11이다. 눈덩이의 시작 위치는 00이다. 가장 큰 눈사람을 만들고 싶던 수수는 눈덩이를 굴리는 법을 연구했다. 눈덩이를 굴리는 방법에는 두 가지가 있다. 눈덩이를 굴리거나 던질 때 1초가 소모된다. 눈덩이를 현재 위치 +1칸으로 굴린다. 현재 칸의 위치를 i라고 하면 눈덩이의 크기는 ai+1+1 만큼 늘어난다. 눈덩이를 현..

[백준 / Python 파이썬] 15900번 - 나무 탈출

[Silver I] 나무 탈출 - 15900 문제 링크 분류 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리 문제 설명 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게임이다. '나무 탈출' 은 N개의 정점이 있는 트리 모양으로 생긴 게임판과 몇 개의 게임말로 이루어진다. 트리의 각 정점에는 1번부터 N번까지 번호가 붙어있다. 1번 정점은 '루트 노드' 라고 불리며, 이 루트 노드를 중심으로 정점 간에 부모-자식 관계가 만들어진다. 자식이 없는 노드는 '리프 노드' 라고 불린다. 이 게임은 두 사람이 번갈아 가면서 게임판에 놓여있는 게임말을 움직이는 게임이다. ..

[백준 / Python 파이썬] 15805번 - 트리 나라 관광 가이드

[Silver I] 트리 나라 관광 가이드 - 15805 문제 링크 분류 자료 구조, 그래프 이론, 그래프 탐색, 트리 문제 설명 윤호는 K개의 도시들이 트리 형태로 연결되어 있는 트리 나라의 관광 가이드이다. 윤호가 새롭게 맡게 된 패키지는 트리 나라의 루트 도시에서 시작해서 모든 도시를 순회하고 오는 상품이다. 이 상품은 컨셉만 결정된 상태이기 때문에 어떤 도시들을 방문할 지는 윤호가 결정할 수 있다. 윤호는 게임 폐인이기 때문에 빠르게 일을 끝내고 보틀 그라운드를 하러 가고 싶다. 그래서 방문할 도시를 최소한으로 하는 패키지 상품을 짜서 투어를 진행해왔다. 위와 같은 트리 나라가 있다고 해보자. 이 트리 나라의 경우에는 루트 도시가 0번이다. 따라서 위와 같은 트리 나라에서 윤호가 패키지를 짤 경우..