자료구조

0. Intro- 자료구조에서 꼭 알아야하는 연결리스트에 대해 알아보자.- 해당 게시글에서는 단방향 연결리스트만 서술하고자 한다.1. 리스트- 리스트(list | 파이썬 내장 리스트와 다름)는 순서가 있는 데이터를 나열한 자료구조- 실생활 예) 학생 명단, 상점의 판매 품목, 실시간 급상승 검색어... 2. 노드- 연결리스트를 구성하는 각각의 원소- 데이터와 포인터(reference)를 가진다. 2.1. 노드 클래스 구현class Node: def __init__(self,data=None,next = None): self.data = data self.next = next #ex 1n0 = Node('A')n1 = Node('B')n2 = Node('C')n0.next =..

0. Intro- 해당 게시글에서는 어떤 배열의 최솟값과 최댓값을 구할 수 있는 알고리즘을 구현하고자 한다.- 다른 알고리즘 게시글에 비해 난이도가 상당히 쉬우니까 가볍게 보고 가자. 1. minimum- 최솟값을 구하는 코드를 구현해보면 다음과 같다.def minimum(arr): min = arr[0] for i in arr[1:]: if min > i: min = i return min - 배열을 한번씩 전부 돌면서 최솟값을 갱신하는 알고리즘이다.- 시간복잡도는 O(N)이 된다. 2. maximum- 최댓값을 구하는 코드를 구현하면 다음과 같다.- 최솟값을 구하는 코드와 크게 다르지 않는다.def maximum(arr): max = arr[0] ..

1. Bucket Sort?- Bucket Sort는 데이터를 일정한 범위로 나눈 여러 버킷에 분배하고,- 각 버킷 내부에서 정려한 후 각 버킷을 합쳐서 전체 데이터를 정렬하는 알고리즘이다.- 마치 다음 그림과 같다. - 그림을 보면 알 수 있겠지만,- 데이터가 특정 범위 안에서 균등하게 분포된 경우 매우 효율적으로 작동한다.- 주로 0과 1사이의 실수나 버뮈가 제한된 정수를 정렬할 때 사용된다. 2. Bucket Sort의 알고리즘i) 버킷 분할:- 데이터를 특정 구간으로 나누어 각 구간을 '버킷'이라고 정의한다.- 이때 버킷의 개수는 데이터의 분포에 따라 적절히 설정하는 것이 중요하다. ex) 데이터가 0과 1사이의 실수라면 각 버킷은[0,0.1) , [0.1,0.2), ... , [0.9,1)로 설..

1. Counting Sort?- Counting Sort는 정수로 표현할 수 있는 데이터에 대해 효율적으로 작동하는 O(n) 정렬 알고리즘.- 정렬의 대상이 되는 데이터 값의 범위가 명확할 때 주로 사용.- Counting Sort는 비교 정렬 알고리즘이 아닌 분포 정렬 알고리즘이다.  2. Counting Sort 알고리즘i) 입력 배열과 범위 설정- 주어진 입력 배열이 A라고 하고, 배열의 길이를 n이라고 하자.- 데이터 값은 0 이상 k이하인 양수라고 가정해보자. (이때 k == max(A)) ii) 카운트 배열 초기화- C라는 배열을 만들고, 길이를 k+1로 설정 (또는 max(A) - min(A)로 설정)- C[i]는 입력 배열에서 값이 i인 요소가 몇 번 등장하는지 저장함- C의 초기값은 전..