매석의 메모장

삽입, 검색, 삭제 배열 또는 연결 리스트는 평균적으로 빅세타 n, 이진 검색 트리는 평균 빅세타 logn, 균형 이진 검색 트리는 최악의 경우 빅세타 logn, 균형 다진 검색 트리는 최악의 경우 빅세타 logn 정도가 걸린다. ​ 이것을 더 빠르게 사용하기 위해 해시 테이블을 사용한다. 이는 평균적으로 빅세타 1이 걸린다. 해시 테이블 출처 : 쉽게 배우는 자료구조 with 파이썬 검색 키 값을 해시 함수를 통해 해시 테이블에 적재하는 것을 말한다. 검색, 삽입, 삭제에 극한에 달하는 효율을 가진다. 해시 테이블에 적재율이 올라갈수록 충돌 확률이 올라가며, 이는 성능 저하를 의미한다. 충돌은 같은 해시 테이블 자리에 값이 다시 배정되는 것을 말하며 충돌 처리가 해시 테이블에서 중요하다. 출처 : 쉽게..

색인 레코드는 개체에 대한 모든 정보가 들어 있다. 예시로 사람 레코드에는 주민번호, 이름, 집주소 등의 정보가 포함되어 있다. 이들 각각의 정보를 나타내는 부분은 필드라고 한다. ​ 색인의 결국 개체의 레코드를 검색하는 것을 의미한다. 레코드를 구분할 수 있는 필드를 색인으로 사용하는데 키라고 한다. 색인은 key+해당 레코드의 page 번호로 구성하곤 한다. ​ 배열에 키를 정렬시켜 색인을 만들면 검색에선 빅세타 lonN, 삽입과 삭제에선 빅세타 N만큼 시간이 들어 색인의 크기가 크면 사용할 수 없다. 그래서 이를 구현할 때 검색 트리가 사용된다. 검색 트리 출처 : 쉽게 배우는 자료구조 with 파이썬 검색 트리는 이진 검색 트리와 다진 검색 트리, 균형 검색 트리로 나누어지는데 이번 포스팅에서는 ..

퀵 정렬 선행 작업을 한 다음 재귀적으로 작은 문제를 해결하는 방식의 정렬이다. 기준 원소를 하나 잡아 작은 원소와 큰 원소 그룹을 나누어 기준 원소의 좌우로 분할하는 방법이다. 출처 : 쉽게 배우는 자료구조 with 파이썬 ​ 1~4구역까지 나누어 분할하여 정렬을 수행한다. 1구역은 기준 원소보다 작은 원소들 즉 왼쪽, 2구역은 기준 원소보다 크거나 같은 원소들 즉 오른쪽, 3구역은 아직 정해지지 않은 원소들 즉 아래에서 흰 색 부분, 4구역은 기준 원소 부분이다. 출처 : 쉽게 배우는 자료구조 with 파이썬 위에서 보면 기준 원소를 정하고 정렬되지 않은 3구역 원소들을 기준 원소와 비교해 1구역과 2구역으로 나누는 과정을 반복한다. 최종적으로 기준 원소를 1구역과 2구역 사이에 배치한다. 이후 1구..

정렬 정렬은 원소들을 순서대로 배열하는 것을 말한다. 크기가 작은 순 혹은 큰 순으로 정렬하기도 한다. ​ 정렬 알고리즘은 대략 3개의 그룹으로 나뉜다. ​ -기본 정렬 - 빅 세타 n^2 선택 정렬 버블 정렬 삽입 정렬 ​ - 고급 정렬 - 빅 세타 nlogn 병합 정렬 퀵 정렬 힙 정렬 셸 정렬 ​ - 특수 정렬 - 빅 세타 n 계수 정렬 기수 정렬 버킷 정렬 ​ 기본 정렬 선택 정렬 리스트의 가장 큰 원소를 찾아 리스트의 맨 끝자리 원소와 자리를 바꾸고, 정렬된 맨 오른쪽 부분은 제외한 상태로 반복하여 최종적으로 리스트를 오름차순 정렬하는 방법이다. 출처 : 쉽게 배우는 자료구조 with 파이썬 출처 : 쉽게 배우는 자료구조 with 파이썬 파이썬으로는 위와 같이 구현할 수 있다. 두 수를 비교하는..

데이터 집합 - 정적 데이터 집합 : 한번 구축되고 나면 변하지 않음 ​ - 동적 데이터 집합 : 데이터가 계속 변함 Dictionary(Table) : 삽입, 삭제, 검색을 지원하는 동적 데이터 집합 (배열, 리스트, 해시 테이블 등) 우선순위 큐 : 삽입, 최우선 원소 삭제, 최우선 원소 검색 지원하는 동적 데이터 집합(배열, 리스트 힙 등) ​ -> 테이블은 삭제할 원소를 제공하지만, 우선순위 큐는 가장 높은 우선순위를 가진 원소만 삭제 가능하다. -> 삽입의 경우 둘 다 삽입할 원소를 제공한다, 또한 값의 중복은 우선순위 큐만 허용한다. 우선 순위 큐 배열 ,리스트, 연결리스트 등의 선형 자료구조로 구현 가능하지만, Heap으로 구현하는 것이 효율적이다. 우선순위 큐는 우선순위를 관리하기 위한 특..

스택 LIFO 구조로 마지막에 넣은 것이 처음으로 나가는 구조이다. 예시로 쌓여있는 식판이 있다. 출처 : 쉽게 배우는 자료구조 with 파이썬 기본적으로 push는 append의 동작을 수행하고, pop은 top 값을 제거한다. 원하는 값을 삭제하기 위해서는 따로 지정이 필요하다. ​ 출처 : 쉽게 배우는 자료구조 with 파이썬 정적 영역은 컴파일 직후 상대적인 위치를 정할 수 있는 정보가 있고, 동적 영역은 수행을 시작한 후에야 알 수 있다. 즉 정적은 프로그램 수행 코드와 프로그램이 끝날 때까지 존재하는 데이터가 있고, 동적은 프로그램 수행 중 할당받는 메모리(힙)와 다른 함수 호출할 때 정보를 저장하는 스택이 있다. 리스트를 이용한 스택 리스트를 이용하여 스택을 구현하면 삽입은 append(값)..

리스트 출처 : 쉽게 배우는 자료구조 with 파이썬 위와 같이 배열 리스트로 구현하는 것과 아래와 같이 연결 리스트로 구분하는 형식이 있다. 보편적으로 배열 리스트를 자주 사용하는데, 아래와 같은 객체 구조를 가진다. 출처 : 쉽게 배우는 자료구조 with 파이썬 배열 리스트 즉 내장 리스트는 한계를 가진다. 아래 사진과 같이 3번 원소에 추가하기 위해 뒤의 원소를 모두 shift한다. 즉 추가 혹은 제거할 때 이러한 불필요한 shift를 거치는 등 비효율적이다. 그렇기에 이를 해결할 연결 리스트를 사용하는 것이다. 출처 : 쉽게 배우는 자료구조 with 파이썬 연결 리스트 연결 리스트는 배열의 공간 낭비를 피할 수 있는 자료구조이다. 원소가 추가될 때마다 공간을 할당받아 추가하는 동적 할당 방식을 따..

불변 타입과 가변 타입 출처 : 쉽게 배우는 자료구조 with 파이썬 id를 확인해보면 정수의 경우 값이 바뀌게 된다. 이는 불변이기에 그 자리에서 값을 바꿀 수 없어 다른 자리에 복사해 바꾼다. 리스트는 그 자리의 내용을 바꿀 수 있어 id값이 변하지 않는다. ​ (불변 : 숫자, 문자열, 튜플 가변 : 리스트) 복사호출, 참조호출, 할당호출 출처 : 쉽게 배우는 자료구조 with 파이썬 (a), (b)의 경우는 복사호출로 값이 복사되어 파라미터로 전달되는 형태다. (c), (d)의 경우는 참조호출로 그 값의 래퍼런스를 넘긴다. 그렇기에 결과적으로 단순 복사의 경우 x의 값이 5, 주소를 넘긴 경우 10의 결과가 나온다. ​ 출처 : 쉽게 배우는 자료구조 with 파이썬 할당 호출의 경우 불변 타입이면..

입력의 크기 출처 : 쉽게 배우는 자료구조 with 파이썬 각 알고리즘 마다 수행 시간이 다르다. 입력의 크기가 작으면 알고리즘 마다의 시간 차이도 적어서 괜찮은 경우가 많지만, n의 크기가 커질수록 그 시간 차이도 상당히 커지기에 알고리즘의 성능이 중요해진다. ​ 출처 : 쉽게 배우는 자료구조 with 파이썬 위와 같이 1번째는 n이 엄청 커져도 결국 나누기 2를 하기에 상수 시간이 걸린다. 2번째 경우는 n이 커질수록 for문의 반복횟수가 늘기에 n에 비례한다. 3번째 경우는 n이 커질수록 이중 for문과 수행시간을 확인해보면 n(n-1)/2로 n제곱에 비례한다. 알고리즘 복잡도 점근적 복잡도 : 입력의 크기가 충분히 클 때의 복잡도 출처 : 쉽게 배우는 자료구조 with 파이썬 차례대로 위의 기호는..

ㅈ자료구조 데이터를 저장, 조직, 관리할 때 사용하는 방법을 말한다. 컴퓨터 프로그래밍 언어에서는 효율적인 데이터의 형태를 사용하는 것이 중요하다. ​ 출처 : 쉽게 배우는 자료구조 with 파이썬 ​ 자료구조는 아래와 여러 종류로 나뉘어진다. 출처 : 쉽게 배우는 자료구조 with 파이썬 ​ ​ 동일한 type을 가지는 배열, 리스트 중간에 데이터를 삽입하거나 삭제할 때 사용하는 링크드 리스트, 행과 열을 가진 2차원 데이터를 사용할 때는 행렬, LIFO 방식의 스택, FIFO 방식의 큐 등 다양한 형태가 있다. 자료구조와 알고리즘 자료구조는 부품으로, 알고리즘은 설계도 정도로 표현할 수 있다. 이 둘이 합쳐져 완성품 즉 프로그래밍 언어로 나타낼 수 있다. ​ 알고리즘은 자연어, 순서도, 프로그래밍 언..