nyunu

현재 상황에서 최선의 선택을 반복한다는 그리디 알고리즘의 특징 때문에 우선순위 큐는 특히 그리디 알고리즘에서 자주 사용된다. 파이썬에서 우선순위 큐를 구현할 수 있는 방법에는 두 가지가 있다. 우선순위 큐 : 값이 들어올 때마다 오름차순으로 정렬 & 값을 꺼내면 가장 작은 값부터 꺼내짐 💡 파이썬 모듈 (1) PriorityQueue from queue import PriorityQueue myque = PriorityQueue() # 데이터 추가 myque.put(data) # 데이터 추출 myque.get() # 사이즈 반환 myque.qsize() # 비었는지 확인 myque.empty() (2) heapq import heapq myqueue = [] # 데이터 추가 heapq.heappush(m..

💡 그래프 탐색 하나의 노드에서 시작하여 노드와 연결된 모든 정점들을 한 번씩 방문하는 것 💡 DFS (깊이 우선 탐색) DFS는 이름 그대로 깊이를 우선으로 탐색하는 방법이다. 전회 순회라고도 할 수 있는데 쉽게 말하면 아래 그림처럼, "루트 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리" 순으로 방문하는 방식이다. 그리고 이 과정이 재귀적으로 반복된다고 이해하면 된다. 왼쪽 서브트리에 방문하면 왼쪽 서브트리에서는 왼쪽 서브트리의 루트 노드를 먼저 방문하고 그 루트 노드의 왼쪽 서브트리 -> 오른쪽 서브트리를 방문하는 방식이다. 예시를 통해 더욱 쉽게 이해할 수 있는데, 만약 그래프가 위와 같다고 하면 DFS의 순회 순서는 0 - 1 - 2 - 3 - 4 - 5가 된다. 루트 노드의 0 방문 0이 루트..

💡 알고리즘의 분석 알고리즘의 성능을 평가하기 위한 분석으로, 크게 수행 시간(시간 복잡도)과 필요한 기억 장치의 양(공간 복잡도)으로 평가되는데, 대부분의 경우에 수행 시간이 더 중요한 의미를 지닌다. 따라서, 해당 글에서는 시간 복잡도 분석을 통해 설계한 알고리즘이 얼마나 효율적으로 문제를 풀어내는가에 대한 지표를 제시하고 판단의 근거를 제시하는 방법을 나열한다. 시간 복잡도 분석이란 입력크기에 따라 단위연산이 몇 번 수행되는지 결정하는 절차이다. 💡 분석 방법의 종류 1. 일정시간 (모든 경우) 분석 (Every-case analysis) 입력 값에는 종속되지 않으며, 입력 크기에만 종속되어 있는 경우이다. 즉, 입력 값에 상관없이 항상 연산의 실행 횟수가 동일한 경우를 의미하며, 아래에서의 $T(..

강의출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님 코드 결과) https://github.com/nyunu/data_structure/blob/main/%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%AC.ipynb GitHub - nyunu/data_structure Contribute to nyunu/data_structure development by creating an account on GitHub. github.com 평가트리 평가트리란 ? : 이진 트리에 저장된 수식을 탐색하면서 값을 계산할 수 있는 트리 -> 노드 구조 left, right : 연결 링크 data : 노드가 가지고 있는 값 value : 수식의 계산 값 [예제 1] 논리 연산식 평가..

강의출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님 코드 결과) https://github.com/nyunu/data_structure/blob/main/%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%AC.ipynb GitHub - nyunu/data_structure Contribute to nyunu/data_structure development by creating an account on GitHub. github.com 이진트리 표현법 1. 선형리스트 이용 [배열 표현법] 루트를 배열의 1번 인덱스에 저장 -> 나머지 노드들도 위치에 따라 번호 부여 -> 배열에 각 노드를 인덱스 번호에 맞게 저장 0번 인덱스는 인덱스로 트리의 관계를 나타낼 수 있기 때문..

강의 출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님 1. 트리 : 계층적 자료의 표현에 적합한 자료 구조 = 루트 노드 + 서브 트리 2. 이진트리 1) 이진트리란 ? : 모든 노드가 2개의 서브 트리(노드)를 갖는 트리 서브 트리는 공집합일 수도 있음 루트와 왼쪽 서브트리 & 오른쪽 서브트리로 구성된 노드들의 집합 이진트리의 서브트리는 모두 이진트리 2) 허프만 코드 트리 : 문자에 대한 컴퓨터 내부 표현 중 하나 -> 텍스트 문서 압축 빈도수가 높은 문자에 대해서는 짧은 코드를 부여 빈도수가 적은 문자에 대해서는 긴 코드를 부여 결론적으로 최대한 적은 비트만 차지하도록 하는 것 3) 트리 관련 용어 노드 : 데이터와 연결선으로 구성된 트리의 한 유닛 노드의 차수 : 해당 노..

강의 출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님 원형 리스트 1. 원형 리스트란 ? 단일 리스트에서의 마지막 노드가 맨처음 노드와 연결된 형태 마지막 노드의 link가 NULL이 아님 head가 변경되어도 연결리스트를 유지할 수 있음 2. 원형 리스트 구현 1) 노드 기본 구현 class Node: def __init__(self, item): self.data = item self.link = None 2) 원형 연결 리스트 연산 종류 삽입 연산 삭제 연산 리스트 길이 계산 3) 원형 연결 리스트 구현 (1) 삽입 연산 삽입 연산의 경우의 수 세 가지 빈리스트에 삽입하는 경우 리스트 맨 앞 위치로 삽입하는 경우 리스트 중간(OR 끝)에 삽입하는 경우 코드 구현1 - 빈리스..

강의 출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님 연결리스트의 기본 구조 데이터 필드와 하나 이상의 링크 필드로 구성된 노드가 연결된 형태 => 노드 = 데이터 필드(해당 노드가 담고있는 data) + 링크 필드(다음 노드를 가리키는 link) 단일 연결 리스트 1. 단일 연결 리스트란 ? 노드들이 한 방향으로 연달아 연결되어 있는 구조 head, tail 노드 head : 리스트의 첫 노드 tail : 리스트의 끝 노드 2. 단일 연결 리스트 구현 1) 노드 기본 구현 class Node: def __init__(self, item): self.data = item self.link = None 2) 단일 연결 리스트 연산 종류 삽입 연산 삭제 연산 리스트 길이 계산 리스트..