본문 바로가기

Programming [Python]

 (411)
#154 백준 파이썬 [10844] 쉬운 계단 수 https://www.acmicpc.net/problem/10844 #Solution 정답 비율이 저렇게 낮은 이유를 잘 모르겠다. 다음과 같은 로직이다. 1) 0~9로 시작하는 숫자 * 100번째 자리 까지 리스트를 만들어준다. 2) n번째 k로 시작하는 계단수는 n-1번째의 k-1, k+1번째로 시작하는 계단수를 더해준 값 3) 단지 0으로 시작하는 것은 n-1의 1로 시작하는 계단수, 9로 시작하는 것은 n-1의 8로 시작하는 계단수만 더해주면 된다. 4) 0으로 시작하는 숫자는 없다고 해주었으므로 stair_numbers[N]의 1부터 9까지의 숫자만 더해서 출력해준다. stair_numbers = [[0 for _ in range(10)] for _ in range(101)] for i in r..
#153 백준 파이썬 [2960] 에라토스테네스의 체 https://www.acmicpc.net/problem/2960 #Solution 에라토스테네스의 체를 활용하되, 걸러지는 숫자가 나올 때마다 num에 1을 더해준다. num == K가 되면 해당 소수를 출력한다. N, K = map(int, input().split()) prime_ox = [True for _ in range(N + 1)] num = 1 for i in range(2, N+1): if prime_ox[i] == True: for j in range(i, N + 1, i): if prime_ox[j] == False: continue if num == K: print(j) prime_ox[j] = False num += 1
#152 백준 파이썬 [1929] 소수 구하기 https://www.acmicpc.net/problem/1929 #Solution 에라토스테네스의 체로 풀어준다. 시간초과가 나지 않으니 아직까진 잘 되는 소수 프로그래밍인듯. #소수리스트 만들어주기 prime_ox = [True for _ in range(1000000)] for i in range(2, int(1000000 ** 0.5)): if prime_ox[i] == True: for j in range(i+i, 1000000, i): prime_ox[j] = False prime_list = [i for i, j in enumerate(prime_ox) if j == True and i >=2 ] #소수 출력하기 M, N = map(int, input().split()) for i in pr..
#151 백준 파이썬 [9020] 골드바흐의 추측 https://www.acmicpc.net/problem/9020 #Solution 다음과 같은 알고리즘으로 효율적으로 구하였다. 1) 10000 이하의 모든 소수 생성 2) 두 소수의 값을 더했을 때 짝수이며, 10000 이하인 모든 소수를 goldbach 리스트 안에 넣어줌 3) 리스트 안의 숫자 페어 중 곱이 가장 큰 수 = 가장 인접한 수를 출력 # 재료가 될 소수 생성 prime_ox = [True for _ in range(10001)] for i in range(2, int((10001) ** 0.5)): if prime_ox[i] == True: for j in range(i+i, 10001, i): prime_ox[j] = False prime_list = [i for i, j in en..
#150 백준 파이썬 [4948] 베르트랑 공준 https://www.acmicpc.net/problem/4948 #Solution 에라토스테네스의 체를 이용하여 소수를 구해준 다음, 맞는 소수의 개수를 출력하는 방법이 가장 빠르다. import sys #소수리스트 만들어주기 prime_ox = [True for _ in range(123457 * 2)] for i in range(2, int((123457 * 2) ** 0.5)): if prime_ox[i] == True: for j in range(i+i, 123457 * 2, i): prime_ox[j] = False prime_list = [i for i, j in enumerate(prime_ox) if j == True and i >=2 ] #소수 출력하기 num = int(sys.stdi..
#149 백준 파이썬 [5430] AC - 덱 https://www.acmicpc.net/problem/5430 #Solution 생각해보면 간단한 것인데 너무 오래 풀었다. 굳이 덱을 이용하지 않아도된다! 앞에서 빼주는 것을 단순히 pop하면 리스트가 전부 앞으로 당겨지므로 시간이 굉장히 오래걸린다. 순서에 따라 뒤집는 것도 당연 오래걸린다. 먼저 R이 홀이냐 짝이냐에 따라 앞뒤에서 빠지는 것이 결정되므로 R의 개수는 그다지 중요하지 않다. 따라서 앞에서 빠지는 것은 D_front에 하나씩 더해주면서 답을 출력할 때 슬라이싱을 하면되고 뒤에서 빠지는 것은 바로 pop하여 없애주면 된다. 시간 복잡도는 O(N) case = int(input()) for _ in range(case): function = list(input()) num = int(i..
#148 백준 파이썬 [11866] 조세퍼스 문제 0 https://www.acmicpc.net/problem/11866 #Solution 숫자를 담은 리스트(stack), 이를 지속적으로 도는 temp, 맞는 숫자를 pop하여 result에 넣는 식을 통해 간단하게 해결할 수 있다. N, K = map(int, input().split()) stack = [i for i in range(1, N + 1)] result = [] temp = K - 1 for i in range(N): if len(stack) > temp: result.append(stack.pop(temp)) temp += K - 1 elif len(stack)
#147 백준 파이썬 [1932] 정수 삼각형 https://www.acmicpc.net/problem/1932 #Solution 삼각형의 제일 밑에서부터 최댓값을 저장해가면서 올라간다. 대각선 왼쪽 아래와 대각선 오른쪽 아래 중 큰 수와 자기자신을 더한 값이 그 아래 경로의 최댓값이다. triangle = int(input()) triangle_matrix = [] max_matrix = [[] for _ in range(triangle)] for _ in range(triangle): triangle_matrix.append(list(map(int, input().split()))) #역순으로 하위 항목을 모두 더한 최댓값을 저장 for i in range(triangle - 1, -1, -1): for j in range(len(triangle..

티스토리툴바