자바 프로그래밍 검색 결과

해당 글 45건

자료구조 - 정렬 1 (Bubble / Selection / Insertion)

전체 정렬 개요의 설명은 여기를 참조 Shell 정렬의 설명은 여기를 참조 Merge 정렬의 설명은 여기를 참조 Quick 정렬의 설명은 여기를 참조 Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조 Counting 정렬의 설명은 여기를 참조 Radix 정렬의 설명은 여기를 참조 Bucket 정렬의 설명은 여기를 참조 Topological 정렬의 설명은 여기를 참조 1. Bubble Sort(버블 정렬) 설명보단 보는 것이 제일 빠르다. 다음의 애니메이션을 보고 버블 정렬이 무엇인지 이해해보자. 한 눈에 보아도 이해가 쉽다. 오름차순 정렬을 기준으로 보여주는 애니메이션이다. 연속된 값들을 서로 비교하면서 더 작은 값이 왼쪽에 위치하도록 상호 위치 변경을 해주는 작업을 해주고 있..
자바 프로그래밍/자료구조(Data Structure) 2020. 11. 7. 11:01

자료구조 - 정렬 (개요)

Bubble / Selection / Insertion 정렬의 설명은 여기를 참조 Shell 정렬의 설명은 여기를 참조 Merge 정렬의 설명은 여기를 참조 Quick 정렬의 설명은 여기를 참조 Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조 Counting 정렬의 설명은 여기를 참조 Radix 정렬의 설명은 여기를 참조 Bucket 정렬의 설명은 여기를 참조 Topological 정렬의 설명은 여기를 참조 1. 정렬 알고리즘 개요 지금까지의 포스팅을 통해 다양한 자료구조를 배열 / 리스트 기반으로 구현할 수 있다는 것을 확인하였으므로 이제 그 데이터를 다루는 방법에 대해 좀 더 알아보자. 가장 기본적으로 자료 구조에 정의된 데이터들을 어떻게 정렬할 수 있는지에 대해서 알아보..
자바 프로그래밍/자료구조(Data Structure) 2020. 11. 6. 15:57

알고리즘 - Union-Find(Disjoint-Set 구현하기)

1. Union-Find 란? 이는 Disjoint-Set을 표현할 때 사용되는 자료구조이다. Disjoint-Set이란 공통의 원소가 없는 "상호 배타적"인 부분 집합으로 이루어진 원소에 대한 정보 저장 / 조작을 수행하는 자료구조를 의미한다. 자, 여기서 몇 가지 용어를 이해해 보자. Set - 집합을 의미한다. 원소를 가지며 순서는 고려하지 않는다.(List와의 차이점) Subset - 부분 집합을 의미. 집합 A의 모든 원소가 집합 B에 포함된다면 A를 B의 부분 집합이라고 한다. Superset - 초월 집합을 의미. 집합 A의 모든 원소가 집합 B에 포함된다면 B는 A의 초월 집합이라고 한다. 상호 배타적 집합 - Mutually Disjoint Set. A와 B가 서로 공유하는 원소가 전혀 ..
자바 프로그래밍/알고리즘(Algorithm) 2020. 11. 4. 20:43

자료구조 - 세그먼트 트리(Segment Tree)2 - 느린 전파

이번 내용은 지난 세그먼트 트리(Segment Tree) 자료구조 포스팅에 이어서 느린 전파(Lazy Propagation) 기능에 대해 설명하는 포스팅입니다. 지난 포스팅은 아래 링크를 참고 hongjw1938.tistory.com/20 자료구조 - 세그먼트 트리(Segment Tree) 1. 세그먼트 트리(Segment Tree, 구간 트리)란? 특정 구간 내 연산(쿼리)에 대해 빠르게 응답하기 위해 만들어진 자료구조이다. 예를 들어 크기가 n=100인 int배열 arr이 있다면 0~99의 인덱스 내 숫자들이 hongjw1938.tistory.com 1. 세그먼트 트리 아래의 그림을 보면서 세그먼트 트리의 기존 구조를 복습해 보자. 위 그림에서 합 연산의 결과를 얻고자 한다면 어느 정도의 연산이 필요..
자바 프로그래밍/자료구조(Data Structure) 2020. 11. 2. 22:03

자료구조 - 트라이(Trie)

1. 트라이(Trie)란? 트라이(Trie)는 효율적인 문자열 저장 및 탐색이 가능한 자료구조의 형태이다. 우리가 수많은 문자열을 저장하였는데 입력으로 어떤 문자열이 주어졌을 때, 그것이 내가 저장한 구조에 포함된 문자열인지 어떻게 알 수 있을까? 아래와 같은 방식이 있을 것이다. ① 단순 비교 전체 문자열의 맨 처음부터 끝까지 개별 문자를 비교하는 방식 최대 문자열 길이 m, 전체 문자 개수 n개 시 시간복잡도 : 최악의 경우 O(nm) ② 이진 탐색 기법 전체 문자열을 사전 순으로 배열 저장 후, 중간 값과 비교해 사전적으로 이전이면 좌측의 반 / 이후면 우측의 반으로 비교하는 방식을 반복 최대 문자열 길이 m, 전체 문자 개수 n개 시 시간복잡도 : 정렬 O(nmlogn) / 탐색 O(mlogn) ..
자바 프로그래밍/자료구조(Data Structure) 2020. 10. 25. 22:56

자료구조 - 그래프(Graph)

1. 그래프(Graph)란? 그래프는 객체들이 쌍으로 연관되어 집합을 이루는 구조를 의미한다. 말이 어렵다면, 그래프 구조의 일종인 트리(Tree) 구조를 생각하면 된다. 트리(Tree) 구조 또한 노드(Node)들이 부모/자식 관계로 연결되어 있었다. 노드(Node)가 객체이며 그 관계를 연관성으로 하나의 전체 구조를 이루었다고 보면 된다. 트리(Tree) 처럼, 그래프 또한 내부적으로 부분 그래프(Sub Graphs)로 이루어진다. 그래프는 가장 기본적이고 유연한 구조로 관계를 나타낼 수 있다. 많은 문제들 중 그래프로 해결 가능한 문제가 50% 정도 된다고 이야기하는 엔지니어도 있다. (참고) 해결 가능한 문제들의 예시를 대충 알아보자. 어떠한 것들이 특히 해결이 가능할까? ⓐ 네트워크 : 우리가 ..
자바 프로그래밍/자료구조(Data Structure) 2020. 10. 20. 20:57

자료구조 - 우선순위 큐(Heap, Priority Queue)

1. 우선순위 큐(Priority Queue)란? 이 자료구조는 우선순위 큐라는 말에서 볼 수 있다시피 우선순위가 높은 것을 먼저 꺼내기 위하여 만들어진 자료구조이며, 힙(Heap)이라고도 부른다. 예를 들어서, 숫자 1~10을 저장하는 자료구조를 구현하고 싶은데, 이 숫자들이 랜덤으로 삽입된다고 하자. 숫자가 클 수록 우선순위가 높다고 가정하자. 그렇다면 10이 가장 먼저 꺼내지고, 그 뒤로 9, 8, 7, ... , 1 순으로 추출될 수 있을 것이다.(이것을 최대힙, Max Heap 이라 부른다.) 숫자가 작을 수록 우선순위가 높다고 가정하자. 이 경우 1이 가장 먼저 꺼내지고, 그 뒤로 2, 3, 4, ... , 10순으로 추출될 수 있을 것이다.(이것을 최소힙, Min Heap 이라 부른다.) 여..
자바 프로그래밍/자료구조(Data Structure) 2020. 9. 30. 22:29

자료구조 - 스택, 큐 직접 구현(Stack, Queue)

1. 스택, 큐란? 이미 이전의 포스팅들에서 설명을 완료하였으므로 해당 포스팅의 링크를 아래와 같이 표시해두겠습니다. 간단히 설명하면 스택은 LIFO(Last-In, First-Out), 큐는 FIFO(First-In, First-Out) 방식을 취하는 자료구조이다. hongjw1938.tistory.com/4?category=884192 자료구조(Java) - Collection Framework 자바(Java)에서는 다양한 자료구조를 사용자가 쉽게 활용하도록 성능적으로도 우수하며 코딩에 할애하는 시간을 줄일 수 있는 Collection Framework를 제공하고 있다. 이 Collection Framework는 자료를 저장 hongjw1938.tistory.com 아래에 각각의 자료구조를 배열 또는..
자바 프로그래밍/자료구조(Data Structure) 2020. 9. 30. 13:57