-
[Sorting #6] Quick Sort
Quick Sort Problem Solving with Algorithms and Data Structures using Python 을 공부하고 정리한 내용입니다. quick sort 는 추가적인 메모리 사용 없이 Divide and Conquer 를 사용할 수 있습니다.pivot 을 이용해 divide 될 지점을 찾아주는 것이 핵심입니다. 그림으로 예를 들어 설명해보겠습니다. 이 리스트에서 첫번째 pivot 을 54 라고 합시다.( pivot 을 정하는 방법은 여러가지가 있지만, 예제에서는 첫번째 원소를 pivot 으로 하는 방법을 선택하고 있습니다.) 이제 이 pivot 을 기준으로 하고, 나머지 리스트 에 대해 leftmartk...
-
[Sorting #5] Merge Sort
Merge Sort Problem Solving with Algorithms and Data Structures using Python 을 공부하고 정리한 내용입니다. sorting 알고리즘의 성능을 높이기 위해 Dived and Conquer 전략을 사용할 수 있습니다. Merge Sort 는 리스트를 재귀적으로 두개로 나누어 정렬 후 정렬된 부분들을 다시 합치는 방식입니다.base case는 merge 를 수행하는 부분이 되겠고, 그 조건은 리스트의 값이 하나 이하일 경우 입니다. 그림으로 예를 들어보겠습니다. 위의 그림은 Merge Sort 를 위해 리스트를 분할하는 과정을 나타냅니다.리스트의 원소가 하나 이하가 될 때 까지 계속...
-
[Sorting #4] Shell Sort
Shell Sort Problem Solving with Algorithms and Data Structures using Python 을 공부하고 정리한 내용입니다. shell sort 는 조금 생소할 수도 있는 소팅 방법입니다.insertion sort 방식을 조금 개선한 방법인데, insertion sort 가 두 연속된 sublist 로 나누어 정렬하는 방식이었다면shell sort 는 일정 gap 을 가진 sublist 로 나누어 정렬하는 방식입니다. 그림을 보면서 설명하겠습니다. 이 그림은 gap 이 2 인 sublist 로 나누어 정렬한 예시입니다.그림처럼 일정한 gap 만큼 떨어진 값들을 하나의 sublist 로 묶어서 생각해 정렬하면...
-
[Sorting #3] Insertion Sort
Insertion Sort Problem Solving with Algorithms and Data Structures using Python 을 공부하고 정리한 내용입니다. insertion sort 는 한 리스트 내에서 두 부분으로 리스트를 나누고, 뒤의 리스트의 값들을 하나씩 앞의 리스트에 정렬해서 넣는 방식입니다. 결론부터 말하자면 bubble sort 와 마찬가지로 성능이 좋지 않은 방법입니다. 그림으로 예를 들어보겠습니다. 편의상 앞의 list 를 sorted sublist , 뒤의 list 를 unsorted sublist 라고 이름붙여 보겠습니다. unsorted sublist 에 있는 값들을 차례로 sorted sublist 로 가져오는데, 이 때 가져오는...
-
[Sorting #2] Selection Sort
Selection Sort Problem Solving with Algorithms and Data Structures using Python 을 공부하고 정리한 내용입니다. selection sort 는 리스트 중 가장 큰 값을 골라 뒤에서 부터 채우는 형식입니다.bubble sort 와는 달리 selection sort 는 리스트를 처음부터 끝까지 볼 때 한 번 의 swap 연산만 합니다. bubble sort 는 한 값을 정렬하기 위해 $n-1$ 번의 검사와 최대 $n-1$ 번의 swap 연산을 했다면,selection sort 는 $n-1$ 번의 검사와 한번의 swap 연산을 합니다. 그림으로 예시를 보겠습니다. 정렬되지 않은...
-
[Sorting #1] Bubble Sort
Bubble Sort Problem Solving with Algorithms and Data Structures using Python 을 공부하고 정리한 내용입니다. bubble sort 는 인접한 값을 비교하고 순서를 정렬하는 방법입니다.sorting 방법 중 가장 많이 알고있는 방법인데, 성능면에서는 우수하지 않습니다.compare 와 swapping 을 불필요하게 여러 번 하기 때문입니다. 그림으로 예를 들어보겠습니다. [54, 26, 93, 17, 77, 31, 44, 55, 20] 이라는 bubble sort 방식으로 정렬할 때, 처음 비교해야 하는 쌍은 총 8 ( 9-1 ) 개 입니다. 8쌍을 비교하고 나면, 리스트 내에서...
-
알고리즘 스터디 3주차
알고리즘 스터디 3주차 백준의 단계별 풀어보기에서 정렬해보기 를 풀어보았습니다. 2750 수 정렬하기 def problem_2750(input_num): input_list = [] for i in range(int(input_num)): input_list.append(int(input())) input_list.sort() for i in range(int(input_num)): print(input_list[i]) my_num = input() problem_2750(my_num) 간단한 정렬문제인데, 파이썬에서는 더 간단하게 sort 함수를 제공하고 있습니다. 문제는 이 sort 함수의 성능인데, 파이썬의 sort 함수는 timsort 라는 알고리즘으로 구성되었다고 합니다. timsort는 worst 인 경우 시간복잡도가 O(n log(n)) 으로 상당히 빠른 알고리즘입니다. timsort에 관한 자세한 설명은 링크 를 참고하시기 바랍니다. sort 의...
-
알고리즘 스터디 2주차
알고리즘 스터디 2주차 백준의 단계별 풀어보기에서 규칙찾기를 풀어보았습니다. 1193 분수찾기 def problem_1193(input_num): # 대각선 기준으로 몇 번째 대각선에 속하는 수 인지 알기 c = 0 while input_num > 0: c = c+1 input_num = input_num - c # c = 몇 번째 대각선에 속하는지, c1 = 해당 대각선의 분수를 만들기 위해 c1 = c # l = 해당 대각선의 분수 list l = [] # 지그재그 이므로, 홀수번째 대각선과 짝수번째 대각선의 규칙이 다름 if c1...
-
알고리즘 스터디 1주차
알고리즘 스터디 1주차 백준의 단계별 풀어보기에서 문자열 사용하기 를 풀어보았습니다. 파이썬으로 백준 알고리즘 문제를 처음 풀어보았는데, 문자열 반환의 경우 return 을 해주면 따옴표(‘’) 까지 인식 해 틀렸다고 나왔습니다. return 대신 print 를 해 주면 정상적으로 작동하는 것을 알 수 있었습니다. 1157 단어공부 import collections def problem_1157(input_string): # 대소문자 구분을 하지 않으므로 upper case 로 변경 input_string = input_string.upper() # input 에 대해 count cnt = collections.Counter(list(input_string)) # count 횟수를 key 로 갖는 딕셔너리 생성 d...