개발스토리

분할 정복 문제를 나눌 수 없을 때까지 나눈 뒤, 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘. 분할 정복 설계 전략 1. 분할(Divide) 단계 - 문제를 같은 유형의 여러 개의 더 작은 부분 문제들로 나눈다. - 부분 문제는 풀기 쉬울 때까지 계속 나눈다. 2. 정복(Conquer) 단계 - 부분 문제들을 보통 재귀적으로 해결하여 해를 구한다. 3. 합병(Merge) 단계 - 문제에 대한 해를 구하기 위해 부분 문제들의 해를 합친다. -> 문제를 제대로 나눈다면 정복 단계는 쉬워지므로 분할 단계를 제대로 해야한다. 문제 : 최댓값 최솟값 찾기 문제: 크기가 n인 배열내의 요소들 중 최댓값과 최솟값을 찾는다. 1.최댓값을 찾는다. -- 비교 횟수: n – 1 2.남은 배열 요소들의 최솟값을..

순차 탐색(Sequential Search) 순차 탐색은 말 그대로 순차적으로 비교해가면서 찾는 것이다. data = {28, 40, 56, 63, 74, 87, 95}라는 배열이 있다. 74가 어디에 있는 지 알고 싶다. data[0]부터 값을 살펴봐서 74인지 아닌지 하나하나 확인하는 것이다. data[0], data[1] ... 탐색하다가 data[4] == 74이므로 여기서 탐색을 멈추게 되는 것이다. 복잡도(Time Complexity) 만약 data 배열에서 28을 탐색하면 1번만에 찾아낼 것이다. 40을 탐색하고자 한다면 2번만에 찾아낼 것이고, 56을 탐색하고자 한다면 3번만에 찾아낼 것이고, … 95를 탐색하고자 한다면 7번만에 찾아낼 것이다. 그럼 탐색하는게 걸리는 평균 연산 횟수는 (..

문제 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, 주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙이면 새로운 수를 만들 수 있다. 다음 예를 보자. 26부터 시작한다. 2+6 = 8이다. 새로운 수는 68이다. 6+8 = 14이다. 새로운 수는 84이다. 8+4 = 12이다. 새로운 수는 42이다. 4+2 = 6이다. 새로운 수는 26이다. 위의 예는 4번만에 원래 수로 돌아올 수 있다. 따라서 26의 사이클의 길이는 4이다. N이 주어졌을 때, N의 사이클의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 ..

문제 본격적으로 for문 문제를 풀기 전에 주의해야 할 점이 있다. 입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있다는 점이다. C++을 사용하고 있고 cin/cout을 사용하고자 한다면, cin.tie(NULL)과 sync_with_stdio(false)를 둘 다 적용해 주고, endl 대신 개행문자(\n)를 쓰자. 단, 이렇게 하면 더 이상 scanf/printf/puts/getchar/putchar 등 C의 입출력 방식을 사용하면 안 된다. Java를 사용하고 있다면, Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 사용할 수 있다. BufferedWriter.flush는 맨 마지막에 한 번만 하면 된다. P..