라떼는말이야

문제 일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다. 출력 입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다. 예제 나의 풀이 N과 M이 최대 100,000이 될 수 있으므로 순차적으로 탐색한다면 최악의 상황에 100,000 x 100,000 = 10,00..

문제 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. 입력 첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄에 N번째 감소하는 수를 출력한다. 나의 풀이 문제에서 0은 0번째, 1은 1번째 감소하는 수라고 했다. 즉, 한 자릿수는 모두 감소하는 수라고 할 수 있다. 2 자릿수 이상부터는 마지막 숫자보다 그 뒤에 붙는 숫자가 작아야 한다. 어떤 리스트에 감..

문제 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y) 값을 더한 값은 g(x)로 표현한다. 자연수 N이 주어졌을 때, g(N)을 구해보자. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 g(N)를 출력한다. 나의 풀이 여러 번의 시간 초과 끝에 맞춘 문제이다. 그만큼 이 문제를 풀 수 있는 방법도 다양하고, 훨씬 더 효율적인 풀이가 존재한다는 의미이다. 실패한 코드들은 깃허브에 올려놓았다...

문제 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다. 출력 1로 이루어진 n의 배수 중 가장 작은 수의 자릿수를 출력한다. 나의 풀이 단순한 풀이 기본적인 아이디어로는 1, 11, 111, 1111... 순으로 늘려보며 n으로 나누어 떨어지는지 확인하는 방법을 생각해볼 수 있다. 틀린 풀이는 아니지만 큰 수를 나눠야 하는 상황이 발생하기 때문에 시간 복잡도가 증가할 수 있다. PyPy3 언어로 백준에 제출한 결과 통과할 수 있었다. 해당 코드는 다음과 같다. def solution(n): count..

파이썬에는 다양한 출력 방법이 존재한다. 코딩 테스트 같은 경우 시간 복잡도와 공간 복잡도가 아주 중요한데 특히 시간 복잡도에서 좌절을 겪는 경우가 상당히 많다. 이 글은 알고리즘 문제를 풀다가 동일한 알고리즘인데 시간 차이가 많이 나는 경우를 발견해서 작성하게 되었다. 파이썬의 다양한 출력 방법 문자열 결합 방식 가장 기본적인 방법이다. a, b, c = 1, 2, 3 print("a는:", a, "b는:",b , "c는:", c) print("a는:" + str(a), "b는:" + str(b) , "c는:" + str(c)) ,(comma)로 이어서 출력할 수 있다. 이때 a, b, c는 정수 타입이지만 별도의 변환 없이 출력이 가능하다. +(plus)로 이어 줄 수도 있다. 하지만 이 방법은 문자..

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 나의 풀이 2022.01.24 - [solved.ac 실버3] 15652_N과 M (4) (python, brute force) [solved.ac 실버3] 15652_N과 M (4) (python, brute force) 문제 자..

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 나의 풀이 2022.01.24 - [solved.ac 실버3] 15651_N과 M (3) (pytho..

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 나의 풀이 2022.01.24 - [solved.ac 실버3] N과 M (3) (python, brute force) [solved.ac 실버3] N과 M (3) (python, brute force) 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이..