Data Structure - Heap (힙) | Python 구현 Heap은 이진트리의 변형된 자료구조라고 할 수 있는데, 최댓값 최솟값을 빠르게 찾아야 할 때 많이 사용된다. 📌Heap : 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Complete Binary Tree) 트리를 기반으로 변형된 구조! 완전 이진 트리(Complete Binary Tree): 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨. array vs. heap : 배열에서 최댓값/최솟값을 탐색하는데 걸리는 시간복잡도는 $O(n)$, 힙에서 최댓값/최솟값을 찾는데 걸리는 시간복잡도는 $O(log n)$ 📌Heap 구조 최대값을 구하기 위.. Data Structure (3) Hash Table (해시 테이블) 📌Hash 구조 Hash Table: key에 data(value)를 저장하는 데이터 구조 ex) Python의 Dictionary : key와 value를 가지고 있는 데이터 타입으로, key값을 통해 value를 바로 꺼낼 수 있음 (Python에서는 hash구현 없이 바로 dictionary 사용하면 됨) 보통 미리 hash table의 크기만큼 배열 생성 후 사용 (공간과 탐색 시간을 맞바꾸는 기법) 📌용어 hash: random 값을 고정 길이로 변환하는 것 (단방향 암호화 기법으로, 해시 알고리즘을 이용하여 고정된 길이의 암호화된 문자열로 변환) hash table: hashing function: key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수, 즉 임이이 길이의 데이터를.. Data Structure (2) Tree (트리) 📌트리 node와 branch를 이용해서, cycle을 이루지 않도록 구성한 데이터 구조 트리 중 binary tree(이진 트리) 형태의 구조는 탐색(search) 알고리즘 구현에 많이 사용됨 In computer science, a tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes. A tree data structure can be defined recursively as a collection of nodes (sta.. Data Structure(1) Linked List (연결 리스트) 📌Linked List (연결 리스트) linked list는 떨어진 곳에 존재하는 데이터들을 포인터로 '연결'해서 관리하는 data structure 장점(배열의 단점 극복): 비연속적 데이터를 포인터로 연결하기 때문에 메모리를 미리 할당받을 필요가 없음 배열은 연속적으로 연결된 공간에 데이터를 나열하기 때문에 특정한 연결된 공간을 미리 할당받아야 함 단점: 각 데이터마다 다음 노드를 가리키는 주소(포인터)도 같이 저장해야하므로 저장공간 효율↓ 첫 노드(head)부터 쭈우우-욱 검색해야 해서 연결 정보를 찾는 시간이 필요하여 데이터에 접근하는데에 시간이 소요 (배열은 index로 바로 접근 가능) 중간에 데이터를 추가/삭제할 때, 추가적 작업이 필요 📌일반(간단한) linked list .. BAEKJOON #2920) 음계 # 내 풀이 num = list(map(int, input().split())) result = [] for i in range(len(num)-1): if num[i]+1 == num[i+1]: result.append("ascending") elif num[i]-1 == num[i+1]: result.append("descending") else: result.append("mixed") if "mixed" in result: print("mixed") elif "ascending" in result: print("ascending") else: print("descending") # 풀이 num = list(map(int, input().split())) ascending = True descend.. Recursive Call (재귀함수, 재귀호출) 재귀함수는 매우 많은 알고리즘에서 사용된다. 앞으로 다룰 quick sort와 merge sort 알고리즘을 공부하기 전, 이 알고리즘들에 쓰이는 전략인 Dynamic Programming(동적 계획법)과 Divide and Conquer(분할 정복)에 대해 공부하기 위하여 오늘은 재귀함수를 공부하여 보겠다. 즉, quick sort와 merge sort를 공부하기 위해 DP와 DC를 공부해야하고 이를 위해서는 기본적인 재귀함수(재귀호출/재귀용법/recursive call)을 알아야한다... ㅎㅎ(앞으로 더 배워야 할 알고리즘들이 많으니 기쁜 마음으로 차곡차곡 공부를 해보자^0^/) 📌재귀 함수 recursive call 재귀 함수란, 함수가 본인 함수를 다시 호출하는 함수를 말한다. 📌재귀 함수의 일반.. 탐색알고리즘(2) Binary Search (이진 탐색) Binary Search 이진 탐색 탐색 알고리즘 중 두번째, 이진 탐색이다. 순차 탐색은 그냥 말그대로 앞에서부터 쭈우우-욱 미련하게 찾는 것이었다면 binary search는 리스트를 반씩 쪼개면서 찾는 데이터가 없을 것이라고 판단한 반쪽 리스트는 과감히 버린다. 따라서 당연히 순차 탐색보다 계산량이 적다. 반복문을 쓰지는 않지만 재귀용법을 사용하여 그에 따른 시간 복잡도를 가진다. 알고리즘 구현 def binary_search(data_list, search): if len(data_list) == 1 and search == data_list[0]: return True if len(data_list) == 1 and search != data_list[0]: return False if len(.. 탐색알고리즘(1) Sequential Search (순차 탐색) 정렬 알고리즘 5개를 마치고, 이번 포스팅은 탐색 알고리즘의 시작으로 순차 탐색에 대한 포스팅이다. 탐색 알고리즘은 말그대로 여러 데이터 중에서 내가 원하는 데이터를 찾아내는 알고리즘이다. 이 중 순차탐색은 알고리즘/자료구조 강의 전체를 통틀어서 가장 쉬웠던 부분이다. 그냥 python 기본 문법 공부하는 정도의 난이도랄까..?ㅎㅎㅋ 간단히 포스팅해보도록 하겠다-! Sequential Search 순차 탐색 순차탐색은 원하는 데이터를 찾고자할 때, 데이터가 담겨있는 리스트에의 맨 처음부터 하나하나 순서대로 비교해가며 탐색하는 알고리즘이다. sequential search 또는 linear search 알고리즘이라고도 불린다. (뭔가 더 설명을 쓰고 싶지만 진짜 이게 끝이다. ,,,ㅎㅋㅋ) 알고리즘 구현 .. 정렬알고리즘 - Quick Sort (퀵 정렬) | C, Python 코드 구현 이제 재귀함수에 대해 공부했으니 이를 이용해 quick sort를 공부하여 보겠다. Quick Sort. 정렬 알고리즘의 꽃이라고 할 수 있는 알고리즘이다. 공부하면서 정말 quick이라는 말이 왜 붙었는지 알 정도로 이해하기 간단하고 구현하기 굉장히 편리했다. 특히 pythonic code로 구현하니 코드가 아주아주 간결하고 깔끔했다. 코드가 간결할 뿐만 아니라 시간 복잡도 측면에서도 지금까지의 정렬 알고리즘보다 낮아지는 경우가 가능하였다. 살펴보자. 📌Quick Sort 퀵 정렬 quick sort는 pivot(기준점)을 정해서, 기준점보다 작은 데이터는 왼쪽에, 큰 데이터는 오른쪽으로 모으는 과정을 반복하여 정렬을 하는 알고리즘이다. 나누어진 왼쪽과 오른쪽이 재귀용법을 사용해서 그 안에서 또 왼쪽과.. 정렬알고리즘 - Merge Sort (병합정렬) | C, Python 코드 구현 📌Merge Sort 병합 정렬 분할(Divide): 정렬하고자 하는 리스트를 같은 크기의 2개의 리스트로 분할한다. 정복(Conquer): 각 리스트를 정렬하고, 각 리스트의 크기가 더 분할 가능하다면 재귀적으로 분할 정복을 반복한다. 결합(Combine): 정렬된 각 리스트를 하나의 리스트로 합친다. 📌puedo code 구현 split 만약 리스트 개수가 한 개이면 해당 값 리턴 그렇지 않으면 리스트를 left와 right로 나누기 (재귀용법을 이용하여 리스트 개수가 한 개가 될 때까지(더이상 쪼갤 수 없을 때까지)) left = split(앞) right = split(뒤) left와 right 합치기 merge 정렬된 숫자들을 넣을 리스트 생성 (sorted) left와 right의 비교할 데이.. 정렬알고리즘- Selection Sort (선택 정렬) | C, Python 코드 구현 정렬 알고리즘 중 세번째이다. 선택 정렬이다. 개인적으로 bubble sort와 insertion sort보다는 직관적으로 더 쉽다고 생각이 들었다. 왜냐하면 selection sort는 그냥 전체에서 최솟값을 찾아서 앞으로 옮기는 걸 계속 반복하는 알고리즘이기 때문이다. 우리가 흔히 프로그래밍이아닌 현실에서 숫자들을 정렬한다고 하면 바로 이 selection sort와 같은 방법을 쓸 것이다. 📌선택 정렬 Selection Sort 선택 정렬이란, 먼저 최소값을 찾고 그 최소값을 정렬된 이후의 맨 앞 인덱스까지 옮기며 정렬하는 것이다. 즉, 주어진 데이터 중 최소값을 찾음 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함 pseudo code .. 정렬알고리즘 - Insertion Sort (삽입 정렬) | C, Python 코드 구현 계속해서 정렬알고리즘에 대하여 공부하고 있다. 오늘은 정렬 알고리즘 중 삽입정렬 insertion sort에 대하여 알아보겠다. 삽입정렬을 두 번째 인덱스부터 기준점으로 잡고 기준점에서 앞 데이터들과 비교하며 기준점 데이터를 삽입할 위치를 정하여 정렬하는 알고리즘이다. 📌삽입정렬이란 삽입정렬은 두 번째 index부터 시작하고, 이를 기준점으로 잡는다. 해당 인덱스 앞에 있는 데이터들과 비교하여 기준점의 데이터의 값이 앞 데이터들보다 더 작으면, 기준점을 그 앞 데이터의 뒤 인덱스로 복사한다. (기준점 바로 앞에 있는 값들부터 하나하나 비교하며 기준점이 더 크면 swap한다고 볼 수도 있겠다.) 기준점이 앞 데이터들 중에서 자신보다 더 큰 데이터를 만날 때까지 이를 반복하고, 큰 데이터를 만난 위치 바로 .. 이전 1 ··· 4 5 6 7 8 다음
