본문 바로가기

바킹독의실전알고리즘

[바킹독의 실전 알고리즘] 0x04강 - 연결 리스트
Algorithm 2022. 11. 26. [바킹독의 실전 알고리즘] 0x04강 - 연결 리스트 - 정의와 성질 - 연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다. 이중 연결 리스트는 단일 연결 리스트와 달리 주어진 원소의 이전 원소를 알 수 있다. 다만 원소가 갖고 있어야 할 정보가 1개 더 많아져서 메모리를 더 많이 차지하게 된다. 원형 연결 리스트는 원소의 처음과 끝이 연결되어 있는 리스트이다. 배열과 달리 연결 리스트는 다음 원소의 주소 값 또는 이전 원소의 주소 값을 갖..
[바킹독의 실전 알고리즘] 0x03강 - 배열
Algorithm 2022. 11. 25. [바킹독의 실전 알고리즘] 0x03강 - 배열 - 배열의 정의 - 배열을 선언한 뒤에 배열의 길이를 변경하는 게 불가능하지만, 자료구조로써의 배열에서는 길이를 마음대로 늘리거나 줄일 수 있다고 가정하자. - 배열의 성질 - 1) 배열은 메모리 상에 원소를 연속하게 배치한 자료구조이기 때문에 k번째 원소의 위치를 바로 계산할 수 있다. k번만큼 이동하면 되기 때문에 시간복잡도 O(1) 2) 다른 자료구조들과 다르게 추가적으로 소모되는 메모리 양이 거의 없다. 3) 메모리 상에 데이터들이 붙어있기 때문에 Cache hit rate가 높다. 4) 메모리 상에 연속한 구간을 잡아야 하기 때문에 할당에 제약이 걸린다. - 배열의 기능(시간복잡도) - -배열을 특정 값으로 초기화시키는 방법- 1) cstring의 memset 함수는 memset(포인터(배열의 ..

티스토리툴바