brute force '무식하게 푼다(brute-force)'는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 말합니다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전 탐색(exhaustive search)라고 부릅니다. + 프로그래밍 대회에서 대부분의 사람들이 가장 많이 하는 실수는 쉬운 문제를 어렵게 푸는 것입니다. 문제를 마주하면 가장 먼저 무식하게 풀 수 있는 지 생각 해보는 것도 좋은 방법입니다. 재귀호출과 완전 탐색 재귀 호출 (recursion) 재귀함수 (recursive funciton): 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼객 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수입니다..

정렬되지 않은 숫자들 중 k번째 작은 수 찾기 수열 [7, 2, 6, 3, 10, 5, 1, 8, 4, 9] 에서 4번째 작은 수를 찾는다. > 숫자 하나(Pivot)를 기준으로 작은 수는 왼쪽 큰 수는 오른쪽으로 위치시킨다. 5를 기준(피벗)이라고 하자. 업포인터와 다운포인터를 설정한다. 업포인터: 왼쪽 -> 오른쪽 이동 (7->2->6-> . . .) 다운포인터: 왼쪽

아래 그림에서 원으로 표시한 것을 노드(Node)라고 한다. 직접 갈 수 있는 노드를 인접 노드(Adjacent Node)라고 한다. 예를 들어 A의 인접 노드는 G, B다. 그리고 각 노드를 잇는 선을 간선이라고 한다. A에서 I로 갈 수 있을까? 소모적 탐색 A에서 출발하여 갈 수 있는 모든 곳을 가 본 후, 가는 길이 없다면 길이 없다는 결론을 내리고, 만약 있다면 더 이상 다른 길을 찾지 말고, 길이 있다는 결론을 내린다. 소모적 탐색에는 깊이우선 탐색과 너비우선 탐색이 있다.

2022.04.10 - [C++] - 예외처리 #include using namespace std; int fact(int ); int main(void) { int n; cin>>n; try { cout

정렬된 배열의 탐색에서 사용한다. 배열의 중앙아 있는 값을 조사하여 찾고자하는 값이 중앙값보다 큰지 작은지를 판단한다. 만약 크다면 찾고자하는 값은 중앙값보다 오른쪽에 있는 것이고, 작다면 중앙값보다 왼쪽에 있는 것이다. 예를 들어 배열{1,2,3,4,5} 가 있을 때, 찾고자하는 값이 2라면 중앙값 3보다 작으므로 왼쪽에 있다. 이렇게 탐색의 범위를 반으로 줄일수 잇고, 이러한 방법에 의해 매 단계에서 검색해야할 리스트의 크기를 반으로 줄인다. 다음은 이진탐색이 성공한 경우이다. 만약 다음과 같이 배열안에 찾고자하는 원소가 존재하지 않는다면 탐색은 실패한다. 아래는 이진탐색을 C++로 구현한 예이다. #include using namespace std; #define ARRAY_SIZE 10 int m..

버블 정렬 (bubble sort) 버블 정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 이러한 리스트의 비료-교환 과정이 한번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다. 아래의 그림은 (22,37,15,19,12) 버블 정렬로 정렬한 것이다. 아래는 위의 그림을 코드로 구현한 것이다. #include using namespace std; #define ARRAY_SIZE 5 int main(void) { int array[ARRAY_SIZE] = {22,37,15,19,12}; for(int j = 0; j