TIL - 2024.04.16 화요일

· 성취/개선/학습한 내용 🏆

 스위프트는 다른 언어와 달리 스택, 큐를 직접 구현을 해야 사용할 수 있다. 즉, 자신에게 필요한 자료구조를 정확하게 이해를 하고 있어야 된다. 스택은 간단하게 배열을 활용해서 어팬드를 해주고 popLast를 하는 방법으로 간단하게 구현이 가능하다. 그러나 큐는 여러 가지 방법으로 구현할 수 있다.

 우선 배열을 활용하면 간단하게 구현할 수 있지만, removeFirst 메서드를 사용해야해서 시간복잡도가 O(N)이 된다. 그다음 방법은 배열과 포인터로 구현하는 방법이다. front라는 index 번호를 가지고 있는 변수를 만들어서 deque (deque는 커스텀 메서드)라는 메서드를 사용할 때마다 front의 값을 += 1 해줘서, 배열은 그대로 두는 대신 포인터의 값이 계속 바뀌는 방법이다. 이 방법은 배열이 그대로 유지돼서 공간을 효율적으로 사용하지 못한다는 단점이 있다. 그리고 이런 단점을 해결하기 위해 원형 큐가 등장했다. front와 rear 포인터의 값이 배열의 끝에 도달하면 0이 되도록 설정해 배열의 빈 공간을 활용하는 방법이다. 그러나 생성시점에 배열의 크기를 정해져서 큐의 크기가 고정되는 문제점이 있다. 그리고 이런 문제는 링크드리스트로 해결할 수 있다.

 또 지금까지는 해시 자료구조가 단순히 키 값이 고유하다고만 알고 있었는데, 이를 구현하는 과정이 굉장히 새로웠다. 해시 자료구조는 비둘기집 원리 때문에 해시 충돌이 일어날 수 밖에 없다. 예를 들어 전화번호부가 있다고 한다면 해시 자료구조는 키 값으로 전화번호를 value로 사람 이름을 저장할 것이다. 이때, 만일 전화번호의 마지막 번호를 활용해 구별한다고 한다면 0~9까지의 수로 구별을 하게 될 것이다. 즉 사람이 10명만 있어도 마지막 전화번호가 같은 사람이 무조건 생길 것이며, 이를 해시 충돌이라고 한다. 이 충돌의 해결방법으로는 Chaining과 Open Addressing이 있다. 

 

• 스위프트 자료구조
  • 스택
  • 큐
  • 해시
• 알고리즘
  • dfs 
  • bfs

 

· 궁금한 내용과 부족한 내용 ⁉️🤔

• 스택을 활용해 큐를 구현하려면 어떻게 해야 할까?
• Swift에서 Hashable 프로토콜이 무엇을 의미하는지
• Hashable 프로토콜은 왜 Equtable 프로토콜을 채택하고 있는지