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

다이나믹 프로그래밍(동적 계획법)이란 무엇일까? 다이나믹 프로그래밍(동적 계획법)은 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. 일반적인 분할 정복 기법(ex. 일반적 재귀로 구현한 피보나치 수열 함수)의 경우 동일한 문제를 다시 푼다는 단점을 가지고 있다. 이러한 경우에 하나의 문제를 단 한 번만 풀게해 더 효율적으로 만드는 것이 다이나믹 프로그래밍이다. 다이나믹 프로그래밍은 아래와 같은 가정 하에 사용할 수 있다. 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..

Insertion sort, Selection sort, Bubble sort은 모두 시간 복잡도가 O(n^2)으로 한 family의 알고리즘이라고 한다. 이들을 가지고 '백준 알고리즘 2750번 - 수 정렬하기' 문제를 풀어보겠다. 물론 파이썬의 내장함수를 쓸 수도 있다. 하지만 문제의 의도가 그것이 아니기 때문에 정렬 알고리즘들을 가지고 풀어보겠다. Insertion Sort 알고리즘은 위와 같은 개념으로 정렬되는 알고리즘이다. ### N = int(input()) result = [] for _ in range(N): result.append(int(input())) for i in range(1, N): cursor = result[i] j = i while j ..

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