[Python] 백준 알고리즘 온라인 저지 17298 오큰수 출처 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 알고리즘 분류 자료 구조 스택 문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]..
[Python] 백준 알고리즘 온라인 저지 1699 제곱수의 합 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 어떠한 수 N이 합하여 N이 될 때 가장 큰 제곱수 자신보다 작은 수를 하나씩 늘리며 제곱해보면 찾을 수 있다. 알고리즘 분류 다이내믹 프로그래밍 소스코드 import sys input = sys.stdin.readline n = int(input()) dp = [k for k in range(..
[Python] 백준 알고리즘 온라인 저지 1912 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 연속되는 수의 합이 가장 큰 값을 구하는 문제로 더해져 온 값과 비교하는 코드를 작성해야 한다. 알고리즘 분류 다이내믹 프로그래밍 소스코드 import sys input = sys.stdin.readline n = int(input()) nums = list(map(int, input().split())) dp = [nums[0]] for i in ..
[Python] 백준 알고리즘 온라인 저지 13305 주유소 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 한 방향(왼쪽에서 오른쪽)으로 도시를 이동해야 하므로 리터 당 가격을 비교하며 이동하는 방법으로 풀이했다. 요즘 기름 값이 비싸긴 하다... 알고리즘 분류 그리디 알고리즘 소스코드 import sys input = sys.stdin.readline n = int(input()) dist = list(map(int, inpu..
[Python] 백준 알고리즘 온라인 저지 1541 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 괄호를 쳐서 최소가 되는 값을 구하기 위해서는 마이너스되는 값이 클수록 값은 작아지므로 -를 기준으로 문제를 풀이했다. 알고리즘 분류 수학 문자열 그리디 알고리즘 파싱 소스코드 import sys input = sys.stdin.readline exp = input().split("-") s = 0 # 마이너스가 나오기 전까지..
[Python] 백준 알고리즘 온라인 저지 14002 가장 긴 증가하는 부분 수열 4 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 수열을 받으면 그중 길이가 제일 긴 증가하는 수열을 구하는 문제이다. 11053번 문제와 유사하지만 그 수열까지 출력하여야 한다. 필자는 순서가 꼬여 이 문제부터 접하고 11053번을 풀게 되었다;; 소스코드 import sys i..
🚀 새로운 블로그로 이전했습니다.
살펴보러 가기
