안녕하세요 Dibrary입니다.
파이썬으로 설명된 자료구조 책을 보면 여느 다른 책들과 같이 '리스트, 트리, 정렬, 탐색, 그래프' 등이 나와있습니다. 근데 파이썬을 자주 써 본 사람이라면 이런 의문이 들죠.
파이썬에서는 어차피 리스트 자료형이 있는데....
물론, 저도 그런 생각을 한 적이 있습니다. (그리고 그 리스트 자료형은 여기서 말한 연결리스트도 아니죠;;)
그런 혼란을 가지고 있지만 불편함은 없어서 그냥 유야무야 넘어가다가,
자료형 리스트가 아닌 자료구조 '단순 연결리스트, 이중 연결리스트, 원형 연결리스트' 등을 배워야 하는 이유를 최근에 알고리즘을 풀다가 깨달았습니다.
1. 불필요한 공간 낭비를 위해서 사용할 수 있다.
애초에 리스트를 배열 대신에 쓰는 이유는 공간 사용의 효율을 높이기 위한 것이죠.
배열은 반드시 순서대로 들어갈 수 밖에 없는 반면, 리스트는 연결만 되면 쓸 수 있는 거니까요.
여기서 핵심은 '연결만 되면 쓸 수 있음' 입니다. 즉, 연결만 되면 공간 낭비를 줄이면서 쓸 수 있는 것이죠.
제가 이를 깨달은 문제를 하나 보겠습니다.
Swap Nodes in Pairs - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
저는 이 문제를 어떻게 풀었냐면, 모든 노드의 값을 뽑아다가 순서를 변경한 후에 다시 노드를 만들어서 구성했습니다.
근데, 만일 '연결'에 초점을 둔다면 굳이 다 뽑아낼 필요가 없죠
바로 이렇게 말이죠. 별도의 리스트를 사용하지 않기 때문에 공간낭비는 매우 줄어들게 됩니다.
2. 포인터로 접근하는 사고를 키울 수 있다.
이는 위 문제에도 해당되는데, 주어진 문제변수에 접근할 때 항상 for문이나 while문을 사용해서 전체 접근을 하지 않고 선택적으로 접근할 수 있게 됩니다.
이런 접근법이 왜 중요하냐면, 알고리즘 문제에는 굉장히 빈번하게 '시간초과' 제약이 있기 때문이죠.
이걸 꽤 와닿게 느낀 문제는 아래 문제입니다.
3Sum - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
그냥 for문 3번 돌려서 해도 되는데, 시간초과가 걸릴거 같았죠. (물론 당연히 시간초과 ㅎ;;)
그럼 for문 중에 하나라도 좀 효율을 높여야 하는데, 이때 '선택해서 접근'할 필요가 있습니다.
여기서 포인터 접근방식 개념이 필요하다는 것을 깨달은 것이죠.
개인적으로 아직도 알고리즘을 풀다가 곧바로 떠오르는 경지까지는 오르지 않았습니다만, 해당 문제를 풀 때 '어디서 배운 개념이 이렇게 녹아있구나'를 알아차릴 때 굉장히 좋네요. ㅎㅎ