알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 1 2018년 봄학기 강원대학교 컴퓨터과학전공 문양세

프로그램과 알고리즘 순차검색과 이진검색 피보나찌 수 구하기 알고리즘 분석 차수 (O, , ) – Part 2 강의 내용

프로그램의 설계 과정 알고리즘은 주어진 문제를 논리적으로 해결하는 과정이다. 알고리즘: 효율, 분석, 차수 – Part 1 만족? 프로그램 문제 알고리즘 설계 분석 예 아니오 재설계 알고리즘은 주어진 문제를 논리적으로 해결하는 과정이다. 분석을 통해 작성한 알고리즘의 정확성을 파악할 수 있고, 효율성을 정량적으로 나타낼 수 있다. (일반적으로) 알고리즘은 프로그래밍 언어에 독립적이다.

알고리즘 과목의 학습 목표 Design(설계): 다양한 문제에 대해, 알고리즘을 설계하는 기법을 배운다. 알고리즘: 효율, 분석, 차수 – Part 1 Design(설계): 다양한 문제에 대해, 알고리즘을 설계하는 기법을 배운다. Analysis(분석): 알고리즘을 분석하여 시간/공간 복잡도를 구하는 방법을 배운다. Computational Complexity(계산 복잡도): 문제를 분석하여 계산 복잡도를 구하는 방법을 배운다.

설계(알고리즘)가 없다면 … 알고리즘: 효율, 분석, 차수 – Part 1

알고리즘이란? 정의: 문제에 대한 답(해결책)을 찾기 위해서 계산하는 절차이다. 좀 더 구체적인 정의 알고리즘: 효율, 분석, 차수 – Part 1 정의: 문제에 대한 답(해결책)을 찾기 위해서 계산하는 절차이다. 좀 더 구체적인 정의 알고리즘은 단계별로 주의 깊게 설계된 계산 과정이다. 알고리즘은 입력을 받아서 출력으로 전환시켜주는 일련의 계산 절차이다. 음…. 결국, 알고리즘이라는 것은 어떤 절차를 기술하는 것이다. 또 한번 음… 주어진 입력이 있을 때, 원하는 해답을 출력하기 위해서, 어떻게 계산하면 되는지 그 절차를 기술하는 것이다.

알고리즘의 예 주어진 문제: 전화번호부에서 “홍길동”의 전화번호 찾기 알고리즘(해결책) 분석: 어떤 알고리즘이 더 좋은가? 알고리즘: 효율, 분석, 차수 – Part 1 주어진 문제: 전화번호부에서 “홍길동”의 전화번호 찾기 알고리즘(해결책) 순차검색(sequential search): 전화번호부의 첫 쪽부터 홍길동이라는 이름이 나올 때까지 순서대로 찾는다. (수정된) 이진검색(binary search): 전환번호부는 “가나다”순으로 되어있으므로 먼저 “ㅎ”이 있을 만한 곳으로 넘겨본 후 앞뒤로 뒤적여가며 찾는다. 분석: 어떤 알고리즘이 더 좋은가?

문제(Problem)의 표기/표현 방법 문제: 해결책을 찾고자 던지는 질문 알고리즘: 효율, 분석, 차수 – Part 1 문제: 해결책을 찾고자 던지는 질문 매개변수(파라미터, parameter): 문제에서 어떤 특정 값이 주어지지 않은 변수(variable) 문제의 사례(instance) = 입력(input): 문제에 주어진 파라미터에 특정 값을 지정한 것(예) 사례에 대한 해답(solution) = 출력(output): 주어진 사례에 관한 질문에 대한 답

문제의 표기 예 알고리즘: 효율, 분석, 차수 – Part 1 문제: n개의 수로 된 리스트 S에 x라는 수가 있는지 알아내시오. 그 결과, x가 S에 있으면 “예”, 없으면 “아니오”로 답하시오. 파라미터: S, n, x 입력의 예1: S = [10,7,11,5,3,8], n = 6, x = 5 출력의 예1: “예” 입력의 예2: S = [10,7,11], n = 3, x = 5 출력의 예2: “아니오”

알고리즘의 표기(기술) 자연어: 한글 또는 영어 ( 부정확하고 모호함) 알고리즘: 효율, 분석, 차수 – Part 1 자연어: 한글 또는 영어 ( 부정확하고 모호함) 프로그래밍언어: C, C++, Java, Pascal 등 ( 특정 언어에 의존적이어서 일반적인 알고리즘 기술에 부적합) 의사코드(Pseudo-code): 직접 실행할 수 있는 프로그래밍언어는 아니지만, 실제 프로그램에 거의 가깝게 계산과정을 표현할 수 있는 언어 알고리즘은 보통 의사코드로 표현한다. 본 강의에서는 C++(혹은 C)에 가까운 의사코드를 사용한다.

프로그래밍 언어 vs 알고리즘/자료구조 알고리즘: 효율, 분석, 차수 – Part 1

C/C++와 의사코드의 차이점 (1/3) 배열 인덱스의 범위에 제한 없음 프로시저의 파라미터에 2차원 배열 크기의 가변성 허용 알고리즘: 효율, 분석, 차수 – Part 1 배열 인덱스의 범위에 제한 없음 C/C++는 반드시 0부터 시작 의사코드는 임의의 값 사용 가능 (예: int x[5..10];) 프로시저의 파라미터에 2차원 배열 크기의 가변성 허용 예: void pname(A[][]) { … } C/C++에서는 다음과 같이 제한이 필요함: void pname(A[][10]){ … } 지역배열에 변수 인덱스 허용 예: keytype S[low..high]; C/C++에서는 숫자 인덱스만 가능함

C/C++과 의사코드의 차이점 (2/3) 수학 표현식 및 간단한 자연어 허용 C/C++에 없는 타입 사용 가능 알고리즘: 효율, 분석, 차수 – Part 1 수학 표현식 및 간단한 자연어 허용 low <= x && x <= high  low  x  high temp = x; x = y; y = temp;  exchange x and y; C/C++에 없는 타입 사용 가능 index: 첨자로 사용되는 정수 변수 number: 정수(int) 또는 실수(float) 모두 사용가능 bool: “true”나 “false” 값을 가질 수 있는 변수 이외에도 잘 알려진 키워드(예: record, list)는 별도 정의 없이 사용

C/C++과 의사코드의 차이점 (3/3) 제어 구조 프로시저와 함수의 구분 알고리즘: 효율, 분석, 차수 – Part 1 제어 구조 repeat (n times) { … } 프로시저와 함수의 구분 프로시저: void pname(…) {…} 함수: returntype fname (…) {… return x;} 참조 파라미터(reference parameter)를 사용하여 프로시저의 결과값 전달 방법 (call by reference를 설명하고 있음) 배열: (기본적으로) 참조 파라미터로 전달 나머지: 데이터 타입 이름 뒤에 &를 붙임 const 배열: 전달되는 배열의 값이 불변

프로그램과 알고리즘 순차검색과 이진검색 피보나찌 수 구하기 알고리즘 분석 차수 (O, , ) – Part 2 강의 내용

순차검색 (Sequential Search) (1/3) 알고리즘: 효율, 분석, 차수 – Part 1 문제: 크기가 n인 배열 S에 x가 있는가? 입력(파라미터): (1) 양수 n, (2) 배열 S[1..n], (3) 키 x 출력: x가 S의 어디에 있는지의 위치, 만약 없으면 0 알고리즘(자연어): x와 같은 아이템을 찾을 때까지 S에 있는 모든 아이템을 차례로 검사한다. 만일 x 와 같은 아이템을 찾으면 S에서 해당 위치를 출력하고, S 를 모두 검사하고도 찾지 못하면 0을 출력한다.  자연어 알고리즘은 문제를 풀기는 하였으나, 프로그램으로 전환하기에는 용이하지 않다.

순차검색 (Sequential Search) (2/3) 알고리즘: 효율, 분석, 차수 – Part 1 알고리즘(의사코드) void seqsearch(int n, // 입력(1) const keytype S[], // 입력(2) keytype x, // 입력(3) index& location) // 출력 { location = 1; while (location <= n && S[location] != x) location++; if (location > n) location = 0; } while-루프: 아직 검사할 항목이 있고, x를 찾지 못하였나? if-문: 모두 검사하였으나, x를 찾지 못했나? 돌아가기

순차검색 (Sequential Search) (3/3) 알고리즘: 효율, 분석, 차수 – Part 1 순차검색 알고리즘으로 키를 찾기 위해서 S에 있는 항목을 몇 개나 검색해야 하는가? 키와 같은 항목의 위치에 따라 다름 최악의 경우: n 평균의 경우: n/2 좀 더 빨리 찾을 수는 없는가? 더 이상 빨리 찾을 수 있는 알고리즘은 존재하지 않는다. 배열 S에 있는 항목에 대한 정보가 전혀 없는 상황에서, 모든 항목을 검색하지 않고 임의의 항목 x를 항상 찾을 수 있다는 보장이 없기 때문이다. 만약, 배열 S가 정렬되어 있다는 정보가 존재한다면?  이진검색

순차검색 -- C Program 실제 C 프로그램을 봅시다. (seqsrh.c) 알고리즘과는 어떤 차이가 있는지 확인합시다. 알고리즘: 효율, 분석, 차수 – Part 1 실제 C 프로그램을 봅시다. (seqsrh.c) 알고리즘과는 어떤 차이가 있는지 확인합시다.

이진검색 (Binary Search) (1/3) 알고리즘: 효율, 분석, 차수 – Part 1 문제: 크기가 n인 정렬된 배열 S에 x가 있는가? 입력: (1) 양수 n, (2) 배열 S[1..n], (3) 키 x 출력: x가 S의 어디에 있는지의 위치, 만약 없으면, 0 순차검색의 문제와 다른 점은 배열 S가 “정렬”되어 있다는 정보를 알고 있다는 점이다. 순차검색의 문제가 보다 일반적이므로, 순차검색을 사용하여 이 문제를 풀 수 있다. 그러나, 순차검색을 사용하면 “정렬”되어 있다는 정보를 사용하지 못하는 것이 된다.

이진검색 (Binary Search) (2/3) 알고리즘: 효율, 분석, 차수 – Part 1 알고리즘(의사코드) void binsearch(int n, // 입력(1) const keytype S[], // 입력(2) keytype x, // 입력(3) index& location) // 출력 { index low, high, mid; low = 1; high = n; location = 0; while (low <= high && location == 0) { mid = (low + high) / 2; // 정수나눗셈 if (x == S[mid]) location = mid; else if (x < S[mid]) high = mid – 1; else low = mid + 1; } while-루프: 아직 검사할 항목이 있고, x를 찾지 못하였나?

이진검색 (Binary Search) (3/3) 알고리즘: 효율, 분석, 차수 – Part 1 비교 횟수를 (개략적으로) 분석해 본다. 배열의 크기가 32라면  6번의 비교가 필요하다. 이때, 6 = lg 32 + 1이다. 배열의 크기가 64라면  7번의 비교가 필요하다. 이때, 7 = lg 64 + 1이다. 배열의 크기가 2k라면  k+1번의 비교가 필요하다. 이때, k+1 = lg 2k + 1이다. … 이진검색 알고리즘으로 키를 찾기 위해서 S에 있는 항목을 몇 개나 검색해야 하는가? while 문을 수행할 때마다 검색 대상의 크기가 절반으로 감소하기 때문에 최악의 경우라도 lg n + 1번만 비교하면 된다. 상기 횟수 분석에서 n = 2k라 하면, 비교 횟수는 lg n + 1이 된다.

순차검색 vs. 이진검색 배열의 크기 순차검색 이진검색 비고 n lg n + 1 128 8 1,024 11 1,048,576 알고리즘: 효율, 분석, 차수 – Part 1 배열의 크기 순차검색 이진검색 비고 n lg n + 1 두 방법 모두 최악의 경우에 대한 비교 횟수임 128 8 1,024 11 1,048,576 21 4,294,967,296 33

프로그램과 알고리즘 순차검색과 이진검색 피보나찌 수 구하기 알고리즘 분석 차수 (O, , ) – Part 2 강의 내용

피보나찌(Fibonacci) 수열 피보나찌 수열의 정의 알고리즘: 효율, 분석, 차수 – Part 1 피보나찌 수열의 정의 예: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …

자연계의 피보나찌 수열 알고리즘: 효율, 분석, 차수 – Part 1

피보나찌 수 구하기 – 재귀 알고리즘 (1/4) 문제: n번째 피보나찌 수를 구하라. 입력: 양수 n 알고리즘: 효율, 분석, 차수 – Part 1 문제: n번째 피보나찌 수를 구하라. 입력: 양수 n 출력: n 번째 피보나찌 수 재귀(recursive) 알고리즘: int fib(int n) { if (n <= 1) return n; else return (fib(n-1) + fib(n-2)); }

피보나찌 수 구하기 – 재귀 알고리즘 (2/4) 분석: 피보나찌 수 구하기 재귀 알고리즘은 수행속도가 매우 느리다. 알고리즘: 효율, 분석, 차수 – Part 1 분석: 피보나찌 수 구하기 재귀 알고리즘은 수행속도가 매우 느리다. 이유: 같은 피보나찌 수를 중복하여 계산한다. 예: fib(5) 계산을 위해서는 fib(2)를 세 번이나 중복 계산한다. 함수 fib(5) 호출 시의 재귀 트리 (recursive tree) 실제 호출되는 상황을 봅시다!

피보나찌 수 구하기 – 재귀 알고리즘 (3/4) fib(n) 함수 호출 횟수 계산 알고리즘: 효율, 분석, 차수 – Part 1 fib(n) 함수 호출 횟수 계산 T(n) = fib(n)을 계산하기 위하여 fib() 함수를 호출하는 횟수 즉, T(n)은 재귀 트리 상의 마디의 개수

피보나찌 수 구하기 – 재귀 알고리즘 (4/4) 알고리즘: 효율, 분석, 차수 – Part 1 정리: 재귀적 알고리즘으로 구성한 재귀 트리의 노드의 수를 T(n)이라 하면, n  2인 모든 n에 대하여 T(n) > 2n/2이다. 증명: (n에 대한 수학적 귀납법으로 증명) Induction base: T(2) = T(1) + T(0) + 1 = 3 > 2 = 22/2 T(3) = T(2) + T(1) + 1 = 5 > 2.83  23/2 Induction hypothesis: 2  m < n인 모든 m 에 대해서 T(m) > 2m/2 이라 가정 Induction step: T(n) > 2n/2임을 보인다. T(n) = T(n - 1) + T(n - 2) + 1 > 2(n - 1)/2 + 2(n - 2)/2 + 1 [귀납가정에 의하여] > 2(n - 2)/2 + 2(n - 2)/2 = 2  2(n / 2)-1 = 2 n/2

피보나찌 수 구하기 – 반복 알고리즘 (1/2) 문제: n번째 피보나찌 수를 구하라. 입력: 양수 n 알고리즘: 효율, 분석, 차수 – Part 1 문제: n번째 피보나찌 수를 구하라. 입력: 양수 n 출력: n 번째 피보나찌 수 반복(iterative) 알고리즘: int fib2 (int n) { index i; int f[0..n]; f[0] = 0; if (n > 0) { f[1] = 1; for (i = 2; i <= n; i++) f[i] = f[i-1] + f[i-2]; } return f[n];

피보나찌 수 구하기 – 반복 알고리즘 (2/2) 분석: 반복 알고리즘은 수행속도가 훨씬 더 빠르다. 알고리즘: 효율, 분석, 차수 – Part 1 분석: 반복 알고리즘은 수행속도가 훨씬 더 빠르다. 이유: 재귀 알고리즘과는 달리 중복 계산이 없다. 계산하는 항(f[i])의 총 개수 T(n) = n + 1 즉, f[0]부터 f[n]까지 단 한번씩만 계산한다.

피보나찌 수 구하기 – 재귀 vs. 반복 (1/2) 노드 하나(혹은 항 하나) 계산에 1 ns 걸린다고 가정하자. n n+1 알고리즘: 효율, 분석, 차수 – Part 1 노드 하나(혹은 항 하나) 계산에 1 ns 걸린다고 가정하자. n n+1 2n/2 반복 재귀(하한) 40 41 1,048,576 41ns 1048s 60 61 1.1109 61ns 1s 80 81 1.11012 81ns 18min 100 101 1.11015 101ns 13days 120 121 1.21018 121ns 36years 160 161 1.21024 161ns 3.8 107years 200 201 1.31030 201ns 4 1013years

피보나찌 수 구하기 – 재귀 vs. 반복 (2/2) 알고리즘: 효율, 분석, 차수 – Part 1 재귀 알고리즘 보다는 반복 알고리즘이 항상 효율적이다?  꼭 그렇지만은 않다.  특히, 설계 단계에서 재귀 알고리즘은 매우 유용하다. 피보나찌 수 구하기의 재귀 알고리즘은 강의노트 05에서 다루는 분할정복(Divide & Conquer)의 전형적인 예이다. 피보나찌 수 구하기의 반복 알고리즘은 강의노트 06에서 다루는 동적 프로그래밍(Dynamic Programming)의 간단한 보기이다.

프로그램과 알고리즘 순차검색과 이진검색 피보나찌 수 구하기 알고리즘 분석 차수 (O, , ) – Part 2 강의 내용

알고리즘의 분석(analysis) 시간복잡도(Time Complexity) 분석 표현 척도 알고리즘: 효율, 분석, 차수 – Part 1 시간복잡도(Time Complexity) 분석 입력 크기에 따라서 단위 연산이 몇 번 수행되는지 결정하는 절차 표현 척도 단위연산(basic operation): 비교문(comparison), 지정문(assignment) 등 입력크기(input size): 배열의 크기, 리스트의 길이, 행렬에서 행과 열의 크기, 트리에서 꼭지점과 에지의 수

분석 방법의 종류 (1/2) 모든 경우 분석(Every-case analysis) 알고리즘: 효율, 분석, 차수 – Part 1 모든 경우 분석(Every-case analysis) 복잡도는 입력 크기에만 종속(dependent)적임 입력 값과는 무관(independent)하게 복잡도는 항상 일정 예: 평균을 구하라. 최악의 경우 분석(Worst-case analysis) 복잡도는 입력 크기와 입력 값 모두에 종속 단위연산이 수행되는 횟수가 최대(최악)인 경우 선택

분석 방법의 종류 (2/2) 평균의 경우 분석(Average-case analysis) 알고리즘: 효율, 분석, 차수 – Part 1 평균의 경우 분석(Average-case analysis) 입력 크기와 입력 값 모두에 종속 모든 입력에 대해서 단위연산이 수행되는 기대치(평균) 각 입력 값에 대해서 확률 할당이 가능  확률에 따라 기대치가 다르게 계산될 수 있음 일반적으로 최악의 경우보다 계산이 복잡 최선의 경우 분석(Best-case analysis) 단위 연산이 수행되는 횟수가 최소(최선)인 경우 선택

배열 덧셈 알고리즘 문제: 크기가 n인 배열 S의 모든 수를 더하라. 입력: 양수 n, 배열 S[1..n] 알고리즘: 효율, 분석, 차수 – Part 1 문제: 크기가 n인 배열 S의 모든 수를 더하라. 입력: 양수 n, 배열 S[1..n] 출력: 배열 S에 있는 모든 수의 합 알고리즘: number sum (int n, const number S[]) { index i; number result; result = 0; for (i = 1; i <= n; i++) result = result + S[i]; return result; }

배열 덧셈 알고리즘: 시간 복잡도 분석 단위연산: 덧셈 입력크기: 배열의 크기 n 모든 경우 분석: 알고리즘: 효율, 분석, 차수 – Part 1 단위연산: 덧셈 입력크기: 배열의 크기 n 모든 경우 분석: 배열 내용에 상관없이 for-루프가 n번 반복된다. 각 루프마다 덧셈이 1회 수행된다. 따라서, n에 대해서 덧셈이 수행되는 총 횟수는 T(n) = n 이다. 단위연산: 지정문 (for-루프의 첨자 지정문 포함) 입력크기: 배열의 크기 n 모든 경우 분석: 배열 내용에 상관없이 for-루프가 n번 반복된다. 따라서, 지정문이 T(n) = n + n + 1번 수행된다. 기본 동작을 다르게 함으로써, 시간 복잡도가 다르게 나왔다.  그러나, 사실 둘 모두는 같은 복잡도 카테고리에 속한다.

버블 정렬(Bubble Sort) 알고리즘 알고리즘: 효율, 분석, 차수 – Part 1 문제: 비내림차순으로 n개의 키를 정렬 입력: 양수 n, 배열 S[1..n] 출력: 비내림차순으로 정렬된 배열 알고리즘: void bubblesort (int n, keytype S[]) { index i, j; for (i = 1; i <= n-1; i++) for(j = 1;j <= (n-i); j++) if (S[j] > S[j+1]) exchange S[j] and S[j+1]; }

버블 정렬 알고리즘: 시간 복잡도 분석 I 단위연산: 조건문 (S[j]와 S[i]의 비교) 입력크기: 정렬할 항목의 수 n 알고리즘: 효율, 분석, 차수 – Part 1 단위연산: 조건문 (S[j]와 S[i]의 비교) 입력크기: 정렬할 항목의 수 n 모든 경우 분석: j-루프가 수행될 때마다 조건문을 1번씩 수행 조건문의 총 수행횟수 i = 1 : j-루프 n – 1 번 수행 i = 2 : j-루프 n – 2 번 수행 i = 3 : j-루프 n – 3 번 수행 i = n – 1 : j-루프 1 번 수행 따라서

버블 정렬 알고리즘: 시간 복잡도 분석 II 단위연산: 교환하는 연산 (exchange S[j] and S[j+1]) 알고리즘: 효율, 분석, 차수 – Part 1 단위연산: 교환하는 연산 (exchange S[j] and S[j+1]) 입력크기: 정렬할 항목의 수 n 최악의 경우 분석: 조건문의 결과에 따라서 교환 연산의 수행여부가 결정된다. 최악의 경우 = 조건문이 항상 참(true)이 되는 경우 = 입력 배열이 거꾸로 정렬되어 있는 경우

순차 검색 알고리즘: 시간 복잡도 분석(1/4) 알고리즘: 효율, 분석, 차수 – Part 1 단위연산: 배열의 아이템과 키 x와 비교 연산 (S[location] != x) 입력크기: 배열 안에 있는 아이템의 수 n 최악의 경우 분석: x가 배열의 마지막 아이템이거나, x가 배열에 없는 경우, 단위 연산이 n번 수행된다. 따라서, 순차검색 알고리즘의 경우 입력배열의 값에 따라서 검색하는 횟수가 달라지므로, 모든 경우(every-case)의 시간 복잡도 분석은 불가능하다. 순차 검색 알고리즘 보기

순차 검색 알고리즘: 시간 복잡도 분석(2/4) 알고리즘: 효율, 분석, 차수 – Part 1 단위연산: 배열의 아이템과 키 x와 비교 연산 (S[location] != x) 입력크기: 배열 안에 있는 아이템의 수 n 가정: 배열의 아이템이 모두 다르다. 평균의 경우 분석(경우 1): x가 배열 S안에 있는 경우만 고려 에 대해서 x가 배열의 k번째 있을 확률 = 1/n x가 배열의 k번째 있다면, x를 찾기 위해서 수행하는 단위연산의 횟수 = k 따라서,

순차 검색 알고리즘: 시간 복잡도 분석(3/4) 평균의 경우 분석(경우 2): x가 배열 S안에 없는 경우도 고려 알고리즘: 효율, 분석, 차수 – Part 1 평균의 경우 분석(경우 2): x가 배열 S안에 없는 경우도 고려 x가 배열 S안에 있을 확률을 p라고 하면, x가 배열에 있을 확률 = p (x가 배열의 k번째 있을 확률 = p/n) x가 배열에 없을 확률 = 1 – p 따라서, 참고:

순차 검색 알고리즘: 시간 복잡도 분석(4/4) 알고리즘: 효율, 분석, 차수 – Part 1 단위연산: 배열의 아이템과 키 x와 비교 연산 (S[location] != x) 입력크기: 배열 안에 있는 아이템의 수 n 최선의 경우 분석: x가 S[1]일 때, 입력의 크기에 상관없이 단위연산이 1번만 수행된다. 따라서, B(n) = 1

계산(시간) 복잡도: 어떤 것을 사용하지? 알고리즘: 효율, 분석, 차수 – Part 1 최악, 평균, 최선의 경우 분석 방법 중에서 어떤 분석이 가장 정확한가? ( 분석 자체야 모두 정확해야 한다.) 최악, 평균, 최선의 경우 분석 방법 중에서 어떤 분석을 사용할 것인가? ( 응용에 따라 다르나, 대개 최악/평균을 사용한다.)

Homework #1 알고리즘: 효율, 분석, 차수 – Part 1