Algorithm & Data Structure

선택 정렬

가장 최소인 값을 맨 앞 값이랑 바꿔주는 "선택" 정렬 패턴 파악 데이터 3개 (턴 2번, 1. 최솟값과 비교 2번 2. 최솟값과 비교 1번) 1. 턴 한번 5 4 2 2 4 5 데이터 4개 (턴 3번, 1. 최솟값과 비교 3번 2. 최솟값과 비교 2번 3. 최솟값과 비교 1번) 5 4 3 1 1 4 3 5 1 3 4 5 파악되는 중요 패턴은 다음과 같다. 1. 매 턴마다 앞 자리가 정해지면서 반복 횟수가 줄어든다. 2. (매 반복에서) 맨 앞 인덱스의 값과 최솟값을 바꾼다. psudo 코드 for i in range( len(data) -1 ): min = i for j in range( i+1, len(data) ) : if data[min] > data[j]: min = j swap(data[min..

버블 정렬

앞에서부터 2개씩 크기를 비교하여 정렬하는 "버블" 정렬 패턴 파악 데이터 2개 (턴 한번, 비교 1번) 1. 턴 한번 5 2 2 5 데이터 3개 (턴 두번, 비교 2번) 1. 턴 한번 5 4 2 4 5 2 2. 턴 두번 4 2 5 2 4 5 데이터 4개까지 해보면 패턴이 보일 것이다. 1. 한 턴에서 비교 횟수 : [데이터 길이 -1]번 진행 2. 턴 횟수 : [데이터 길이 -1]번 진행 3. 한 턴이 마무리되면 가장 큰 값은 맨 뒤에 위치하게 된다. -> 매 턴마다 비교 횟수를 줄여도 된다. psudo 코드 for index in 데이터 길이 -1 만큼 반복: for 데이터 길이 -1 -index 만큼 조건 체크: if 앞데이터 > 뒤데이터: swap(앞, 뒤) * 스왑이 일어났는지 체크해서, 이미 ..

[Concept] 해쉬 테이블 (Hash Table)

대표적인 데이터구조로 해쉬 테이블이 있습니다. Hash Table 키(key)에 데이터(Value)를 저장하는 데이터 구조 예) 파이썬 딕셔너리 타입 보통은 배열로 미리 Hash Table의 사이즈만큼 생성 후에 사용하지만 파이썬은 그럴 필요 X 용어 해쉬(Hash) : 임의 값을 고정 길이로 변환하는 것 해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 (데이터를 저장할 공간 :Slot) 해싱 함수 : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 key가 입력, 해쉬 주소(해쉬 값)가 출력 해쉬 값 or 해쉬 주소 : Key를 해싱함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 쉽게 찾을 수 있습니다. 저..

[Concept] 시간 복잡도

알고리즘에는 다양한 방법이 있습니다. 하나의 문제를 푸는데도 다양한 풀이 방법이 있는데, 이중 무엇이 정답이라고는 할 수 없지만, 더 나은, 더 좋은 알고리즘을 고를 수 있습니다. 그 (정량적인) 기준이 되는 것이 속도와 메모리공간입니다. 문제를 푸는 데에 빠르게 풀 수 있고, 더 적은 메모리양을 쓰는 알고리즘이 좋은 알고리즘이라 할 수 있습니다. 대표적으로 알고리즘의 복잡도를 계산할 때 시간복잡도와 공간복잡도를 체크합니다. 시간 복잡도: 알고리즘 실행 속도 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈 ex)변수 사용갯수, 메모리 etc.. 시간 복잡도 시간 복잡도는 말그대로 알고리즘을 실행하는데 걸리는 속도를 의미합니다. 프로그래밍에서 이 속도, 즉 시간 복잡도에 가장 영향을 많이 미치는 요소는 반..

[Concept] 더블 링크드 리스트 (double linked list)

이번 글에서는 더블 링크드 리스트 (이중 연결 리스트) 에 대해 적어보겠습니다. 이전 글에서 적었던 일반 링크드 리스트는 데이터를 조회할 때 head, 즉 앞에서부터 찾아가는 방식이었습니다. But, 만약 데이터가 20000개가 있고, 맨 마지막 데이터를 조회하고자한다면, 20000번 조회를 해야하는거겠죠? 대신 뒤에서부터 조회한다면 어떨까요? 즉, 앞쪽의 데이터를 조회할 떄는 앞에서부터, 뒤쪽의 데이터를 조회할 때는 뒤에서부터 찾아나갈 수 있는 리스트가 더블 링크드 리스트 입니다. 이전 기본 연결 리스트의 노드에는 데이터와 next 주소만 있었다면, 더블 연결 리스트에는 prev 주소도 함께 저장됩니다. 이전 기본 연결 리스트에서는, self.head()만 지정했다면, 더블 연결 리스트에는 self.t..

[Concept] 재귀함수와 연결리스트(linked list)

패스트 캠퍼스 알고리즘 강의를 듣고 정리한 글입니다. 재귀함수 재귀란 컴퓨터 과학에 있어서 재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출의 형태로 많이 사용된다. - 위키백과 - 재귀함수는 함수가 자신을 정의할 때 다시 자신(함수)을 호출하는 함수입니다. 자칫하면 무한 반복이 될 수 있기 때문에 종료 조건을 무조건 추가해주어야 합니다. 하나의 예를 봅시다. def recursive(data): if data