항해일지

배열 ( Array ) 📝 연속된 메모리 공간에 요소들을 저장하는 자료구조이다. 👍 장점 연속된 데이터 공간을 사용하고 있기 때문에 각 칸의 크기와 요소의 인덱스를 알고 있을 때 임의 접근이 가능하여 고정 시간을 가진다. 👎 단점 배열의 새로운 요소를 추가하거나 삭제할 때 해 연속된 모든 요소의 위치를 옮겨야 하기 때문에 추가•삭제가 힘들다. 배열을 미리 생성해 두는 방법도 있지만 이런 경우 사용하지 않는 메모리 공간이 발생할 수 있어 메모리 누수가 생길 수 있다. 연결 리스트 📝 각 원소들을 메모리 주소로 연결해 저장하는 자료구조이다. 👍 장점 각 원소를 주소 값을 참조하는 방식으로 연결 해두었기 때문에 원소를 추가하거나 삭제할 때 가리키고 있는 주소값을 변경하거나 추가로 가리키게 하면 되기 때문에 배..

이진 탐색 ( Birnary Search ) 🤔 단순 탐색과 문제점 사전에서 정지 라는 단어를 찾는다고 생각해보자. 보통의 사전은 자음과 모음 순으로 정렬되어 있다. 정렬되어 있다는 사실을 알았으니 우리는 ㄱ ~ ㅈ 까지 찾은 후 ㅏ ~ ㅓ 까지 찾아갈 것이다. 이렇게 앞에서부터 순서대로 찾아나가는 방법을 단순 탐색 이라고 부른다. 다만 이런 방식은 상당히 비효율 적일 수 있다. 만약 앞에서 32000번째 단어의 경우 찾기 위해 앞에서 부터 32000개의 단어를 확인 해보아야 한다. 💡 즉, M개의 정렬된 데이터를 찾기 위해 최대 M번 최소 1번 평균적으로 M/2번의 탐색 횟수가 필요하다. 👍 이진 탐색 ( Binary Search ) 단순 탐색(Simple Search) 방식은 데이터의 개수가 늘어남에..

균형 트리 (Balanced Tree) 이진트리는 그 균형이 맞지 않으면 검색 성능이 선형 탐색과 유사해진다. 한 방향의 트리는 연결 리스트와 같다. 이러한 문제를 해결하기 위해 균형 트리가 탄생하였다. 종류는 Red-Black Tree, B-Tree등이 있는데 이러한 균형 트리는 균형을 유지하기 위해 삽입 or 삭제시 스스로 균형을 유지해 나간다. 균형을 유지한 덕분에 균형트리는 O(logN)의 탐색 성능을 보장한다. B-Tree 균형트리의 한 종류로 자식 노드가 두 개로 고정된 이진 트리와 달리 자식 노드의 개수가 최대 M개인 트리로 자식 노드의 최대 개수를 차수라고 한다. 이 차수가 홀수인지 짝수인지에 따라 알고리즘이 많이 달라진다. 조건 B-Tree의 조건은 아래와 같다. 노드의 데이터 개수가 n..

해시 함수 문자열을 받아서 숫자로 반환하는 함수로 문자열에 대해 숫자를 할당(mapping)한다고 함. 해시 함수의 요건 일관성이 있어 같은 문자열에 같은 숫자를 할당해야함. 서로 다른 단어에 대해 서로 다른 숫자를 반환해야함. 서로 다른 단어에 대해 같은 숫자를 반환하면 이를 충돌이라고 하는데, 충돌이 많을 수록 좋은 해시 함수로 보기는 힘들다. 최대한 모두 다른 숫자를 반환하게 하여 충돌을 줄여야 함. 💡 충돌을 피하기 위한 방법 1. 낮은 사용률 - 해시테이블의 사용률(사용하고 있는 인덱스/전체 배열 크기)이 낮으면, 충돌이 일어날 가능성이 적다. 2. 좋은 해시 함수 - 해시 함수를 통해 반환되는 값이 고르게 분포되어 있어야 함. 해시 테이블 ( hash Table ) 필요 배경 책으로된 사전 처..