출처

천인국, 최영규, 『C++로 쉽게 풀어쓴 자료구조』, (주)생능출판사(2016-08-09), 19-50p

1.1 자료구조

자료구조란?

• 컴퓨터의 자료들을 정리하고 조직화하는 여러 가지 구조들

자료구조의 분류

선형 자료구조

• 자료들이 순서적으로 나열되어 있음
• 순서 접근(sequential access): 연결리스트 같은 것
• 직접 접근(direct access): 배열 같은 것

비선형 자료구조

• 선형적인 순서가 아니라 복잡한 연결을 갖는 형태 –> 트리, 그래프 같은 것

자료구조의 활용

• 대표적으로 정렬과 탐색이 효율적이여서 많이 활용됨

1.2 알고리즘

알고리즘이란?

• 어떤 문제를 해결하는 절차
• 프로그래밍 언어와 상관 없음

프로그램 = 자료구조 + 알고리즘

• 데이터는 자료구조로 처리하고 문제 해결은 알고리즘으로 함
• 자료구조가 결정되면 그에따른 알고리즘도 결정됨

정의 1.1 알고리즘의 조건

• 입력: 0개 이상의 입력이 존재해야 함
• 출력: 1개 이상의 출력이 존재해야 함
• 명백성: 각 명령어의 의미는 모호하지 않고 명확해야 함
• 유한성: 한정된 수의 단계 후에는 반드시 종료되어야 함
• 유효성: 각 명령어들은 실행 가능한 연산이어야 함

알고리즘 기술 방법

영어나 한국어와 같은 자연어

• 자연어를 사용하여 기술이 편리하지만 명백하게 해야 함

알고리즘 1.1 최댓값을 찾는 알고리즘을 자연어로 표현한 예

• ArrayMax(A,n)
  1. 배열 A의 첫 번째 요소를 변수 tmp에 복사한다.
  2. 배열 A의 다음 요소들을 차례대로 tmp와 비교하여, 더 크면 그 값을 tmp로 복사한다.
  3. 배열 A의 모든 요소를 비교했으면 tmp를 반환한다.

흐름도(flowchart)

• 흐름도는 명확한데 복잡해지면 복잡해짐

유사 코드(pseud-code)

• 자연어보다 체계적이고 프로그래밍 언어보다는 덜 엄격한 언어
• 대입 연산자가 =가 아니라 <-임을 유의
• =는 비교 연산자로 사용
• 가장 선호되는 표기법

알고리즘 1.2 최댓값을 찾는 알고리즘을 유사 코드로 표현한 예

• ArrayMax(A,n)

  tmp <- A[0];  
  for i<- to n-1 do  
  if tmp < A[i] then  
    tmp <- A[i];  
  return tmp
  

특정한 프로그래밍 언어

• 알고리즘의 가장 정확한 표현
• 구현을 위한 많은 구체적인 사항들을 포함

프로그램 1.1 최댓값을 찾는 알고리즘을 C++ 함수로 구현한 예

int ArrayMax(int score[], int n) { // 자료구조: 배열 array, n은 배열 길이
  int tmp = score[0];
  for (int i = 1; i < n; i++) { // 알고리즘
    if (score[1] > tmp) {
      tmp = score[i];
    }
  }
  return tmp;
}

1.3 추상 자료형

추상화란?

• 복잡한 자료, 모듈, 시스템 등으로부터 핵섬적인 개념이나 기능을 간추려 내는 것
• 정보은닉법: 추상화에서 중요하지 않은 정보를 제거하는 것

추상 자료형이란?

• 추상 자료형(Abstract Data Type: ADT): 추상적으로 정의한 자료형
• 자료나 연산이 무엇인지는 정의하지만 어떻게 구현할 것인지는 정의하지 않음

ADT 1.1 Natural_Number(자연수에 대한 추상 자료형)
객체: 1에서 시작하여 INT_MAX까지의 순서화된 정수의 부분범위
연산:

• add(x,y): x+y가 INT_MAX보다 크면 INT_MAX를 반환하고 아니면 x+y를 반환한다.
• distance(x,y): x가 y보다 크면 x-y를 반환하고 작으면 y-x를 반환한다.
• equal(x,y): x와 y가 같은 값이면 TRUE를 반환하고 아니면 FALSE를 반환한다.
• successor(x): x가 INT_MAX보다 작으면 x+1을 반환한다.

• 추상 자료형은 먼저 객체를 정의한 후 연산들을 정의함
• 객체는 주로 집합의 개념을 사용하여 표현
• 연산의 정의에는 연산의 이름, 매개변수, 연산의 결과, 연산이 수행하는 기능 등을 기술
• 인터페이스: 구현에 관한 세부사항을 모르게하면서 외부에 제공하는 방법 –> 정보은닉의 기본 개념
• 구현으로부터 명세의 분리가 추상 자료형의 중심 아이디어

추상 자료형과 C++

• 추상 자료형의 개념은 객체지향의 개념과 정확히 일치함
• C++은 클래스를 사용하여 추상 자료형 구현
• 객체는 클래스의 속성(멤버 변수)으로 구현, 연산은 클래스의 메소드(멤버 함수)로 구현
• 클래스는 계층구조(상속)로 구성될 수 있음

1.4 알고리즘의 성능 분석

• 전체 실행 시간이 짧으면서 메모리가 적은게 효율이 좋은 알고리즘

실행 시간 측정 방법

• clock() 함수를 이용해 실행 시간을 측정
• clock() 함수의 반환형은 clock_t형

프로그램 1.2 실행 시간을 측정하는 프로그램의 예

#include <cstdio>  /* C 헤더파일 <stdio.h>을 포함하는 것과 동일 */
#include <cstdlib> /* C 헤더파일 <stdlib.h>을 포함하는 것과 동일 */
#include <ctime>   /* C 헤더파일 <time.h>을 포함하는 것과 동일 */
// ctime 헤더는 clock_t 구조체와 clock() 함수 등을 사용하기 위한 헤더파일

int main(void) {
  clock_t start, finish; // 시작 시간 및 종료 시간을 저장할 변수 선언
  double duration;       // 실행 시간을 저장할 변수 선언
  start = clock();       // 컴퓨터의 현재 시각을 start에 저장
  // 실행 시간을 측정하고자 하는 코드....
  // ....
  finish() = clock(); // 코드 실행 후의 현재 시각을 finish에 저장
  duration = (double)(finish - start) / CLOCKS_PER_SEC;
  /*
   *실행 시간(finish-start)을 CLOCKS_PER_SEC로 나누어
   * 초 단위의 실행 시간을 계산해 duration 변수에 저장,
   * 나눗셈 연산이 double 형으로 이루어지도록 피연산자를
   * (double)로 형 변환해야 하는 것에 유의할 것.
   */
  printf("%f초입니다.\n", duration);
  return 0;
}

• 위와 같은 방식은 구현해야 하고 여러 문제가 있어 안 씀

빅오, 빅오메가, 빅세타가 있는데 결론은 빅오 표기법 사용

정의 1.2 빅오 표기법
두 개의 함수 $f(n)$과 $g(n)$이 주어졌을 때 모든 $n>n_0$에 대해 $|f(n)|≤c|g(n)|$을 만족하는 상수 $c$와 $n_0$가 존재하면 $f(n)=O(g(n))$이다.

프로그램 1.3 순차 탐색

int sequentialSearch(int list[], int n, int key) {
  for (int i = 0; i < n; i++)
    if (list[i] == key)
      return i; // 탐색에 성공하면 키 값의 인덱스 반환
  return -1;    // 탐색에 실패하면 -1 반환
}

• 최선의 경우: $O(1)$
• 최악의 경우: $O(n)$
• 평균적인 경우: $O(\frac{n+1}{2})=O(n)$

–> 결론은 $O(n)$

1.5 자료구조 표기법

ADT = Class Diagram - C++

• 추상 자료형으로 자료구조에 필요한 데이터(객체)와 연산을 정의
• UML 다이어그램으로 필요한 클래ㅏ스들을 구체화하기
• C++ 클래스로 구현하기

UML Diagram
소프트웨어 개발에서 시스템의 구조와 상호 작용, 컴포넌트의 관계, 객체 간의 메시지 전달,
업무 흐름 등을 표현하는 통합된 객체지향개발 표준통합 모델링 언어

C++

표준 템플릿 라이브러리(STL)

• 간간히 소개할 것

연습문제

1. 선형 구조만으로 나열된 것은?

1번 답

배열, 스택, 큐

2. 자료 구조의 성격이 나머지 셋과 다른 하나는?

2번 답

그래프(Graph)

3. Set(집합) 추상 데이터 타입을 정의하라. 다음과 같은 연산자들을 포함시켜라.

Create, Insert, Remove, Is_In, Union, intersection, Difference

3번 답

객체: 원소들의 모임
연산:

• Create(): 집합 A를 생성한다.
• Insert(A, a): 집합 A에 원소 a를 저장한다.
• Remove(A, a): 집합 A에서 원소 a를 제거한다.
• Is_In(A, a): 집합 A에서 원소 a가 있는지 확인한다.
• Union(A, B): 집합 A와 집합 B의 합집합을 구한다.
• intersection(A, B): 집합 A와 B의 교집합을 구한다.
• Difference(A, B): 집합 A와 B의 차집합을 구한다.

4. 시간 복잡도 함수 $n^2+10n+8$를 빅오 표기법으로 나타내면?

4번 답

5. 다음의 빅오 표기법들을 수행 시간이 적게 걸리는 것 부터 나열하라.

5번 답

6. 다음 알고리즘의 시간 복잡도를 n에 대한 함수로 나타내고, 빅오 표기법으로 나타내라.

int algorithm(int n) {
  int k = 0;
  while(n > 1) {
    n = n/2;
    k++;
  }
  return k;
}

6번 답

7. 빅오 표기법의 정의를 사용하여 다음을 증명하라.

7번 답

정의 1.2 빅오 표기법
두 개의 함수 $f(n)$과 $g(n)$이 주어졌을 때 모든 $n>n_0$에 대해 $|f(n)|≤c|g(n)|$을 만족하는 상수 $c$와 $n_0$가 존재하면 $f(n)=O(g(n))$이다.

따라서 $n>10$일 때,
$|3n^2+10n+2|≤4|n^2|$을 만족하므로
$3n^2+10n+2=O(n^2)$이다.

8. sub 함수의 시간 복잡도가 $o(n)$일 때 다음 문장의 시간 복잡도는?

for(i = 0; i < n; i *= 2)
  sub();

8번 답

9. 배열에 정수가 들어 있다고 가정하고 다음 작업의 최악, 최선의 시간 복잡도를 빅오 표기법으로 말하라.

(1) 배열의 $n$번째 숫자를 화면에 출력한다.

(2) 배열안의 숫자 중에서 최솟값을 찾는다.

(3) 배열의 모든 숫자를 더한다.

9번 답

(1) 최악, 최선 둘 다 $O(1)$

(2) 최악: $O(1)$, 최선: $O(n)$

(3) 최악, 최선 둘 다 $O(n)$

프로그래밍 프로젝트

1. 1부터 n까지의 합을 구하는 방법은 다음과 같이 3가지가 있다.

• 알고리즘 A: $sum=\frac{n(n+1)}{2}$ 공식 사용
• 알고리즘 B: $sum=1+2+...+n$
• 알고리즘 C: $sum=0+(1)+(1+1)+(1+1+1)+...(1+1+...+1)$

(1) 각 알고리즘을 함수로 구현하라. $n$을 매개변수로 전달받고 결과를 반환한다.

예) int sumAlgorithmA (int n); // 알고리즘 A 구현 함수

(2) 비교적 작은 $n$에 대해 각 함수를 호출하여 세 알고리즘의 계산 결과가 동일함을 확인하라.

(3) 세 알고리즘의 시간 복잡도를 이론적으로 분석해보고 빅오 표기법으로 나타내라.

(4) 각 알고리즘의 실제 실행 시간을 측정하여 이론적인 분석과 같게 나오는지를 조사해보라. 실행 시간 측정을 위해 한 번의 루프에서 n은 2000 정도씩 증가시키고, 알고리즘 C의 실행 시간이 5초가 이하일 때까지 실행시킨 결과를 표로 만들고 다음과 같이 선 그래프로 그려라.

(5) 앞에서 알고리즘 A와 B의 시간 차이가 나타나지 않았을 것이다. 그 이유를 생각해보라. 이제 이 두 알고리즘만을 비교해보자. 한 번의 루프에서 n을 보다 더 크게 증가시켜 알고리즘 B가 1초 이하일 때까지 실행시킨 결과를 표로 만들고, 그래프로 그려라. 결과가 이론적인 분석과 같은지 조사해보라.

프로젝트 결과

pp1-1.cpp

// pp1-1.cpp
#include <cstdio>
#include <cstdlib>
#include <ctime>

int sumAlgorithmA(int n) { // 알고리즘 A의 합
  return n * (n + 1) / 2;
}

int sumAlgorithmB(int n) { // 알고리즘 B의 합
  int sum = 0;
  for (int i = 1; i <= n; i++)
    sum += i;
  return sum;
}

int sumAlgorithmC(int n) { // 알고리즘 C의 합
  int sum = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < i; j++)
      sum += 1;
  return sum;
}

int main(void) {
  // 프로그램 1.2 참조
  clock_t start, finish;
  int n;      // sum에서 n의 값
  int result; // 알고리즘 A, B, C의 결과 값을 받을 변수

  printf("n: ");
  scanf("%d", &n);

  start = clock();
  result = sumAlgorithmA(n);
  finish = clock();
  printf("알고리즘 A 결과: %d, 걸린 시간: %f\n", result,
         (double)(finish - start) / CLOCKS_PER_SEC);

  start = clock();
  result = sumAlgorithmB(n);
  finish = clock();
  printf("알고리즘 B 결과: %d, 걸린 시간: %f\n", result,
         (double)(finish - start) / CLOCKS_PER_SEC);

  start = clock();
  result = sumAlgorithmC(n);
  finish = clock();
  printf("알고리즘 C 결과: %d, 걸린 시간: %f\n", result,
         (double)(finish - start) / CLOCKS_PER_SEC);

  return 0;
}

pp1-1.cpp 실행 결과 –> (1), (2)번 해결

n: 1000
알고리즘 A 결과: 500500, 걸린 시간: 0.000000
알고리즘 B 결과: 500500, 걸린 시간: 0.000000
알고리즘 C 결과: 500500, 걸린 시간: 0.000000

(3) A, B, C 순서대로 $O(1), O(n), O(n^2)$

pp1-1-4.cpp –> (4) 해결

// pp1-1-4.cpp
#include <cstdio>
#include <cstdlib>
#include <ctime>

int sumAlgorithmA(int n) { // 알고리즘 A의 합
  return n * (n + 1) / 2;
}

int sumAlgorithmB(int n) { // 알고리즘 B의 합
  int sum = 0;
  for (int i = 1; i <= n; i++)
    sum += i;
  return sum;
}

int sumAlgorithmC(int n) { // 알고리즘 C의 합
  int sum = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < i; j++)
      sum += 1;
  return sum;
}

int main(void) {
  // 프로그램 1.2 참조
  clock_t start, finish;
  int n = 0;  // sum에서 n의 값
  int result; // 알고리즘 A, B, C의 결과 값을 받을 변수

  while (1) {
    start = clock();
    result = sumAlgorithmA(n);
    finish = clock();
    printf("n = %d, 알고리즘 A 결과: %d, 걸린 시간: %f\n", n, result,
           (double)(finish - start) / CLOCKS_PER_SEC);

    start = clock();
    result = sumAlgorithmB(n);
    finish = clock();
    printf("n = %d, 알고리즘 B 결과: %d, 걸린 시간: %f\n", n, result,
           (double)(finish - start) / CLOCKS_PER_SEC);

    start = clock();
    result = sumAlgorithmC(n);
    finish = clock();
    printf("n = %d, 알고리즘 C 결과: %d, 걸린 시간: %f\n", n, result,
           (double)(finish - start) / CLOCKS_PER_SEC);
    n += 2000;
  }
  return 0;
}

pp1-1-4.cpp 실행결과(C가 5초이상 될 때 중지했음), 표, 그래프는 생략함

n = 0, 알고리즘 A 결과: 0, 걸린 시간: 0.000000
n = 0, 알고리즘 B 결과: 0, 걸린 시간: 0.000000
n = 0, 알고리즘 C 결과: 0, 걸린 시간: 0.000000
n = 2000, 알고리즘 A 결과: 2001000, 걸린 시간: 0.000000
n = 2000, 알고리즘 B 결과: 2001000, 걸린 시간: 0.000000
n = 2000, 알고리즘 C 결과: 2001000, 걸린 시간: 0.015625
n = 4000, 알고리즘 A 결과: 8002000, 걸린 시간: 0.000000
n = 4000, 알고리즘 B 결과: 8002000, 걸린 시간: 0.000000
n = 4000, 알고리즘 C 결과: 8002000, 걸린 시간: 0.000000
n = 6000, 알고리즘 A 결과: 18003000, 걸린 시간: 0.000000
n = 6000, 알고리즘 B 결과: 18003000, 걸린 시간: 0.000000
n = 6000, 알고리즘 C 결과: 18003000, 걸린 시간: 0.031250
n = 8000, 알고리즘 A 결과: 32004000, 걸린 시간: 0.000000
n = 8000, 알고리즘 B 결과: 32004000, 걸린 시간: 0.000000
n = 8000, 알고리즘 C 결과: 32004000, 걸린 시간: 0.046875
n = 10000, 알고리즘 A 결과: 50005000, 걸린 시간: 0.000000
n = 10000, 알고리즘 B 결과: 50005000, 걸린 시간: 0.000000
n = 10000, 알고리즘 C 결과: 50005000, 걸린 시간: 0.078125
n = 12000, 알고리즘 A 결과: 72006000, 걸린 시간: 0.000000
n = 12000, 알고리즘 B 결과: 72006000, 걸린 시간: 0.000000
n = 12000, 알고리즘 C 결과: 72006000, 걸린 시간: 0.109375
n = 14000, 알고리즘 A 결과: 98007000, 걸린 시간: 0.000000
n = 14000, 알고리즘 B 결과: 98007000, 걸린 시간: 0.000000
n = 14000, 알고리즘 C 결과: 98007000, 걸린 시간: 0.140625
n = 16000, 알고리즘 A 결과: 128008000, 걸린 시간: 0.000000
n = 16000, 알고리즘 B 결과: 128008000, 걸린 시간: 0.000000
n = 16000, 알고리즘 C 결과: 128008000, 걸린 시간: 0.187500
n = 18000, 알고리즘 A 결과: 162009000, 걸린 시간: 0.000000
n = 18000, 알고리즘 B 결과: 162009000, 걸린 시간: 0.000000
n = 18000, 알고리즘 C 결과: 162009000, 걸린 시간: 0.234375
n = 20000, 알고리즘 A 결과: 200010000, 걸린 시간: 0.000000
n = 20000, 알고리즘 B 결과: 200010000, 걸린 시간: 0.000000
n = 20000, 알고리즘 C 결과: 200010000, 걸린 시간: 0.281250
n = 22000, 알고리즘 A 결과: 242011000, 걸린 시간: 0.000000
n = 22000, 알고리즘 B 결과: 242011000, 걸린 시간: 0.015625
n = 22000, 알고리즘 C 결과: 242011000, 걸린 시간: 0.343750
n = 24000, 알고리즘 A 결과: 288012000, 걸린 시간: 0.000000
n = 24000, 알고리즘 B 결과: 288012000, 걸린 시간: 0.000000
n = 24000, 알고리즘 C 결과: 288012000, 걸린 시간: 0.421875
n = 26000, 알고리즘 A 결과: 338013000, 걸린 시간: 0.000000
n = 26000, 알고리즘 B 결과: 338013000, 걸린 시간: 0.000000
n = 26000, 알고리즘 C 결과: 338013000, 걸린 시간: 0.500000
n = 28000, 알고리즘 A 결과: 392014000, 걸린 시간: 0.000000
n = 28000, 알고리즘 B 결과: 392014000, 걸린 시간: 0.000000
n = 28000, 알고리즘 C 결과: 392014000, 걸린 시간: 0.562500

pp1-1-5.cpp –> (5) 해결

#include <cstdio>
#include <cstdlib>
#include <ctime>

long long sumAlgorithmA(long long n) { // 알고리즘 A의 합
  return n * (n + 1) / 2;
}

long long sumAlgorithmB(long long n) { // 알고리즘 B의 합
  long long sum = 0;
  for (long long i = 1; i <= n; i++)
    sum += i;
  return sum;
}

int main(void) {
  // 프로그램 1.2 참조
  clock_t start, finish;
  long long n = 0;  // sum에서 n의 값
  long long result; // 알고리즘 A, B, C의 결과 값을 받을 변수

  while (1) {
    start = clock();
    result = sumAlgorithmA(n);
    finish = clock();
    printf("n = %lld, 알고리즘 A 결과: %lld, 걸린 시간: %f\n", n, result,
           (double)(finish - start) / CLOCKS_PER_SEC);

    start = clock();
    result = sumAlgorithmB(n);
    finish = clock();
    printf("n = %lld, 알고리즘 B 결과: %lld, 걸린 시간: %f\n", n, result,
           (double)(finish - start) / CLOCKS_PER_SEC);
    n += 20000000;
  }
  return 0;
}

pp1-1-5.cpp 실행 결과(역시나 표, 그래프는 생략함)

n = 0, 알고리즘 A 결과: 0, 걸린 시간: 0.000000
n = 0, 알고리즘 B 결과: 0, 걸린 시간: 0.000000
n = 20000000, 알고리즘 A 결과: 200000010000000, 걸린 시간: 0.000000
n = 20000000, 알고리즘 B 결과: 200000010000000, 걸린 시간: 0.046875
n = 40000000, 알고리즘 A 결과: 800000020000000, 걸린 시간: 0.000000
n = 40000000, 알고리즘 B 결과: 800000020000000, 걸린 시간: 0.109375
n = 60000000, 알고리즘 A 결과: 1800000030000000, 걸린 시간: 0.000000
n = 60000000, 알고리즘 B 결과: 1800000030000000, 걸린 시간: 0.156250
n = 80000000, 알고리즘 A 결과: 3200000040000000, 걸린 시간: 0.000000
n = 80000000, 알고리즘 B 결과: 3200000040000000, 걸린 시간: 0.218750
n = 100000000, 알고리즘 A 결과: 5000000050000000, 걸린 시간: 0.000000
n = 100000000, 알고리즘 B 결과: 5000000050000000, 걸린 시간: 0.250000
n = 120000000, 알고리즘 A 결과: 7200000060000000, 걸린 시간: 0.000000
n = 120000000, 알고리즘 B 결과: 7200000060000000, 걸린 시간: 0.312500
n = 140000000, 알고리즘 A 결과: 9800000070000000, 걸린 시간: 0.000000
n = 140000000, 알고리즘 B 결과: 9800000070000000, 걸린 시간: 0.359375
n = 160000000, 알고리즘 A 결과: 12800000080000000, 걸린 시간: 0.000000
n = 160000000, 알고리즘 B 결과: 12800000080000000, 걸린 시간: 0.421875
n = 180000000, 알고리즘 A 결과: 16200000090000000, 걸린 시간: 0.000000
n = 180000000, 알고리즘 B 결과: 16200000090000000, 걸린 시간: 0.468750
n = 200000000, 알고리즘 A 결과: 20000000100000000, 걸린 시간: 0.000000
n = 200000000, 알고리즘 B 결과: 20000000100000000, 걸린 시간: 0.562500
n = 220000000, 알고리즘 A 결과: 24200000110000000, 걸린 시간: 0.000000
n = 220000000, 알고리즘 B 결과: 24200000110000000, 걸린 시간: 0.578125
n = 240000000, 알고리즘 A 결과: 28800000120000000, 걸린 시간: 0.000000
n = 240000000, 알고리즘 B 결과: 28800000120000000, 걸린 시간: 0.625000
n = 260000000, 알고리즘 A 결과: 33800000130000000, 걸린 시간: 0.000000
n = 260000000, 알고리즘 B 결과: 33800000130000000, 걸린 시간: 0.703125
n = 280000000, 알고리즘 A 결과: 39200000140000000, 걸린 시간: 0.000000
n = 280000000, 알고리즘 B 결과: 39200000140000000, 걸린 시간: 0.750000
n = 300000000, 알고리즘 A 결과: 45000000150000000, 걸린 시간: 0.000000
n = 300000000, 알고리즘 B 결과: 45000000150000000, 걸린 시간: 0.781250
n = 320000000, 알고리즘 A 결과: 51200000160000000, 걸린 시간: 0.000000
n = 320000000, 알고리즘 B 결과: 51200000160000000, 걸린 시간: 0.843750
n = 340000000, 알고리즘 A 결과: 57800000170000000, 걸린 시간: 0.000000
n = 340000000, 알고리즘 B 결과: 57800000170000000, 걸린 시간: 0.937500
n = 360000000, 알고리즘 A 결과: 64800000180000000, 걸린 시간: 0.000000
n = 360000000, 알고리즘 B 결과: 64800000180000000, 걸린 시간: 0.937500
n = 380000000, 알고리즘 A 결과: 72200000190000000, 걸린 시간: 0.000000
n = 380000000, 알고리즘 B 결과: 72200000190000000, 걸린 시간: 0.968750

• (4)에서 알고리즘 A와 B의 시간 차이가 나지 않았던 이유는 n이 너무 작았기 때문
• int를 long long 타입으로 바꾸고 n을 2000이 아니라 20000000씩 증가하게 함
• 실행결과 알고리즘 A와 달리 B는 시간이 늘어나는 것을 알 수 있음
• 따라서 결과가 이론적인 분석과 같다는 것을 알 수 있음