자료구조 검색 결과

해당 글 34건
java hashset : 어떻게 구현이 되어 있을까요?

java의 hashset은 어떻게 동작할까요? hashmap과 다른 점은 map은 Key로부터 Value를 뽑아올 수 있지만, set은 Key값만을 중요하게 여긴다는 것입니다. 그런데, 뭔가 이상하지 않나요? HashMap하고, Set은 그것 말고는 거의 동일한 기능을 수행합니다. 상식적으로 생각해 보았을 때, HashSet 기능들을 일일히 다 구현을 하는 게 효율적일까요? 아니면 이미 구현된 HashMap의 기능을 이용하는 게 효율적일까요? 후자일 겁니다. 이 정도만 이해하셨다면, 이 글의 90%를 이해하신 겁니다. 나머지 10%는 밑에서 후술하도록 하겠습니다. 예제 프로그램을 보겠습니다. 간단하게 HashSet hs를 선언했습니다. 이것은 Integer를 Key로 가지는 자료 구조입니다. 안에 필드를..
레퍼런스/분석 2020. 8. 8. 21:58
스택계산기 구현 : 연산자 우선순위와 결합 순서만 생각해 봅시다.

안녕하세요. 오늘은 간단하게 스택 계산기 프로그램을 만드려고 합니다. 일단 괄호가 없는 유효한 식은 숫자 (연산자 숫자)* 이런 패턴으로 들어올 겁니다. 예를 들어 3도 유효한 계산 식입니다. 그리고, 3*7-2도 유효한 식입니다. 연산자는 *과 +, -만 들어온다고 가정해 보겠습니다. 먼저 우선순위부터 set 하도록 하겠습니다. *는 +, -보다 우선순위가 높으니, *의 priority를 0으로, +과 -를 1로 설정하였습니다. 11번째 줄이 그러한 일을 수행합니다. 그리고, ArrayList인 num과 op는, 수식으로부터 들어온 수와 연산자를 순서대로 넣어놓았습니다. 예를 들어서 2-3+7이 들어왔다면, num에는 2, 3, 7 순서대로 들어가고, op에는 -와 +이 순서대로 들어가 있습니다. 이제..
자료알고/자료구조 2020. 7. 2. 02:21
trie에서 공간을 줄이기 위해 포인터를 어떻게 쪼갤까요?

안녕하세요. 백준에서 chogahui05로 활동하고 있는 조경완입니다. 트라이에서 x진법으로 쪼갠다. 무슨 소리일까요? 사실 Trie가 어떤 것을 처리하기 위한 자료구조인지는, 카카오 문제에 출제되어서 익숙하신 분들이 많으실 거라고 생각합니다. 여기서 한 단계 더 깊이 들어가 보도록 하겠습니다. 공간을 줄이기 위해서는 어떻게 잘 쪼개야 할까요? 먼저 소문자로만 이루어진 문자열들을 Trie에 넣었을 때 상황을 생각해 보겠습니다. 문자열들의 길이 합은 10만을 넘지 않는다고 해 보겠습니다. 그리고 소문자만 나온다고 해 보겠습니다. 그러면, 다음과 같이 정적 Trie를 구축할 수 있을 겁니다. 여기서 26은 다음을 의미합니다. 'a'가 나왔을 때, 'b'가 나왔을 때, ... , 'z'가 나왔을 때 어디로 갈..
자료알고/자료구조 2020. 5. 5. 21:31
event driven : ps 문제에서 간단하게 활용해 봅시다.

이벤트를 넣어두고 그것을 활용한다. 작년에 스터디를 하면서 처음 들어본 말이였습니다. 사실, Java에서 mouse event listener와 같은 것이나 call back 패턴에서만 쓰이는 줄 알았기 때문입니다. 그런데, 특정 문제에서 이것을 잘 활용하면 생각보다 간단하게 풀 수 있습니다. Egg라는 문제를 보도록 하겠습니다. 이 문제를 간단하게 설명하면 아래와 같습니다. 생각보다 쉽지 않습니다. 그런데, 점들이 삭제되거나, 생성되는 이벤트가 주어지지 않으므로, 다음의 발상을 생각해 볼 수 있습니다. 사실, 이것만 계산을 하면, 문제에서 요구하는 쿼리도 해결할 수 있습니다. 이것을 어떻게 해결하면 좋을까요? 보라색 영역에 점이 있다고 해 보겠습니다. 우리는 x좌표가 A 이하이고, y 좌표가 B 이하인..
자료알고/알고리즘 2020. 5. 1. 17:58
랜덤 접근이 가능한 deque 자료구조를 chunk로 구현하면 어떤 이점이 있을까요?

deque를 공식 레퍼런스 사이트에서 보면, Chunk로도 구현이 된다고 되어 있습니다. 그러면, Chunk로 구현했을 때, 장점이 무엇일까요? 일단, deque가 Random 접근이 되려면, 기본적으로 연속적이여야 합니다. List는 Random access를 지원하지 않습니다. 더 정확히 이야기 하면, base 주소가 있고, 그것을 통해서 i번째 index에 접근할 수 있어야 합니다. 1차 구조의 덱을 생각해 보겠습니다. 원래 4개의 원소가 있었고, 5를 어딘가에 추가한다고 해 보겠습니다. 원래 capacity가 4였다면, 하나를 추가하려는 순간 추가하지 못하게 될 겁니다. 그러므로 확장 연산이 수행이 될 겁니다. 그러면 확장된 후에 기존의 원소가 어떻게 들어가는 것이 좋을까요? 이렇게 들어가는 것이..
자료알고/자료구조 2020. 4. 7. 01:08