본문 바로가기

코딩 및 기타/코딩 테스트 준비

 (8)
BFS BFS 그래프를 탐색하는 알고리즘이며 어떤 정점에서 시작해 다음 깊이의 정점으로 이동하기전 현재 깊이의 모든 정점을 탐색하며 방먼한 정점은 다시 방문하지 않는 알고리즘으로 같은 가중치를 가진 그래프에서 최단거리알고리즘으로 쓰인다. BFS(G, u){ u.visited = 1; q.push(u); while(q.size()){ u = q.front(); q.pop() for each : G.adj[u] if v.visited = false{ v.visited = u.visited + 1 q.push(v) } } } #include #include #include using namespace std; vector adj[100]; int visited[100]; int nodeList[] = {10, 12,..
DFS DFS 그래프를 탐색할 때 쓰는 알고리즘이며 어떤 노드부터 시작해 인접한 노드들을 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않으며 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘 DFS(u, adj){ u.visited = true; for (each = adj[u]){ if (v, visited == 0) DFS(u, adj) } } #include #include using namespace std; const int v = 10; vector adj[v]; int visited[v]; void dfs(int u){ visited[u] = true; cout > m; // 입력 받는 부분 for (int i = 0 ; i < n; i++){ for (int j = 0; j < m..
2주차(개념) ∙ 그래프 이론 기초 - 정점(verteix) : 노드라고 불리며 그래프를 형성하는 기본 단위이고, 분할할 수 없는 객체이자 "점"으로 표현한다. - 간선(Edge) : 정점을 잇는 선을 의미한다. ex) "어떠한 위치나 어떠한 사람" 으로부터 "무엇인가를 통해 간다" => 정점 : 어떠한 사람, 간선 : 무엇가를 통해 간다 - 가중치 : 정점과 정점사이에 드는 비용을 뜻한다. ex) 1번노드와 2번노드까지 가는 비용이 한칸이라면 1번노드에서 2번까지의 가중치는 한칸이다. ∙ 트리(Tree Data Structure) 자식노드와 부모노드로 이루어진 계층적인 구조를 가지며 무방향 그래프의 일종이자 사이클이 없는 자료구조를 의미한다. ∙ 이진트리(BT, Binary Tree)와 이진탐색트리(BST, Bina..
1주차 (개념) ∙ 시간복잡도 입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 주요로직의 반복횟수를 중점으로 측정 ∙ 빅오표기법 복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법 // 시간 복잡도는 2분의1 의 n제곱 - n 이다. // 빅오표기법으로는 n의 제곱이다. #include using namespace std; int n; int main() { cin >> n; int a = 0; for (int i = 0; i < n; i++){ for (int j = 0; j < i; j++){ a += i + j; } } cout
[필수 개념] 중복된 요소 제거 방법 과 unique() ∙ map // map 함수를 사용해 중복된 요소 제거 #include #include #include using namespace std; map mp; int main() { vector v{1, 1, 2, 2, 3, 3}; for (int i : v){ if(mp[i]){ continue; } else{ mp[i] = 1; } } vector ret; for (auto it : mp){ ret.push_back(it.first); } for (int i : ret) cout
[필수 개념] Split ∙ split() - 코딩테스트에서는 문자열을 split() 하는 로직이 많이 등장 - split 함수는 다른 프로그래밍 언어에서도 특정 문자열을 기준으로 쪼개어서 배열화시키는 함수라의 의미 - C++에서는 STL에서 지원하지 않아 만들어야 함 // split() 함수 // o(n)의 시간복잡도 가짐 #include #include #include using namespace std; vector split(string input, string delimiter){ vector ret; long long pos = 0; string token = ""; // while문이 중요하다 // input에서 delimiter를 찾는다. 못 찾을 때까지는 루프 반복 while ((pos = input.find(d..
[필수 개념] 순열 / 조합 ∙ 순열 - 순서와 상관 O 뽑는다면 -> 순열 ex) 문제에서 순서를 재배치하여....~한 순서의 경우 max 값 // 순열 #include #include #include using namespace std; int main() { int a[] = {1, 2, 3}; sort(a,a+3); do{ for(int i : a) cout
[필수 개념] 재귀함수 ∙ 재귀함수 - 재귀함수(Recursion)는 정의 단계에서 자신을 재참조하는 함수 - 전달되는 상태인 매개변수가 달라질 뿐 똑같은 일을 하는 함수 - 큰 문제를 작은 부분문제로 나눠서 풀 때 사용 ∙ 주의사항 - 반드시 기저사례를 써야한다. (종료조건) - 사이클이 있다면 쓰면 안된다. ex) f(a)가 f(b)를 호출한 뒤 f(b)가 다시 f(a)를 호출하는 것 - 반복문으로 될 거 같으면 반복문으로 사용한다. (함수호출에 대한 코스트) ∙ 예시 - 팩토리얼 n! : 그 이전의 항을 모두 곱하는 것. 곱한다는 행위의 반복? - 피보나치 : 점화식 : f(n - 1) + f(n - 2) 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.... // 팩토리얼, 피보나치 #includ..

티스토리툴바