전체 글45 [자료 구조] 트리(Tree) - 1.구조 이해 * 해당 글은 패스트캠퍼스의 자료구조 알고리즘 강의를 듣고 정리하였습니다. 저작권은 패스트캠퍼스에 있습니다. 📌 트리(Tree)란 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 그 중에서 노드의 Branch가 최대 2개인 경우를 이진 트리라고 부른다. ✔️ 이진 트리 종류 이진 탐색 트리 완전 이진 트리 (Heap에서 사용) ... ✔️ 이진 트리에서 알아야 하는 용어 노드(Node) : 트리에서 데이터를 저장하는 기본 요소 (그림에선 동그라미임. data + branch 정보) 루트 노드(Root Node) : 트리 맨 위에 있는 노드 레벨 (Level) : 최상위 노드를 Lv0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄. 부모 노드 (Parent .. 2021. 6. 25. [자료구조] 힙(Heap) - 2. 파이썬 구현 * 해당 글은 패스트캠퍼스의 자료구조 알고리즘 강의를 듣고 정리하였습니다. 저작권은 패스트캠퍼스에 있습니다. 📌힙과 배열 일반적으로 힙 구현시 배열 자료구조를 활용한다. 주의할 점은 배열은 인덱스가 0부터지만, 힙 구현의 편의를 위해 root의 인덱스를 1로 지정한다. 부모 인덱스 번호 = 자식 노드 인덱스 번호 // 2 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 *2 + 1 📌 힙에서 데이터 삽입 구현 (Max Heap) ✔️ move_up, insert 구현 class Heap: def __init__(self, data): # 배열로 힙을 구현 self.heap_array = list() # heap_array[0]은 사용.. 2021. 6. 25. [자료구조] 힙(heap) - 1.구조 이해 * 해당 글은 패스트캠퍼스의 자료구조 알고리즘 강의를 듣고 정리하였습니다. 저작권은 패스트캠퍼스에 있습니다. 📌힙 (Heap) 이란 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Complete Binary Tree)이다. 여기서 완전 이진 트리는 노드를 삽입할 때, 최하단 왼쪽 노드부터 차례대로 삽입하는 트리이다. 따라서 완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다. 📌힙을 사용하는 이유 배열에 데이터를 넣고 최대값/ 최소값을 찾으려면 O(n)이 걸린다. 하지만 힙에 데이터를 넣고, 최대값과 최소값을 찾으면 O(logn)이 걸린다. ✔️ 이처럼 최대값 또는 최소값을 빨리 찾아야 하는 자료구조 및 알고리즘 구현에 활용된다. 📈 시간 복잡도 배열에 데이.. 2021. 6. 25. [컴퓨터 구조] 산술 논리 시프트 장치 (ALU) 컴퓨터에서는 각 마이크로 연산마다 독립된 레지스터를 두는 대신에 산술 논리 장치(ALU)라고 하는 공용 연산 장치에 연결된 레지스터 그룹을 사용한다. 즉 간단히 말해서 앞에서 배웠던 모든 마이크로 연산을 한 곳에 모아서 수행한다는 뜻이다. 레지스터 전송,산술, 논리, 시프트 모두 한 회로에 나타내면 다음과 같다. 여기서 산술회로와 논리회로 블록은 밑에 있는 회로를 간단히 표현한 것이다. (좌) 산술 회로 / (우) 논리 회로 그림1을 보면 시프트 회로 블록은 확인할 수 없는데, ALU에서는 시프트 마이크로 연산을 한 부분으로 구현된다. 즉 자세히 보면 4x1 mux에 2, 3 입력으로 Ai-1과 Ai+1이 들어가는 것을 볼 수 있는데, 이것이 시프트 마이크로 연산을 ALU.. 2021. 6. 25. [컴퓨터 구조] 논리 마이크로연산, 시프트 마이크로 연산 마이크로 연산이란 레지스터에 저장된 데이터에 대해 수행되는 기본적인 연산이다. 크게는 네가지로 나눌 수 있다. 1) 레지스터 전송 마이크로 연산 2) 산술 마이크로 연산 3) 논리 마이크로 연산 4) 시프트 마이크로 연산 1),2) 는 이전 포스팅을 참고하면 된다. https://programming-hee.tistory.com/5 [컴퓨터구조] 산술 마이크로 연산 3) 논리 마이크로 연산 논리 마이크로 연산은 레지스터에 저장된 비트열에 대한 이진 연산으로 각 비트를 독립된 이진 변수로 간주하고 연산을 수행한다. 간단히 말하면 레지스터에 들어있는 값을 산술적으로 보지 않고, 비트연산을 수행한다는 뜻이다. 비트 연산은 대표적으로 AND, OR, XOR, complement가 있다. 그렇다면 산술.. 2021. 6. 25. [컴퓨터 구조] 산술 마이크로 연산 마이크로 연산이란 레지스터에 저장된 데이터에 대해 수행되는 기본적인 연산이다. 크게는 네가지로 나눌 수 있다. 1) 레지스터 전송 마이크로 연산 2) 산술 마이크로 연산 3) 논리 마이크로 연산 4) 시프트 마이크로 연산 1) 레지스터 전송 마이크로 연산 여기서 레지스터 전송 마이크로 연산은 이전 블로그 포스팅에서 확인할 수 있다. https://programming-hee.tistory.com/3 [컴퓨터구조] 버스와 메모리전송 (multiplexer, 3 state buffer) 2) 산술 마이크로 연산 산술 마이크로 연산이란 레지스터 안에 들어있는 값들을 더하거나 빼는 과정을 뜻한다. 레지스터 A에 들어있는 값과 레지스터 B에 들어있는 값을 가지고 산술 연산을 하는 것을 예시로 들.. 2021. 6. 25. 이전 1 ··· 4 5 6 7 8 다음
