백준 닷컴 단계 별로 풀어보기 11단계

1단계 알고리즘 수업 - 알고리즘의 수행 시간 1

• MenOfPassion 알고리즘은 다음과 같다.

MenOfPassion(A[], n) {
    i = ⌊n / 2⌋;
    return A[i]; # 코드1
}

• 첫째 줄에 코드1 의 수행 횟수를 출력한다.
• 둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

public class Step_1 {
	public static void main(String[] args) {
		System.out.println(1);
		System.out.println(0);
		
	}
}

A.

• 상수 값을 받아 배열에서 특정 값을 리턴한다.
• 코드는 1번만 실행되고 코드 실행 회수는 상수부만 있기 때문에 0차원이다.

2단계 알고리즘 수업 - 알고리즘의 수행 시간 2

• MenOfPassion 알고리즘은 다음과 같다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        sum <- sum + A[i]; # 코드1
    return sum;
}

• 첫째 줄에 코드1 의 수행 횟수를 출력한다.
• 둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

import java.util.Scanner;

public class Step_2 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		
		System.out.println(a);
		System.out.println(1);
		
	}
}

A.

• 반복문을 통해 n번의 반복이 발생한다.
• 발생 회수가 n번이기 때문에 최고차항은 1이다.

3단계 알고리즘 수업 - 알고리즘의 수행 시간 3

• MenOfPassion 알고리즘은 다음과 같다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

• 첫째 줄에 코드1 의 수행 횟수를 출력한다.
• 둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

import java.util.Scanner;

public class Step_2 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		long a = scan.nextInt();
		
		System.out.println(a*a);
		System.out.println(2);
		
	}
}

A.

• 반복문을 통해 n의 제곱 번의 반복이 발생한다.
• 발생 회수가 n제곱 번이기 때문에 최고차항은 2이다.
• 반복 회수가 int의 범위를 넘어가기 때문에 long으로 받아야 한다.

4단계 알고리즘 수업 - 알고리즘의 수행 시간 4

• MenOfPassion 알고리즘은 다음과 같다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 1
        for j <- i + 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

• 첫째 줄에 코드1 의 수행 횟수를 출력한다.
• 둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

import java.util.Scanner;

public class Step_4 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		long a = scan.nextLong();
		
		System.out.println(a*(a-1)/2);
		System.out.println(2);
	}
}

A.

• 1~n-1까지의 회수만큼 반복이 발생하기 때문에 n(n-1)/2 만큼의 반복이 발생한다.
• n의 제곱이 가장 지수가 높기 때문에 최고차항 2 출력

5단계 알고리즘 수업 - 알고리즘의 수행 시간 5

• MenOfPassion 알고리즘은 다음과 같다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            for k <- 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

• 첫째 줄에 코드1 의 수행 횟수를 출력한다.
• 둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

import java.util.Scanner;

public class Step_5 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		long a = scan.nextLong();

		System.out.println(a*a*a);
		System.out.println(3);
	}
}

A.

• n의 3제곱의 반복을 한다.
• 최고차항은 3제곱이니까 3

6단계 알고리즘 수업 - 알고리즘의 수행 시간 6

• MenOfPassion 알고리즘은 다음과 같다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

• 첫째 줄에 코드1 의 수행 횟수를 출력한다.
• 둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

import java.util.Scanner;

public class Step_5 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		long a = scan.nextLong();
		
		System.out.println(a*(a-1)*(a-2)/6);
		System.out.println(3);
	}
}

A.

• 1~n까지 숫자 중 중복 없이 3 가지 숫자를 뽑는 시행. 즉 순열과 조합의 종류를 나타낸다.
• 3Cn의 결과가 출력된다.
• 즉 (n)(n-1)(n-2)/123 이다.

7단계 알고리즘 수업 - 점근적 표기 1

• O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}
• 함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.
• 첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다. (0 ≤ |ai| ≤ 100)
• 다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 100)
• 다음 줄에 양의 정수 n0가 주어진다. (1 ≤ n0 ≤ 100)
• f(n), c, n0가 O(n) 정의를 만족하면 1, 아니면 0을 출력한다.

import java.util.Scanner;

public class Step_7 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n1=scan.nextInt();
		int n0=scan.nextInt();
		int c=scan.nextInt();
		int a=scan.nextInt();
		
		if(n1<=c&&(n1*a+n0)<=a*c) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
	}
}

A.

• f(n)이 1차식이기 때문에 g(n)에는 n이 들어가야 한다.
• f(n)의 1차항 계수가 a1, g(n)쪽의 1차항 계수가 c인데 c보다 a1이 큰 경우 n이 커졌을 때 조건이 성립하지 않기 때문에 c가 a1보다 커야 한다.
• 그 이외에는 주어진 조건에 맞고, c가 a1보다 큰 경우에 1을 출력, 그 이외에 0을 출력하면 된다.