목록Programming (52)
MJay
trie 혹은 prefix tree라 함은, 주로 스트링을 가지는 동적 셋 혹은 연관 배열을 저장하는데 사용되는 정렬된 트리 자료구조를 의미한다. 이진 검색 트리와는 다르게, 트리상에서의 노드들은 그 노드와 연관된 키를 저장하지 않는다. 이 대신, 트리상에서의 위치가 현재의 키를 나타낸다. 특정 노드의 모든 후손들은 그 노드에서와 동일한 prefix를 가지며, 루트 노드는 빈 문자열을 갖는다. 값은 모든 노드에서 존재하는 것이 아니고, 말단 노드(leaves) 혹은 특정 키에 해당하는 내부(inner) 노드에서만 존재한다. prefix tree의 공간사용을 최적화 하기 위하여, compact prefix tree가 구상되었다. trie라는 단어는 reTrieval이라는 단어에서 유래하였다. Trie를 왜..
스택이란제한적으로 접근할 수 있는 나열 구조이다. 접근 방법은 언제나 목록의 끝에서만 일어난다.LIFO-> Last in First Out으로 되어 있다.자료를 넣는 걸 Push자료를 빼는 걸 Pop이라고 한다.쓰임컴퓨터에서 포인터라고 하는 자료의 위치 표시자와 넣고 빼는 명령어를 사용해서 스택을 이용한다. 주로 함수를 호출할 때 인수의 전달 등에 이용된다. LIFO의 특징을 이용하여 역폴란드 표기법을 이용한 프로그래밍 언어인 포스등에서도 이용된다.스택(Stack)의 동작 출처 (1) 삽입 – Push스택(Stack)에 새로운 데이터를 삽입하는 작업을 push라고 한다. 이는 top 값을 하나 증가시킨 후 새로운 데이터를 삽입하도록 구현한다.(2) 삭제(추출) – Pop스택(Stack)에서 데이터를 제거..