본문 바로가기

알고리즘4

[개념 정리] 백트래킹 백트래킹이 뭘까? 이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다. 백트래킹백트래킹은 완전 탐색과 가지 치기를 결합한 방식입니다.모든 가능한 해를 찾는 과정에서 불필요한 탐색을 줄여줍니다. 완전 탐색과 어떤 차이가 있을까요? 완전탐색은 모든 경우의 수를 전부 탐색하며 해를 찾는 방법입니다. 이 과정에서 불필요한 탐색이 발생할 수 있습니다.백트래킹은 이러한 불필요한 탐색을 줄이고, 더 작은 시간복잡도를 가지고 찾고자하는 해를 찾을 수 있도록 해줍니다. 가지 치기란 무엇일까요? 백트래킹의 핵심 기법 중 하나입니다. 현재 탐색 중인 경로가 찾고자하는 해에 도달할 수 없다고 판단하는 경우, 가차없이 그 경로를 탐색하지 않고, 다시 되돌아가는 방법을 말합니.. 2025. 3. 2.
[개념 정리] 완전 탐색 완전 탐색이 뭘까? 이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다. 완전 탐색완전탐색은 brute force라고도 불리며 모든 경우의 수를 탐색하는 알고리즘입니다.경우의 수는 순열 또는 조합을 의미합니다. 보통 완전탐색은 경우의 수 생성 (순열/조합) + 각 경우마다 조건 검사 및 처리 (DFS 또는 BFS 등)으로 구성되어 있습니다.  언제 완전탐색을 사용해야 할까요? 시간복잡도가 약 1억 번 이내라면 완전탐색을 써도 현실적으로 문제가 풀리게 됩니다. 컴퓨터가 1초에 약 1억 번 연산 가능하다고 보는 게 일반적 기준이기 때문입니다. 완전 탐색은 어떻게 구현할 수 있을까요? 완전 탐색을 하는 방법은 반복문을 활용한 완전 탐색, 재귀 호출을 활용한.. 2025. 3. 1.
[개념 정리] 트리 순회 트리 순회가 뭘까요? 이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다. 트리 순회트리 순회는 트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정입니다.순회 방식에는 깊이 우선 순회와 너비 우선 순회가 있고, 깊이 우선 순회는 전위 순회, 중위 순회, 후위 순회로 나뉩니다.  깊이 우선 순회전위 순회 : 부모노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드중위 순회 :  왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드후위 순회 : 왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드 예시 그림을 통해서 전위, 중위, 후위 순회, 레벨 순회의 순서를 알아보겠습니다.전위 순회 : A  → B  → C  → D  → E중위 순회 .. 2025. 2. 28.
최대 증가 부분 수열 최대 증가 부분 수열(LIS)이 뭘까요?  최대 증가 부분 수열(Longest Increasing Sequence)은 오름 차순으로 증가하는 부분 수열 중 가장 긴 부분 수열을 의미합니다.하나의 예시를 통해서 알아보겠습니다.10 20 30 10 40 50 오름 차순으로 증가 하는 부분 수열 중 가장 긴 부분 수열은 어떻게 될까요? 10 20 30 20 40 50 [10,20,30,40,50]이 됩니다. 중간에 20이 있는데 오름 차순으로 증가하는 부분 수열이 아니지 않나요?10 20 30 20 40 50 [10,20]도 오름 차순으로 증가하는 부분 수열입니다. 어떤 부분 수열 배열이 최대 증가 부분 수열일까요? [10,20,30,40,50]은 길이가 5인 부분 수열이고, [10,20]은 길이가 2인 부분.. 2025. 2. 22.

티스토리툴바