Development/Knowledge5 백트래킹 (Back Tracking) 목차백트래킹 (Back Tracking): 해를 찾는 도중 해가 절대 될 수 없다고 판단되면, 되돌아가서 해를 다시 찾아가는 기법이다.--> 알고리즘 기법 중 하나로 모든 경우의 수를 전부 고려하는 알고리즘이다. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식으로 일종의 트리 탐색 알고리즘이라고 봐도 된다. >> 방식에 따른 종류깊이우선탐색(Depth First Search, DFS)너비우선탐색(Breadth First Search, BFS)최선우선탐색(Best First Search/Heuristic Search) DFS(Depth First Search, 깊이우선탐색): 그래프 순회 방식의 일종으로, 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가.. 2025. 12. 16. 자료구조 목차Stack: Last In First Out (LIFO) 원칙을 따르는 자료구조 >> 주요 메서드Push(x) : 주어진 요소 x를 Stack의 맨 위에 추가한다.Pop() : Stack이 비어있지 않으면 맨 위에 있는 요소를 제거하고 반환한다.Peek() : Stack이 비어있지 않으면 맨 위에 있는 요소를 반환한다.Count : Stack에 있는 요소의 개수를 반환한다.Clear() : Stack에 있는 요소를 전부 제거한다.※ 공식 문서 - Stack 클래스 (System.Collections.Generic)" data-og-description="동일한 지정된 형식의 인스턴스에 대한 LIFO(Last-in-First-out) 컬렉션의 변수 크기를 나타냅니다." data-og-host="lear.. 2025. 11. 15. 소수 판별 함수 만들기 목차합성수의 특성: 합성수 N에 대하여 N = a × b 라고 하면, a와 b 둘 중 하나는 √N 보다 작거나 같다.--> 이를 활용하면 N이 소수인지 확인할 때, 1부터 √N까지만 반복하여 N을 나눈 나머지가 0이 아니라면 N이 소수임을 알 수 있다. - 증명: 만약 a와 b 둘다 √N 보다 크다면? 'a × b > √N × √N = N' 이 성립되어야 한다. 하지만 a × b = N 이기 때문에 a × b > N 라는 건 성립할 수 없다. 따라서 a와 b 둘 중 하나는 √N 보다 작거나 같다.ex) N = 100 일 때, 나올 수 있는 약수의 곱은 아래와 같다.1 × 1002 × 504 × 255 × 2010 × 10--> 모든 쌍에서 작은 값은 1, 2, 4, 5, 10 으로 모두 √100 즉, 1.. 2025. 11. 11. 유클리드 호제법을 활용하여 최대공약수, 최소공배수 구하기 목차유클리드 호제법 (Euclidean Algorithm): 두 자연수의 최대공약수를 구하는 알고리즘. 이때 호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 뜻한다.--> 두 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a > b) a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. - 반복문을 활용한 코드 (C#)// a > bint GCD(int a, int b){ while (b != 0) { int temp = a % b; a = b.. 2025. 11. 6. 정렬 알고리즘 목차C# 언어로 백준 문제를 풀다가 연습한 정렬 알고리즘을 한 게시글로 정리했습니다.혹시나 틀린 정보가 있다면 알려주시기 바랍니다 :) 시간 복잡도가 O(n²)└ 버블 정렬(Bubble Sort): 인접한 두 원소를 비교하여 정렬하는 간단한 알고리즘--> 1번째 원소와 2번째 원소를 비교하여 정렬하는 식으로 n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 이번에는 n-2번째와 n-1번째까지 정렬하는 방식으로 반복하여 정렬한다. - 코드public void BubbleSort(int[] arr){ int n = arr.Length; for (int i = 0; i arr[j]) { (arr[j - 1], arr[j]) = (arr[j], ar.. 2025. 10. 27. 이전 1 다음
