https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 트리 재귀 순회 문제이다. 이런 문제를 몇번 풀어보긴 했지만, 익숙하지 않아서 꽤 애를 먹었다. 알고리즘은 뭔가 답답할 땐 항상 그림을 그리며 직접 손으로 따라가보자! --설명-- 1. (0,8)을 넘겨준다 2. mid는 end+1로 설정하고, ( 아래 for문에서 mid값이 갱신되지 않는다면, end를 그대로 넘겨야 하는데 넘길 때 -1을 해주므로 ) 3. start를 pivot 삼..
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 오랜만에 푼 구현 + 브루트 포스 + 백트래킹 문제이다. 문제 자체는 크게 까다롭지 않지만, 백트래킹에서 고민을 좀 많이 하였고 결국 다른 글을 참고하게 되었다..(시무룩) 1. 입력을 받는다 (CCTV가 나오면 해당 좌표를 벡터에 담아준다!) 2. 완전 탐색을 실시한다. 3-1. 만약 모든 CCTV를 확인하여, 감시 구역을 정했으면 사각지대의 수를 세서 최솟값을 저장한다. 3-2. 아..
정렬 - 선택 정렬 void sort(int* a, const int n) { // n개의 정수 a[0]부터 a[n-1]까지 비감소순 정렬 for (int i = 0; i < n; i++) { int j = i; //a[i]와 a[n-1]사이에 가장 작은 정수 값을 찾음 for (int k = i + 1; k < n; k++) { if (a[k] < a[j]) { j = k; // 교환 } } swap(a[i], a[j]); } } 제일 작은 정수를 찾아 앞으로 보내는 작업을 계속 반복한다. 탐색 이원탐색(binary search) int binarySearch (int arr[], int low, int high, int key) { while (low key) high = mid - 1; else..
