노는 게 제일 좋아

그래프 용어랑 종류랑 저번에 익혔으니까 이제 그래프를 만들 기초는 다져놨네? 그럼 그래프를 만들어봐야겠지?? 그래프는 노드간의 연결관계를 나타내야하는데 저번에도 매트릭스로 나타내면 좋을 것 같다고 했잖아. 정말 행렬로 만드는게 효율적이라서 2차원 매트릭스로 구성해야겠는데 n개와 연결관계를 나타낼거니까 n*n행렬로 만들면 될것같음. 그런 생각을 하면 굿굿 근데 연결리스트로도 만들 수 있다? 그건 나중에보고 아무튼 제일먼저 생각난 것이 배열이니까 행렬로 만들어보자 배열은 G[i][j]이런식으로 만드는 거 알지? 연결되었으면 1, 아니면 0으로 표시하자 그렇게해도 충분히 연결관계를 파악할 수 있으니까 우선 무방향그래프로 구현한다면 i행 j열의 관계와 j행 i열의 값이 똑같겠지? 대각선을 기준으로 대칭이 되겠다..

이어서 그래프에 대해서 배워볼건데... 그래프가 눈에 가장 잘띄는데 코딩은 가장 귀찮은 듯한 느낌이야. ㅠㅠㅠㅠㅠ 뭐 그래프는 뭐 요소들끼리 서로 연결되어 있는 관계를 나타내는 자료구조인데.. 말도 쉽고, 눈도 쉽지만 ,, 손은 어려운 ㅋㅋㅋㅋㅋ 아무튼 최단경로찾는 그런 교통어플리케이션도 이러한 그래프를 이용하는 경우가 정말 많다. 지하철 노선도 처럼 ~~~도로 끝나는 것은 거의 다 그래프다. ㅋㅋㅋ 그래프의 역사를 올라가고 싶지만... 너무 길기에 바로 본론으로 들어가자 그래프의 정의를 보자 vertex 와 edge로 이루어지며 다르게 불리기도 한다. 정점(vertices) 또는 노드(node) •여러 가지 특성을 가질 수 있는 객체 의미 •V(G) : 그래프 G의 정점들의 집합 간선(edge) 또는 ..

이번에는 힙의 기본연산을 알아볼 시간인데요. 우선 트리를 만들 때 했던 것처럼 노드를 정의해야겠죠? 어차피 배열이니까 데이터를 넣는데 이제 우선순위 큐를 만들려고 하는 것이니까 우선순위도 포함되어있어야 하는데...? 어떻게 할 것인지 코드로 보면서 알아보자 우선 정수의 데이터를 다룬다고 치고 알아보도록 하자 저기 전처리기 #define은 우선순위를 정하는 것이다. 저거 없으면 그냥 트리랑 다를바가 없다. 다른 식으로도 우선순위 큐 만들기도 하던데,, 저부분은 더 공부해야할 부분인건 확실하다. ★★★★★ 까먹지 마라고 별도 붙혀놓음 아무튼 저렇게 하도록 하고,,? 배열로 만들거니까 배열선언은 쉬우니까 넘어가고? 기본연산중 하나인 삽입연산으로 ㄱㄱㄱ 우선 알고리즘부터 알아보자면 삽입은 힙의 가장 마지막 부분..

오늘은 우선순위 큐 구현방법 중에서 가장 효율적이라는 힙에 대해서 공부하도록 합시다 힙은 영어로 heap인데 뜻이 쌓다, 더미 이런 뜻을 가지고 있고, 완전이진트리를 기반으로 합니다. 완전이진트리에 대해 복습하자면 얘는 마지막 레벨 빼고는 모두 포화인 트리라고 말했죠?? 아무튼 힙에는 2가지 종류가 있는데 최대힙이랑 최소힙이 있지 max heap, min heap 영어로 이렇게 쓴다고 하더라 ??? 최대, 최소하니까 뭔가 크기를 가지고 있나보구나 생각이 들지? 아 그럼 그 크기가 우선순위가 되어야 힙으로 우선순위 큐를 구현할 것 같다... 라는 생각이 들면 굿 Max Heap이란 ○부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리 key(부모노드) ≥key(자식노드) Min Heap이..

우선 Queue라는 또 다른 자료구조 형태가 있다. 참 많지,, 자료구조형태가?? 자료마다 용도가 다르니 다르게 저장하고 다르게 꺼낼 수 밖에 ㅠㅠㅠ 근데 큐면 큐지 무슨 우선순위 큐가 있는거지...? 라고 생각할 수 있지 뭐랄까.. 비행기 탈때도 VIP들은 다른 입구로 들어가잖아?? 그런 것과 같이 조금 차등을 둔다고하는거지 그니까 뭐 순위를 줘가지고 우선순위가 가장 높은 사람을 먼저 태우는 것처럼 자료도 우선순위가 높은 것을 출력한다 뭐 이런 비슷한 느낌을 가지면 될거야. 우선순위 큐가 이용되는 분야는 시뮬레이션, 네트워크 트래픽 제어, OS의 작업 스케쥴링 이런 곳? 아무튼 우선순위 큐는 스택으로도, 큐로도 구현할 수 있는데 그보다 제일 효율적인 구조는 heap이라는 구조인데 나중에 더 자세히 살펴..

저번에 이진트리에서 삽입, 연산, 탐색에 대해 함수를 만들고 넘어가지 않았다. 왜냐하면 선형적인 구조의 자료구조가 아니기 때문에 연산 후에도 이러한 계층적 자료구조의 형태를 유지하기 위해 따로 해줘야 하는 부분이 있어서 그랬다. 즉, 트리의 조건을 유지하면서 연산을 수행해야한다. 그 연산을 하기 위해서 BST라는 것을 이용해보자 우선 이진탐색트리를 정의하자면 1. key(왼쪽서브트리)≤key(루트노드)≤key(오른쪽서브트리) 2. 이진탐색를 중위순회하면 오름차순으로 정렬된 값을 얻을 수 있다. 그렇다면 이 이진트리는 정렬된 것일까? 맞다. 거의 모든 데이터들은 정렬되었을 때 의미를 가지게 된다. 탐색연산 이진탐색트리에서 특정한 값을 찾는다. 그렇다면 무엇을 기준으로 찾을까? 바로 key 값입니다. 트리기..

트리에 대해 적당히 알아보았고 이제 기본함수를 알기 전에 연결리스트로 트리를 구성했기 때문에 우선 순회라는 것을 알아야하는데 순회라는 것은 트리에 속하는 모든 노드를 한 번 씩 방문한다는 것으로 방문해서 데이터를 목적에 맞게 처리하기 위함이다. 선형 자료구조에서는 순회방법이 단순하지만,, 얘는 알다시피 선형자료구조가 아니기 때문에 다른 방식이다. 아무튼 이진트리의 순위에는 4가지정도가 있다. 여기서는 3가지만 하겠다. 1. 전위 순회 VLR 2. 중위 순회 LVR 3. 후위 순회 LRV 4. 레벨순회 V는 value라고 보면된다. 자료를 의미한다. 우선 전위순회부터 알아보자. 스크립트를 먼저 보자면 void preorder(TNode *n){ if(n != NULL){ // 루트를 가르키는 것이겠다. p..

트리에 대해서 알아보자. 트리는 계층적인 구조(hierarchical structure)로서 선형이 아닌 구조를 띄고 있다. 선형이 아니라는 것은? 선형보다는 삽입,삭제가 쉽지 않음을 의미한다. 그렇지만 그럼에도 쓰는 이유에는 장점이 커서 그렇다. 트리는 말 그대로 나무를 뒤집어놓은 모양과 비슷하다고 해서 붙혀진 이름이다. 뭐 이런 형식으로 저장해놓은 것이다. 우선 용어부터 정리하고 가자면 –노드(node) : 트리의 구성요소 –루트(root) : 부모가 없는 노드(A) –서브트리(subtree) : 하나의 노드와 자손들로 이루어짐 –단말노드(terminal) : 자식이 없는 노드(A,B,C,D) –비단말노드 : 자식을 가지는 노드(E,F,G,H,I,J) –자식, 부모, 형제, 조상, 자손 노드 : 내 ..

체이닝은 앞에서 말했다시피 슬롯의 개수가 정해져있어서 오버플로우가 생기는데 그렇다면 자료구조의 형태를 배열이 아닌 연결리스트로 연결하겠다!!! 라고 해서 만든 것이다. 그래서 여기에는 슬롯 사이즈가 들어가지 않는다. 대충 이렇게 만든다. void main() { init_map(); add_record("age", "A"); add_record("ant", "A"); add_record("allow", "A"); add_record("best","B"); add_record("beef","B"); add_record("bye","B"); add_record("creep", "C"); add_record("conscience", "C"); add_record("dirty", "D"); add_record(..

앞에서 오버플로우가 일어나는 원인을 알아보았다. 자료가 들어가는 자리에 버킷이 겹칠 때, 또한 슬롯도 꽉 차있을 때 오버플로우가 생긴다고 했는데 그렇다면 다른 버킷은 비어있는데 어느 특정 버킷만 자꾸 나와서 오버플로우가 된 경우를 생각하자 200개 중에 자꾸 1개 버킷에만 몰려서 오버플로우가 발생하는데, 오버플로우를 막으려면 해시함수부터 수정해야한다. 해시함수를 잘못만들어서 테이블 전체를 골고루 활용하지 못하고 편중되게 사용하는 것이다. 해시함수가 가져야 할 특징을 못가져서 그렇다. 해시함수가 가져야 할 특징 1. 충돌이 적어야함 2. 해시 테이블에 고르게 분포시킬 수 있는 주소의 연산 값이 나와야 한다. 3. 계산이 빨라야 한다. 아무튼 이러한 특징을 가지는 함수 중 가장 대표적인 것만 알아보자 제산 ..