글 읽기 - ㅠㅠ 풀긴 풀었는데 처음에 푼 코드가 시간 초과가 나요. 시간복잡도가 궁금합니다.

hot1614 3년 전 1

코드 블록이 통과한 코드입니다.

캡쳐 이미지가 제가 처음에 풀고 제출했던 코드인데 시간초과가 떠서요. 재귀 호출의 시간복잡도를 아직 이해를 잘 못한거 같은데 검색해도 이해하기가 힘듭니다 ㅠㅠ 혹시 두 코드의 시간 복잡도 차이를 설명해줄수 있을까요??

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_15661 {
	// BOJ / 15661번 / 링크와 스타트 / 브루트포스 / 실1

	static int board[][];
	static int n, min;
	static boolean visit[];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		n = Integer.parseInt(br.readLine());
		
		board = new int [n][n];
		min = Integer.MAX_VALUE;
		visit = new boolean[n];
		for(int i=0; i<n; i++) {
			stk = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<n; j++) {
				board[i][j] = Integer.parseInt(stk.nextToken());
			}
		}
		
		recursion(0);
		
		System.out.println(min);
		
	}
	
	public static void recursion(int depth) {
		
		// depth를 n까지 한다. 
		// 첫 n까지 재귀에는 모든 visit 배열에 true가 들어가겠지만 
		// 그 이후부터는 false가 하나씩 들어가면서 최솟값을 구하기 때문.
		// 최솟값만 구하면 되기 때문에 첫 n까지 재귀에 모든 visit 배열에 true가 들어가도 상관x
		if(depth == n) {
			diff();
			return;
		}
		
		visit[depth] = true;
		recursion(depth + 1);
		visit[depth] = false;
		recursion(depth + 1);
		
//		for(int i=start; i<n; i++) {
//			if(!visit[i]) {
//				visit[i] = true;
//				recursion(depth+1, start +1);
//				visit[i] = false;
//				recursion(depth+1, start +1);
//			}
//		}
	}
	
	public static void diff() {
		int start = 0;
		int link = 0;
		
		for(int i=0; i<n-1; i++) {
			for(int j=i+1; j<n; j++) {

				if(visit[i] && visit[j]) {
					start += board[i][j]+board[j][i];
				}
				else if(!visit[i] && !visit[j]) {
					link += board[i][j]+board[j][i];
				}
			}
		}
		
		int temp = Math.abs(start - link);
		
		min = Math.min(min, temp);
	}
}

tor012 3년 전 5

사진의 소스는 다음과 같은 상태공간트리를 가지게 됩니다.

게시해 주신 소스는 다음과 같은 상태공간 트리를 가지게 됩니다.

n이 3일때의 기준으로 diff()의 호출횟수가

전자는 192회 후자는 8회입니다.

n이 20에 달하는 경우 후자는 105만번정도의 diff 호출만 일어나지만

전자의경우는 셀수도없을정도로 많은 호출이 일어나곘죠.

전자의 재귀함수가 만드는 visit의 경우는 문제에서 필요한 것 보다 너무많은 중복의 경우를 만들고 있습니다. (재귀의 파라미터가 의미를 가지지 못하고, 의미없는 반복문이 호출되기 때문입니다)

후자의 경우는 나이브하게 생각할수 있는 팀의 조합을 딱 맞게 구하긴 하지만(그리고 시간제한 내에도 돌만하게 만들긴 하지만)

정답을 구할 수 있는 조합보다는 2배 많은 조합을 만들게 됩니다.

후자의 경우 정답을 2배만든다고 하는 이유에 대해선 다음 예를 들어볼 수 있습니다.

A, B, C 세 사람이 있습니다.

start팀에 A만

link팀에 B,C 가 들어갔을때의 시너지 차이와

start팀에 B,C가

link팀에 A만 들어갔을때의 시너지 차이가 과연 다를까요? 두 경우를 다 따져야만 정답을 알 수 있을까요?

tor012 3년 전 2

사진의 53번줄 if문을 확인하지못해 실제 호출횟수는 n=3일때 192보다는 작을듯합니다만 여전히 말도안되게 불필요한 경우를 많이 만드는것은 변함없습니다.

hot1614 3년 전 0

제대로 이해했습니다. 감사합니다. 그림 까지 그려주셔서 확실히 이해됐습니다!! 감사합니다 ㅠㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

ㅠㅠ 풀긴 풀었는데 처음에 푼 코드가 시간 초과가 나요. 시간복잡도가 궁금합니다.

hot1614 3년 전 1

tor012 3년 전 5

tor012 3년 전 2

hot1614 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말