알고리즘을 공부하면서 많은 정렬들이 등장한다. 버블 정렬, 삽입 정렬 등등... 오늘 공부한 내용은 이렇게 수많은 정렬 알고리즘 중 시간 복잡도가 O(n)으로 엄청난 성능을 보여주는 알고리즘이다. 카운팅 정렬을 공부하면서 처음에는 이게 왜 빠를까?를 생각했다. 시간 복잡도를 공부할 때, 시간 복잡도 도출 기준은 상수의 시간 복잡도는 계산에서 제외하고, 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다고 배웠다. 카운팅 정렬은 각 배열 원소끼리(예를 들어 for문 중첩) 직접 비교하지 않고, 인덱스를 가지고 위치를 찾아나가는 것이다. 이 방법의 가장 큰 장점은 매우 빠르다는 것이다. 하지만 카운팅 정렬은 수의 범위가 매우 클 경우(예를 들어 10억, 100억 등등...) 심한 메모리 낭비를..
문제 접근 처음에 문제를 접하고, 큐를 사용한 문제 풀이와 인덱스와 pop을 활용한 문제 풀이 2가지를 생각해보았다. 1. 파이썬(Python) 1) index와 pop을 이용한 문제 풀이 n, k = map(int, input().split()) arr = [i for i in range(1, n + 1)] ans_arr = [] idx = k - 1 # 시작 인덱스를 K-1로 설정 while arr: # 인덱스가 배열의 길이를 초과하는 경우, 인덱스를 배열의 길이로 나눈 나머지로 조정 if idx >= len(arr): idx %= len(arr) remove_elem = arr.pop(idx) ans_arr.append(remove_elem) # 다음 시작 인덱스를 K-1만큼 증가 idx += k ..
1. 문제 접근 처음 이 문제를 보고 바로 풀지 못하였다. 정렬을 사용해야 하나? 라는 생각을 했지만, 정렬로는 떨어져서 나타나는 단어를 구할 수 없었기에 넘어갔고, 그 다음으로 입력을 배열의 형태로 받아서 각 단어를 비교하는 방법을 생각했지만, 그것 또한 아니었다. 그리고 생각한 결과, 문제는 의외로 간단하였다. 예를 들어, abcdef라는 단어가 있다고 가정하자. a와 b를 비교하여 두 단어가 다르다면, b부터 끝까지인 bcdef를 새로운 단어로 저장하고, bcdef 안에 a가 있는지를 확인하면 된다. 확인 후 a가 존재하지 않는다면 그룹 단어에 1을 더하고, a가 존재한다면 그 단어는 그룹 단어가 아닌 것이다. 2. Python n = int(input()) # 입력받을 문자의 개수 group_wo..
1. 파이썬(Python) 1) 첫번째 풀이(오답) import sys input = sys.stdin.readline a, b, n = map(int, input().split()) x = a / b x = x * pow(10, n) y = int(x / 10) * 10 print(int(x-y)) 런타임 에러(OverflowError)가 발생했다. 찾아보니 파이썬은 소수점 15자리까지만 표시하기에 n이 15가 넘어가면 오류가 발생한다. 따라서 오류가 발생한다. 2) 두번째 풀이(정답) a, b, n = map(int, input().split()) for i in range(n): a = (a % b) * 10 result = a // b print(result) 처음부터 다시 생각하여 실제로 나눗셈..
1. Python 풀이 word = list(input()) answer = [] temp = [] for i in range(1,len(word)-1): for j in range(i+1, len(word)): a = word[:i] b = word[i:j] c = word[j:] a.reverse() b.reverse() c.reverse() temp.append(a+b+c) for piece in temp: answer.append(''.join(piece)) print(sorted(answer)[0]) 코드설명 python과 java를 함께 사용하여 문제를 풀이하니 python이 알고리즘 풀이에 있어서 얼마나 유용한지 새삼 느낀다. 입력부터 list로 받아와서 이중 for문을 이용하여 3등분을 할..
1. 첫번째 풀이(실패) 이 문제는 처음에 쉬워보여서 바로 시도하였으나, 런타임에러로 실패하였다. 처음에 제출한 코드는 다음과 같다. import sys input = sys.stdin.readLine n = int(input()) lst = [] for i in range(n): lst.append(input().strip()) lst = list(set(lst)) lst.sort() lst.sort(key = len) for i in lst: print(i) 실패 원인 sys.stdin.readLine() 함수를 사용하여 입력을 받을 때, 전체 입력을 한 번에 처리하기 때문. 입력이 많은 경우 처리 시간이 길어질 수 있다. 시간을 줄이기 위해서는 입력을 한 줄씩 처리해야 한다. 2. 두번째 코드(성공..
