BOJ 24262~24264 (단계별 풀이 : 시간복잡도(1))

• 24262번

• 문제
  오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
  
  입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
  MenOfPassion 알고리즘은 다음과 같다.
  
  MenOfPassion(A[], n) {
  i = ⌊n / 2⌋;
  return A[i]; // => 코드1
  }
  
  
• 입력
  첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.
• 출력
  첫째 줄에 코드1 의 수행 횟수를 출력한다.
  
  둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

#include<iostream>
using namespace std;
int N;
void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}
int main()
{
	fast_io();
	cin >> N;
	cout << 1 << '\n' << 0;
}

단순 배열의 특정 값을 가져오는 부분이므로 상수 시간이 소요된다 (수행 횟수 1, 최고차항 0)

• 24263번

  MenOfPassion 알고리즘은 다음과 같다.
  
  MenOfPassion(A[], n) {
  sum <- 0;
  for i <- 1 to n
  sum <- sum + A[i]; // => 코드1
  return sum;
  }

#include<iostream>
using namespace std;
int N;
void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}
int main()
{
	fast_io();
	cin >> N;
	cout << N << '\n' << 1;
}

sum 변수와 배열의 원소를 더하는 과정에서 반복문이 호출된다 1중첩 반복문이 돌아가기 때문에 최고차항의 계수는 1이된다 (호출 횟수 입력 크기, 최고차항 1)

• 24264번

  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;
  }

#include<iostream>
using namespace std;
long long N;
void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}
int main()
{
	fast_io();
	cin >> N;
	cout << N*N << '\n' << 2;
}

2중첩 반복문이 돌아가기 때문에 최고차항의 계수가 N^2이 된다. 다만 이 문제에서는 입력 범위가 500000까지라 int 자료형 변수를 선언하면 범위 초과가 되므로 자료형에 신경써줘야 한다 그래서 정답률이 갑자기 떨어진듯 싶다. (호출 횟수 입력크기^2, 최고차항 2)

  아주 간단한 문제들 같지만 실제 문제 풀때 시간복잡도까지 고려하면서 문제를 푸는 습관이 중요해보인다 * 알고리즘의 핵심이 되는 KEY part를 찾고 시간복잡도 고려하기