거누의 개발노트

트리란? 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조이다. 큐(Queue)와 스택(Stack)은 자료구조에서 선형 구조라고 한다. 선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미합니다. 비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어있습니다. 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다. 트리구조는 위 그림에서 보는 것 처럼 폴더 구조와 같습니다. 이진 트리 이진 트리는 최대 두 개의 자식을 가집니다. ( 0, 1, 2 ) 완전 이진 트리 완전 이진트리는 마지막 레벨을 제외 하고 모든 레벨이 완전히 채워져 있습니다. 마지막 레벨은 꽉 차 있지 않아도 되지만, ..

이번주는 폭풍의 시간이 었다. 자료구조를 배우고 알고리즘을 배우고 빠르게 진행된다. 빠르게 배우고 적용시켜서 문제를 풀려고 해도 잘 풀리지 않는게 코딩테스트 문제인거 같다. 1일차에는 알고리즘 개요와 배열을 간단히 배운다. (간단하지만 간단한게 아니다.) 알고리즘 개요 점근 표기법 알고리즘의 성능을 수학적으로 표기하는 방법이다. 알고리즘의 "효율성"을 평가하는 방법 점근 표기법의 종류 점근 표기법의 종류에는 빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법이 있다. 빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지, 빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기하는것이다. 예를 들어 빅오 표기법으로 표시하면 O(N), 빅 오메가 표기법으로 ..

해시테이블? 해시 테이블 또는 해시 맵은 키를 값에 맵핑할 수 있는 구조로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. 해시 테이블의 가장 큰 특징은 시간 복잡도가 O(1) 이라는 점이다. 덕분에 데이터에 양에 관계 없이 빠른 성능을 기대할 수 있다는 장점이 있다. 해시 함수? 해시함수는 임의의 길이의 데이터를 입력받아 일정한 길이의 비트열로 반환 시켜주는 함수이다. 입력값의 길이가 달라도 출력값은 언제나 고정된 길이로 반환한다. 동일한 값이 입력되면 언제나 동일한 출력값을 보장한다. ex) AFJQ..