본문 바로가기

🖥️ Computer Science25

[자료구조] 트리(Tree) 트리(Tree) 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조 계층적인 자료를 표현하는데 이용 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성 하나의 루트노드를 가짐 트리와 관련된 용어 노드(node) 트리를 구성하고 있는 기본요소 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음 간선(edge) 노드와 노드 간의 연결선 (link, branch라고도 부름) 루트 노드(root node) 부모가 없는 최상위 노드, 트리는 하나의 루트 노드만을 가짐 (A) 부모 노드(parent node) 자신 노드를 가진 노드 (H, I의 부모 노드는 D) 자식 노드(child node) 부모 노드의 하위 노드 (노드 D의 자식 노드는 H, I) 형제 노드(sibling node) 같은.. 2023. 3. 9.
[자료구조] 그래프(Graph) 그래프(Graph) 연결되어있는 원소간의 관계를 표현한 자료구조 노드(Node)와 그 노드를 연결하는 간선(Edge)을 하나로 모아 놓은 자료구조 그래프 관련 용어 정점(vertex): 위치라는 개념 (node 라고도 부름) 간선(edge): 위치 간의 관계, 노드를 연결하는 선 (link, branch 라고도 부름) 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름) 진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 .. 2023. 3. 8.
[자료구조] Time Complexity (시간 복잡도) Time Complexity (시간 복잡도) 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계 알고리즘의 로직이 얼마나 오랜 시간이 걸리는지 나타내는 데 사용 알고리즘의 로직을 코드로 구현할 때, 효율적으로 구현하기위해 고려해야 함 효율적인 알고리즘 구현: 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성 주로 빅-오 표기법을 사용해 나타냄 시간 복잡도를 표기하는 방법 Big-O(Big-Oh, 빅-오) ⇒ 상한 점근, 최악의 경우에 대해 나타내는 방법 Big-Ω(Big-Omega, 빅-오메가) ⇒ 하한 점근, 최선의 경우에 대해 나타내는 방법 Big-θ(Big-Theta, 빅-세타) ⇒ 빅 오와 빅 오메가의 공통부.. 2023. 3. 7.
[자료구조] 큐(Queue) 큐(Queue) 선입선출(First-In-First-Out, FIFO) 원칙에 따라 데이터를 저장하는 자료구조 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조 한쪽 끝에서만 삽입이 이루어지고, 다른 한쪽 끝에서는 삭제 연산만 이루어지는 유한 순서 리스트 일상생활에서 줄을 서서 기다리는 것과 유사 대기열이나 작업 스케줄링 등에서 유용하게 사용 삽입 및 삭제에 O(1), 탐색에 O(n) 의 시간 복잡도를 가짐 큐(Queue)의 구현 큐는 대개 배열이나 연결 리스트를 이용해 구현 배열을 이용하는 경우, front와 rear라는 두 개의 인덱스 변수를 사용하여 큐의 시작과 끝을 가리킴 데이터를 삽입할 때에는 rear 변수를 증가시켜 새로운 데이터를 마지막에 추가 데이터를 추출할 때에는 front 변수를 증가시.. 2023. 3. 6.
[자료구조] 스택(Stack) 스택(Stack) 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조 LIFO(후입선출): 가장 최근에 들어온 데이터가 가장 먼저 나감 재귀적인 함수, 알고리즘에 사용 웹브라우저 방문 기록 등에 사용 삽입 및 삭제에 O(1), 탐색에 O(n)의 시간복잡도를 가짐 스택의 구조 스택 상단(stack top): 스택의 가장 윗부분, 스택에서 입출력이 이루어지는 부분 스택 하단(stack bottom): 스택의 가장 아랫부분 요소(element): 스택에 저장되는 것 공백 스택(empty stack): 비어있는 스택 포화 스택(full stack): 포화 상태의 스택 스택의 연산 pop(): 스택에서 가장 위에 있는 항목 제거 push(element): 요소를 스.. 2023. 2. 14.
[자료구조] 연결 리스트(Linked List) 연결 리스트(Linked List) 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조 배열의 고정 크기의 단점을 보완하기 위해 만들어짐 배열과 달리 연속적인 메모리 공간에 저장되어 있지 않기 때문에 연결 필요 연결 리스트 표현 Head는 리스트의 처음을 나타냄 노드는 데이터와 다음 노드를 가리키는 Next 포인터로 구성 각 노드는 Next 포인터를 사용해 다음 노드와 연결 마지막 노드는 null을 가리켜 리스트의 끝을 나타냄 연결 리스트 종류 1. 단일 연결 리스트 각 노드당 한 개의 포인터르 가지고 있음 포인터는 다음 노드의 위치를 가리킴 2. 이중 연결 리스트 각 노드당 두 개의 포인터를 가지고 있음 포인터는 각각 이전 노드와 다음노드의 위치를 가리킴 3... 2023. 2. 10.
[자료구조] 배열(Array)이란? 배열(Array) 연속된 메모리 공간에 순차적으로 저장된 데이터 모음 같은 타입의 데이터를 저장 요소(elemnet): 배열을 구성하는 각각의 값 인덱스(index): 배열에서의 위치를 가리키는 숫자 (0부터 시작) 배열 표현 크기가 5인 Int형 배열 array를 선언 swift var array: [Int] = [1, 2, 3, 4, 5] python array = [1, 2, 3, 4, 5] C int array[5] = {1, 2, 3, 4, 5}; Java Int[] array = {1, 2, 3, 4, 5}; 다차원 배열 (Multidimensional Array) index가 2개 이상으로 이루어진 배열 다차원 배열은 인덱스를 2개부터 최대 n개까지 만들 수 있음 //2차원 var array.. 2023. 2. 10.
[알고리즘] 그래프 알고리즘 그래프(Graph) 노드(Node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조 서로 다른 개체(혹은 객체)(Object)가 연결되어 있다는 문제는 그래프 알고리즘 떠올리기 그래프 구현 방법 인접 행렬(Adjacency Matrix) : 2차원 배열 사용 메모리 공간이 많이 필요하지만 특정 노드 간 간선의 비용을 O(1) 시간으로 즉시 알 수 있음 인접 리스트 (Adjacency List) : 리스트 사용 간선의 개수인 O(E) 만큼만 메모리 공간이 필요하지만 O(V) 시간 소요 그래프 트리 방향성 방향 그래프 혹은 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 루트 노드가 없음 루트 노드가 존재 노드간 관계성 부모와 자식 관계 없음 부모 자식 관계.. 2022. 4. 14.
[알고리즘] 최단 경로(Shortest Path) 최단 경로(Shortest Path) 알고리즘 가장 짧은 경로를 찾는 알고리즘 길 찾기 문제라고도 불림 그래프를 이용하여 표현 각 지점은 노드로 표현 지점과 연결된 도로는 간선으로 표현 최단 경로 문제의 종류 단일 출발(single-source) 최단 경로 어떤 하나의 정점에서 출발하여 나머지 모든 정점까지의 최단 경로를 찾는 문제 단일 도착(single-destination) 최단 경로 모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로를 찾는 문제 그래프 내의 간선을 뒤집으면 단일 출발 최단거리 문제로 바뀔 수 있음 단일 쌍(single-pair) 최단 경로 모든 정점 쌍들 사이의 최단 경로를 찾는 문제 주요 알고리즘 다익스트라(Dijkstra) 알고리즘 벨만-포드(Bellman-Ford-Moo.. 2022. 3. 31.
[알고리즘] 다이나믹 프로그래밍(Dynamic Programming) 컴퓨터를 활용해도 어려운 문제 최적의 해를 구하기에 시간이 매우 많이 필요한 문제 최적의 해를 구하기에 메모리 공간이 매우 많이 필요한 문제 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라 많은 제약 발생 ☞ 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘 작성 필요 다이나믹 프로그래밍(Dynamic Programming) 동적 계획법 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 다이나믹 프로그래밍은 다음 조건을 만족할 때만 사용 가능 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 .. 2022. 3. 30.
반응형

티스토리툴바