Algorithms/개념 (8) 썸네일형 리스트형 탐욕 알고리즘(Greedy), 분할정복 알고리즘(Divide and Conquer), 다이나믹 알고리즘 (Dynamic) ㆍ탐욕 알고리즘 (Greedy) 개념 - 각 단계에서 가장 좋은 선택을 하는 방식으로 동작하는 알고리즘 ㆍ탐욕 알고리즘의 특징 - 각 단계에서 가능한 선택지들 중에서 가장 좋은 선택을 하여 해를 구하는 것 - 이 때 "가장 좋은 선택"이란 각 단계에서의 최적해로 이어지는 선택을 의미 - 즉, 현재 상태에서의 최적해를 선택하여 다음 단계로 넘어가는 방식 - 항상 최적해를 보장하지는 않음 ㆍ탐욕 알고리즘 예시 https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 .. 배열과 연결리스트로 Graph 구현 및 기본 개념 정리 ㆍGraph의 구현 ( 인접행렬 ) - 2차원 배열 사용 - 장점 : 간선 정보의 확인과 업데이트가 빠름 - 단점 : 인접 행렬을 위한 메모리 공간 차지 오늘은 비선형자료구조인 그래프의 개념 및 배열과 연결리스트를 통해서 Graph로 간단히 구현해보는 시간을 가지려고 한다. ㆍGraph의 개념 - 정점과 간선으로 이루어진 자료구조(Cycle 0) ㆍGraph의 구조 정점 (Vertex) - 각 노드 간선 (Edge) - 노드와 노드를 연결하는 선 (link, branch) 인접정점 (Adjacent vertex) - 간선 하나를 두고 바로 연결된 정점 정점의 차수 (Degree) - 무방향 그래프에서 하나의 정점에 인접한 정점의 수 무방향 그래프 모든 정점 차수의 합 -> 그래프 간선의 수 2배 진입차수.. 배열과 연결리스트로 Tree 구현 및 기본 개념 정리 오늘은 비선형자료구조인 트리의 개념 및 배열과 연결리스를 통해서 Tree로 간단히 구현해보는 시간을 가지려고 한다. ㆍTree의 개념 - 노드와 링크로 구성된 자료구조 (그래프의 일종, cycle x) - 계층적 구조를 나타낼 때 사용 ㆍTree의 구조 노드 (Node) - 트리구조3의 자료값을 담고있는 단위 에지 (Edge) - 노드간의 연결선 루트노드 (Root Node) - 부모가 없는 노드, 최상위 노드 잎새노드 (Leaf Node) - 자식이 없는 노드, 단말 노드 내부노드 (Internal Node) - 잎새노드를 제외한 모든 노드 부모노드 (Parent Node) - 연결된 두 노드 중 상위의 노드 자식노드 (Child Node) - 연결된 두 노드 중 하위의 노드 형제노드 (Sibling .. ArrayList를 이용한 Deque구현 및 기본 개념 정리 오늘은 선형자료구조인 데크의 개념 및 arrayList를 통해서 deque을 간단히 구현 그리고 마지막으로 deque함수에는 어떤 것들이 있는 지 알아보는 시간을 가지려고 한다. ㆍDeque의 개념 - 큐(Queue)와 스택(Stack)의 특징을 모두 가지고 있는 자료구조 - 양쪽 끝에서 삽입과 삭제가 모두 가능 ㆍArrayList로 Deque구현 import java.util.ArrayList; public class DequeActive { ArrayList list; DequeActive() { list = new ArrayList(); } private boolean isEmpty() { if (list.size() == 0) { return true; } return false; } privat.. ArrayList를 이용한 Queue구현 및 기본 개념 정리 오늘은 선형자료구조인 큐의 개념 및 arrayList를 통해서 queue을 간단히 구현 그리고 마지막으로 queue함수에는 어떤 것들이 있는 지 알아보는 시간을 가지려고 한다. ㆍQueue의 개념 - 데이터를 차곡차곡 쌓아 올리는 형태의 자료구조 - " First In, First Out" (FIFO) : 가장 최근에 추가된 데이터가 가장 먼저 제거되는 원리 ㆍ큐의 구성 Rear - 큐에 끝 Front - 큐에 시작 ㆍArrayList로 Queue구현 import java.util.ArrayList; public class QueueActive { ArrayList list; QueueActive() { list = new ArrayList(); } public static void main(String.. ArrayList를 이용한 Stack 구현 및 기본 개념 정리 오늘은 선형자료구조인 스택의 개념 및 arrayList를 통해서 stack을 간단히 구현 그리고 마지막으로 stack함수에는 어떤 것들이 있는 지 알아보는 시간을 가지려고 한다. ㆍStack의 개념 - 데이터를 차곡차곡 쌓아 올리는 형태의 자료구조 - "Last In, First Out" (LIFO) : 가장 나중에 추가된 데이터가 가장 먼저 제거되는 원리 ㆍ스택의 구성 Push 데이터를 스택에 추가하는 작업, data는 스택의 최상단에 추가 Pop 스택에서 데이터를 제거하는 작업, 가장 최근에 추가된 data가 제거 Top 스택의 최상단에 위치한 데이터, 이는 가장 최근에 추가된 데이터를 가리키는 위치 ㆍArrayList로 Stack구현 import java.util.ArrayList; public c.. 연결리스트 구현 및 기본 개념 정리 오늘은 선형자료구조인 연결리스트의 개념과 배열을 통해서 간단히 구현 그리고 마지막으로 연결리스트 기반인 LinkedList에 대해서 알아보는 시간을 가지려고 한다. ㆍ연결리스트의 개념 연결리스트는 요소가 data와 다음 요소를 가리키는 pointer(참조)로 이뤄져있다. 각 요소를 노드(Node)라고 부르며, 노드는 데이터 필드와 다음 노드에 대한 참조(링크)로 구성. ㆍ연결리스트의 특징 비연속적인 메모리 공간 - 각 노드는 독립적인 객체로 메모리에 분산되어 저장 가변 크기 - 크기가 동적으로 조절 가능 삽입 및 삭제 성능 우수 - 중간에 요소를 추가하거나 삭제할 때 다른 노드들과의 연결만 수정하면 되므로 성능이 우수 접근 성능 떨어짐 - 특정 인덱스의 요소에 접근할 때 처음부터 찾아가야 하므로 배열이나.. 자바 배열을 활용한 ArrayList 구현 및 기본 개념 정리 오늘은 선형자료구조인 배열의 개념 및 arrayList를 배열을 통해서 간단히 구현 그리고 마지막으로 arrayList의 함수에는 어떤 것들이 있는 지 알아보는 시간을 가지려고 한다. ㆍ배열의 개념 배열은 동일한 데이터 유형의 요소를 갖는 데이터 구조로서 여러 값을 하나의 변수에 저장할 수 있도록 해주는 자료구조 ㆍ배열의 특징 동일한 데이터 유형의 요소 - 배열은 동일한 데이터 유형의 요소들로 구성 고정된 크기 - 배열은 생성될 때 크기가 fix되어 나중에 변경 - 크기 변경을 원하면 새 배열 생성 후 복사하는 작업 인덱스 - 배열의 각 요소는 고유한 인덱스(위치)를 가진다. - 첫 번째 인덱스는 0부터 시작해서 순차적으로 증가 메모리에 연속적으로 저장 - 배열의 요소들은 메모리에 연속적으로 저장 - 특.. 이전 1 다음
