알고리즘 유형 정리


브루트포스 란


완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.

  • 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.
  • 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구이다.
    너비 우선 탐색은 브루트 포스와 관련이 깊고, 깊이 우선 탐색은 다음에 작성될 백트래킹과 관련이 깊으므로 그때 따로 작성하도록 하겠다.

문제풀이

  1. 문제
    어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오.

  2. 입력
    첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다.

  3. 출력
    첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다

  4. 예제입력 : 110, 예제 출력 : 99

import java.util.Scanner;

public class 백준1065_한수 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		String N = sc.nextLine();
		
		System.out.println(solution(N));
	}
	
	public static  int solution(String N) {
		
		int n =Integer.parseInt(N);
		if(n <100) {
			return n;
		}else {
			int cnt =99;
			for(int i=100; i<=n ; i++) {
				int 백의자리 = i/100;
				int 십의자리 = i%100 / 10;
				int 일의자리 = i % 10;
				
				if((백의자리-십의자리) == (십의자리-일의자리)) {
					cnt++;
				}
			}
			return cnt;
		}
	}
}


해설

위의 문제에서는 100이하의 자연수는 모두 자기 자신만큼 결과 값이 나온다 왜냐하면 세자리 이하의 자연수는 비교가 불가능하기 때문이다. 따라서 세자리 이하일때와 아닐때를 분기하여 처리하면 된다. 세자리 이상일 때를 구해야하는데 브루트포스는 완전탐색유형이기 때문에 N보다 작은 자연수를 모두 검사하여 등차수열이 성립되는 방식으로 문제를 풀었다.
이런 상황에서 정답을 빠르게 찾는 규칙이나 패턴이 존재하면 해당 패턴을 통해 등차수열여부만 빠르게 검증하여 개수를 카운트하는 방식이 있을까 고민하였다. 당연히 등차가 성립안되는 수도 일일히 검증하는게 어떻게 보면은 시간낭비일 수 있지만 for 구문의 탐색 범위가 1000개 이하이기 때문에 시간 복잡도가 N (최대 1000) 으로 오버헤드가 크지 않기 때문에 문제가 없는것으로 판단하여 진행하였다.