[백준 24262 ~ 24267] 알고리즘 수업 - 알고리즘의 수행 시간 (1~6) (Swift)

1

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

코드 1의 수행 횟수와 알고리즘 수행 시간을 출력하면 된다.

• 코드 1의 수행 횟수는 언제나 1번
• 코드 1은 return A[i] 이며, n과 관계없이 상수 시간이 소요되므로 0 출력

풀이

print(1, 0)

2

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

• 코드1은 sum = sum + A[i] 이며, 1부터 n까지 반복하는 반복문 내에 있으므로 언제나 n번 실행된다.
• 알고리즘의 수행 시간은 n에 비례하므로 1을 출력.

풀이

let input = Int(readLine()!)!
print(input, 1)

3

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

• 코드 1은 sum = sum + A[i] * A[j] 이며, 1부터 n까지 반복되는 이중 for문에 있으므로 언제나 n의 2제곱만큼 실행된다.
• 알고리즘의 수행 시간은 n의 2제곱에 비례하므로 2 출력

풀이

let count = Int(readLine()!)!
print(count * count, 2)

4

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

• 코드1은 이중 for문 내에 있는 sum = sum + A[i] * A[j] 이지만, 첫번째 for문의 i는 1부터 n-1까지, 두번째 for문의 j는 i + 1 부터 n까지 반복된다.
  • 반복 횟수가 매번 다르므로 계산이 필요함
  • 처음에는 문제에 주어진 반복문대로 반복횟수를 구했는데, n의 최댓값만 생각해봐도 50만이니 시간제한인 1초에 걸린다.
  • 결국 규칙을 찾아 공식을 구해야 함
  • 주어진 반복문의 끝 범위인 n-1과 n을 곱한 값과 단순반복했을때의 결과값을 비교해 본다.
  • 1의 결과값 : 0, n(n-1) = 0
  • 2의 결과값 : 1, n(n-1) = 2 → /2해야 1이 될 것임
  • 3의 결과값 : 3, n(n-1) = 6 → /2해야 1이 될 것임
  • 4의 결과값 : 6, n(n-1) = 12 → /2해야 1이 될 것임
  • 와 같은 식으로 패턴을 찾을 수 있다.. (물론 나는 구글링의 도움을 받았다..)
  • 따라서 공식은 n(n-1)/2가 된다.
  • 알고 보니 삼각수 라는 수열 패턴이었다.. 배경지식이 있었다면 더 빠르게 찾았을 듯!
• 알고리즘의 수행 시간은 이중for문이므로 n2 → 2를 출력한다.

풀이

let input = Int(readLine()!)!
print(input * (input - 1) / 2, 2)

5

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

• 코드1은 sum = sum + A[i] * A[j] * A[k] 이며, 1부터 n까지 반복하는 3중 for문 내부에 있다. 따라서 수행 횟수는 n의 3제곱이 된다.
• 알고리즘의 수행 시간은 n의 세제곱에 비례하므로 3을 출력한다.

풀이

let input = Int(readLine()!)!
print(input * input * input, 3)

6

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

• 코드1은 sum = sum + A[i] * A[j] * A[k] 이며, 3중 for문 내에 있다.
• 반복 횟수가 i와 j에 따라 다르므로 패턴을 찾아 공식을 만들어야 한다.
  • 반복문에 사용된 범위에서 힌트를 얻고, 코드를 단순반복한 결과와 비교해 공식을 유추한다.
  • 반복문에 사용된 범위 : n(n-1)(n-2)
  • n이 1,2일 때 : (X) → 근데 예외처리는 필요없는듯.. 어차피 공식의 결과가 0으로 같다
  • n이 3일 때 : 1
    • n(n-1)(n-2) = 6
    • /6을 한 결과와 같아진다.
  • n이 4일 때 : 4
    • n(n-1)(n-2) = 24
    • /6을 한 결과와 같아진다.
  • n이 5일 때 : 10
    • n(n-1)(n-2) = 60
    • /6을 한 결과와 같아진다.
  • .. 같은 식으로 공식을 n(n-1)(n-2) / 6 으로 유추할 수 있다.
  • (역시 이것도 구글링의 도움을 받았다..)
• 알고리즘의 수행 시간은 3중 for문이므로 n의 3제곱에 비례함. 따라서 3을 출력한다.