[CS] - Data Structure4 # 3. 단방향 연결 리스트 (Single Linked List) 지난 포스트에서는 데크에 대해서 다루었다. 데크의 직접 구현 부분에서는 연결 리스트를 사용하여 구현했다. 그래서 실은 순서가 뒤집히지 않았나 싶지만.. collections 라이브러를 통해서도 데크를 사용할 수 있기에 이번 포스트를 읽고 지난 포스트를 다시 보기를 권장한다. 각설하고, 이번 포스트에서는 연결 리스트에 대해서 다루겠다. 연결리스트의 키워드를 세 가지 뽑으라면 필자는 이렇게 말할 것이다. 노드, 삽입, 수정 리스트나 스택, 큐에서는 보관하고 있는 데이터가 raw data (원시 데이터 - 이를테면, 정수형) 였다. 하지만, 연결 리스트에 사용되는 데이터의 (클래스) 타입은 Node 이다. 왜 굳이 클래스를 사용하는가? 그것은 단순히 원시 데이터 이외에도 다음 노드를 가르킬 포인터(next)가.. 2021. 12. 3. # 2. 데크 (Deque) 저번 포스트에서는 나서스의 스택에 스택과 큐에 대해 알아보았다. 이번 포스트에서는 큐의 연장선상 개념(?)인 데크에 대해서 알아보겠다. 데크는 풀네임 영어로 Double Ended Queue를 의미한다. 즉, 양방향으로 끝이 존재하는 큐를 뜻한다. 이번에도 역시 그림을 그려보자. 큐와 모양 자체는 똑같다! 하지만, 큐는 한뱡으로 들어가고 나갈 수 없는 방면에 데크는 양끝에 데이터가 들어오고 나갈 수 있는 특징이 있다. 그렇다면 데크를 왜 사용하는지 알아보자. 이는 파이썬의 리스트 자료형과 비교하면 알 수 있다. 우리가 리스트에 insert하는 과정을 그림으로 그리면 다음과 같다. 먼저 insert를 하기 위한 공간 하나를 할당해주어야 한다. 그 다음 기존에 존재하던 자료의 갯수(N개, 위 그림에서는 2개.. 2021. 12. 2. # 1. 스택과 큐 (Stack and Queue) 스택과 큐라고 하면 무엇이 떠오르는가? 지금은.. 나서스의 스택을 안떠올렸으면 좋겠다. (스택의 의미가 아닌것은 아니지만..) 이 포스트를 통해 스택의 개념을 익히면 나서스가 왜 스택을 쌓는다고 표현할지 알것이다. 우선 직관적으로 접근하기 위해서는 그림을 그려보자. 스택과 큐를 유리컵에 비유하자면, 스택은 바닥이 막혀있는 유리컵이고 큐는 바닥이 뚫려있는 유리컵이다. 그리고 우리가 물건을 넣은 모습은 다음과 같다. 둘다 물건을 위에서 집어넣었다고 생각해보자. 그럼 물건을 어떻게 꺼낼까? 스택은 마지막에 넣은 물건을 먼저 꺼내야하고, 큐는 가장 처음에 넣었던 물건을 먼저 꺼낼 수 있다. [정리] 스택은 선입후출(FILO: First In Last Out, 먼저 들어온게 마지막에 나감) 큐는 선입선출(FIFO.. 2021. 12. 2. # 0. 자료구조 카테고리의 시작.. 해당 카테고리는 코딩 테스트에 준비하기 위한 카테고리이다. 보통 코딩 테스트를 준비한다하면, Only 알고리즘부터 생각하는 사람들이 있을 것이다. 물론 필자도 컴퓨터 공학과를 졸업했음에도 불구하고.. 부끄럽지만, 마음이 급해서 알고리즘 문제부터 무지성으로 풀었다. 그 결과 말할 것이 있겠나 ㅋㅋ 결과는 아주 처참했다. 그래서 알고리즘도 중요하지만, 자료구조를 베이스로 문제에 접근해야 한다고 판단했다. 물론, 프XXXX스, 백X 등.. 아주 좋은 문제들과 다른 사람들이 적어놓은 포스팅 혹은 유튜브 강의들도 넘친다. 하지만.. 기죽지 않고 내 소신대로 자료구조가 어느정도 기본은 잡혔다고 판단이 되면 알고리즘 카테고리도 새로 만들 예정이다. 일단 자료구조의 로드맵(?)과 같은 전체적인 맥락부터 살펴보자. 구글.. 2021. 12. 2. 이전 1 다음
