백준 24262~24267번: 알고리즘 수업 1~6 (JAVA)

TIL

백준 단계별로 풀어보기 시간 복잡도 파트를 풀었다.
https://www.acmicpc.net/step/53

백준 24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1

https://www.acmicpc.net/problem/24262
단일 연산의 경우 연산을 하는 횟수 만큼 시간 복잡도가 고정적으로 나온다
O(1) 의 시간 복잡도를 가짐

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

백준 24263번: 알고리즘 수업 - 알고리즘의 수행 시간 2

https://www.acmicpc.net/problem/24263
for문이 한번 돌면 for문에 적힌 변수(i,n 등등..) 만큼 시간 복잡도가 나온다
O(n) 의 시간 복잡도를 가짐.
차수는 1

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int n= Integer.parseInt(br.readLine());
		System.out.println(n);
		System.out.println('1');
	}
}

백준 24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3

https://www.acmicpc.net/problem/24264

이중 for문의 경우 n*n만큼의 시간이 소요된다
O(n^2)만큼의 시간 복잡도를 가짐.
차수는 2

그런데 이 문제를 풀 때 int로 변수를 받으면 오버플로우가 나서 틀렸다고 나온다.
int는 -2,147,483,648~ 2,147,483,647 범위의 수를 표현할 수 있는데
46341 * 46341 을 하면 이 범위를 넘어선다.
그래서 Long형으로 받아 줘야 한다.

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

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		Long n= Long.parseLong(br.readLine());
		System.out.println(n*n);
		System.out.println('2');
	}
}

백준 24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4

https://www.acmicpc.net/problem/24265
i는 [1, n-1], j는 [i+1, n]번 돈다.
n-1 + n-2 + ... + 1 번 돌게된다.
차가 1인 등차수열만큼 돌게 되므로 n*(n-1)/2 만큼 돈다
그래도 시간 복잡도는 똑같이 O(n^2)다. 차수는 2

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		Long n= Long.parseLong(br.readLine());

		System.out.println(n*(n-1)/2);
		System.out.println('2');
	}
}	

백준 24266번: 알고리즘 수업 - 알고리즘의 수행 시간 5

https://www.acmicpc.net/problem/24266

for문이 3번 돈다
O(n^3)만큼의 시간 복잡도를 가진다.

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

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		Long n= Long.parseLong(br.readLine());
		System.out.println(n*n*n);
		System.out.println('3');
	}
}

백준 24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6

https://www.acmicpc.net/problem/24267
반복문의 범위는 n, n-1, n-2이다.

import java.io.IOException;
import java.io.InputStreamReader;

public class n24267{
	public static void main(String[] args) throws IOException{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		Long n= Long.parseLong(br.readLine());

		int sum=0;
		int count=0;
		for( int i=1;i<=n-2;i++) {
			for(int j= i+1;j<=n-1;j++) {
				for(int k=j+1;k<=n;k++) {
					sum=sum +i*j*k;
					count++;
				}
			}
		}
		System.out.println(count);
		System.out.println(n*(n-1)*(n-2));
		System.out.println('3');
	}
}	

위의 코드를 돌려서 확인해본다.!

6을 나누면 원하는 값을 얻을 수 있음을 알 수 있다.

import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		Long n= Long.parseLong(br.readLine());

	
		System.out.println(n*(n-1)*(n-2)/6);
		System.out.println('3');
	}
}