[Data Structure] Bipartite Graph (이분 그래프) | 자바

백준 문제를 풀다가 처음보는 자료구조를 정리하려고 한다. "이분" 이라는 단어가 들어가는 자료구조들이 꽤 있는 만큼, 개념을 헷갈리지 않게 정리하는 것도 중요하지 않나 싶다. 순서는 간단하게 이분 그래프란 ?이분그래프의 탐색방법BFSDFS로 진행하려고 한다! * 이분 그래프의 개념과 글에 나온 이미지는 아래 글을 참고하였습니다 *https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html [알고리즘] 이분 그래프(Bipartite Graph)란 - Heee's Development BlogStep by step goes a long way.gmlwjd9405.github.io1. 이분 그래프란 ?이분 그래프는 그래프 형태의 자료구조로, 인..

백준 문제를 풀다가 정리하지 않은 자료구조가 나와서 정리하고자 글을 쓴다 ! 이번 주제는 세그먼트 트리이다.순서는 아래와 같다. 세그먼트 트리란?구현하기 (구간합을 예시로)생성데이터를 수정하게 된다면? * 세그먼트 트리의 개념은 아래를 참고하였습니다 *https://cano721.tistory.com/38 [알고리즘 개념] 세그먼트 트리(Segment Tree) / Java세그먼트 트리란 특정 구간 내 데이터에 대한 연산(쿼리)을 빠르게 구할 수 있는 트리. ex) 특정 구간 합,최소값,최대값,평균값 등등 Segment : 부분.분할.나누다.분할하다. 시간복잡도 데이터 변경:cano721.tistory.comhttps://book.acmicpc.net/ds/segment-tree 1. 세그먼트 트리?일반..

이번 챕터에서는 트리 중 가장 대표적인 binary tree (이진 트리)를 기록할 예정이다. 순서는 다음과 같다. binary tree - binary tree의 정의와 종류 - binary tree의 ADT - binary tree를 linked list로 나타내면? binary tree traversal - tree algorithm 종류 1. Binary Tree 1-1. Binary Tree 정의와 종류 Binary Tree는 각 노드가 최대 2개의 자식노드만 갖는 트리를 의미하며, 정확히 2개만 갖는 트리는 proper binary tree라고 부른다. 참고로 트리의 종류를정짓는 요소는 크게 2가지로 structural property, relational property가 있다. struct..

이번 챕터에서는 정말 중요한 자료구조 중 하나인 트리에 대해 공부하려고 한다. 정리 순서는 아래와 같다. 트리란 무엇인가? Linked Structure for Trees tree method & tree method's running time 그럼 시작! 1. 트리란 무엇인가? 트리는 그래프의 일종으로, 간단하게 이야기하면 노드로 이루어진 계층 구조를 나타낸다. tree라고 정의될 수 있는 조건은 루트노드가 필수로 존재해야 한다 루트 밑에 있는 노드들도 트리 조건을 만족해야한다 자식노드는 부모노드가 1개여야만 한다 정도로 정의할 수 있다. 위 조건을 모두 만족해야 tree라고 정의할 수 있다. 트리는 File systems, Web sites, Databases 등에서 활용하고, linked list로..

이번 챕터에서는 recursion 재귀에 대해 공부해보려고 한다. 자료구조론에서 중요하게 다루게 될 tree가 재귀로 구현되기 때문에 잘 알아둬야한다! 순서는 다음과 같다. 재귀함수로 코드 짜는 방법 binary recursion (이진재귀) 그럼 시쟉🌟 1. Recursion (재귀) 1-1. 재귀함수란? 재귀는 자체 코드 내에 자기자신을 불러오는 것을 의미한다. 재귀의 예시로 팩토리얼(!)을 들 수 있는데, 재귀함수를 이용한 팩토리얼은 다음과 같다. 위 사진을 보면, n! 안에 (n-1)! 즉 팩토리얼이 포함되어 있는 것을 확인할 수 있다. 만약 n에 4를 대입하면 4 x 3! 이 되고 3!은 3 x 2! 을 불러오는 과정을 반복하여 결국 n = 0이 되어 함수를 불러오는 과정이 종료된다. 이후에는 ..

저번 챕터에서 했던 스택과 큐 구현에 이어, 이번 챕터에서는 다항식을 연결리스트로 구현하는 방법을 작성할 예정이다. 작성은 다음과 같은 순서로 진행할 것이다. 왜 연결리스트( linked list )로 구현할까? 구현방법과 소스코드 그럼 스타-트! 1. 왜 연결리스트로 구현할까? 다항식은 말 그대로 여러개의 단항식이 연결된 구조를 띈다. 이러한 다항식의 특성상 항의 개수 변동이 심하기 때문에 미리 크기를 정해둬야하는 배열은 효율성이 떨어진다. 따라서 배열보다는 linked list로 짜는 것이 더 효율적이다 😎 2. linked list를 이용한 다항식 구현방법 구현방법을 보이기 위해 c = a + b 를 예시로 보여주려고 한다. 이때, a = 6x^6 + 2x^3 + 2 , b = 2x^6 + 7x^4..

저번 챕터에서 했던 연결리스트에 이어 이번 챕터에서는 연결 리스트를 이용해 스택과 큐를 구현하는 것을 기록하려고 한다. 배운거 + 배운거 = 쉬운거 일 줄 알았으나.. 아니었던 거😂 이번 챕터에서는 아래 순서로 작성할 예정이다. 연결리스트로 스택 구현하기 연결리스트로 큐 구현하기 그럼 시작-!! 1. 연결리스트로 스택 구현하기 배운지 오래돼서 리마인드를 해주자면, 스택은 후입선출구조 즉 push와 pop이 top에서만 이루어지는 자료구조이다. 위 사진에서 t는 top을 가리키며, push,pop 모두 t에서 일어난다. 1-1. push 구현 push는 새 요소를 넣는 것을 말한다. 위 linked list에 black이라는 요소를 넣는다고 가정하자. 먼저 black이라는 새 노드를 생성한다. 그 후 이 ..

이번 챕터에서는 연결리스트에 관한 내용을 작성하려고 한다. 관련내용은 아래와 같은 순서로 정리할 예정이다. 연결리스트의 원리 단일 연결리스트의 특징 단일 연결리스트 생성코드 단일 연결리스트에서 노드 추가/제거 순환 연결리스트의 특징 순환 연결리스트에서 노드 추가/제거 그럼 시작 -! 0. Linked Lists 연결리스트란 노드들로 구성된 자료구조형태이며 노드는 두 칸으로 쓴다. 앞에는 데이터를 저장하고, 뒤 칸에는 다음 노드의 주소값을 저장해 멀리 있어도 찾아갈 수 있도록 한다. 첫 노드의 주소는 head라는 변수를 설정하여 저장하고, 마지막 노드는 주소값을 NULL값으로 가진다. 배열은 값이 연속으로 할당된다는 특징이 있어, 만약 내가 5칸의 메모리공간이 필요한데 2칸, 4칸의 공간이 각각 있다면 이..

이번 챕터에서는 꽤나 중요한 자료구조형태인 스택과 큐를 아래와 같은 순서대로 작성할 것이다. ✅ 스택의 원리 ✅ 스택의 ADT와 알고리즘코드 ✅ 큐의 원리 ✅ 큐의 ADT와 알고리즘코드 1. Stacks (스택) 스택은 한 쪽 끝에서 데이터를 넣고 뺄 수 있는 구조를 의미한다. 아래 그림과 같이 스택의 아래 부분을 bottom, 윗 부분을 top 이라고 칭하며, 데이터를 넣고 빼는 것은 top에서만 이루어진다. 스택은 후입선출(lifo, last in first out) 방식으로 처리된다는 특징이 있다. 1-1. stack ADT 스택을 ADT로 나타낸다면 아래와 같이 쓸 수 있다. ADT Stack is objects : a finite ordered list with zero or more eleme..

학교 강의 2번째 강의자료 마지막 학습 키워드 Sparse Matrix이다. 그냥 matrix는 1학년 2학기 전산통계학시간에 배워서 알고 있었으나 sparse matrix는 생소했다. 이번 챕터에서는 ✅ Sparse Matrix란? ✅ Sparse Matrix의 ADT와 표기법 이 두가지를 학습할 예정이다. 1. Sparse Matrix Sparse는 사전적으로 '드문, 희박한'의 뜻을 가지고있다. 즉, 가치있는 값을 가지고 있는 항이 적은 매트릭스를 의미한다. matrix : 값이 숫자인 배열이 행과 열 형태로 이루어져있는 데이터구조의 종류이다. sparse matrix : matrix중에서 값이 0인 요소들이 많은 매트릭스를 의미한다. 값이 0인 요소가 많으면 메모리 낭비가 심해질 수밖에 없다. 6..