::public265 (c++17) 가변 길이 템플릿(variadic template)... 함수나 클래스 템플릿이 n 개수의 템플릿 파라미터를 받을 수 있도록 해주는 기능C++11에서 추가된 기능으로, “...”(ellipsis) 문법을 사용"templete" 이 부분이 가변 길이 템플릿"Args... args" 이 부분이 파라미터 팩 Fold 형식 (Fold expression)C++17에서 추가된 기능으로, 파라미터 팩에 대해 산술, 논리 연산 등을 순차적으로 적용할 때 간결하게 표현하는 방법.“인자들을 하나씩 꺼내서, 어떤 연산을 적용해 전부 하나의 결과로 합치는” 식"(args + ...)" 이 부분이 Fold 형식 내부적으로 ((1 + 2) + 3) + 4와 같이 전개됨. 초기값이 있는 Fold내부적으로 (initial + ... + args)는 ((10 + 1) + 2) + 3.. 2025. 1. 24. DFS(깊이 우선 탐색) & BFS(너비 우선 탐색) DFS와 BFS는 모두 *그래프를 탐색할 때 사용한다. *그래프:정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조 하나의 정점에서 시작하여 차례대로 모든 노드들을 순회(방문)하면서 탐색하는 탐색 알고리즘이다. DFS(깊이 우선 탐색) ; 루트 노드(혹은 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 모두 순환하여 탐색하는 방법. 모든 노드를 방문하고자 하는 경우나 이전 경로의 정보가 필요한 경우에 사용한다. 최대한 깊이 내려간 뒤에 더 이상 깊이 갈 곳이 없으면 옆으로 이동한다. 스택(stack) 또는 재귀함수로 구현한다. DFS 구현(재귀) 1. 노드를 방문 리스트에 기록 2. 현재 노드에 인접한 노드를 기준으로 반복 3. 노드의 인접 리스트가 비었을 경우 .. 2023. 8. 17. 그래프(Graph) 그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node) 와 간선(Edge)로 표현하기 위해 사용한다. 노드(Node) : 위치를 말한다. 정점(Vertex)이라고도 함. 간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨.(link or branch) 인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드) 무방향 그래프 ; 방향이 없는 그래프 간선을 통해 노드는 양방향으로 갈 수 있음 보통 노드 A,B가 연결되어 있을 경우, (A, B) 또는 (B, A)로 표기 방향 그래프 ; 간선에 방향이 있는 그래프 보통 노드 A,B가 A->B로 가는 간선으로 연결되어 있을 경우, 로 표기. 는 B -> A로 가는 간선이 있을때에 표.. 2023. 8. 14. 백 트래킹(backtracking) 제약 조건 만족 문제에서 해를 찾기 위한 전략 ; 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack(다시는 이 후보군을 체크하지 않을 것을 표기)하고 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법. 실제 구현시, 고려할 수 있는 모든 경우의 수(후보군)를 상태공간트리를 통해 표현 ; 각 후보군을 DFS(깊이 우선 탐색)방식으로 확인 Promising: 해당 루트가 조건에 맞는지를 검사하는 기법 Pruning(가지치기) : 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서 탐색의 시간을 절약하는 기법 즉, 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는.. 2023. 8. 13. 하노이의 탑 하노이 탑이란 1883년 프랑스 수학자 루카스(Lucas)에 의해 고안된 문제인데, 가운데 기둥을 이용해서 왼쪽 기둥에 놓인 크기가 다른 원판을 오른쪽 기둥으로 옮기는 문제였다. 이때 원판은 한번에 한 개씩만 옮길 수 있으며, 작은 원판 위에 큰 원판이 놓일 수 없다는 조건이 따른다. 최소 이동 횟수를 구하거나 원반의 이동 순서를 출력하는 문제가 나온다. [참고] https://shoark7.github.io/programming/algorithm/tower-of-hanoi [참고] https://splendidlolli.tistory.com/344 공식의 개념을 이해하라면 우선, n개의 원반을 '맨 아래 원반'과 '나머지 원반묶음'이라는 두 분류로 봐야한다. 그리고 나서 다시 '맨 아래 원반'과 '나머.. 2023. 8. 13. 피보나치 수 수학에서 피보나치 수(Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다. 재귀함수를 통해 푸는 방법은 가장 기본적이지만 수가 커질수록 함수 오버플로우가 발생한다. 즉, 시간초과. #include #include using namespace std; int fibonacci(int n) { if(n == 1 || n == 2) return 1; return fibonacci(n - 1) + fibonacci(n - 2); } 시간초과를 해결하는 방법은 Bottom to Top 의 방향으로 쉽게 구현할 수 있다. n번째 피보나치 수를 구하기 위해 .. 2023. 8. 12. 이전 1 2 3 4 ··· 45 다음
