본문 바로가기

내맘대로 코딩32

[05-1] 큐(Queue)란? 보자마자 살짝 멈칫하게 되는 그 이름 큐(Queue). 내가 코테를 공부하기 위해 자료구조를 공부하면서 항상 큐에서 멈췄다. 옛날 집합파트까지만 헌책이던 수학책 같은 느낌이랄까. 각설하고 큐에 대해 큰 흐름부터 이해해보자. 큐(Queue)는 Array list, Linked list, FIFO로 만들 수 있다. 하지만 Array list로 만들면 Queue의 장점이 하~나도 없다. 그래서 Linked list로 만드는 편이지만, 우리는 Queue를 따로 만들 필요가 없다. 왜? 파이썬에서 이미 Deque라는 자료구조로 제공하고 있으니까! Queue는 FIFO(First In, First Out)의 방식으로 저장하는 데이터구조이다. Queue의 뒤쪽(rear)에 자료를 저장하는 것을 enqueue, 앞(f.. 2023. 11. 9.
[04-2] 연결 리스트의 활용 연결 리스트는 앞서 정리한대로 활용성이 매우 뛰어나다. 분명 용량도 크고, 시간도 오래걸리고 복잡도도 크지만 쓰는 데에는 다 이유가 있다. 그래서 활용할 수 있는 Operations들을 정리해보고 구현해보자. - get() 특정 인덱스의 값을 가져온다. 어떻게 해야할까? 1번의 인덱스,,n번의 인덱스 값을 가져오려면? 앞서 든 예시로 보자. 우리반에 18번애 이름을 알고 싶으면? 1번부터 물어서...18번까지 찾으면 된다. 그러면 1번(head)에 접근해서 18번까지 쭉 간다음에 value를 return 하면 되겠지? 즉 n번까지 해야하니까 시간 복잡도는 O(n)이 된다. -insert_at() 특정 위치에 값을 넣고 싶다 어떻게 해야할까? 우선 넣고 싶은 위치(idx)와 값(value)를 받아야겠지. .. 2023. 11. 9.
[04-1] 연결 리스트란? Linked List(연결 리스트)는 Node(노드)로 구성되어 있다. 이 Node를 어떻게 구성하냐에 따라 Tree가 될 수도, Graph가 될 수도 있다. Array 리스트는 파이썬에 리스트로 구현되어 있기 때문에 따로 구현을 하지 않았지만, Linked list의 경우 직접 구현하는 것이 매우 중요하다! Linked List? Node 구조가 연결된 형식으로 저장된 구조로, 데이터값과 Next node의 주소값을 저장한다. Linked List의 구조는 다음과 같다. 어디서 많이 본 것 같은데.. 이것을 보니까 블록체인의 구조가 떠올랐다. 블록체인은 이전 해시값을 갖고 있는 차이가 있지만, 어쨌든 연결되어 있지 않은가? 그래서 Node라고 하는것인가 싶기도 그렇다면 리스트랑 차이는 무엇일까? 리스트.. 2023. 11. 9.
[03-3] 배열을 알아보자(활용편) 여태까지 배열의 구조와 원리를 알아보았다. 역시 가장 중요한건, 그래서 코테에서 어떻게 쓰이는데? 결론부터 말하면, 배열은 반복문에서 많이 쓰인다. list는 순서가 있기 때문에, 순차적으로 접근하는 반복문과 잘어울린다. 1. for 문 우리가 쉽게 생각하는 구조인 for문은 대표적 리스트 활용사례라고 봐도 무방하다. 예를 들어서 A = [5, 8, 3, 2, 11, 9, 4, 1, 13] 라는 리스트가 주어졌을 때, "두개의 값 합했을 때 10이 나오면 True, 넘지 않으면 Fasle를 반환하시오" 라는 문제가 주어졌다면 A[i] + A[j]를 활용해야 겠다는 생각을 하게 된다. 자연스럽게 for문을 떠올리고, for문 안에 for 문인 이중for문을 구성하는데 우선은 이렇게 자연스럽게 for for.. 2023. 11. 9.
[03-2] 배열을 알아보자(Dynamic Array) 앞에서 배열을 알아보았다(Static Array). 우리가 쉽게 쓰는 것이지만, 어떻게 메모리에 저장되고 불러오고 활용하는지는 고민해본적이 없었을 것이다. 왜냐하면 파이썬에서는 Dyanmic Array를 기본으로 하니까. 그래서 이번에는 익숙한 동적배열(Dynamic Arrray)을 알아보자. 동적배열의 특징은 딱 하나! 1. 배열 선언 이후에 사이즈를 증가할 수 있다. 동적배열의 원리를 알아보자 지난번처럼 {1,2,3,4}의 배열을 넣으려고 하는데, 정적배열은 4칸의 배열을 선언했다면, 동적배열은 그냥 추가하면 된다. 예를 들어 3개의 공간이 있었는데 {1,2,3,4}를 넣는다면? 4를 못넣게 되는데! 그 순간에 Resizing을 해서 기존에 있던 {1,2,3}을 다시 새로운 배열에 {1,2,3}을 넣.. 2023. 11. 9.
[03-1] 배열을 알아보자(Static Array) 배열(Array)은 무엇인가? 파이선에서 의도하진 않아도 가장 많이 쓰는게 array 아닐까? np.array를 참 많이 쓰고 있다. 심지어 이미지 처리할때도 np.array를 할정도니까. 가장 기본적인 자료구조가 배열인 셈이다. * 여기서는 정적 배열(Static array)을 가정하고 있다. 배열의 특성은 2개를 기억하면 된다. 1. 배열은 고정된 저장 공간을 갖는다. 2. 순차적(order)인 데이터 저장을 갖는다. 즉, 선언할 때 배열의 사이즈를 정하며, 순차적으로 입력된다. int형의 경우(4byte)이기 때문에 4개의 배열은 결국 16byte이며, 순서대로 (ex. {1, 2, 3, 4}) 할당된다. 이렇게 메모리가 비어있던 공간에 1, 2, 3, 4가 순차적으로 들어가게 된다. 4byte라고.. 2023. 11. 8.