전체 글

[Python] 2491 - 수열 (실버4)

1. 문제 설명 https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 2. 아이디어 쉽고 간단하고 재밌는 문제. 수열을 훑으면서 오름차순과 내림차순인 경우를 동시에 판단하면 된다. 오름차순이면 decending을 초기화하고, 내림차순이면 ascending을 초기화한다. 만약 값이 같다면 ascending과 decending 모두 1씩 증가시키면서 max값을 갱신하다가 마지막에 더 큰 값을 출력하면 끝난다. 3. 코드 def read_sequence(se..

[Python] 14225 - 부분수열의 합 (실버1)

1. 문제 설명 https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 2. 아이디어 처음 알고리즘을 공부할 때 함수명을 dfs나 dijkstra처럼 쓰지 않는 사소한 반항을 했었는데, 그땐 그게 멋있어 보였나..덕분에 블로그에 정리하는데 무슨 의도로 썼었는지 헷갈린다. N의 범위가 고작 해봐야 20이하이므로 brute-force로 끝내버렸다. 모든 경우의 수를 조합하여 가능한 결과값..

[Python] 11051 - 이항 계수2 (실버3)

1. 문제 설명 https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 2. 아이디어 값의 범위가 크지 않아서 팩토리얼을 사용하면 간단하게 해결되는 문제다. 이항 계수가 무엇인지에 대한 설명은 따로 다루지 않겠다. 3. 코드 import sys sys.setrecursionlimit(100000) def factorial(nb): if (nb == 0 or nb == 1): return 1 return (nb * factorial(nb - 1)) def solution(): n, k = map(int, input().sp..

[Python] 1790 - 수 이어 쓰기 (실버1)

1. 문제 설명 https://www.acmicpc.net/problem/1790 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net 2. 아이디어 약간의 수학적 사고력을 필요로 하는 구현 문제다. 이 문제를 정직하게 풀려고 한다면 n만큼 수를 이어붙인 문자열에서 k번째 숫자를 찾아나서야 하는데 최악의 경우가 n == 100,000,000이고 k == 1,000,000,000이다. 데이터 1억개를 처리하는 시간이 대략 1초정도 걸리는데 이걸 다 이어붙이고, 문자열 1억 번째 위치를 찾으려 하면 당연히 타임에러가 발생한다. 이런 문제를 해결할 방..