성장일기

▼ 다들 엄청 자세하게 설명해주셨다 ! ㅜㅜ KMP : 문자열 검색 알고리즘 문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다. 아래 이미지는 브라우저에서 "테이프"를 검색했 bowbowbow.tistory.com [Python] KMP 알고리즘으로 문자열 찾기 들어가면서KMP(Knuth, Morris, Pratt) 알고리즘은 찾고자 하는 문자열(Pattern)을 주어진 문자열(Text)에서 빠르게 찾아내는 방법 중 하나입니다. KMP의 강력함을 알기 위해서 먼저 가장 쉽게 문자열 탐색을 devbull.xyz [Python]KMP 알고리즘 커누스 모리스 프랫 알고리즘(Knuth-Morris-Pratt algori..

1. 퀵 정렬(quick sort)이란? 🌸 정렬 알고리즘의 꽃 🖐 기준점(pivot)을 정해서 피벗보다 작은데이터는 왼쪽, 큰 데이터는 오른쪽으로 -> 반복 🖐 왼쪽 + 기준점 + 오른쪽 리턴 2. 순서대로 생각해보기 data = [4, 6, 3, 7, 1] 일 때, 👉 맨 앞 기준으로 작으면 left, 크면 right에 넣어보자 data = [4,6,3,7,1] pivot = data[0] left = [] right = [] for idx in range(1,len(data)): if data[idx] < pivot: left.append(data[idx]) else: right.append(data[idx]) print(left, pivot, right) #출력 결과 : [3, 1] 4 [6, 7..

1. 카운팅 소트(counting sort)란? 🖐 각 숫자가 등장하는 횟수를 세어서 정렬! 🖐 누적합을 활용 2. 순서대로 생각하기 data = [0, 4, 1, 3, 1, 2, 4, 1, 5, 7, 7, 2] 일 때, 👉 각 숫자가 등장하는 횟수를 세보자 0 1 2 3 4 5 7 1 3 2 1 2 1 2 👉 누적합을 구해보자 0 1 2 3 4 5 7 1 4 6 7 9 10 12 ✨ 각 숫자가 위치한 인덱스를 알 수 있다! 0은 0번째, 1은 1~3번째, 2는 4~5번째 .... 👉 재배치 ! 배치하고 인덱스 줄여주고 배치하고 인덱스 줄여주고 ..... 3. 구현하기 def counting(array,k): # 배열과 맥스값 k cnt_array = [0] * (k + 1) # 초기화 for num i..

1. 병합 정렬(merge sort)란? 🖐 재귀를 활용 🖐 리스트를 반으로 자르고 각 부분을 정렬 -> 두 부분을 다시 정렬 2. 순서대로 생각하기 data = [1, 8, 4, 2] 일 때 👉 두 개로 자른다! [1, 8] 과 [4, 2] 👉 앞부분을 자르고 다시 정렬해서 합친다! [1] [8] -> [1, 8] 👉 뒷부분을 자르고 다시 정렬해서 합친다! [4] [2] -> [2, 4] 👉 두 부분을 합친다! [1, 2, 4, 9] ( 1 right[right_idx]: # 왼쪽 첫번째와 오른쪽 첫번째를 비교 merged.append(right[right_idx]) # 오른쪽이 더 작으면 오른쪽(작은 수)를 리스트에 삽입..

1. 선택 정렬(selection sort) 란? 🖐 주어진 데이터 중 최소값을 찾아 맨 앞 값과 교체 🖐 맨 앞을 빼고 다시 반복 Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only "payment" that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Fa..

1. 삽입 정렬(insertion sort) 란? 🖐 두 번째 인덱스부터 시작하여 앞의 수와 비교하는 알고리즘 Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only "payment" that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Facebook/Twitt..