C C++/C C++ 유용한 알고리즘 기법17 DFS - 전위순회, 중위순회, 후위순회 전위순회, 중위순회, 후위순회란?이진 트리(Binary Tree)를 순회하는 방법을 얘기한다.전위순회는 루트 -> 왼쪽 자식 -> 오른쪽 자식중위순회는 왼쪽 자식 -> 루트 -> 오른쪽 자식후위순회는 왼쪽 자식 -> 오른쪽 자식 -> 루트를 의미한다. 아래 1부터 7까지 가지는 Tree를 순회하며 출력해보자.DFS를 표현하면 다음과 같다. 다음은 전위 순회를 의미한다.#include #include using namespace std;void ch(int x){ if (x>7){ return; } else{ cout cout 전위 순회cout 중위 순회cout 후위 순회ch(2*x);ch(2*x+1);cout 2024. 11. 23. [C/C++] 연속된 숫자 한자리씩 나누어 입력 받기 방법 1. scanf 이용하여 나누어 받기 가장 흔한 방법이다. C에서 주로 사용하는 scanf에서는 입력 형식을 지정해주어야한다. 이 때 입력을 "%1d"로 지정하면 된다. 이렇게 지정하면 하나의 정수가 들어오면 입력이 모두 된 것으로 간주하고 다음 입력으로 넘어가게 된다. 같은 방식으로 이중 for문에도 활용할 수 있다. #include using namespace std; int main() { int a[10]; for (int i=0; i 2023. 3. 16. 알고리즘 병합 정렬 완벽 이해하기 병합 정렬이란? 병합 정렬은 나누고 붙이는 과정을 기반으로 한 정렬 알고리즘이다. 하나의 배열을 둘로 나누고, 이를 정렬하여 다시 붙이게 된다. 병합 정렬은 재귀 함수 호출로 정렬할 수 있는 데, 배열을 1/2씩 최대한 쪼갠 후 쪼개진 배열을 정렬하고, 최대한 쪼개진 배열을 둘씩 붙이고, 다시 정렬하고, 다시 붙이고...를 반복한다. 사실 설명보다 아래 그림을 이해하는 편이 더 쉽다. 이 정렬 방식은 최악, 최선 어느 경우에도 O(Nlong(N))의 시간 복잡도를 가진다. 공간 복잡도는 O(n)이다. 코드 부분 부분 해설 코드는 아래와 같은 형식으로 풀 수 있다. 1. 반으로 최대한 쪼갤 수 있을 때까지 쪼갠다. (재귀 함수 호출, 더 쪼갤 수 없을 때는 리턴) 2. 정렬의 가장 왼쪽을 가리키는 값(p1.. 2022. 10. 29. [C/C++] 배열값 옮기기 배열값 한 칸씩 옮기기 오늘은 배열값을 한칸씩 옮길 때 유의할 점을 따져 보려고 한다. 예를 들자면, [1,2,3] 값을 [3,1,2] 등으로 옮겨본다고 하자. 쉽다고 생각할만 하지만 유의할 점이 하나 있다. #include #include #define endl "\n" using namespace std; int arr[]={1,2,3}; void print() { for (int i=0; i 2022. 10. 15. 이전 1 2 3 4 5 다음
