리스트 검색 결과

해당 글 4건
LRU 알고리즘 : 리스트를 활용해서 구현해 봅시다.

고급 자료구조 이론에 들어가기 전에, 복습 겸 코딩 테스트에 자주 나오는 LRU 알고리즘을 간단하게 구현해 보도록 하겠습니다. 어떠한 페이지를 찾아야 한다고 해 봅시다. 메모리에서. 그런데, 그 페이지가 없어요. p라는 페이지가. 이 때, 메모리에서 어떤 페이지를 제거해야 할까요? 가장 오래 전에 사용이 된 것을 제거하는 것을 LRU 알고리즘이라고 합니다. 약어로는 Least Recently Used한 것을 제거하는 것이죠. 보통, 이러한 문제를 만났을 때, 저는 map 2개로 많이 코딩하라고 이야기를 합니다. 그런데, STL을 쓸 수 없는 환경에서는 어떻게 해야 할까요? 코딩하기도 어려운 레드 블랙 트리를 500줄 가까이 작성해야 할까요? 아니면 포인터의 향연에서 벗어날 수 없는 skip list를 작..
자료알고/자료구조 2019. 9. 23. 21:33
백준 1406 에디터 : List를 이용해서 해결해 봅시다.

링크드 리스트를 이용해서 간단한 편집 프로그램, 그러니까 vim과 같은 것들을 구현할 수 없을까요? 물론, 실제로 제가 구현할 것은 이것보다는 간단한 녀석입니다. 보통, 자료구조 프로젝트 때 적지 않게 하실 수도 있을 듯 싶네요. 사실 기능은 생각보다 단순해 보입니다. 커서를 이동시킵니다. 그리고 커서 앞에 문자를 추가시킵니다. + 앞에 't'를 추가시켰습니다. 이게 add 연산입니다. 아니면, 커서 앞에 있는 문자를 제거할 수도 있어요. 예를 들어서, 여기에서는 ( 앞에 있는 y라는 문자를 제거했습니다. 이런 간단한 편집 프로그램은 어떻게 구성하면 좋을까요? 단, 삽입, 삭제, 커서 이동 쿼리가 최대 60만개 들어옵니다. 배열은 장점이 무엇인가요? cache friendly 하다는 겁니다. 단점이 무엇..
자료알고/자료구조 2019. 8. 4. 00:57
이중 연결 리스트 : 노드를 연결하는 포인터가 2개다.

보통 C++의 STL에서는 double list를 많이 쓰는데요. 노드를 가리키는 포인터가 2개입니다. 각각 이전 것과, 다음 것을 가리키고 있습니다. 실제로, 이전 것도 가지고 있으면, 삭제하거나, 들어가야 하는 위치를 안다고 했을 때, 빠르게 자료구조에서 데이터를 삭제하거나, insert를 할 수 있어요. 기준 위치로부터 이전 노드의 주소도 알고 있기 때문입니다. 오늘은 이중 연결 리스트를 구현 해 보도록 하겠습니다. 먼저 node형 구조체는 다음과 같이 선언합니다. 각각, data를 담아두는 필드와, 이전 것 prev, 그리고 next를 가리키는 요소를 저장하고 있습니다. 다음에 head와 tail이 있는데요. 이것은 각각 리스트의 시작 위치와 끝나는 위치를 나타냅니다. 그러면 연결 리스트를 초기화..
자료알고/자료구조 2019. 7. 27. 17:30
링크드 리스트 : 왜 순회 시간이 배열보다 오래 걸릴까요?

리스트와 배열의 차이점은 면접에서 자주 나오는 질문 중에 하나입니다. 저에게 메일로 질문이 들어온 것 중 하나는, 순회 속도가 어떻게 차이가 나느냐였습니다. n이 작을 때는 별 차이가 없을 수도 있습니다. 하지만 n이 3000 ~ 4000만 정도만 되도 이야기가 달라집니다. 배열은 순차적으로 저장이 되지만, 리스트는 그렇지 않습니다. cache를 이용하기 좋은 구조는 리스트보다 배열이라는 겁니다. 정말 그런지 실험을 해 봅시다. 배열과 링크드 리스트의 순회 성능 테스트를 위한 코드를 작성해 봅시다. node형을 하나 선언해 주었는데요. data 필드와, 다음 주소를 가리킬 필드를 선언해 주었습니다. 단일 링크드 리스트는 포인터가 1개, 더블은 2개일 거에요. C++의 리스트는 더블로 구현이 되어 있습니다..
자료알고/자료구조 2019. 7. 4. 18:08