노는 게 제일 좋아

탐색을 배웠는데, 이제 탐색도 응용해봐야 하는데 이게 좀 중요한 내용이다. 연결 성분이라는 것인데 connected component 라고 한다. 최대로 연결된 부분 그래프를 말한다. 연결성분을 찾기 위해서는 앞에서 배웠던 깊이, 너비 우선 탐색을 모두 이용할 수 있는데 상관없다. 그렇지만 예를 들어서 깊이 우선 탐색을 해보자 먼저 임의의 정점을 선택, 깊이우선탐색을 통해 연결되어 있는 모든 정점을 출력한다. 더 이상 연결된 정점이 없으면 그래프에서 아직 방문되지 않은 다른 정점을 선택해 반복한다. 이 과정을 그래프의 모든 정점이 방문될 때 까지 방문하면 모든 연결 성분을 찾을 수 있다. 연결 성분 탐색을 위해서는 각 정점마다 저런식으로 111 22 이렇게 저장하려면 저러한 번호를 저장할 공간이 필요한데..

그래프의 탐색은 가장 기본이라고 할 수 있을거야. 그럼에도 조금 나중에 배우는 이유는 제일 중요해서 그래 기본이 가장 중요한거지 그래프에서 탐색은 특정한 것을 찾는다기보다는 "시작 정점부터 차례대로 모든 정점들을 한 번씩 방문" 을 의미해 또한 연결되었는지 안되어있는지가 중요한 회로같은 경우 탐색만으로도 문제를 발견할 수 있는거지 •도로망 예: 특정 도시에서 다른 도시로 갈 수 있는지 여부 •전자회로 예: 특정 단자와 다른 단자의 연결 여부 우선 탐색에는 2가지 정도가 있어. 1. 깊이우선탐색(Depth First Search) DFS 2. 너비우선탐색(Breadth First Search) BFS 이렇게 2가지가 있는데 비교는 이제부터 할거야 1. 깊이우선탐색 깊이부터 가자 갈수 있을 때까지 계속 가다..

이번에는 배열이 아닌 연결리스트로 구현할건데 뭐 그래프의 목적 자체는 똑같으니까 그렇게 어렵지는 않아. 오히려 더 쉬울수도 있다? 이런식으로 만드는거다? 어 근데 연결리스트에는 순서가 있는데 어떻게 하냐고?? 순서는 상관없어ㅋㅋㅋㅋ 그리고 무방향그래프인 경우에는 조금 번거로운게 a와 b가 이어져있다면 b와 a도 이어져있는 거겠지?? 그래서 그런 것 또한 고려해줘야할 필요가 있지. 이런 식으로 간선 없는 것들도 이렇게 표현하고 방향그래프면 이렇게 할 수 있고 그러면 코드랑 같이 보자. 이런식으로? 짤 수 있어 이제 무방향일 때는 간선 2개 만들어야하는 것도 잊지말고 이런식으로 짜면 된다 이제 더 연산에 대해 알아볼건데 탐색은 조금 특별해서 다음 글에서 알아보자.. 내가 쓴 코드가 전부가 아니니,, 원하는 ..

그래프 용어랑 종류랑 저번에 익혔으니까 이제 그래프를 만들 기초는 다져놨네? 그럼 그래프를 만들어봐야겠지?? 그래프는 노드간의 연결관계를 나타내야하는데 저번에도 매트릭스로 나타내면 좋을 것 같다고 했잖아. 정말 행렬로 만드는게 효율적이라서 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..