TIL_5 | 자료구조(feat. Stack, Queue, Hash, Heap)

어제 stack과 queue에 대해서 간략히 말해봤는데, 오늘은 이것들과 함께 hash, heaq에 대해서도 알아봤다!

stack이란 '겹겹이 쌓다'라는 뜻 그대로 한 방향으로만 in/out이 가능한 자료구조라고 한다.
그림과 같이 5, 2가 입력되고, 5를 바로 꺼낼 수 없다. (3번 stack처럼 막혀있기 때문에) 5를 꺼내기 위해선 반드시 2를 꺼내고 5를 꺼낼 수 있는 구조!
이러한 구조를 LIFO(Last In First Out)이라고 한다.

활용예시

• 선수 과목이 있는 과정의 경우 스케줄 구조를 옳바른지 아닌지 푸는 문제를 풀 수 있다.
  • 선수과목: A->B->C
  • 1번 학생의 구조: A->B->D->F->C (True)
  • 2번 학생의 구조: D->A->F->C->G (False)
  • 3번 학생의 구조: A->B (True)

3번 학생의 경우에는 모든 과목을 듣지 않아도 구조상에는 문제가 없으므로 True이다.

queue 자료형은 긴 파이프 구조에 먼저 들어온것이 먼저 나가는 자료구조이다. 이러한 자료구조를 FIFO(First In First Out)이라고 한다.
python에서는 deque자료형을 많이 쓰는데, 이 자료형은 양쪽으로 in/out이 가능한 구조이기에 알고리즘 문제를 풀때 한쪽 방향으로만 in/out 제한을 벗어나 유연하게 대처하기 좋다.

활용예시

• 대표적으로 DFS/BFS가 있다. 특히 BFS를 풀때 해당 인덱스가 접근 가능한 node를 queue자료형에 다 넣어놓고 하나씩 꺼내서 확인할때 유용하다.
  • [[], [2, 3], [1], []] 이런 리스트라면 1번 index에서 queue자료형에 2, 3을 넣어 놓고 2를 꺼내어 확인하고, 3을 꺼내어 마저 확인할 수 있다.

heap자료형은 위와같이 Tree구조로 되어있다. 대표적으로 최소힙, 최대힙이 있는데, 왼쪽 그림이 최소힙이고 오른쪽 그림이 최대힙이다.
(지금까지 자료구조와 모양이 달라서 어려웠다...😂)

최소힙

최소힙은 부모node가 자식node보다 무조건 작다. Sub Tree는 왼쪽 오른쪽 두개가 있는데, 왼쪽이 오른쪽보다 작게 되어있다. 그림은 일부러 완전한 heap으로 그리지 않았는데, 모양과는 상관없다는 것을 전달하고 싶었다.

최대힙

최소힙과 거의 모든 부분이 비슷하지만, 부모node가 자식node보다 무조건 크다는 점이 다르다.

활용예시

• 내가 알아본 예시로는 지금까진 최소힙, 최대힙만 알고 있다!(추후에 더 공부하자!!)

hash 자료구조는 다른 자료구조보다 조금 개념이 어려웠다... key값을 hash함수로 작동시켜 HashCode를 만든다. (만드는 방법은 함수마다 다를 수 있지만 한 리스트에 접근하고 저장할때는 동일한 함수를 사용해야 한다.)

위의 그림에서는 각 글자에 해당하는 ASCII Code를 사용하여 HashCode를 얻어왔는데, 사실 첫번째 sung외에는 임의의 값을 넣어주어 정확하지 않다...😭

Index로 접근하기 위해서는 HashCode를 Index의 길이로 나머지 연산을 통해 접근 할 수 있다.

hash는 검색을 활용하여 만들때 유용하다. HashCode가 정수로 만들어지기 때문에 HashCode 자체가 배열의 Index로 바로 접근이 가능하기 때문에 빠르다.

다만, 주의할점이 있다!💡
HashCode를 만드는 방법을 짤 때 한쪽 Index로만 몰리지 않고 짜서 검색이 빠르다는 장점을 살려줄 수 있도록 한다. 원래는 O(1)의 시간복잡도를 가졌지만, 한쪽으로 몰리는 Collision(충돌)이 발생하면 O(n)까지 늘어날 수 있다.

Today, Learned

배운점

• hash 알고리즘에 대해서는 확실히 알고 가는것 같다! 블록체인같은 시스템도 hash 알고리즘으로 작동한다니... 신기하다!👍
• heaq 알고리즘의 최대힙, 최소힙 구현 방법에 대해 배웠다. 비록 내장함수를 이용한 방법이지만, 그런 내장함수가 있다는 것 자체를 알았으니 만족!🙌

느낀점

• 아직 hash를 이용한 문제를 아직 안풀어서 아쉽다.. 한번 찾아봐서 찾아서 완전한 내껄로 만들고 싶다! (열정 뿜뿜🔥)
• Tree의 종류가 많이 있는데, 이것에 대해서도 조금씩 알아나가고 싶다. (너무 넓은 Tree의 세상...)

오늘의 한마디

자료구조만으로도 두꺼운 책이 많은걸 보니 내가 아는 지식은 새발의 피겠지만, 이렇게 오늘도 한걸음 성장!!😎