알고리즘 썸네일형 리스트형 [CS/Python] 자료구조 & 알고리즘 정리 - 큐, 트리, 힙 큐 (Queues)큐 또한 스택과 함께 많이 사용되는 자료 구조이다. 스택과 마찬가지로 선형 구조라는 공통점을 가지고 있지만, 다른 특성을 가지고 있다. 스택이 LIFO(후입선출) 방식인 반면에, 큐는 FIFO(선입선출) 방식을 가지고 있다. 데이터 원소를 큐에 넣는 동작을 인큐 (enqueue) 연산이라고 부르고, 반대로 큐로부터 데이터 원소를 꺼내는 동작을 디큐 (dequeue) 연산이라고 부른다. 큐를 구현할 때는 선형 배열(리스트)보다 연결 리스트를 사용하는 것이 더 유리하다. 선형 배열은 디큐 연산 시 모든 원소를 한 칸씩 옮겨야 하기 때문에, 시간 복잡도 측면에서 불리하기 때문이다. 양방향 연결 리스트를 이용한 큐 구현class Node: def __init__(self, item): .. 더보기 [CS/Python] 자료구조 & 알고리즘 정리 - 연결 리스트, 스택, 후위 표기법 연결 리스트 (Linked lists)연결 리스트는 선형 배열과는 유사한 구조이지만, 데이터 원소를 늘어놓는 방식에서 큰 차이가 있다. 선 형 배열이 "번호가 붙여진 칸에 원소들을 채워넣는" 방식이라고 한다면, 연결 리스트는 "각 원소들을 줄줄이 엮어서" 관리하는 방식이다. 연결 리스트가 가지는 이점은 원소의 삽입, 삭제가 선형 배열과 비교해 쉽게 처리할 수 있다는 것이다. 원소들이 link라는 고리로 연결되어 있기 때문에 가능한 일이다. 삽입/삭제가 빈번히 일어나는 응용에서 연결 리스트가 많이 이용되며, OS 내부에서도 많이 이용된다. 연결리스트가 가지는 단점도 물론 있다. 선형 배열에 비해 소요되는 메모리 요구량이 크다. 또한, 특정 위치의 원소를 찾기 어렵다. 선형 배열의 경우 index가 지정되어.. 더보기 [CS] 알고리즘의 복잡도 (시간 복잡도) 알고리즘의 복잡도는 알고리즘의 성능을 평가하는 중요한 척도 중 하나이다. 이 글에서는 시간 복잡도와 공간 복잡도 중 시간 복잡도에 대해서만 간단히 정리한다. 시간 복잡도알고리즘이 실행되는 데 걸리는 시간Big O 표기법을 사용하여 표현 ex) O(n), O(log n), O(n²) 등.입력 크기에 따른 연산 횟수의 증가율을 나타냄 예시O(1) - 상수 시간 복잡도: 연산 횟수가 입력 크기와 관계없이 일정한 경우def get_first_element(arr): return arr[0] if arr else None# 사용 예시print(get_first_element([1, 2, 3, 4, 5])) # 출력: 1 배열의 크기와 관계 없이 첫 번째 원소를 반환하는 함수이므로 일정하다. O(n) - .. 더보기 [CS/Python] 자료구조 & 알고리즘 정리 - 선형 배열, 정렬, 탐색, 재귀, 순열 자료구조는 왜 알아야 하는가?ex) 리스트 내 최대값을 max() 함수를 통해 알아내고자 한다면, 리스트 전체 원소를 하나씩 읽어 비교하는 수 밖에 없다.즉, 위의 예시의 경우 리스트의 크기가 커질수록 시간은 비례적으로 많이 걸릴 수 밖에 없다는 뜻이다. 이런 경우 자료구조를 잘 활용한다면, 낭비되는 시간을 획기적으로 줄일 수 있다. 알고리즘이란? 프로그래밍에서의 알고리즘은 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택을 뜻한다. 같은 문제가 주어지더라도 어떤 자료구조와 연산 방법을 사용하느냐에 따라 효율성의 크기가 달라질 수 있다. 자료구조와 알고리즘이 깊은 관계를 가지고 있는 것도 이런 이유 때문이다. 알고리즘의 '선택'에는 자료구조에 대한 이해가 필수적이다. 선형 배열 (Linear.. 더보기 이전 1 다음
