자료구조

해시 테이블이란? 해시 테이블은 key - value 시스템의 자료구조다다. key 는 배열의 index 처럼 value 에 바로 접근할 수 있도록 하는 값이다. index 와 달리 문자열, 파일 등 다양한 데이터가 가능해서 value와 관련 있는 값으로 설정할 수 있다. fruits = { key: "사과", value: "맛있다", key: "복숭아", value: "딱딱한게 맛있다." } //key값으로 데이터 바로 접근 fruits["사과"] -> "맛있다" 어떻게 가능하지? 사실 해시테이블의 내부는 배열과 비슷하게 index 와 value 로 구성되어 있다. key 는 hash function 을 통해 해시 코드로 계산되고, 이 해시코드는 index 로 환산된다. hash function 은 입..

시간복잡도란? 알고리즘의 성능을 측정하는 방법이다. 실제로 걸리는 시간이 아니라, 이 알고리즘이 입력되는 데이터의 양에 따라 얼마나 많은 단계를 거쳐야 하는지의 비율을 말한다. 빅오(Big-O) 란? 시간 복잡도를 표기하는 방법 중 대표적으로 쓰이는 표기법이다. 입력되는 데이터의 개수를 n이라고 하면 O(n) 같이 표기한다. 참고로, 10개, 100개 데이터에 따른 성능 차이는 미미하다. 하지만, 100000개, 100000000개의 경우를 보면 성능 차이가 눈에 띄게 난다. 그러니 적은 양의 데이터의 경우는 고려하지 않는다. 또 빅오는 대충 이런 비율로 증가할 것이다~ 라는 의미에서 사용되므로 일정하게 증가하는 상수항은 의미가 없어 표기하지 않는다.(n*n-1 이나 n*n 이나 의미는 같으니...) 또..

연결리스트란? 배열이 메모리의 공간을 연속적으로 할당받은 형태라면, 연결리스트는 연속적이지 않고 빈 공간 어디든 할당받는 형태다. 데이터가 여기저기 산재해있으니 각 데이터는 자신의 다음 데이터가 어디에 있는지 알아야 한다. 그래서 연결리스트의 데이터는 값 뿐만 아니라 다음 데이터의 주소값도 가지고 있다. 연결리스트의 한 데이터(데이터와 주소값)을 노드(Node) 라고 부른다. 노드들은 다음 노드의 주소를 가지고 있음으로써 연결된다. 맨 끝의 노드는 자신이 끝이라는 걸 알리기 위해 Null 값을 가진다. 기본적인 연결 리스트는 단방향으로만 연결되어 있어 현재 노드의 이전 노드를 알 수 없다. 이를 개선한 것이 이중 연결리스트 (Doubly Linked List) 이다. 현재 노드가 이전/다음 노드의 주소값..

배열이란? 배열은 데이터를 메모리에 연속으로 넣어두는 형태다. 맨 첫번째 칸의 주소만 가지고 있으면 그 다음 칸의 주소도 바로 알 수 있기 때문에 주소로 바로 접근해 빠르게 읽을 수 있다. 배열을 할당할 때는 arr = a[8] 처럼 메모리에게 '얼마만큼' 연속적으로 차지할지 알려줘야 한다. 일부 프로그래밍 언어에서는 길이를 알려주지 않아도 내부적으로 알아서 할당해주고 확장한다. 데이터 접근 시에는 주소를 쓰지 않고 arr[1] 처럼 인덱스라는 0부터 시작되는 숫자를 사용한다. 배열의 이름이 첫번째 주소를 가지고 있고, 칸마다 +1 되는 인덱스를 이용해 다음 주소를 알아내는 것이다. 인덱스는 0부터 시작하기 때문에 length - 1 까지다. 배열의 연산 READ 인덱스를 이용하면 RAM에 바로 접근해 ..

알고리즘과 자료구조 문제를 어떻게 해결할지에 대한 일련의 단계를 알고리즘이라고 한다. 어떤 문제에 어떤 알고리즘을 쓰냐에 따라 처리 시간이 달라진다. 이 문제를 해결하는 과정에서 수많은 데이터를 처리하는데, 데이터를 체계 없이 저장하면 한정된 메모리 공간을 비효율적으로 쓰게 된다. 자료구조는 데이터를 효율적으로 처리하기 위해 메모리에 어떻게 저장하고 어떻게 관리할지의 방법을 말한다. 개발할 때 우리는 얼마나 빨리 해결할 수 있을지와 얼마나 메모리 공간을 절약할 수 있을지에 초점을 둔다. 적합한 알고리즘과 자료구조를 선택하면 처리 효율성을 높일 수 있다. 자주 쓰이는 자료구조는 대부분 프로그래밍 언어에 따라 이미 구현된 라이브러리가 있기 때문에 모든 로직을 구현하지 않아도 된다. 자료구조와 알고리즘을 공부..