개발/자료구조

유니온 파인드(Union Find)

이 글은 아래에 블로그를 참고하여 작성되었습니다. https://twpower.github.io/115-union-find-disjoint-set [Algorithm] 유니온 파인드(Union Find)와 서로소 집합(Disjoint Set) Practice makes perfect! twpower.github.io https://www.crocus.co.kr/683 유니온 파인드(Union Find, Disjoint Set) 유니온 파인드(Union Find)란? 유니온 파인드(Union Find)는 Disjoint Set라고도 불리기도 하며, 이 자료구조는 일상속에서 우리가 은연중에 접하는 자료구조이다. 예를 들어보자. 우리는 학창 시절에 수학여행을.. www.crocus.co.kr Disjoint ..

이진 트리의 구현과 순회 방식

이 챕터는 알고리즘보다는 자료구조에 가까운 것 같아 자료구조 게시판에 게시한다. 이진 트리는 대표적인 비선형 자료구조이다. 완전 이진 트리와 이진 트리의 차이를 분명히 하고 넘어가야 한다. --> 나도 처음에 배열로 표현하면 될 것 같은데? 라고 생각했는데 여기서 할 것은 !이진 트리! 이다. 충분히 배열로 표현이 가능하나, 오른쪽에만 노드가 이어져있다 생각해보면 메모리 낭비가 심하다고 생각할 수 있다. 순회 방식은 3개 있다. 1. 전위 순회 (1) 먼저 자기 자신을 처리. (2) 왼쪽 자신을 방문 (3) 오른쪽 자식을 방문 2. 중위 순회 (1) 왼쪽 자신을 방문 (2) 먼저 자기 자신을 처리. (3) 오른쪽 자식을 방문 3. 후위 순회 (1) 왼쪽 자신을 방문 (2) 오른쪽 자식을 방문 (3) 먼저..

큐(Queue)

큐도 스택에 이어 같이 나오는 자료구조이다. 큐의 특징은? 먼저 들어 간 데이터가 먼저 나온다 스택과 다르다 그래서 입구와 출구가 각각 다른 구조라고 생각하면 된다. 앞에 스택과 같이 STL라이브러리를 사용해 큐를 구현할 예정이다. 똑같이 결과 값을 예상하고, 코딩을 했으면 좋겠다. #include #include using namespace std; int main(void) { queue q; q.push(7); q.push(5); q.push(4); q.pop(); q.push(6); q.pop(); while (!q.empty()) { cout

스택(Stack)

스택은 자료구조이다. 스택의 특징은? 가장 늦게들어오는 데이터가 먼저 나가는 구조이다. 스택은 입구와 출구가 하나밖에없는 구조로 생각하면 쉽다. 여기서는 STL 라이브러리를 사용한 스택을 프로그래밍 할 예정이다. 먼저 해당 코드를 보고, 결과 값이 어떻게 나올지 생각해보고 코딩했으면 좋겠다. 사실 이해했으면 코딩 안해도 된다. #include #include using namespace std; int main(void) { stack s; s.push(7); s.push(5); s.push(4); s.pop(); s.push(6); s.pop(); while (!s.empty()) { cout

힙(Heap)

처음에 공부했을 때, 그 프로세스의 메모리 구조인 힙을 생각했었다. 틀린 건 아닌데, 카테고리가 자료구조이니깐 자료구조/힙을 생각합시다. 이것 또한 면접 대비를 위해 기초 질문, 심화 질문? 점차 확장해간다. 힙(Heap) 은 완전 이진 트리 형태를 가지고 잇어야하고, 부모의 값보다 크거나 작아야하는 규칙을 가진 자료구조 그리고 영단어로는 힙은 무엇인가를 차곡차곡 쌓아올린 더미라는 뜻이다. 그래서 Max Heap, Min Heap 이 나오게되는데, 목적이 중요하다. 말 그대로 최댓값, 최솟값을 빠르게 찾기위해서 사용된다는 것을 알아두고 규칙을 이해하면 된다. 그리고, 찾아보면 단순히 최댓값또는 최솟값을 찾기 위해서라면 항상 완전 이진트리 형태일 필요는 없다고 한다. --> 아직 더 찾아봐야하는데, 사실 ..

스택과 큐

면접 대비용으로 쓰이는 것이니, 올바른 답변을 쓰도록 노력은 하고 있습니다. 그러나 올바르지 않을 경우 언제든지 댓글로 알려주시면 바로 수정하고, 다시 복습하겠습니다. --> 사실 제 블로그를 보는 사람이 없어서 아무도 피드백을 안해주는게 사실.... 스택은 후입 선출 ( 나중에 들어온 데이터가 제일 먼저 나간다 ) 특징의 자료구조 큐는 선입 선출 ( 먼저 들어온 데이터가 먼저 나간다 ) 특징의 자료구조 스택은 우리도 모르게 사용되고 있다. 재귀함수 재귀함수가 제일 나중에 호출된 데이터의 반환을 먼저하는 형식이다. 큐는 다른 알고리즘에서도 많이 쓰이지만, 대표적인 운영체제에서 사용되고 있다. 우선 순위 큐를 사용하여, 들어온 프로세스를 라운드 로빈 형식으로 처리하고 있다. 여기서 은근 운영체제 공부도 되..

배열과 연결리스트

면접 대비용으로 이 게시글을 업로드 한다. 그래서 자세한 내용은 없을 수 있다. 먼저, 정의를 내리자면, 배열은 연속된 형태의 데이터를 그 자체 메모리에 올리는 자료구조 연결리스트는 각각의 데이터를 포인터로 연결해서 공간 효율성을 극대화 시킨 자료구조 그래서 굳이 비교하자면, 배열은 순차적으로 데이터 접근이 가능하다. 즉, 인덱스를 이용해서 랜덤 액세스가 가능하다. --> 그래서 이진탐색이 배열에서 쉽게 적용됨. 그러나 배열의 끝 데이터 추가 및 삭제는 상관없으나, 중간에 데이터 추가 및 삭제는 비효율적인 처리가 발생 반대로, 연결리스트는 데이터 추가 및 삭제에 유리한 자료구조.

트리

그림을 만들기 귀찮아 정리만 간단히 하도록 한다 트리의 요소 : Root, Branch, Leaf 부모-자식관계, 형제관계 Degree(차수) 는 관점에 따라 다른데, 노드의 Degree는 그 노드의 자식 노드 개수! 트리의 Degree는 트리 내에 노드들 가운데 자식 노드가 가장많은 노드의 차수를 의미 트리 표현하는 방법 중 중첩된 괄호, 중첩된 집합, 들여쓰기가 있지만, 표현할 일이 있을까 ? 아마 직접 검색해보면 금방 익숙해질 거 같다 노드를 표현하기 --> Key Point - N링크 표현법 : 노드의 Degree가 N이라면 노드가 N개의 링크를 가지고 있어서 각각 자식 노드를 가리키도록 노드를 구성하는 방법. --> 생각해보자, 자식 노드의 수(Degree)가 다 다른데, 이렇게 하면 복잡해진다..