라떼는말이야

문제 정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 n이 주어진다. (0 ≤ n < 2^63) 출력 첫째 줄에 q^2 ≥ n인 가장 작은 음이 아닌 정수 q를 출력한다. 예제 나의 풀이 이분 탐색으로 풀이했다. 입력 조건에 보면 n은 0 ≤ n < 2^63 이기 때문에 나올 수 있는 답 중 가장 큰 값은 2^63의 제곱근이 되겠다. 그래서 end 초기 값을 3,037,000,500 정도로 시작했다. (파이썬이 아닌 언어를 사용하면 int와 같이 최대 21억 정도의 숫자를 담을 수 있는 자료형으로는 불가능하니 주의가 필요하다) n = int(input()) start, end = 0, 3037000500 suspend = False answer = 0 whil..

문제 음이 아닌 정수 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이 주어졌을 때, 아래 조건을 만족하는 길이..