공부40 알고리즘 문제 풀때 보이는 O(n) 은 무엇일까? (시간 복잡도, 공간 복잡도) 알고리즘 문제를 풀 때 보면 시간 복잡도니, 공간 복잡도니, O(n)이니 무슨 소리인지 모르겠는 말이 많습니다. Big O 그러니까 O(n) 같은 표시가 무엇인지 궁금해서 클릭하셨겠지만 시간복잡도랑 공간 복잡도부터 정리해보겠습니다. 시간 복잡도는 쉽게 말하면 들어오는 데이터 갯수 n에 대해 몇 번 연산을 하는가 라고 보시면 되겠습니다. input_data = [x for x in random.sample(range(1000), 10)] 예를 들어 위와 같은 길이 10 짜리 랜덤 수열이 생성 되고 (정렬 연산 없이) 가장 큰 수를 찾는다고 가정해봅시다. 그러기 위해서는 모든 수를 돌아봐야겠죠? 그러면 input_data[0]에서 input_data [9]까지 모두 돌게 될 것입니다. 주어진 데이터 n 만큼.. 2021. 5. 25. [자료구조 공부기록] 5. Tree 특징 비선형 자료구조입니다. 계층적인 구조를 가지고 있습니다. 장점 및 단점 1) 장점 (특정 트리의 경우) 선형 자료구조에 비해서 탐색 및 검색이 빨라집니다. 2) 단점 (대부분의 경우) 트리가 편향된 경우 삽입, 삭제가 늦어질 수 있습니다. 관련 용어 노드(node): 트리를 구성하는 기본 원소 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드 자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들 리프 노드(leaf (node))/단말 노드(terminal node): 자식이 없는 노드 경로(pat.. 2021. 5. 24. [자료구조 공부기록] 4. Queue + Python 구현 특징 선형구조를 가진 자료구조입니다. FIFO(First In First Out/먼저 들어온 원소가 가장 먼저 나감) 구조를 가지고 있습니다. 오래된 데이터가 있는 곳이 앞(front), 새로운 데이터가 쌓인 곳이 뒤(back)입니다. 장점 및 단점 1) 장점 데이터의 삽입, 삭제가 빠릅니다. 2) 단점 중간에 있는 데이터에 접근이 불편합니다. 배열로 구현할 경우 삽입, 삭제 시 데이터를 모두 옮겨주어야 합니다. 큐의 데이터 삽입은 Enqueue, 삭제(데이터를 내보냄)는 Dequeue라고 합니다. 큐에는 구현 방식에 따라서 몇 가지 분류가 있습니다. 일반적으로 선형 큐 : 일반적인 큐이지만 데이터 Enqueue, Dequeue 할 때 데이터를 옮겨줘야 합니다. 원형 큐(Circular Queue) : .. 2021. 5. 21. [자료구조 공부기록] 3. Stack + Python 구현 특징 선형구조를 가진 자료구조입니다. LIFO(Last In First Out / 제일 나중에 들어온 원소가 제일 먼저 나감) 구조를 가지고 있습니다. 장점 및 단점 1) 장점 구조가 단순하여 구현이 간단합니다. 성능이 좋습니다. 2) 단점 일부 구현 방법은 미리 크기를 정해주어야 합니다. 오래된 데이터에 접근이 힘듭니다. 데이터가 들어가고 나가는 방법만 이해하신다면 스택은 구조가 정말 단순하여 크게 말씀드릴 것은 없습니다. 왼쪽의 사진처럼 Push로 데이터를 넣게 되면 맨 위에 저장되고 오른쪽 사진처럼 Pop으로 데이터를 뺀다면 맨 위의 데이터가 나가는 형식입니다. # 데이터 저장 노드 정의 class Node: def __init__(self, data): self.data = data self.be.. 2021. 5. 20. 이전 1 ··· 4 5 6 7 8 9 10 다음
