본문 바로가기

기타38

[자료구조 알고리즘] 자료구조 효율적인 탐색을 위한 정렬알고리즘#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.
[자료구조 알고리즘] 기능성 이진트리 - 우선순위큐, 힙 [구현코드 - github]- primitive val heap : https://goo.gl/FYP5im- heap : https://goo.gl/kc6KKT [우선순위큐]1) 입구 - 출구가 나뉘어져있어서 붙여진 이름 큐2) 비선형자료구조 : 우선순위에 의해 계층적으로 데이터를 표현/동작, 선형자료구조인 큐와는 다름(단지 입출구때문에)3) 우선순위에 의해서 Out 순서가 정해짐 : 들어온 순서는 상관없음4) 힙을 기반으로 만들어짐 : 내부적으로 힙을 사용, 힙의 메서드 호출, 같은 구현내용 [힙 소개]- 배열로 만들어지는 이진트리 : 삽입, 삭제 과정에서 트리의 마지막노드를 알아야 쉽게 구현할 수 있어서- 기능성 이진트리 : 우선순위에 의한 내부 정렬 + 데이터 계층 표현 1) 조건 : 완전이진트리 .. 2017. 11. 9.
[자료구조 알고리즘] 이진트리 - 수식트리 만들기 [수식트리]- 수식을 여러가지로 표현하기위해서 구성해놓는 트리 : 이진트리(연산자 수식 트리로 변경 : 수식트리의 루트노드만 리턴받으면 됨 */ char[] data = exp.toCharArra.. 2017. 10. 17.
[자료구조 알고리즘] 트리, 이진트리, 이진트리 순회 [트리란]1) 비선형자로구조 : 데이터의 관계를 나타내는 것에 비중이 큼2) 뿌리에서 가지를 뻗어나가는 형태의 자료구조 : 계층을 나타냄 [트리 관련 개념]1) 노드 : 트리 구성요소2) 엣지 : 노드와 노드를 연결하는 선3) 루트노드 : 트리구조에서의 최상위노드(서브트리도 포함, 어떤 트리가 문제해결의 중심이냐에 따라)4) 단말노드 : 아래로 다른 노드와의 연결없는 노드5) 내부노드 : 단말노드를 제외한 노드, 관계가 있는 노드6) 레벨 : 같은 높이에 있는 노드들7) 높이 : 루트노드(0)를 기준으로 가지가 총 몇단계에 걸쳐 뻗어져있는가?, 최대 레벨은 높이와 같음8) 서브트리 : 루트노드에서 뻗어져나온 노트들이 또 뻗었을 때 그때 트리 형태9) 형제관계 : 같은 레벨의 노드10) 부모관계11) 포화.. 2017. 10. 13.
[자료구조 알고리즘] BOJ 풀기 [BOJ 풀기]- 자바를 활용한 프로그램 개발에 익숙해지고 문제해결력을 높이기위해서 필요하다고 생각함- 아래 커리큘럼 순서대로 예제가 있음 : 푼 문제는 깃헙에 푸쉬 - https://github.com/imjinbro/algorithm - 어려움.... 그리고 문법 배울 때 그런거지 자료구조 이런거지 했던 것들을 실전에서 써보니깐 확실하게 익혀짐 [알고리즘]- 전체 커리큘럼 : https://offline.startlink.help/hc/ko/articles/217245158 - 기본 : https://code.plus/course/4- 중급 : https://code.plus/course/5- 중급 : https://code.plus/course/6- 중급 : https://code.plus/cour.. 2017. 10. 9.
[자료구조 알고리즘] 덱 [덱]- 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.
[자료구조 알고리즘] 큐 - ADT, Array/Circular/LinkedQueue 구현 [큐]- FIFO : 첫번째로 들어온 데이터가 첫번째로 나감 - 데이터 저장 입구와 출구가 각각 나뉨- 예시 : 매표소, 맛집 줄 등 [큐 ADT]1) isEmpty : 큐가 비었는지 확인2) enQueue : 큐에 데이터 저장3) deQueue : 큐에서 데이터 빼기(삭제)4) qPeek : 첫번째로 저장된 데이터 조회 [큐 구현]- Array, Linked(노드 간 연결)로 구현 1) ArrayQueue- 고정적인 크기 - 내부적으로는 index로 제어- 1열 형태 + 고정적인 크기 : 입구는 막혔고, 출구는 조금씩 입구와 가까워질 때 데이터가 지워진 공간이 메모리 낭비 => CircularQueue 구현이유 2) CircularQueue- Array를 사용- ArrayQueue의 한계점을 극복하기위.. 2017. 9. 29.
[자료구조, 알고리즘] 스택 - Array, Linked 기반 구현(설명, 구현 수정함) [Stack]1) 구현 기반만 다를 뿐 같은 스택을 구현하는 것이기 때문에 Stack 인터페이스 생성해두고 상속 - ArrayStack - LinkedListStack 2) 인터페이스 public interface Stack { public boolean isEmpty(); public void push(Object data); public Object pop(); public Object peek() throws Exception;} [도구가 되는 자료구조] (1) 배열 (2) 연결리스트 - 배열과 연결리스트는 자체만으로도 좋은 자료구조이지만 다른 자료구조를 구성하는데에 있어서 도구가 되는 자료구조 [Array Stack](1) 스택 생성 : N의 크기로 생성, 현재는 비어있음 N개가 그럼 그걸 체크하.. 2017. 9. 22.
[자료구조, 알고리즘] 스택 #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.

티스토리툴바