persistent linked list이용한 문자열 변화 추적하기

1. persistent linked list “퍼시스턴트(Persistent) 연결 리스트”는 한 번 만든 리스트를 “불변(immutable)”으로 유지하면서도, 수정할 때마다 과거 버전까지 그대로 보존할 수 있게 해 주는 연결 리스트입니다. 1) 왜 ‘퍼시스턴트’인가?일반 연결 리스트는 노드 값을 바꾸거나 추가·삭제하면 기존 상태가 없던 일처럼 사라집니다.반면 퍼시스턴트 리스트는 “이전 상태”를 그대로 남겨 두고, 수정 후 새 리스트 버전을 만들어 줍니다.즉, 여러 시점(version)의 리스트를 동시에 관리할 수 있죠. 2) 어떻게 불변성을 지키나?노드는 절대 수정하지 않는다.새로운 내용만 새 노드로 생성하고,변경되지 않은 구간은 **기존 노드를 그대로 재사용(공유)**한다.각 버전은 “헤드 포인터..

• format_list_bulleted 알고리즘/고급 자료구조
• · 2025. 6. 23.
• textsms

python 리스트를 이용해 trie 구현하면서 개념 익히기

python에서는 trie가 class로 구현된 경우가 많아 꺼렸는데... 배열로 구현하는 법을 익혀서 기록해보기 https://deepdata.tistory.com/659 문자열 자료구조 Trie 알고리즘 기본기 배우기1. 문자열 단어 저장 'hello', 'hi', 'hey' 등을 저장하고자 할때, 생각할 수 있는 방법중 하나는 dictionary에 저장하는 것이다 d = {'hello':1, 'hi':1, 'hey':1} 단어를 key값으로 저장해두면, 특정 단어를 찾고자deepdata.tistory.com https://blog.encrypted.gg/1059 [실전 알고리즘] 0x1F강 - 트라이안녕하세요, 드디어 마지막 강이라니 가슴이 웅장해집니다. 마지막인만큼 난이도도 끝판왕일 수 있지만 개..

• format_list_bulleted 알고리즘/고급 자료구조
• · 2024. 5. 14.
• textsms

문자열 자료구조 Trie 알고리즘 기본개념 이해하고 삽입, 추가 직접 구현해보기

1. 문자열 단어 저장 'hello', 'hi', 'hey' 등을 저장하고자 할때, 생각할 수 있는 방법중 하나는 dictionary에 저장하는 것이다 d = {'hello':1, 'hi':1, 'hey':1} 단어를 key값으로 저장해두면, 특정 단어를 찾고자 할때, d['hello']같이 key로 접근해서 1인지 확인해보면 되니까 O(1)로 바로 찾을 수 있는 장점이 있다 하지만 공간복잡도 측면에서 단어가 100만개가 있다면 100만개의 공간이나 필요할 것이다  2. Trie 자료구조 Trie 자료구조는 효율적인 공간복잡도를 가지면서도, 시간복잡도도 충분히 효율적으로 만드는 문자열 저장 자료구조라고 할 수 있다. dictionary보다 조금 느리지만, 단어를 찾는데 단어를 구성하는 알파벳(문자)개수만..

• format_list_bulleted 알고리즘/고급 자료구조
• · 2023. 1. 23.
• textsms