고코딩

그래프(Graph) 그래프는 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결관계를 표현한다. 단순히 정점,노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조라고 할 수 있다. Ex) 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목 등 그래프와 트리의 차이점 오일러 경로 그래프에 존재하는 모든 간선(edge)을 한번만 통과하면 다시 정점(vertex)으로 돌아오는 그래프를 말한다. 그래프에 존재하는 모든 정점에 연결된 간선의 갯수가 짝수일때만 오일러 경로가 존재한다. 그래프(Graph)와 관련된 용어 정점(Vertex): 위치라는 개념. 노드(node)라고도 부름 간선(edge): 위치 간의 관계. 즉, 노드..

코딩테스트 문제를 풀다가 막히는 문제가 있었다. 내가 지금까지 배운 여러가지 자료구조를 생각해보았지만 딱히 올바른게 떠ㅎ오르지 않아서 힌트를 보았다. 힌트를 보니 '이분 탐색, 해시를 사용한 집합과 맵' 이라는 힌트가 있었다. 해시 예전에 배운것 같은데 정확한 개념이 떠오르지 않고 구현도 할줄 몰랐다. 애초에 이게 자바에서 어떻게 사용해야하는지에 대한 개념도 없었다. 항상 배운것들은 그때마다 정리를 해놔야 까먹지 않는데 늦은 정리를 해보자. 해시? 해시테이블? Hash 단어부터가 너무 어렵다. 코딩은 영어로 되어있다보니 단어로 유추하기도 힘들다. 그래서 두 개념의 차이점을 아는 것이 가장 중요한것 같다. 차이점을 알아야 제대로 쓸 수 있으니까. 해시테이블은 해시함수를 사용하여 키를 해시값으..

Disjoint set? Disjoint set은 서로 중복되지 않는 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. 교집합이 존재하지 않는 둘 이상의 집합을 말하고 데이터 집합을 다룰때 유용하게 쓰인다. 분리집합은 자식 노드가 부모 노드를 가리키는 형태이다. 또한 교집합입 없는 집합이기 때문에 차집합 연산이 있지 않다. 오직 Union-Find알고리즘을 사용하며 배열, 연결리스트, 비트벡터 등으로 이용하여 구현할수 있지만 구조는 트리구조를 가지게 된다. Union 연산 두개의 집합을 합한다. 각 집합의 부모 값을 얻어와 한쪽 부모가 다른쪽 부모를 가르키게 해 한개의 부모만 있는 집합을 만든다. 결국 한개의 집합에는 하나의 부모만을 가지게 된다. //N은 원소들을 넣은 배열 pub..

항상 문제를 풀때마다 힙(heap)에 대한 개념이 많이 헷갈려서 포스팅한다. 다른 분의 블로그에 매우 잘 정리된 포스팅을 가져와 정리해서 쓴 글이다. 힙(Heap) 힙은 이진트리의 일종이다. 반정렬 상태(정렬된 상태가 아니다)이며, 완전이진트리와는 다르게 중복값이 허용된다. 삽입/삭제는 트리 구조이기 때문에 O(logN)이므로 매우 빠르다. 보통 우선순위 큐가 힙으로 많이 구현되는데, 배열과 리스트보다 효율적이다. 힙은 최대힙, 최소힙으로 나뉘어진다. 최대힙은 부모노드가 자식노드보다 큼 이라는 특징을 가지고 최소힙은 부모노드가 자식노드보다 작음 이라는 특징을 가지고 있다. 이러한 특징으로 힙에 값을 넣게 되면 최소힙에서는 최소값 순으로, 최대힙에서는 최대값 순으로 값을 얻을수 있다. 힙 자료구조는 보통 ..

순회는 이진 트리에 있는 모든 노드를 한번씩 방문하여 노드가 가지고 있는 데이터를 처리하는 것이다. 여기서 처리라 함은 노드 안의 데이터를 출력할 수도 있고, 데이터 값을 변환할수도 있다. 순회의 종류에는 총3가지가 있다. 전위순회 중위순회 후위순회 현재 노드를 방문하여 데이터를 읽는 작업을 D또는 V라고 한다. 현재 노드의 왼쪽 서브트리로 이동하는 작업을 L이라고 한다. 현재 노드의 오른쪽 서브트리로 이동하는 작업을 R이라고 한다. 전위 순회 전위 순회의 순서는 현재노드(V) -> 왼쪽 서브트리(L) -> 오른쪽 서브트리(R) 순으로 순회 한다. VLR 이라고도 부른다. 전위 순회로 트리를 순회하면 방문하는 노드의 순서이다. 중위 순회 중위 순회의 순서는 왼쪽 서브트리(L) -> 현재노드(V) -> 오..

앞서 포스팅한 스택과 큐는 자료구조에서 선형 구조라고 한다. 선형 구조는 데이터가 순차적으로 나열되어진 형태를 말하는데, 트리는 비선형구조로 이루어져있다. 비선형구조는 데이터가 계층적(혹은 망)으로 구성되어있다. 선형구조와 비선형구조의 차이점은 구성형태뿐만 아니라 용도에서도 차이점이 들어나느데, 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다. 보통 컴퓨터의 폴더 구조가 대표적인 트리의 형태를 가지고 있다. 트리(Tree)의 개념 계층적인 자료를 표현하는데 적합한 자료구조 이다. 노드(node)와 간선(edge)"브랜치(Branch)라고도 불린다" 로 구성되어 있다. 제일 최상위에 위치한 노드를 루트노드(Root Node)라 부르고 나머지 노드들을 서브..

Queue Queue는 자료구조의 스택과 반대의 구조라고 생각하면 된다. 큐는 FIFO(First In First Out)의 형태를 가지게 됩니다. 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조를 말한다. Enqueue : 큐 맨 뒤에 데이터를 추가 Dequeue : 큐 맨 앞쪽의 데이터를 삭제 특징 큐의 한쪽 끝은 Front로 정하여 삭제연산만 수행한다. 다른 한쪽 끝은 Rear로 정하여 삽입연삼나 수행한다. 그래프 넓이 우선 탐색(BFS)에서 사용된다. 컴퓨터 버퍼에서 주로 사용, 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킨다. 먼저 들어온 입력먼저 처리 Java로 큐를 구현 먼저 자바에서 제공해주는 Queue클래스를 이용해 Queue를 구현해보자. 자바에서는 스택을..

스택은 사전적인 의미로 "쌓다"라는 의미를 가지고 있습니다. 스택을 흔히 선출후입(LIFO)라고 부릅니다. 한쪽에서만 자료를 넣고 뺄수 있는 구조입니다. 실제로 인터넷 브라우적의 경우 '뒤로가기','앞으로가기' 버튼을 생각하시면 됩니다. JAVA에서 제공해주는 Stack클래스 자바에서는 기본적으로 Stack클래스를 지원해줍니다. 물론 우리가 만들줄도 알아야 하지만 기왕에 주어진 기능 먼저 활용해 봅시다. Stack stack = new Stack(); 와 같이 생성할 수 있다. 기본적으로 push(), pop(), peek(), empty(), search()기능을 지원해 주는데 예제 코드를 사용해 각각이 어떤 기능인지 알아보자. 참고로 는 Stack 배열안에 들어가 데이터의..

자료 구조는 현실세계에 존재하는 데이터를 효율적으로 저장할 수 있는 구조화 표현의 개념이라고 할 수 있다. 그럼 왜 자료 구조를 알아야 하는것일까? 컴퓨터에는 메모리,CPU, 스토리지가 존재하는데 데이터가 중구난방으로 존재하게 되면 CPU가 메모리나 스토리지에 저장되어있는 데이터를 찾는데 오랜시간이 소비되게 된다. 이 말은 즉, 프로그램의 속도를 저하시키게 된다. 데이터가 자료구조의 개념에 기반하여 저장되어있다면 CPU가 자료를 찾는데 드는 시간은 짧아지고 효율적이 사용이 될 것이다. 자료 구조의 분류는 단순구조, 선형구조, 비선형구조, 파일구조로 나뉘어져 있다. 단순 구조 프로그래밍시 변수도 크기가 커지면 여러공간에 변수를 나눠서 저장하게 된다. 변수의 데이터 타입에 따라 구조도 바뀌게 된다 선형 구조..