CS

삽입 정렬(insertion sort)

📔 삽입 정렬(insertion sort) 이란 숫자를 적절한 위치에 삽입하는 방법 "필요할 경우에만" 위치를 바꾼다. 2개의 반복문을 중첩해서 구현하기 때문에 시간복잡도는 O(n^2) 한 세트가 끝날 때마다 앞의 숫자들은 "정렬"된 상태이다. 📔 삽입 정렬(insertion sort) 예제 위의 예제는 오름차순일 경우의 예제이다. 5개의 원소중 처음과 그 다음을 비교한다. 그 둘을 정렬한다. 1세트가 끝나면 앞의 숫자들(노란색)은 정렬된 상태이다. 다음 세트는 두번째 숫자부터 앞의 숫자와 비교한다. 📔 삽입 정렬(insertion sort) 구현 numbers = [5, 3, 8, 1, 2] print(f'정렬 전: {numbers}') print() for i in range(len(numbers)-..

선택 정렬(selection sort)

📔 선택 정렬(selection sort) 이란 오름차순의 경우 가장 작은 원소를 맨 앞으로 보낸다. 2개의 반복문을 중첩해서 구현하기 때문에 시간복잡도는 O(n^2) 한 세트가 끝날 때마다 가장 작은 수가 맨 앞에 온다. 📔 선택 정렬(selection sort) 예제 위의 예제는 오름차순일 경우의 예제이다. 5개의 원소중 가장 작은 숫자를 맨 앞의 숫자와 바꾼다. 1세트가 끝나면 가장 작은 수가 맨 앞으로 온다. 다음 세트부터는 맨 앞의 숫자를 빼고 비교를 해준다. (이미 가장 작은 수이기 때문) 📔 선택 정렬(selection sort) 구현 numbers = [5, 3, 8, 1, 2] print(f'정렬 전: {numbers}') print() for i in range(len(numbers))..

버블 정렬(bubble sort)

📔 버블 정렬(bubble sort) 이란 서로 인접한 두 원소의 대소를 비교하여 정렬하는 알고리즘 2개의 반복문을 중첩해서 구현하기 때문에 시간복잡도는 O(n^2) 오름차순의 경우 1세트(바깥쪽 반복문)이 끝나면 가장 큰 수가 맨 뒤에 오게 된다. 내림차순의 경우 반대 📔 버블 정렬(bubble sort) 예제 위의 예제는 오름차순일 경우의 예제이다. 앞뒤의 숫자를 비교해서 앞의 숫자가 크면 뒤의 숫자랑 바꾼다. 1세트가 끝나면 가장 큰 수가 맨 뒤로 온다. 다음 세트부터는 맨 뒤의 숫자를 빼고 비교를 해준다. (이미 가장 큰 수이기 때문) 📔 버블 정렬(bubble sort) 구현 numbers = [5, 3, 8, 1, 2] print(f'정렬 전: {numbers}') print() for i i..

빅 오(Big O) - 시간복잡도

📗 빅 오(Big O) - 시간복잡도 🔵 시간 복잡도란? 쉽게 말해 알고리즘의 실행속도 계산이다. - 최악의 실행 시간을 계산 알고리즘을 해결하다 보면 시간에 대해서 신경이 쓰일 것이다. 다를 사람의 풀이와 비교한다던지, 시간초과가 발생한다던지... 알고리즘을 해결하는 방법은 다양하다. 그러므로 어떤 알고리즘이 더 효율적인지 분석하기 위해 시간 복잡도를 계산해야 한다. 복잡도에는 시간 복잡도 - 알고리즘 실행 속도 공간 복잡도 - 메모리 크기(사용량) 이 있지만 보통은 시간 복잡도를 본다. 🔵 빅오 표기법 입력 n에 따라 결정되는 시간 복잡도 함수 O(1), O(logn), O(n), O(nlogn), O(n^2), O(2^n) 등이 있다. 상수 O(1): 데이터 수에 상관없이 연산횟수 고정 로그 O(l..

[python] 이진 탐색 트리 (binary Search tree) - 4. 삭제

📗 이진 트리 (binary Search tree) - 삭제 노드 삭제 노드를 하나 삭제해보자. 노드를 삭제하는 경우는 3가지가 있다. 자식 노드가 없은 경우, 자식 노드가 하나인 경우, 자식노드가 둘인경우로 나눌 수 있다. 🔵 자식 노드가 없는 경우 자식 노드가 없는 경우는 그냥 삭제하면 된다. 🔵 자식 노드가 하나인 경우 자식 노드가 하나인 경우는 삭제할 노드를 삭제하고, 그 자식 노드를 할아버지 노드에 붙이면 된다. 🔵 자식 노드가 둘인 경우 자식 노드가 둘인 경우는 삭제할 노드를 삭제하고, 그 노드의 오른쪽 자식의 가장 왼쪽 자손을 가져와서 삭제한 노드의 부모 노드에 붙여준다. 🔵 전체 코드 # 노드 만들기 # A(val) # / \ # B(left) C(right) class Node: def ..

[python] 이진 탐색 트리 (binary Search tree) - 3. 순회

📗 이진 트리 (binary Search tree) - 순회 트리 순회 트리 순회는 트리에 저장된 값을 모두 확인할 때 사용한다. 순회 방법에 따라 값을 확인하는 순서가 다르다.순회의 종류로는 전위 순회 (preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)이 있다. 🔵 전위 순회 (preorder traversal) 💨 완성되어 있는 트리를 다른 서버에 리스트 형태로 보내서 그 서버에서 다시 트리를 구성할 때 사용 노드 > 왼쪽 서브트리 > 오른쪽 서브트리 순으로 순회한다. 구현 방법은 다음과 같다. 노드 방문 왼쪽 서브트리 방문 오른쪽 서브트리 방문 전위 순회 결과: F, B, A, D, C, E, G, I, H def p..