psb08의 스터디

탐색 알고리즘깊이 우선 탐색 (DFS, Depth First Search)○ 개념 - 그래프 알고리즘의 기본 중의 기본이며, 트리 탐색에도 많이 쓰입니다. - 한 정점에서 시작해서 갈 수 있는 곳까지 계속 들어가며 탐색합니다. - 더 이상 갈 곳이 없으면 되돌아가서 다른 경로 탐색 (백트래킹) - 스택(Stack) 구조 기반 → 재귀 함수 or 명시적 스택으로 구현 가능 ○ 시간 복잡도 - O(V + E) - V : 정점의 수, E : 간선의 수 ○ 정점과 간선 - 정점 : 그래프에서 노드라고도 불리며, 각각의 개체, 지점, 위치 등을 의미합니다. - 간선 : 정점과 정점을 연결하는 선이며, 관계, 경로, 연결 상태 등을 표현합니다. ○ 장단점 및 특징 -..

탐색이란?○ 여러 개의 자료 중에서 원하는 자료를 찾는 방법○ 컴퓨터가 가장 많이 하는 작업 중 하나이며, 탐색을 효율적으로 수행하는 것이 중요합니다.탐색 알고리즘순차 탐색 (Linear search)○ 탐색 방법 중에서 가장 간단하고 직접적인 선택 방법입니다.○ 정렬되지 않은 배열을 처음부터 마지막까지 하나씩 검사합니다. ○ 평균 비교 횟수 - 성공 : (n + 1) / 2 번 비교 - 실패 : n번 비교 ○ 시간 복잡도 - O(n) ○ 장단점 - 장점 : 정렬이 필요 없으며, 구현하기 쉬운 편 입니다. - 단점 : 데이터가 많을 때 특히 느립니다. 이진 탐색 (Binary search)○ 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열..

리스트란?- 여러 개의 항목(데이터)을 차례대로 저장할 수 있는 자료 구조입니다.- 리스트에는 항목들이 차례대로 저장되어 있습니다.- 리스트의 항목들은 순서 또는 위치를 가집니다. 예) 오늘 할 일, 요일들- 스택, 큐도 넓게 보면 연결 리스트의 일종연결 리스트- 자료를 저장하고 있는 노드와 다음 자료의 위치를 가리키는 포인터로 구성되어 있습니다.- 동적으로 크기가 변합니다.- 삽입, 삭제 시 데이터를 이동할 필요가 없습니다. 배열 vs 연결 리스트- 인덱스로 자료에 접근함로 탐색 시간이 빠르다. 특정 노드에 접근하기 위해 이전 노드들을 탐색해야 하므로 탐색 시간이 오래 걸린다 O(n)- 임의의 원소를 삽입하거나 삭제할 때 많은 양의 원소를 이동시켜야 한다. 노드의 이동이 불 필요하여 ..

큐란?- 선입 선출 (First In First Out) 구조를 가지고 있습니다. 가장 먼저 들어온 객체가 가장 먼저 삭제 됩니다. 편의점 물건 채울 때의 원리와 비슷합니다.- 전단(front)은 큐에서 삭제가 일어나는 곳입니다.- 후단(rear)은 큐에서 삽입이 일어나는 곳입니다.큐의 연산삽입 (Enqueue)- 비어 있는 큐의 초기 상태에는 Front와 Rear의 값 모두 -1로 설정되어 있습니다.- 자료가 삽입될 때마다 Rear가 1씩 증가하며 이동합니다.- 새로운 자료를 삽입하기 위해서는 먼저 Rear의 포인터를 증가시켜야 하고, 그 위치에 자료를 입력해야 합니다.삭제 (Dnqueue)- Front 포인터가 1씩 증가하며 자료를 삭제합니다.- 마지막으로 입력된 자료가 삭제되면 Front 포인터와 ..

원래 공부를 한 내용을 작성하고 백준을 푼 뒤 작성하려 했으나 내용 정리, 작성이 엄청 늦어졌습니다. 스택이란?- 한쪽 끝에서만 삽입 or 삭제할 수 있는 구조- 후입선출 (Last In First Out) 구조를 가지고 있습니다. 쉽게 생각해보자면 프링글스를 떠올릴 수 있습니다.스택의 구조입니다.삽입은 push로, 삭제는 pop으로 합니다.스택에 입력할 때 push를, 스택에서 출력할 때 pop을 사용합니다.Top 포인터는 가장 마지막에 들어간 값을 가리킵니다.Bottom 포인터는 가장 먼저 들어간 값을 가리킵니다.삽입 (Push)Top 포인터의 기본값은 -1 입니다.아무것도 없는 스택에 10을 삽입한 뒤 Top 포인터를 1 증가 시킵니다.그럼 Top이 다음 값을 삽입할 준비가 되었다고 생각하고 삽입이..

문제 링크 : https://www.acmicpc.net/problem/28278목차1. 설명 2. 내 코드 3. 실행 결과 설명백준 실버 4 문제 입니다.문제명 : 스택 2 내 코드#include#include#include#include#include#includeusing namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t, t1; string str; cin >> t; stack stack; while (t--) { cin >> str; if (str == "1") { cin >> t1; stack.push(t1); } else if (str == "2") {..

문제 링크 : https://www.acmicpc.net/problem/1158목차1. 설명 2. 내 코드 3. 실행 결과 설명백준 실버 4 문제 입니다.문제명 : 요세푸스 문제이번에는 list, iterator를 사용하여 풀었습니다. 내 코드#include#include#include#include#include#include#includeusing namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k; cin >> n >> k; list circleList; for (int i = 1; i ::iterator target = circleLi..

문제 링크 : https://www.acmicpc.net/problem/1158목차1. 설명 2. 내 코드 3. 문제 풀이 해석 내용 4. 실행 결과 설명백준 실버 4 문제 입니다.문제명 : 요세푸스 문제 내 코드#include#include#include#includeusing namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k; cin >> n >> k; queue que; for (int i = 1; i ';} 문제 풀이 해석 내용 변수 선언 및 큐 초기화int n, k; // 총 인원수 n, 제거할 순서 kcin >> n >> k; // n, k 입력받기q..

문제 링크 : https://www.acmicpc.net/problem/1966목차1. 설명 2. 내 코드 3. 문제 풀이 해석 내용 4. 실행 결과 설명백준 실버 3 문제 입니다.문제명 : 프린터 큐 내 코드#include #include #include #include #include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin >> t; while (t--) { int n, m; cin >> n >> m; queue> q; vector v; for (in..

문제 링크 : https://www.acmicpc.net/problem/1269목차1. 설명 2. 내 코드 3. 문제 풀이 해석 내용 4. 실행 결과 설명백준 실버 4 문제 입니다.문제명 : 대칭 차집합지금까지 푼 문제 모두 비슷한 느낌이 있어 이번에도 vector, sort로 binary_search를 사용하여 이진탐색 방법으로 풀었습니다.확실히 이진탐색으로 문제 푸는 법에 대해서 알아가고 있다는 느낌이 드는 것 같습니다. 내 코드#include #include #include #include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m;..