728x90 반응형 개발 일기58 자료구조 - 우선 순위 큐(Priority Queue) 1. 우선순위 큐란? 우선순위 큐(Priority Queue)는 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리되는 자료구조이다. 큐는 선형 자료구조이고, 우선순위 큐는 비 선형 자료구조이다. 우선순위 큐는 자료가 들어온 순서와 상관 없이 미리 정한 우선순위대로 나간다. 주로 정의된 우선 순위를 heap condition으로 가지는 heap을 이용해 구현된다. 그 이유는 시간 복잡도와 관련이 있는데, 배열 기반 데이터 삽입의 시간 복잡도는 O(n) 이고 배열 기반 데이터 삭제의 시간 복잡도는 O(1)이다. 또 연결 리스트 기반 데이터 삽입과 삭제의 시간 복잡도도 위와 같다. 하지만 힙 기반 데이터 삽입과 삭제의 시간 복잡도는 각각 O(logn)이다. 따라서 힙을 먼저 공부해야 한다... 2021. 1. 7. 자료구조 - 큐 (Queue) 1. 큐란? 큐(Queue)는 데이터를 일시적으로 쌓아두기 위한 자료구조로, 먼저 들어온 데이터가 가장 먼저 나가는 First In First Out인 구조를 말한다. 위 Reference Code처럼 배열로 큐를 구현해도 되지만, 표준 라이브러리에 정의되어 있기 때문에 include하여 사용하면 편리하다. enqueue란 큐 맨 뒤에 데이터를 추가하는 것을 의미하며 dequeue란 큐 맨 앞쪽의 데이터를 삭제하는 것을 의미한다. 데이터가 삽입되는 곳을 front, 제거되는 곳을 back이라고 한다. 선언 queue 큐 이름; 형태로 선언한다. #include queue s1; queue s2; queue s3; 기본 메소드 1. push() : 큐 맨 뒤에 데이터 추가 = enequeue 2. pop(.. 2021. 1. 6. 자료구조 - 스택 (Stack) 1. 스택이란? Stack의 사전적 정의는 '쌓다', '더미'로 나중에 들어간 것이 먼저 나오는 Last In First Out 형태이다. 아래 Reference Code처럼 배열로 스택을 구현해도 되지만, 표준 라이브러리에 정의되어 있기 때문에 include하여 사용하면 편리하다. 맨 위 요소는 top이라고 하며, 이 요소만 접근할 수 있다. 자료가 없을 때 pop을 하는 오류를 stack underflow, 스택의 크기 이상의 자료를 push하려고 할 때의 오류를 stack overflow라고 한다. 선언 stack 스택 이름; 형태로 선언한다. #include stack s1; stack s2; stack s3; 기본 메소드 1. push() : 현재 스택 최상위에 데이터 추가 2. pop() : .. 2021. 1. 6. 알고리즘 - 재귀 (Recursion) 알고리즘 - 재귀 (Recursion) 재귀는 수학이나 컴퓨터 과학 등에서 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. 주로 이 방법은 함수에 적용한 재귀 함수(Recursion Function)의 형태로 많이 사용된다. 재귀함수를 왜 사용해야 할까? 점화식을 세웠을 때, 인자만 바뀌고 같은 로직을 사용해야하는 함수가 필요한 경우 반복문보다 재귀 함수가 적합하다. 변수 사용을 줄여주는 장점도 있기 때문에 사이드 이펙트를 최소화할 수 있고 코드의 가독성도 향상된다. 예시문제 주어진 수의 Factorial 값을 구해 아래와 같이 출력하시오. 주어지는 수는 1 이상 20 이하의 수이다. def factorial(num): if num == 0: return 1 else: return num * f.. 2021. 1. 5. 이전 1 ··· 7 8 9 10 다음 728x90 반응형
