코딩 연구소

💡 Straight InSertion Sort ( 단순 삽입 정렬 ) 단순 삽입 정렬은 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘이다. 선택 정렬과 비슷해 보이지만 값이 가장 작은 원소를 선택하지 않는다는 것이 다르다. 삽입이라는 말 그대로, 들어서 자기 자리에 꽂아주는 것이다. 💡 설명 두 번째 원소인 4 부터 주목하여 진행한다. 4는 6보다 앞쪽에 위치해야 하므로 맨 앞에 삽입한다. 이 상태에서 6을 우측으로 옮기면 [그림1] 의 두 번째 처럼 4, 6, 1 ... 8 이 나오게 된다. 다음으로 세 번째 원소인 1에 주목하여 진행한다. 1은 4보다 앞쪽에 위치해야 하므로 맨 앞에 삽입한다. 이 상태에서 4와 6을 우측으로 옮기면 [그림1] 의 세 번째 처럼 1, 4, 6 ...

자료구조 2022. 3. 17. 01:37

💡 Straight Selection Sort ( 단순 선택 정렬 ) 단순 선택 정렬은 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘이다. 💡 설명 가장 작은 원소 1과 4 의 위치를 변경 두 번째 작은 원소 2와 6의 위치를 변경 하며 정렬 💡 코드 def selectSort(arr): size = len(arr) for i in range(size - 1): min_idx = i for j in range(i + 1, size): print ('i=', i, 'j=',j, arr) if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr arr = [2, 1..

자료구조 2022. 2. 21. 01:10

💡 Bubble sort ( 버블 정렬 ) 버블 정렬은 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘으로, 단순 교환 정렬이라고도 한다 💡 설명 오름차순으로 먼저 정렬하려고 한다. 오른쪽 끝에 있는 두 원소 7과 8 중 작은 숫자를 좌측으로, 큰 숫자를 우측에 둔다. 두 숫자는 7이 8보다 작으므로 교환할 필요가 없다. 오름차순으로 정렬 하려 했기 때문에 현재 같은 상황에서도 교환할 필요가 없다. 이렇게 반복하여 필요한 경우 교환하는 것이 버블 정렬의 기본기이다. 만약 교환해야 되는 대상이 있는 경우 5, 1 ( 4번째)를 보게 되면 1과 5가 바뀌는 경우를 볼 수 있다. 1, 6 / 1. 4 오름차순으로 정렬 한다면 1, 2, 3, 4 ... 8 까지 나와야 하기 때문에 loop..

자료구조 2022. 2. 21. 00:51

💡 하노이 탑 하노이탑은 프랑스 수학자인 루카스가 1883년에 만들어 낸 문제이다. 가운데 기둥을 중심으로 이 기둥을 이용하여 왼쪽 기둥에 놓인 크기가 다른 원판을 오른쪽기둥으로 옮기는 문제로 이때 원판은 한 번씩만 옮길 수 있고 작은 원판 위에 큰 원판이 놓을 수 없다. 💡 공식 하노이 탑의 원판이 n개 일 때, 이동 횟수 공식 💡 설명 이 하노이탑 문제를 풀어내기 위해 원판이 이동해야 하는 횟수를 구하는 공식으로 하노이탑공식을 알고 있다면 굳이 직접 하노이탑퍼즐을 풀지 않아도 몇번을 이동해야 하는지 알 수 있다. 하노이탑 공식은 원판이 n개가 있을 경우 2의 n제곱 -1인데요. 만약 4개의 원판이 있을 경우 최소 이동횟수는 2의4제곱-1 16-1이 되므로 총 15번이 되는 공식이다. 💡 코드 def ..

자료구조 2022. 2. 13. 20:19

💡 Circular Queue 번거로운 데이터 이동을 발생시키지 않고 주어진 공간을 활용하여, 디큐할 때 배열 안의 원소를 옮기지 않는 것이 Circular Queue 이다. 큐는 한쪽 끝에서만 데이터를 넣을 수 있고 다른 한쪽 끝에서만 데이터를 뺄 수 있는 구조를 가지고있다. Circular 에서 사용되는 용어로는 2가지가 있다. 프런트(front) : 맨 앞 원소의 인덱스 리어(rear) : 맨 끝 원소 뒤의 인덱스 ( 다음 큐 데이터가 저장되는 위치 ) 💡 추가 설명 Queue 자료구조의 특성상 한쪽 방향에선 데이터가 들어가고, 한쪽 방향에서는 데이터가 나가면서, 저장된 데이터들을 한 칸씩 모두 이동해야 하는 단점이 있다. Linked List 를 통해 큐를 구현한다면 이런 한계점을 극복할 수 있다..

자료구조 2022. 2. 11. 02:25

해시 법 설명 : [Python 자료구조] 해시 법 + (체인 법) :: 코딩 연구소 (tistory.com) 💡 해시 충돌 - 오픈 주소법 오픈 주소법은 충돌이 발생했을 시 재해시 ( rehashing ) 을 수행하여 빈 버킷을 찾는 방법을 말하며 닫힌 해시 법 ( closed hashing ) 이라고도 합니다. 66 이라는 숫자를 추가하려 했지만, 충돌이 발생했습니다. 충돌이 발생했을 시 재해시를 수행합니다. 재해시를 위한 식으로 ( 66 + 1 ) % 4 로 77 나누기 4를 진행한 19 를 얻었습니다. 오픈 주소법에서 재해시를 위한 식은 (원소 + 1) % (버킷) 진행한 나머지 값 = 인덱스 만약 들어 가려 하는 버킷이 또 충돌이 발생할 경우 66+1이 아닌 1을 더했던 67을 기준으로 +1 진..

자료구조 2022. 2. 11. 01:36

💡 해시법 '데이터를 저장할 위치 (인덱스)' 를 간단한 연산으로 구하는 것이다. 해시법을 사용하게 되면 원소의 검색뿐 아니라 추가 및 삭제도 효율적으로 수행할 수 있다. 💡 해시 값 배열의 키를 원소 개수로 나눈 나머지를 해시 값 ( hash value ) 라고 하며, 데이터에 접근할 때 기준으로 사용된다. 💡 설명 8개의 원소가 작성되어 있는 표에서 17을 찾고자한다. 17을 찾는 과정에서 해시 함수 ( hash function ) 을 사용하여 변환한다. 해시 함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용된다. 해시 함수를 사용하게 되면 17을 8로 나눈 나머지는 1 이므로 x[1]에 17을 저장한다. 이렇게 변환하는 과정을 해시 함수라고 한다. 파란색 글씨로 작성된 것은 키 ( ..

자료구조 2022. 2. 7. 03:07

💡 이전 글 : [Python 자료구조] 모듈 활용한 큐 (Queue) - 1 :: 코딩 연구소 (tistory.com) 💡 LifoQueue 스택 (Stack) 과 동일하게 LIFO import queue queue = queue.LifoQueue() queue.put("queue") queue.put(3) queue_list = queue.get() print (queue_list) queue_list = queue.get() print (queue_list) 💡 실행 결과 스택과 동일하게 LIFO 이기 때문에, 'queue' 보다 늦게 들어간 3이 먼저 꺼내진다. 💡 PriorityQueue 데이터 마다 우선 순위를 주고, 우선 순위가 높은 순으로 데이터를 출력 튜플 자료형태로 등록하며, 우선 순위..

자료구조 2022. 2. 6. 18:54