컬렉션 프레임워크란? 다수의 데이터를 다루는 데 필요한 배열과 비슷하지만 더 성능이 뛰어난 많은 클래스들을 제공한다 크게 3가지 그룹이 있는데 List, Set, Map이다. 컬렉션 프레임워크의 인터페이스간 상속계층도 계층도와 같이 Map인터페이스는 상속계층도에 포함되지 않는다, 전혀 다른 형태로 컬렉션을 다루기 때문이다. 인터페이스 특 징 List 데이터의 중복을 허용하는 순서가 있는 데이터의 집합. 클래스 : ArrayList, LinkedList, Stack, Vactor 등 Set 데이터의 중복을 허용하지 않고 순서를 유지하지 않는 데이터의 집합. 클래스 : HashSet, TreeSet 등 Map 키(key)와 값(value)로 이루어진 데이터의 집합 키는 중복을 허용하지 않고 값의 중복을 허용..

힙 자료구조 힙 자료구조는 원소 값들 중에서 최대값과 최소값을 구하는데 효율적인 자료 구조를 의미합니다. 트리의 개념을 공부하고 싶으면 04 트리와 이진트리 (Tree & Binary Tree) 기본 여기를 참조해주세요. 힙은 완전 이진 트리의 형태를 가지면서 동시에 다음과 같은 힙 성질을 만족해야 합니다. ● 부모노드가 자식노드보다 큰 경우 - 최대 힙 ● 부모노드가 자식노드보다 작은 경우 - 최소 힙 ▶ 이번 게시글에서는 최대 힙을 기준으로 설명 하겠습니다. 왼쪽 최대 힙을 보면 모두 부모 노드의 값이 자식 노드 값보다 큰 형태를 이루고 있습니다. 부모 노드 50의 경우 자식 노드 25와 40보다 크며, 부모 노드 25는 자식 노드 12와 14보다 큰 형태를 이루고 있습니다. 즉, 힙의 이러한 성질 ..

원형큐 (Circular Queue) 원형 큐는 선형 큐의 문제점을 보완하기 위한 자료구조입니다. 앞선 포스팅에서 선형큐의 문제점은 rear이 가르키는 포인터가 배열의 마지막 인덱스를 가르키고 있을 때 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용 할 수가 없었습니다. 원형큐에서는 포인터 증가 방식이 (rear+1)%arraysize 형식으로 변환하기 때문에 배열의 첫 인덱스부터 다시 데이터의 삽입이 가능해집니다. ■ Enqueue rear의 포인터를 1증가 시키고 그 위치에 데이터 삽입이 이루어집니다. 만약 rear+1이 배열의 끝이고 포화상태가 아니라면 배열의 첫 번째 인덱스에 데이터를 삽입합니다. → 배열의 포화상태 여부를 판단하기 위하여 배열의 1칸은 비워둡니다. (rear+1)%arra..

선형 큐 (Linear Queue) 큐는 가장 먼저 들어온 데이터가 가장 먼저 내보내지는 (FIFO : First In First Out) 구조를 가집니다. 선형 큐는 데이터를 집어넣는 Enqueue 기능과 데이터를 내보내는 Dequeue 기능을 제공합니다. ■Enqueue 기능 Enqueue는 큐 자료구조에 데이터를 집어 넣는 기능을 수행합니다. 영화 매표소에 사람들이 줄을 선다고 생각해봅니다. 이때 매표소 가장 앞사람을 가르키는 것을 front라 하고 마지막에 서있는 사람을 가르키는 것을 rear이라고 부릅니다. 1번이 Enqueue 되어진 상태입니다. 첫 번째로 줄을 선 사람이므로 front와 rear이 둘다 1번을 가르키고 있습니다. 다음으로 2번이 Enqueue 기능을 수행 한 상태입니다. Fr..

스택 (Stack) 스택(Stack)은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO- Last In First Out)으로 되어있습니다. 자료를 넣는 것을 PUSH라고 하고 넣어둔 자료를 꺼내는 것을 POP이라고 합니다. ■ 스택 입/출력 방식 실제로 스택이 어떤 식으로 자료가 입/출력 되는지 살펴 보겠습니다. 상자안에 책을 쌓는다고 생각을 하면 됩니다. 즉 가장 먼저 넣은 책은 가장 나중에 꺼낼 수 있으며, 가장 최근에 넣은 책을 가장 먼저 뺄수 있습니다. 가장 먼저 5를 PUSH 합니다. 스택 자료 구조에 가장 아래에 위치하게 됩니다. 차례대로 PUSH 4, PUSH 3을 한 결과입니다. POP 2회를 실시하게 되면 출력 결과는 3,4가 됩니다. 즉 3은 가장 나중에 입력 되었지만 ..

자료구조는 list, stack, queue, hash table이 있다. 그 중에서 list, set, map의 차이점에 대해 알아보자 1. List : 저장공간이 필요에 의해 자동으로 늘어난다 ( 순서가 있는 저장공간 ) * 특징 : 순서가 있고, 중복을 허용(배열과 유사) * 장점 : 가변적인 배열9배열이 자동으로 늘어남) * 단점 : 원하는 데이터가 뒤쪽에 위치하는 경우 속도의 문제 * 방식 : equals()를 이용한 데이터 검색 자바에서 list자료 구조는 크게 vector, arraylist, linkedlist로 나눠진다. 1) Arraylist : 객체 내부에 있는 배열에 데이터를 저장한다 - 상당히 빠르고 크기를 맘대로 조절할 수 있는 배열 - 단방향 포인터 구조로 자료에 대한 순차적인..

[알고리즘] 알고리즘의 개념과 기본 자료구조 1. 알고리즘의 정의와 조건 1) 알고리즘의 정의 주어진 문제를 풀기 위한 명령어들의 단계적 나열 2) 알고리즘의 조건 입력 : 0개 이상의 외부 입력 출력 : 1개 이상의 출력 명확성 : 각 명령은 모호하지 않고 명확해야 함 유한성 : 한정된 수의 단계를 거쳐 반드시 종료됨 유효성 : 모든 명령은 컴퓨터에서 수행 가능해야 함 알고리즘의 조건을 합쳐서 정의하자면 알고리즘이란 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 컴퓨터가 수행 가능한 일련의 유한개의 명령들을 순서적으로 구성한 것이다. 2. 알고리즘 생성 단계 3. 알고리즘의 표현/기술 방법 알고리즘은 크게 일상 언어, 의사 코드(Pseudo code), 순서도의 세 가지 방법으로 표현할 수 있..

1. 리스트의 개념 리스트의 예 - 리스트는 배열과 달리 원소들 간의 논리적인 순서를 위한 자료구조이다. - 원소들 간의 순서는 논리적으로(추상적으로) 지켜지며 원소가 저장되는 물리적인 위치는 상관하지 않는다. - 배열의 순서 : 물리적 VS 리스트의 순서 : 논리적=추상적=의미적 - 배열을 이용해 리스트를 구현하면 논리적인 순서를 지키기 위해 원소의 이동이 많아진다. - 따라서 리스트는 일반적으로 포인터 변수를 이용한 연결 리스트를 이용한다. - 포인터 변수 : 다음 원소를 가리키는 위치 저장 - 포인터 변수와 동적 메모리 할당을 이용해 메모리 낭비를 막을 수 있다. 2. 배열을 이용한 리스트의 구현 자료의 삽입, 삭제가 빈번히 발생하는 상황에서 리스트를 배열로 구현하는 것은 자료 이동으로 인해 컴퓨팅..

1. 큐(queue)의 개념 큐는 줄을 선 순서대로 처리되는 모습으로 표현할 수 있다. - 큐의 스택의 공통점은 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형이라는 것 - 가장 먼저 입력된 자료가 가장 먼저 출력되는 관계를 표현한다. - FIFO(First In First Out, 선입선출) - FCFS(First Come First Servce, 선착순 서브) - 한쪽 끝에서는 원소의 삽입 연산만, 다른 한쪽 끝에서는 삭제 연산만 발생 - 두개의 큐 포인터 변수(일반적으로 front, rear로 명명)를 사용한다. - front는 큐의 삭제가 발생하는 지점을 가리킨다. - rear는 큐의 삽입이 발생하는 지점을 가리킨다. - 삽입 시 rear를 증가시키고 삭제 시 front를 감소..

1. 스택(Stack)의 개념 스택은 이 동전 더미처럼 위로 쌓아올린 모습으로 표현할 수 있다. - 스택은 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형이다. - 가장 늦게 입력된 자료가 가장 먼저 출력되는 관계를 표현한다. - LIFO(Last In First Out, 후입선출) - 하나의 스택 포인터 변수(일반적으로 top으로 명명)를 사용한다. - top은 스택의 삽입과 삭제가 일어나는 지점을 가리킨다. - 삽입 시 top을 증가시키고 삭제 시 감소시킨다. 2. 스택의 추상 자료형(ADT) * Object(객체) 0개 이상의 원소를 갖는 유한 순서 리스트 * Functions(연산) stack∈Stack, item∈element, maxStackSize∈positive inte..