PYTHON 44

[Python/파이썬] 백준 알고리즘 1463번 - 1로 만들기 (동적 계획법 / 다이나믹 프로그래밍 풀이)

힌트 : 10의 경우에 10 -> 9 -> 3 -> 1로 3번만에 만들 수 있다. 이 문제는 전에 결과를 다음 결과에 이용하는 Dynamic Programming(동적 계획법) 문제이다. 힌트를 보면 정수 X가 10인 경우 10 -> 9 -> 3 -> 1 의 과정으로 1이 된다고 했는데, 10은 정수 X가 9인 경우의 횟수에 +1을 한 값이고 9는 정수 X가 3인 경우의 횟수에 +1을 한 값이고 3은 정수 X가 1인 경우의 횟수에 +1을 한 값이다. 다시 말해서 10을 구할 때는 9의 결과를, 9를 구할 때는 3의 결과를 이용한다. 따라서 아래의 조건을 만족하기 때문에, 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일하다. 동적 계획법을 사용..

[Python/파이썬] 백준 알고리즘 10866번 - 덱 (Stack 두 개로 덱 구현하는 방법)

https://kbwplace.tistory.com/87 [Python/파이썬] 백준 알고리즘 1406번 - 에디터 string = list(input()) N = len(string) M = int(input()) cursor = N for _ in range(M): command = input().split() if command[0] == "L": if cursor > 0: cursor -= 1 elif command[0].. kbwplace.tistory.com 여기서 풀었던 방법을 응용했다. 문제의 시간 제한이 0.5초로 빡빡한 편이라 시간 단축을 위해서 insert와 같은 high cost의 함수는 사용하지 않고 append, pop 함수만으로 구현해야한다. 이것을 구현하는 방법은 위의 140..

[Python/파이썬] 백준 알고리즘 1158번 - 요세푸스 문제

N, K = map(int, input().split()) circular_queue = [i for i in range(1, N+1)] cursor = K-1 result = [] while circular_queue: result.append(str(circular_queue.pop(cursor))) # 순서 중요! N 감소가 cursor 이동보다 선행되어야 함. N -= 1 if N > 0: if (cursor + K) % N == 0: cursor = N - 1 else: cursor = (cursor + K) % N - 1 print("") 처음에 저 N -= 1을 뒷 순서에 놔서 애먹었다.. 커서를 이동시켜가며 해당 인덱스에 도달했을때 pop해 result 리스트에 넣고 마지막에 출력하는 방식..

[Python/파이썬] 백준 알고리즘 18870번 - 좌표 압축

N = int(input()) coList = list(map(int, input().split())) # 중복 값 제거한 후 정렬 coList_sort = sorted(list(set(coList))) for coordinate in coList: print(coList_sort.index(coordinate), end=' ') 처음에 이렇게 풀었으나 시간 초과가 났다. 리스트.index(i)의 시간 복잡도는 O(N)이다. 인덱싱을 방법 중 더 낮은 시간 복잡도의 방법은 딕셔너리를 이용하는 방법이다. (O(1)) N = int(input()) coList = list(map(int, input().split())) # 중복 값 제거한 후 정렬 coList_sort = sorted(list(set(coL..

[Python/파이썬] 백준 알고리즘 1181번 - 단어 정렬

N = int(input()) words_list = [] for _ in range(N): word = input() words_list.append((word, len(word))) # 중복 제거 words_list = list(set(words_list)) # 단어 길이 정렬 > 단어 알파벳 정렬 words_list.sort(key=lambda word: (word[1], word[0])) for word in words_list: print(word[0]) 11651번에서 배웠던 sort함수의 key인자를 이용해 lambda로 정렬할 기준을 잡는 방법을 사용했다. words_list에는 단어와 단어의 길이가 튜플로 들어가고 key=lambda word: (word[1], word[0])에서 wor..

[Python/파이썬] 백준 알고리즘 11651번 - 좌표 정렬하기 2

N = int(input()) coordinates = [] for _ in range(N): coordinates.append(list(map(int, input().split()))) # key=lambda를 이용해서 정렬할 기준을 x[1] 그리고 x[0]으로 잡음 coordinates.sort(key=lambda x: (x[1], x[0])) for co in coordinates: print(co[0], co[1]) sort함수의 key인자를 이용해 lambda로 정렬할 기준을 잡는 방법이다. N = int(input()) coordinates = [] for _ in range(N): a, b = map(int, input().split()) coordinates.append([b, a]) co..

[Python/파이썬] 백준 알고리즘 7568번 - 덩치

브루트 포스 유형 문제이다. N = int(input()) sizeList = [] for _ in range(N): x, y = map(int, input().split()) sizeList.append((x, y)) for size in sizeList: rank = 1 for compare_size in sizeList: if size[0] < compare_size[0] and size[1] < compare_size[1]: rank += 1 print(rank, end=' ') 처음엔 너무 어렵게 접근했다. 사실은 문제에 답이 있었다. 바로 "N명의 집단에서 각 사람의 덩치 등수는 자신보다 더 "큰 덩치"의 사람의 수로 정해진다." 라는 문장에 답이 있었다. 그냥 간단하게 자기보다 몸무게와 키가..

[Python/파이썬] 백준 알고리즘 1929번 - 소수 구하기

M, N = map(int, input().split()) for i in range(M, N+1): primeNum = True if i == 1: primeNum = False else: for j in range(2, i): if i % j == 0: primeNum = False break if primeNum: print(i) 처음엔 위와 같이 풀었었다. 숫자 i 하나에 대해 2부터 i-1까지 나눠보면서 0으로 나누어 떨어지면 소수가 아니므로 이를 제외하는 방식으로 코드를 짰었다. 그러나 1929 문제에서 이 방식은 시간초과가 떴다. 그래서 구글링을 해보니 '에라토스테네스의 체'를 이용해 시간을 단축해야한다고 한다. 에라토스테네스의 체는 가장 대표적인 소수 판별 알고리즘이다. 에라토스테네스의 체..

[Python/파이썬] 백준 알고리즘 2869번 - 달팽이는 올라가고 싶다

개인적으로 풀면서 재밌었다. 그래서 포스팅하려고 한다. A, B, V = map(int, input().split()) pre_move = (V-A) // (A-B) remainder = (V-A) % (A-B) if remainder > 0: print(pre_move + 2) else: print(pre_move + 1) V길이의 막대의 정상에 도달하는 시점은 분명 낮일 것이다. 근데 여기서 중요시 생각해야 될 것은 막대의 정상에 도달하는 시점은 달팽이가 낮에 움직일 수 있는 최대의 거리만큼을 이동함과 동시에 도달하는 것이 아닐 수 있다는 것이다. 다시 말해서, 정상에 도달하고도 달팽이는 더 움직일 수 있지만 정상에 도달했기 때문에 멈추는 경우가 있을 수 있다는 것이다. 때문에 우선 나는 막대의 길이..

반응형