본문 바로가기

자료구조16

[자료구조 알고리즘] 자료구조 효율적인 탐색을 위한 정렬알고리즘#2 [구현한 코드]- https://github.com/imjinbro/datastructure/tree/master/src/main/java/com/jinbro/source/sorting- 이제 배운 정렬 알고리즘으로 여러 데이터를 정렬해봐야지 [병합정렬]1) 큰 문제를 더이상 쪼갤 수 없을 떄까지 쪼개서 해결(정렬)하면서 결합- 결합하면서 정렬 : 1개까지 쪼개버려서 정렬하면서 붙임(완전 단순화)- 실제로 쪼개는게 아니라 접근 제한(1) 쪼갤 수 있을 떄까지 쪼개고(2) 최소한의 상태로 쪼개진 2개를 가지고 정렬 - 병합 2) 성능 : NlgN (데이터 N개 일 때 최악의 경우 얼마나!)- 연산 : 분할(나눠) + 병합(비교 정렬 후 합치기) - 둘 중에 병합 평가만 일단(1)병합 단계가 데이터 개수에 .. 2017. 11. 17.
[자료구조 알고리즘] 자료구조 효율적인 탐색을 위한 정렬알고리즘#1 [정렬]- 자료구조 연산 : 삽입 - 삭제 - 탐색(정렬되어있는 상태로)- 탐색을 위한 정렬 : 탐색을 효율적으로 하기위해서 [버블정렬]1) 구현하기는 쉽지만 데이터 개수가 늘어남에 따라 연산 횟수도 늘어남2) N개의 데이터에서 순서대로 2개씩 잡고 오름/내림차순(비교와 이동 연산)에 따라 정렬함3) 공간복잡도 O(N) : 같은 배열에서 진행하기때문에4) 시간복잡도 - 워스트 케이스- 비교했을 때 모두 이동함- 어쨌든 비교를 데이터 개수만큼 해야하고 비교를 어떻게 하나 : (n-1)번 + (n-2)번 + ...... + 1- 등차수열의 합 : n(n-1)/2 -> O(N^2) static void sort(int[] arr){ int length = arr.length; for(int i=0; i 2017. 11. 11.
[자료구조 알고리즘] 기능성 이진트리 - 우선순위큐, 힙 [구현코드 - github]- primitive val heap : https://goo.gl/FYP5im- heap : https://goo.gl/kc6KKT [우선순위큐]1) 입구 - 출구가 나뉘어져있어서 붙여진 이름 큐2) 비선형자료구조 : 우선순위에 의해 계층적으로 데이터를 표현/동작, 선형자료구조인 큐와는 다름(단지 입출구때문에)3) 우선순위에 의해서 Out 순서가 정해짐 : 들어온 순서는 상관없음4) 힙을 기반으로 만들어짐 : 내부적으로 힙을 사용, 힙의 메서드 호출, 같은 구현내용 [힙 소개]- 배열로 만들어지는 이진트리 : 삽입, 삭제 과정에서 트리의 마지막노드를 알아야 쉽게 구현할 수 있어서- 기능성 이진트리 : 우선순위에 의한 내부 정렬 + 데이터 계층 표현 1) 조건 : 완전이진트리 .. 2017. 11. 9.
[Java] 자료구조 API - 컬렉션프레임워크 [샘플코드]- https://github.com/imjinbro/javaBasic/tree/master/src/com/jinbro/source/collection [컬렉션 프레임워크]- 객체 자료구조를 API로 제공함 : 인터페이스와 인터페이스 구현 클래스 제공- 주요 인터페이스1) List : 선형자료구조(순서O), 중복O2) Set : 순서X, 중복X3) Map : key-value 쌍으로 저장, 순서X, key는 중복되면 X / value는 중복되어도 상관X0) Collection 인터페이스 > List, Set : List와 Set은 Collection으로 묶임- 같은 메서드가 많으니 하나의 타입(Collection)으로 묶음 : 타입에 대한 의미랄까- 제네릭 사용 : 타입인자 넘겨주지않으면 기본.. 2017. 11. 8.
[자료구조 알고리즘] 이진트리 - 수식트리 만들기 [수식트리]- 수식을 여러가지로 표현하기위해서 구성해놓는 트리 : 이진트리(연산자 수식 트리로 변경 : 수식트리의 루트노드만 리턴받으면 됨 */ char[] data = exp.toCharArra.. 2017. 10. 17.
[자료구조 알고리즘] 트리, 이진트리, 이진트리 순회 [트리란]1) 비선형자로구조 : 데이터의 관계를 나타내는 것에 비중이 큼2) 뿌리에서 가지를 뻗어나가는 형태의 자료구조 : 계층을 나타냄 [트리 관련 개념]1) 노드 : 트리 구성요소2) 엣지 : 노드와 노드를 연결하는 선3) 루트노드 : 트리구조에서의 최상위노드(서브트리도 포함, 어떤 트리가 문제해결의 중심이냐에 따라)4) 단말노드 : 아래로 다른 노드와의 연결없는 노드5) 내부노드 : 단말노드를 제외한 노드, 관계가 있는 노드6) 레벨 : 같은 높이에 있는 노드들7) 높이 : 루트노드(0)를 기준으로 가지가 총 몇단계에 걸쳐 뻗어져있는가?, 최대 레벨은 높이와 같음8) 서브트리 : 루트노드에서 뻗어져나온 노트들이 또 뻗었을 때 그때 트리 형태9) 형제관계 : 같은 레벨의 노드10) 부모관계11) 포화.. 2017. 10. 13.
[자료구조 알고리즘] 덱 [덱]- Double Ended Queue- 양쪽 IO 큐 [덱 메서드] 1) isEmpty 2) pushFront3) popFront4) pushLast5) popLast6) peekFront7) peekLast [덱 구현] - https://github.com/imjinbro/datastructure/blob/master/src/main/java/com/jinbro/source/queue/Deque.java [활용하기] - BOJ 덱 활용문제 풀어보기 2017. 10. 4.
[자료구조, 알고리즘] 스택 #1 - 소개, ADT, 구현 전 준비 [스택](1) LIFO : Last-In First-Out, 가장 먼저 들어온 데이터가 가장 마지막에 나가는 구조 (2) push - pop or peek - push : 데이터 푸쉬 - pop : 데이터를 꺼내는 것(삭제 개념까지), 마지막에 푸쉬된 데이터 - peek : 마지막에 푸쉬된 데이터 조회 (3) 응용앱보다 시스템 레벨에서 많이 사용 (4) 스택을 활용하는 예시 : 계산기 - 스택 구현한 뒤 계산기도 만들어볼 예정 (5) ADT - init : 스택 초기화, 생성자 - isEmpty : 스택에 저장된 데이터 있는지 체크, TRUE(1) or FALSE(0) - push : 데이터 푸쉬, 반환값 없음 - pop : 데이터 꺼냄, 반환값 - 스택에서 제거되는 데이터, 내부 동작 전 isEmpty.. 2017. 9. 17.
[자료구조, 알고리즘] 리스트#4 - DoublyLinkedList [연결리스트]- 노드 간의 연결된 형태 : 실제로는 각각 따로 떨어져있음, 이어서 붙여놓음 [양방향 연결리스트 객체의 타입 설계]- 추가해! : 연결리스트에 데이터 노드를 추가(연결), 길이에 따라 다르게(0인 경우 1이상인 경우), 데이터를 받아서 데이터 노드에 넣기 - 첫번째로 가 : 현재 노드를 가장 첫번쨰 노드(헤드노드)로 - 다음번째로 가 : 현재 노드를 기준으로 다음노드로 이동 - 이전번째로 가 : 현재 노드를 기준으로 전 노드로 이동 - 삭제해 : 현재 선택된 노드를 삭제하는데, 선택된게 헤드인지, 중간인지, 마지막인지, 다음은 있는지 없는지 잘 따져서 노드 연결 끊이지않게 하기 - 선택된 노드를 줘 : 현재 선택되어진 노드를 리턴 - 개수 : 현재 양방향 연결리스트에 저장된 데이터가 몇개 .. 2017. 9. 15.
[자료구조, 알고리즘] 리스트#3 - js로 CircularLinkedList 구현, 자바로 생각해보기 [연결리스트]- 메모리 상에서는 떨어져있는 데이터 : 각각 연결하여 1열의 개념의 데이터 저장공간을 만듦- 핵심(1) node : 현재 데이터와 현재와 연결된 다음 데이터를 가리키는 주소를 함께 저장 - node -> data, next(2) node 간 어떻게 연결할 것인가, 연결되어져있는 node 탐색방법 - 연결 형태에 따라 단순/원형/양방향 연결리스트 나뉨 [원형 연결리스트]- 단순 연결리스트와 마찬가지로 단방향 : 역방향까지 지원하는 양방향 연결리스트는 다음 포스팅!- 처음 추가된 node와 마지막 node가 연결되어 원형을 띔 - 단순 연결리스트는 head -> tail node로 가기위해 tail에서 next node로 순차탐색=> 위의 그림처럼 head를 둬도 되지만, 원형 연결리스트의 특.. 2017. 9. 6.

티스토리툴바