HwangHub

오늘은 서로 중복된 원소가 없는 '분리 집합 or 서로소 집합(Disjoint Set)'에 대해 알아보고, 이를 이용하여 노드 간의 연결 여부를 판별하는 'Union Find' 알고리즘에 대해 알아보겠습니다. 이 두 가지는 그래프 알고리즘에서 중요하게 다루어지며, 특히 최소신장트리(Minimum Spanning Tree)를 구현하는 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘에서 활용됩니다. 먼저, Disjoint Set은 각각의 원소가 하나의 집합을 이루며, 교집합이 존재하지 않는 집합을 말합니다. 이를 연결 리스트나 트리를 통해 표현할 수 있지만, 보통 트리 구조를 사용하여 구현합니다. 분리 집합을 표현하기 위해 각 노드가 바라보는 부모 노드를 나타내는 parent[] 배열을 사용합니..

기왕 배운 김에 정리합니다. 코테 빈출 유형은 아니라서, 제 블로그 아무도 안보긴 하겠지만... 혹시나 누군가 본다면 그냥 얘 이런것도 배웠구나 하고 넘어가시면 됩니다. 세그먼트 트리란 세그먼트(Segment)는 '부분'을 의미합니다. 세그먼트 트리는 말 그대로 각 노드에 전체 배열의 부분 정보를 저장시켜두고, 이를 완전 이진 트리로 구성하여 빠르게 해당 값을 탐색할 수 있도록 구현한 자료구조입니다. 각 노드에 담기는 데이터는 대표적으로 "구간합", 그리고 특정 구간에서의 "최대/최소값"이 있습니다. 이 데이터들을 완전 이진 트리로 관리한다는 게 장점인데, 이를 큰 범위의 배열로 관리하기 때문에 메모리를 많이 사용한다는 점을 감안해야 합니다. 공간을 내어주고 시간 활용도를 많이 높이는 전형적인 자료구조입..

이번에는 자바를 이용한 완전탐색의 기본인 순열, 조합, 그리고 부분집합을 구현하는 기본 알고리즘에 대하여 알아보겠습니다. 이를 사용하여 기본 완전탐색을 수행할 수 있습니다. 순열 순열은 서로 다른 것 중 순서를 고려하여 나열하는 것입니다. 우리가 알고리즘에서 순열을 사용하는 경우로는, 순서를 고려하여 경우의 수를 완전 탐색할 때 사용합니다. 이는 서로 다른 것 중 선택을 할 때 중복을 허용하냐 안하냐를 먼저 확인해야 하는데, 이는 중복 검사의 유무만 체크하여 구분해주면 되니 지금은 중복이 없는 경우를 기준으로 하나하나 차근차근 코드와 함께 보겠습니다. public class Permutation { static int[] data; static int N; // 총 개수 static int R; // 구..

순서를 갖지 않는 HashSet과 같은 자료구조를 제외하고, List 계열이나 SortedSet, SortedMap 자식 객체들은 정렬이 가능하다. 또한 custom class를 정의한 것 또한 필요한 조치만 해 주면 정렬이 가능하다. 이를 어떻게 하는지 알아보자. 컬렉션을 정렬하는 인터페이스: Comparator와 Comparable 우리가 int 배열이나 Integer, Double과 같은 numeric 데이터에 대하여는 쉽게 정렬을 해왔다. 심지어 String도 내부적으로 정렬을 위한 구현 코드가 정의되어 있어 별도로 조치하지 않아도 정렬을 해 줬다. 하지만 우리는 종종 (x,y) 형태의 좌표를 custom class로 정의하거나, 유관 데이터를 별도 객체로 묶어서 정의한 뒤에 정렬을 해야 하는 상..

List와 Queue 컬렉션에 대하여 궁금하다면 이전 게시글에서 공부해보자. Set Set 컬렉션은 List 구조와 달리, 저장 순서를 유지하지 않는 자료구조이다. 즉, 선형 구조를 갖고 있지 않다. 객체를 중복해서 저장할 수 없다는 것이 가장 큰 특징이며, null은 하나까진 저장 가능하다. Set hs = new HashSet(); Set lhs = new LinkedHashSet(); Set ts = new TreeSet(); 가장 자주 사용되는 Set 구현 클래스는 HashSet이다. 이 외에도 TreeSet과 LinkedHashSet이 존재한다. 지금은 가장 많이 사용되는 HashSet을 중점으로 Set을 이해해볼 예정이라, 다른 Set 구현체에 대하여는 다음 설명만 드리고 넘어가겠다. 이것에 ..

자바로 자료구조 시작하기 자바는 자료의 관리를 용이하게 하는 많은 자료구조를 인터페이스와 구현 클래스를 정의하여 java.util 패키지에 모아두었고, 이를 컬렉션 프레임워크라고 부른다. 컬렉션 프레임워크의 구조 인터페이스를 통해 자바의 컬렉션 프레임워크가 어떤 구조를 갖고 있는지 이해해보자. 위 그림에서 초록색을 기준으로 보면 구조를 이해할 수 있다. 자바는 Iterable이라는 최상위 인터페이스를 기반으로 List, Set, Queue 컬렉션을 운영하고 있고, 번외로 Map이라는 게 존재한다. 컬렉션 인터페이스 둘러보기 자바를 잘 이해하고 있는 사람은 알겠지만, List, Set, Queue와 같은 인터페이스는 모두 Collection이라는 인터페이스를 상속하고 있기 때문에 기본적인 동작 메서드는 대..

알고리즘 왜 해야해요? 행간에 이런 말이 있다. 알고리즘 잘 하는거랑 개발 잘 하는건 다른 거라던데요? (이는 개인에 따라 다른 관점이 있을 수 있는 부분이며, 철저히 제 사견임을 밝힙니다.) 어느정도 동의는 한다. 우리는 대부분 코딩테스트를 통과하기 위해 알고리즘을 학습한다. 물론, 알고리즘 구현 능력이 실무 개발 역량에 전혀 영향을 미치지 않는다고 할 순 없겠지만, 어느정도 분명 구분되는 영역이라 생각한다. 비유를 하자면 알고리즘 실력과 개발 실력의 상관관계는 마치 토익 실력과 회화 실력 사이의 관계와 유사하다고 생각한다. 즉, 토익을 잘 하면 회화를 잘 할 확률도 높고, 상대적으로 수월하겠지만, 사실 엄격하게 말해선 회화를 잘 하고 싶으면 회화를 공부하는 게 더 효율적이란 이야기다. 그럼에도 불구하..

BST를 탐색하는 시간복잡도가 O(logN)이라고 한다. 이를 어떻게 유도할 수 있나? 유도 과정 기본적으로 크기가 N인 ordered array가 있다고 해 보자. Binary search tree의 매커니즘과 동일하게 생각해보면, 우리는 숫자의 범위를 절반씩 잘라가는 행위를 결국에는 남은 숫자의 개수가 1이 될 때 까지 반복할 것이다. 이렇게 반복한 횟수를 k번이라 해 보자. (즉, 여기서 k가 의미하는 것은 결국 해당 연산을 몇 번 수행하냐를 의미하게 되며, 이는 BST의 탐색 연산 횟수와 같다.) 이를 수식화하면 N * (1/2)^k = 1 라고 표현할 수 있다. 이는 N = 2^k와 같다. 따라서 양 변에 밑이 2인 log를 취하면 log N = k 라는 결과가 나온다. 이는 N개의 숫자를 갖는..

일반적으로 linked list의 중간에 삽입하는건 번거롭다는 것은 우리가 쉽게 알고 있다. 그렇다면 "연결리스트에서 순서 관계 없이 노드를 추가하는 효율적인 위치는 양 끝이다." 라는 명제는 참일까? 그렇지 않다. 연결 리스트의 크기가 n개라고 했을 때, 리스트의 tail노드 위에 붙이기 위해서는 tail 노드를 가리키는 포인터가 있지 않은 이상 n번의 탐색을 통해 tail 노드를 찾아야 할 것이다. 이 과정에서 불필요한 오버헤드가 발생한다. FIFO 구조라면 불가피하게 이렇게 해야 하겠지만 '순서 관계 없이'라는 조건이라면 head 노드의 앞에 붙이는 것이 가장 효율적이다. 이처럼 항상 자료구조를 이해하여 그 연산의 비용을 고려하며 생각해야 한다.

보호되어 있는 글입니다.