코딩 일지

버블 정렬버블 정렬 (Bubble Sort)이란, 인접한 두 데이터를 서로 바꾸면서 정렬해가는 방법이다.두 데이터를 묶은 모양새가 거품과 비슷하다고 하여, 버블 정렬이라고 부른다.구현 난이도가 가장 낮으며,항상 O(N^2)의 시간복잡도를 가진다.#include#define SIZE 9int arr[SIZE+1]={3,7,2,1,9,6,4,8,5};void bubbleSort() { for (int i = 0; i arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } }}int main(){ p..

다익스트라다익스트라 알고리즘(Dijkstra Algorithm)이란, 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 계산하는 알고리즘이다.해당 정점에서 갈 수 있는 최적의 경로로만 가기 때문에 음수 가중치를 가지는 그래프에서는 사용할 수 없다.#include#include#include#define INF 0xFFFFFFFusing namespace std;int dist[5]={0,};vector > graph[5];void dijkstra(int n){ priority_queue > pq; dist[n]=0; pq.push({0,n}); while(!pq.empty()){ int now = pq.top().second; int cost ..

선형 탐색(Linear Search)선형 탐색은 단순히 순서대로 하나씩 찾는 탐색 기법으로평소 우리가 사용하던 탐색 방법과 같다.예를 들어, 우리가 아래 배열에서 8을 찾으려 한다면,1478111516192123어떻게 할까?단순히 for문으로 index 0부터 index 9까지 탐색하면서 8이 나올 때까지 반복할 것이다.이게 선형 탐색이다.선형 탐색은 O(N)의 시간복잡도를 가진다.이진 탐색(Binary Search)이진 탐색은 데이터를 반씩 쪼개가며 찾는 탐색 기법이다.1478111516192123위와 같은 배열에서 8을 찾으려 한다고 하자,(left : index 0, right : index 9)먼저 mid(= (left+right)/2 )만큼 자른다.1478111516192123index가 mid..

깊이 우선 탐색깊이 우선 탐색(DFS, Depth - First - Search)란, 한 분기를 모두 탐색하고 다음 분기를 탐색하는 방법이다.브루트포스백트래킹주로 이 두 문제를 풀 때 사용한다.재귀함수와 비슷하다.단순 속도로 따지면 BFS보다 느리다.dfs로 탐색하면13 -> 6 -> 11 -> 17 -> 31 -> 7 -> 8 -> 21 -> 19순으로 탐색한다.#include#includeusing namespace std;vector tree[100]; // 각 노드의 인접 리스트를 저장할 벡터 배열int visit[100]={0,}; // 노드 방문 여부를 체크할 배열, 초기값은 0(방문하지 않음)// 깊이 우선 탐색(DFS)을 수행하는 함수void dfs(int n){ if(visit[n..

신장 트리신장 트리(Spanning Tree)란, 그래프의 최소 연결 부분 그래프이다.N개의 정점을 가지는 그래프의 최소 간선 수는 (N-1)개이고, (N-1)개의 간선으로 연결되어 있으면 트리의 형태가 된다.신장 트리는 사이클을 포함해서는 안되며, 모든 정점들이 연결되어 있어야 한다.따라서 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결해야 한다.최소 신장 트리최소 신장 트리(MST, Minimum Spanning Tree)란, 최소 비용의 신장 트리를 선택하는 알고리즘이다.MST의 특징은 다음과 같다.간선의 가중치의 합이 최소여야 한다.n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.사이클이 포함되어선느 안된다.MST를 구현하기 위한 방법으..

문제 출처https://www.acmicpc.net/problem/2457골드3 그리디, 정렬 문제이다. 3월 1일부터 11월 30일까지 모든 꽃이 한 개 이상 펴야하면서, 선택한 꽃의 개수가 가장 최소라면 단순히 생각해서펴있는 기간이 가장 길면 된다.그러나, 3월 1일부터 11월 30일까지 라는 조건이 추가적으로 붙어 있으므로, 처음 선택한 꽃은 3월 1일을 포함하면서 가장 긴 기간을 가지는 꽃이 될 것이다.만약 3월 1일을 포함하면서 기간이 가장 긴 꽃이 7월 25일에 진다면, 그 다음 찾아야하는 꽃은 7월 25일을 포함하면서 또 가장 긴 기간을 가지는 꽃을 찾으면 된다.즉, 포함해야하는 날수를 now라고 할 때 now보다 이전에 피는 꽃들 중 지는 날은 가장 나중인 꽃을 찾으면 된다.따라서 피는 날..

문제 출처https://www.acmicpc.net/problem/1991실버1 트리 문제이다. 트리에 관한 설명은 아래 게시물에서 확인할 수 있다.https://codingul1234.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%A6%ACTree [자료구조] 트리(Tree)트리는 앞으로 가장 많이 볼 자료구조이며, 가장 기본적인 그래프다.트리는 유방향 그래프로 위에서 아래로만 진행이 되며, 순환이 없다.트리의 개념은 다음과 같다.트리는 하나의 루트 노드를codingul1234.tistory.com 재귀적으로 봤을 때,전위 탐색은데이터 출력 -> preorder(tree.left) -> preorder(tree.right)중위 ..

그래프는 앞으로 많이 볼 자료구조이다.그래프 용어정점(Vertex or Node) : 데이터를 저장하는 위치간선(Edge) : 정점을 연결하는 선. 링크(Link) 또는 브랜치(branch)로도 불린다.인접 정점(Adjacent Vertex) : 간선에 의해 직접 연결된 정점단순 경로(Simple Path) : 경로 중에서 반복되는 정점이 없는 경우. 한붓 그리기와 같은걸 의미한다.차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수를 의미한다.    정점의 모든 차수의 합 = 간선의 수*2가 성립한다.진출 차수(In-Degree) : 방향 그래프에서 외부로 향하는 간선의 수를 의미한다.진입 차수(Out-Degree) : 방향 그래프에서 외부에서 들어오는 간선의 수를 의미한다.경로 길..

트리는 앞으로 가장 많이 볼 자료구조이며, 가장 기본적인 그래프다.트리는 유방향 그래프로 위에서 아래로만 진행이 되며, 순환이 없다.트리의 개념은 다음과 같다.트리는 하나의 루트 노드를 가진다.루트 노드는 0개 이상의 자식 노드를 갖고 있다.그 자식 노드도 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.트리 용어루트 노드(Root Node) : 부모가 없는 노드    트리는 하나의 루트 노드만을 가진다.단말 노드(Leaf Node) : 자식이 없는 노드내부 노드(Internal Node) : 리프 노드가 아닌 노드간선(Edge) : 노드를 연결하는 선형제(Sibling) : 같은 부모를 가지는 노드부모 노드(Parent Node) : 어떤 노드의 한 단계 위에 연결된 노드    위 트리를..

유니온 파인드유니온 파인드 (Union-Find)란, 합 집합을 만드는 것이다.즉, A, B, C데이터가 존재할 때, A와 B데이터가 하나의 집단이고, C데이터는 또 다른 집단이다를 나타내기 위해 쓰는 알고리즘이다.즉, 개별로 존재하는 데이터들을 하나의 집단으로 나타낼 때 사용한다.이렇게 1, 3, 7이 묶여있고, 2, 4, 6이 묶여있을 때두 집단을 합쳐야될 때 사용한다.parent1234567value12345671, 3, 7이 묶여있고, 2, 4, 6이 묶여있으므로parent1234567value1212521다음과 같이 값을 바꿔준다.이후 두 집단을 합치기 때문에parent1234567value1111511이렇게 바꿔주면 된다.그러면 1, 2, 3, 4, 6, 7의 값이 모두 1로 동일하기 때문에 ..