노랑꼬리의 개발 블로그

목차 1. 백트래킹 알고리즘 2. 로직 3. 구현 1. 백트래킹 알고리즘이란? - 모든 경우에 수에 대해 탐색 - 탐색 중에 해당 경로가 해가 될 가능성이 없다면 경로를 되돌아가 다시 결과를 찾는다. (가지치기) - 주로 DFS(깊이 우선 탐색) 방식으로 확인한다. 2. 로직 가. 유망성 검사 - 해가 될 가능성이 있는지 조건을 설정한다. 나. 가지치기 - 유망성 검사를 통해 가능성이 없는 경로를 차단(가지치기) 하여 탐색의 효율성을 높인다. 3. 구현 문제 예시 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. ..

목차 1. 유클리드 알고리즘 2. 로직 3. 구현하기 1. 유클리드 알고리즘이란? - 2개의 자연수 혹은 두 다항식의 최대 공약수를 구하는 방법 - 서로 나누어 해를 구하므로 유클리드 호제법(互除法 : 합(互)하고 나누는(除) 방법(法))이라고도 한다. 2. 로직 가. 최대 공약수 두개의 자연수 a,b (a>b)에 대하여 a를 b로 나눈 나머지가 r일 때, a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다. 이에 따라 b와 r에 대해서 나머지 r2를 구하고 r을 r2로 나누는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 최대 공약수가 된다. 나. 최소 공배수 최소 공배수는 최대 공약수를 이용하여 구할 수 있다. 두개의 자연수 a,b (a>b)에 대하여 a와 b의 최소 공배수는a와 b의 곱을..

목차 ※ 정렬 #1 버블 정렬 & 선택 정렬 ※ 정렬 #2 삽입 정렬 & 힙 정렬 1. 분할 정복 알고리즘 2. 병합 정렬 (Merge Sort) 3. 퀵 정렬 (Quick Sort) 1. 분할 정복 알고리즘 - 엄청나게 크고 방대한 문제를 나누어 쉽게 풀 수 있는 작은 크기로 나누어 문제를 해결 한 뒤 합쳐서 해결하는 방식이다. - 어려운 문제를 간단하고 빠르게 해결 할 수 있다. - 함수 재귀 호출을 이용하여 구현하므로 오버플로가 발생할 수 있고 쪼갠 문제를 저장해야 하므로 메모리 사용량이 크다. ※ 3가지 단계를 거쳐 해결한다. 가. 분할: 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다. 나. 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다. 다. 조합: 하위 ..

목차 ※ 정렬 #1 버블 정렬 & 선택 정렬 1. 삽입 정렬 (Insertion Sort) 2. 힙 정렬 (Heap Sort) 1. 삽입 정렬 (Insertion Sort) - 배열의 요소를 앞에서 부터 이미 정렬된 배열과 비교하여 자신의 위치를 찾아 정렬 - 1회전 마다 하나씩 요소들을 정렬해나간다. - 배열이 길수록 효율이 떨어진다. (비교할 정렬이 길어지므로) - 본인 위치를 찾아 삽입하여 정렬하므로 삽입 정렬이라 한다. - 시간 복잡도가 버블 정렬, 선택 정렬과 같은 O(n²) 이지만 둘 보다 빠르다. 가. 구현하기 2. 힙 정렬 (Heap Sort) - 완전 이진 트리로 구성되어 최대 힙 트리나 최소 힙 트리를 구성해 정렬. - 정렬된 최대(최소) 힙에서 루트 노드를 꺼내어 배열에 저장한다. -..

목차 1. 정렬 알고리즘 2. 버블 정렬 (Bubble Sort) 3. 선택 정렬 (Selection Sort) 1. 정렬 알고리즘 - 원소들을 번호 순이나 사전 순 같이 일정한 순서로 열거하는 알고리즘 - 다른 알고리즘을 수행 하기 전 최적화를 위해 우선적으로 실행한다. - 대표적인 정렬 알고리즘 6개가 존재한다. ㄴ 버블 정렬, 선택 정렬, 삽입 정렬, 힙 정렬, 병합 정렬, 퀵 정렬 ※ 시간 복잡도 Sorting Best Avg Worst 버블 정렬 O(n²) O(n²) O(n²) 선택 정렬 O(n²) O(n²) O(n²) 삽입 정렬 O(n) O(n²) O(n²) 힙 정렬 O(nlog₂n) O(nlog₂n) O(nlog₂n) 병합 정렬 O(nlog₂n) O(nlog₂n) O(nlog₂n) 퀵 정렬 ..

목차 ※ 트리 #1 Tree ※ 트리 #2 DFS 1. 너비 우선 탐색이란? 2. BFS 구현 1. 너비 우선 탐색이란? (BFS : Breath First Search) - 그래프의 인접한 정점을 우선적으로 탐색 - queue를 이용하여 구현한다. - 장점 : 탐색된 경로가 항상 최단 경로이다, queue를 사용하여 다음 탐색 정점을 지정하므로 DFS 보다 메모리를 적게 사용한다. - 단점 : 목표 노드의 깊이가 깊은 경우 탐색이 오래 걸린다. 2. BFS 구현 (※ 입력 기준 : BFS 애니메이션) ※ 참조 위키 백과 너비 우선 탐색 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

목차 ※ 트리 #1 Tree 1. 깊이 우선 탐색이란? 2. DFS 구현 1. 깊이 우선 탐색이란? (DFS : Depth First Search) - 그래프에서 깊은 부분을 우선적으로 탐색 - 리프 노드에 도달 할 때 까지 목표 노드를 탐색, 발견 되지 않으면 현재 탐색 중인 노드의 부모 노드에서 탐색 되지 않은 자식 노드를 탐색한다. (백 트래킹 : backtracking) ㄴ 노드 방문 시 방문 여부를 검사해야 무한 루프를 방지할 수 있다 (탐색 된 노드 재탐색 방지) - 장점 : 현재 경로만 저장하며 탐색하므로 메모리를 적게 사용한다 (단순 탐색에 비해), 목표 노드가 깊이 있다면 빠르게 구할 수 있다. - 단점 : 탐색된 결과가 최단 경로가 아닐 수 있다. (목표 경로가 여럿일 경우), 목표 노..

목차 1. 트리의 구성요소 2. 트리 구현 1. 트리의 구성요소 Tree는 컴퓨터 친화적인 선형 자료구조가 아닌 사용자 친화적인 비선형 계층 자료 구조이다. 사용자가 원하는 데이터를 얻기 쉽도록 데이터를 구분하여 연결해 준다. ex) 컴퓨터 파일 경로, 회사 조직도 가. 노드(Node) - 트리의 각 요소 - 데이터를 저장하고 다음 노드로 연결 시켜줄 주소 값이 저장되어 있다. 1) 루트 노드 - 트리 구조에서 최상위 노드 (트리 예시 기준 A) - 부모 노드가 없음 2) 부모 노드 - 해당 노드와 연결 된 윗 노드 (트리 예시 기준 D와 E의 부모 노드 : B) 2-a) 조상 노드 - 해당 노드에서 루트 노드까지 경로 상의 윗 노드 들 (트리 노드 예시 기준 H의 조상 노드 : D, B, A) 3) 자..

목차 ※ STL #1 순차 컨테이너 ※ STL #2 연관 컨테이너 ※ STL #3 Stack & Queue 1. Heap 2. Priority_queue 1. Heap - 완전 이진 트리 (Complete Binary Tree) 기반 자료구조 ㄴ 이진 트리 : 자식 노드가 최대 두 개인 노드들로 구성된 트리 ㄴ 완전 이진 트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워진 이진 트리 ※ 마지막 레벨은 왼쪽 부터 순차적으로 채워져야한다. - 최대값 혹은 최소값을 빠르게 구하기 위한 자료구조 - 부모 자식 간의 관계만 중요하고 형제 노드와는 관계성이 없다. - Min Heap : 부모 노드가 자식 노드보다 항상 작다 (= 루트 노드가 최소값이다) - Max Heap : 부모 노드가 자식 노드보다 항상..

목차 ※ STL #1 순차 컨테이너 ※ STL #2 연관 컨테이너 1. stack 2. queue 1. std::stack - LIFO (Last In First Out : 후입선출) 데이터 구조 ㄴ 마지막에 삽입된 데이터가 가장 먼저 삭제된다. (사용처 예시 : ctrl + z, DFS(깊이 우선 탐색) ) - deque를 바탕으로 만들어져 있다. 가. 선언 및 초기화 template //template ≒ 자유 자료형 std::stack //T : 배열에 담길 자료형 - stack s1; // 빈 스택 생성 - stack s2( {'a', 'b', 'c'} ) // 생성과 동시에 초기화 - stack s3(s2); // s2의 값을 복사하여 s3 스택 생성 나. 멤버 함수 (※ 기준 : stack s..