KBW's cosmos

힌트 : 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. 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일하다. 동적 계획법을 사용..

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..

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 리스트에 넣고 마지막에 출력하는 방식..

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] == "D": if cursor 0: string.pop(cursor-1) cursor -= 1 elif command[0] == "P": string.insert(cursor, command[1]) cursor += 1 for s in string: print(s, end='') 처음에 위와 같..

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..

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..

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..

브루트 포스 유형 문제이다. 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명의 집단에서 각 사람의 덩치 등수는 자신보다 더 "큰 덩치"의 사람의 수로 정해진다." 라는 문장에 답이 있었다. 그냥 간단하게 자기보다 몸무게와 키가..

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 문제에서 이 방식은 시간초과가 떴다. 그래서 구글링을 해보니 '에라토스테네스의 체'를 이용해 시간을 단축해야한다고 한다. 에라토스테네스의 체는 가장 대표적인 소수 판별 알고리즘이다. 에라토스테네스의 체..

개인적으로 풀면서 재밌었다. 그래서 포스팅하려고 한다. 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길이의 막대의 정상에 도달하는 시점은 분명 낮일 것이다. 근데 여기서 중요시 생각해야 될 것은 막대의 정상에 도달하는 시점은 달팽이가 낮에 움직일 수 있는 최대의 거리만큼을 이동함과 동시에 도달하는 것이 아닐 수 있다는 것이다. 다시 말해서, 정상에 도달하고도 달팽이는 더 움직일 수 있지만 정상에 도달했기 때문에 멈추는 경우가 있을 수 있다는 것이다. 때문에 우선 나는 막대의 길이..