Bon Voyage

자료구조&알고리즘

그래프 탐색이란?▶  어떤 것들이 연속해서 이어질 때 모두 확인하는 방법▶  Graph: Vertex (어떤 것) + Edge (이어지는 것) 그래프 탐색 종류 ▶  BFS: Breadth-fist search (너비 우선 탐색)      ▷ 자기 자식을 우선으로 탐색함      ▷ 자기 자식 다 끝나고 나면 자식의 자식 탐색  ▶ 아이디어:1. 시작점에 연결된 vertex 찾기2. 찾은 vertex를 queue에 저장3. queue의 가장 먼저인 것을 뽑아서 반복   ▶  DFS: Depth-first search      ▷ 자식 탐색      ▷ 그 후, 자식의 자식 탐색      ▷ 자식이 없다면 위로 올라와서 그 다음 자식 탐색 ▶ 아이디어:1. 시작점에 연결된 vertex 찾기2. 연결된 ve..

2024. 7. 7.

자료구조&알고리즘

2차원 벡터 선언vector> 변수명;vector>v; 1차원 벡터 초기화4열짜리 1차원 벡터를 생성하고 0으로 초기화vector v (4,0);2차원 벡터 초기화 4x4 짜리 2차원 벡터를 생성하고 0으로 초기화vector> v(4, vector(4, 0))

2024. 5. 6.

자료구조&알고리즘

인접 리스트: 그래프의 각 노드에 인접한 노드들을 연결 리스트 (Linked List)로 표현하는 방법▶ 노드의 개수만큼 인접 리스트가 존재▶ 각각의 인접 리스트에는 인접 노드 정보가 저장됨▶ 그래프는 각 인접 리스트에 대한 헤드포인터를 배열로 가짐▶ 헤드 포인터: 연결 리스트의 맨 처음 노드를 가리키는 포인터  아래 그림의 좌측에 그려진 그래프를 인접 리스트로 나타내면 우측 리스트의 형태와 같다.  c++의 벡터 컨테이너를 이용하여 인접 리스트를 아래와 같이 쉽게 구현할 수 있다. vector linkedList [node 개수]vector map[시작 노드].push_back(연결 노드) 위 그래프를 연결 리스트로 구현하는 코드는 아래와 같다. 단방향 그래프가 아니기 때문에 하나하나 연결된 부분을..

2024. 4. 26.

자료구조&알고리즘

까먹지 않으려고 기록하는 게시물 예전 게시물에서 우선 순위 큐에 대해 기록한 적이 있지만 공부하다 보니 추가할 내용이 생겼다. 우선순위 큐 혼공 기록 스타트! 우선순위 큐의 구현 방법 1. 배열을 기반으로 구현하는 방법 - 방법: 데이터의 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치시킴 - 단점: (1) 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 해줘야 함 (2) 삽입할 위치를 찾기 위해 배열 내 저장된 데이터와 하나하나 비교 연산을 해줘야 함 (우선순위가 가장 낮은 데이터를 저장하는 경우에는 배열의 모든 데이터와 다 비교해줘야 함) - 데이터 삽입 시간 복잡도: O(n) → 우선순위가 낮은 데이터를 삽입할 경우 배열의 모든 데이터와 비교 연산을 ..

2024. 2. 12.

자료구조&알고리즘

우선순위 큐: 큐와 유사하지만 우선순위가 높은 아이템이 먼저 처리되는 큐 ▶ 데이터를 우선순위에 따라 처리하고 싶을 때 사용 자료구조 추출되는 데이터 스택 가장 나중에 삽입된 데이터 큐 가장 먼저 삽입된 데이터 우선순위 큐 가장 우선순위가 높은 데이터 우선순위 큐 멤버 함수 ▶ empty: 우선순위 큐가 비어있는지 확인 ▶ size: 우선순위 큐의 크기 확인 ▶ top: 우선순위 큐 내부의 제일 우선순위에 있는 값을 보여줌 ▶ push: 우선순위 큐에 값을 삽입 ▶ emplace: 우선순위 큐에 구조를 삽입 ▶ pop: 우선순위 큐에서 제일 우선순위에 있는 값을 제거 ▶ swap: 두개의 우선순위 큐를 바꿈 간단한 코드 백준 1927번 최소 힙 https://www.acmicpc.net/problem/1..

2023. 10. 27.

자료구조&알고리즘

BFS란?▶ 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘▶ 최단 경로를 찾아주기 때문에 최단 길이를 보장해야 하는 경우에 자주 사용되는 알고리즘 BFS 구현 방법:1. 시작 노드를 큐에 삽입2. 시작 노드 방문 처리3. 큐에서 하나의 노드를 꺼냄4. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입5. 3-4 반복  아래와 같은 그래프가 있다고 치자!위에 적어둔 BFS 구현 방법을 그림으로 알아보자.참고로 방문 처리는 그래프에서 빨갛게 칠하는 걸로 나타냈다.    1. 시작 노드를 큐에 삽입2. 시작 노드 방문 처리▶ 시작 노드인 1을 큐에 삽입하였고, 방문 처리   3. 큐에서 하나의 노드를 꺼냄4. 해당 노드에 연결된..

2023. 10. 24.

자료구조&알고리즘

큐 (Queue): 스택과는 다르게 큐는 선입선출의 구조를 가지고 있다. 즉, 먼저 들어온 자료가 먼저 나간다 (First In First Out, FIFO)는 것이다. 은행 창구나 카페를 떠올리면 이해하기가 쉽다. 먼저 온 손님이 음료를 먼저 받고 나가는 것을 예시로 들면 좋을 것 같다. 삭제 연산이 수행되는 곳은 프론트 (front), 삽입 연산이 이루어지는 곳은 리어 (rear)이다. · Enqueue: 리어 (rear)에서 이루어지는 삽입 연산 · Dequeue: 프론트 (Front)에서 이루어지는 삭제 연산 #include #include using namespace std; int main() { queue q; q.push(7); q.push(5); q.push(4); q.pop(); q.p..

2023. 10. 23.

자료구조&알고리즘

스택 (Stack) 스택은 "쌓다" 라는 의미를 가지고 있으며, 그 의미에 맞게 데이터를 차곡차곡 쌓아올린 형태의 자료구조이다. 아래와 같이 데이터가 순서대로 쌓이게 되고 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되는 구조를 가지고 있다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조이며 데이터를 삽입할 때는 push 연산을 사용하며 데이터를 꺼낼 때는 pop 연산을 사용한다. 이 때 꺼내지는 데이터는 가장 최근에 삽입한 자료부터 나오게 된다. 이는 LIFO (Last In First Out) 구조이다. 스택 연산: · s.top(): 스택의 가장 위 데이터를 반환 · s.pop(): 스택의 가장 위 데이터를 삭제 · s.push(): 데이터 삽입 · s.empty(): 스택이 비었다면..

2023. 10. 23.

자료구조&알고리즘

계수 정렬: 크기를 기준으로 개수를 세어 정렬 → 위치를 바꿔가며 정렬하는 것이 아님 시간 복잡도: O(N) (모든 데이터의 크기 범위를 메모리 상에 표현할 수 있다면) #include #include using namespace std; int main() { cin.tie(NULL); cout.tie(NULL); cin.sync_with_stdio(false); int cnt[11] = { 0 }; int arr[] = { 1,5,8,4,6,9,5,5,1,3,2,4,7,8,2,4,1,1,7,10 }; for (int i = 0; i < 20; i++) { cnt[arr[i]]++; } for (int i = 1; i

2023. 10. 23.

자료구조&알고리즘

이진트리 (Binary Tree): 모든 노드의 자식 노드가 2개 이하인 트리 구조 완전 이진 트리 (Complete Binary Tree): 데이터가 루트 노드부터 시작해서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로 차근차근 들어가는 구조의 이진트리 → 이진 트리의 노드가 중간에 비어있지 않고 빽빽히 들어찬 구조 힙 (Heap): 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료 구조 → 최소값이나 최대값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리 최대 힙 (Max-Heap): 부모 노드가 자식 노드보다 큰 힙 위 그림은 최대 힙을 나타내고 있다. 위에서부터 보면 부모 노드인 17이 자식 노드인 15와 10보다 큰 걸 알 수 있다. 부모 노드인 15는 자식 노드인 ..

2023. 10. 22.

자료구조&알고리즘

버블정렬, 삽입정렬, 퀵정렬, 병합정렬과 같은 다양한 정렬 방법들이 있다. 이를 앞선 포스팅에서처럼 직접 구현해도 되지만 C++ STL sort() 함수를 사용하게 되면 굳이 그럴 필요가 없다. sort() 함수는 기본적으로 오름차순 정렬을 수행한다. 아래와 같이 배열의 시작점 주소와 마지막 주소 +1을 적어주면 된다. 즉, sort (a, a+10);을 해주게 되면 총 10개의 원소가 있는 배열 a를 오름차순으로 정렬하게 되는 것이다. #include #include // sort() 함수는 c++ algorithm 헤더에 포함되어 있음 using namespace std; int main(void) { int a[10] = { 9,3,5,4,1,10,8,6,7,2 }; sort(a, a + 10); ..

2023. 10. 15.

자료구조&알고리즘

병합 정렬: 하나의 큰 문제를 두 개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합치는 방법 일단 정확히 반으로 나누고 나중에 정렬 병합 정렬의 시간 복잡도: O(N*logN) 숫자들을 오름차순으로 정렬하는 코드는 아래와 같다. 코드: #include #include #include #include #include #include //일단 반으로 쪼개고 나중에 합치는 것 // 퀵 정렬과 다르게 피벗 값이 없고 항상 반으로 나눈다는 특징이 있음 int number = 8; int size; int sorted[8]; //정렬된 배열은 반드시 전역 변수로 선언 int count = 0; using namespace std; void merge(int a[], int m, int middle, int n..

2023. 10. 15.