자료구조 05 : 시간 복잡도 (time complexity)

수학과 같이 한 문제를 해결하는 데에 여러가지 알고리즘이 있을 수 있다. 알고리즘 복잡도 표현 방법 : 시간 복잡도★ 이때 알고리즘 실행 속도를, 얼마나 빠르게 문제를 해결하는 알고리즘인지 측정하는 것이 시간 복잡도 이다. 코딩 문제를 풀다가 나오는 O(n), O(n²)이 한 예이다. 당연히 O(n)이 O(n²)보다 좋은(빠른) 코드이고, 이 시간은 반복문에서 크게 좌지우지된다. 알고리즘 복잡도 표현 방법 : 공간 복잡도 알고리즘이 사용하는 메모리 사이즈를 측정하는 기준이다. 사람이 간단히 계산할 수 있는 부분이 아니기 때문에 시간 복잡도에 비해 중요도가 살짝 떨어지는 편이다. ※ k,k'는 상수 무조건 k회 실행하면 O(1), n에 따라 n번, kn+k' 실행하면 O(n) n에 따라 n²번, kn²+k..

2022.10.03

자료구조 04 : 링크드 리스트 (linked list)

배열이 미리 연결된 특정한 공간을 예약을 해놓고 거기에 데이터를 쓰고 읽는 구조라면, 링크드 리스트는 미리 예약을 해놓지 않고 필요할 때마다 데이터를 추가할 수 있는 구조다. 배열의 단점을 극복한 자료구조라고 할 수 있다. 링크드 리스트 구조 (데이터+다음 데이터를 가리키는 주소(포인터)) 가 하나의 데이터로 이걸 노드(Node)라고 한다. 여기서 각 노드 안에 다음/이전 노드와의 연결 정보를 가지고 있는 공간을 포인터라고 한다. 노드마다 다음 노드의 주소가 있기 때문에 첫번째 노드만 알면 꼬리물기 식으로 추적해 원하는 노드의 값을 알아낼 수 있다. 그렇기 때문에 꼭 이어져있는 주어진 공간이 아닌 원하는 곳곳에 노드 생성과 추적이 가능하다. 물론 첫번째 노드 주소를 알고 있고, 노드들이 연결되어 있다는 ..

2022.10.02

자료구조 03 : 스택 (stack)

굉장히 많이 쓰이는 핵심 자료구조 중 하나로 큐와 마찬가지로 구조와 관련된 간단한 용어를 알고 파이썬으로 직접 구현하는 연습까지 할 수 있으면 좋다. 한쪽 끝에서만 자료를 넣거나 뺄 수 있다는 점에서 데이터에 제한적으로 접근한 수 있는 구조란 것은 큐와 유사하다. 중요한 점은 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조란 것이다. 스택 구조 스택은 LIFO 또는 FILO 데이터 관리 방식을 따른다. 책을 가로로 눕혀서 쌓은 것과 같은 상황이다. 맨 위 있는, 즉 가장 나중에 쌓은 책을 먼저 꺼낼 수 밖에 없는 구조. 대표적인 스택 활용 부분은 컴퓨터 내부 프로세스 구조의 함수 동작 방식에 쓰인다. psuh() : 데이터 스택에 넣기 pop() : 데이터 스택에서 꺼내기 ★용어 뜻은 꼭..

2022.09.22

자료구조 02 : 큐 (queue)

운영체제, 인터넷 네트워킹에서 많이 쓰이기 때문에 잘 알고 있어야 하는 자료구조 중 하나이다. 구조(정책), 필수 용어에 대해 잘 알아둘 필요가 있으며 관련 lib.를 활용하지 않고 큐의 정책을 이해하여 순수 코딩으로 조건문/반복문/함수를 활용하여 큐를 구현해 볼 수 있도록 연습하는 것을 권장한다. 큐 구조 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조를 큐라고 한다. 일반적인 큐는 먼저 줄 선 사람이 먼저 입장하는 것과 같이 줄을 서는 행위와 유사하다. FIFO(First-in, First-out), LILO(Last-in, Last-out) 방식(정책)이라고도 하며 스택과는 정반대의 형태이다. 데이터를 넣을 때는 위와 같이 앞쪽부터 순서대로 들어가고, 출력될 때는 앞에서부터 출력되며 잔여 데..

2022.09.21

자료구조 01 : 배열 (array)

파이썬의 리스트(list) 타입. 딱 그게 배열을 다 설명해준다. 유사한 데이터를 연결된 데이터 공간에 넣을 수 있는 것이 배열이다. 좀 더 구체적으로 이야기하자면 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조를 배열이라고 한다. 배열의 장단점을 말하여라 와 같은 질문이 면접에서 CS기본 지식을 묻는 문제로 질문이 나올 수 있다. 평소에 너무 당연하게 쓰고 있는 부분이라 이런 질문을 갑자기 받으면 당황스러울 수 있는데 배열의 장단점을 아래와 같다. 장점 : 인덱스(번호)가 있어 원하는 데이터로의 빠른 접근이 가능하다. 단점 : 가변적인 데이터의 경우 데이터 추가/삭제가 번거롭거나 어렵다. 삭제를 하는 경우 삭제 후 중간에 빈 공간이 없도록 뒤에 있는 데이터를 당겨와줘야 하고, 데..

2022.09.21