자연수 N의 약수를 구할 때, 1부터 N/2 까지 점검하면 N 자신을 제외하는 모든 약수 구할 수 있음 -> 내부 반복 구문 사용 내부 반복 구문을 위해 인덱스 변수 J 사용 -> J는 1부터 INT(N/2)까지 변함
2차시 최대공약수(호제법)와 근사값 알고리즘
최대공약수(호제법)
최대공약수 : Greatest Common Divider(GCD)
최소공배수 : Least Common Multiplier(LCM)
유클리드 호제법
X, Y를 입력받고 최대공약수를 출력하는 알고리즘(반복문 이용)
X가 Y보다 작은 경우 TEMP 변수를 이용해 값을 서로 바꿔준다 X에서 Y로 나눠준 나머지 M이 0인 경우 Y(최대공약수)를 출력하고, 나머지가 0이 아닌 경우에는 X와 Y를 각각 Y와 M으로 바꾸어 새로 설정해줍니다. 그리고 나서 다시 MOD함수를 이용해 나머지 M이 0이 될때까지 반복합니다.
최대공약수로 최대공배수를 구하려면?
X와 Y의 최소공배수는 X와 Y의 곱을 X와 Y의 최대공약수로 나누면 됨
a,b는 서로소인 가정 하에 X=aG, Y=bG로 표현
최소공약수 = G
최소공배수 = X x Y / G = abG
X, Y를 입력받고 최대공약수를 출력하는 알고리즘(재귀호출 방식 이용)
근사값 알고리즘
배열 A(100)의 원소 100개는 절대값이 500 이하, 이중에서 정수 33에 가장 가까운 근사값을 찾아 해당 원소의 첨자를 출력하는 알고리즘
MinCha : 33과의 차이를 가장 크게 만드는 원소 값 -500인 경우를 초깃값으로 설정 Ans : MinCha 값을 갱신하는 배열 원소(N)의 첨자
A(1)부터 A(100)까지 A(N)의 N을 1씩 커지게 해서 A(N)이 33이상이면 차이가 양수이기 때문에 A(N)-33으로 계산하고, 33미만이면 음수이기 때문에 33-A(N)으로 계산한다. (차이는 0 미만이 불가능하기 때문에) 그렇게 해서 구한 Cha(차이)가 지금까지의 최솟값인 MinCha보다 작으면 Cha를 MinCha로 설정하고, 해당 첨자인 N을 새 정답으로 설정한다.
3차시 1의 보수와 2의 보수 알고리즘
2의 보수 = 1의 보수 + 1
어떤 이진수에 대해 2의 보수를 구하는 알고리즘
C : 캐리를 보관하는 변수(덧셈에서 말하는 자리 올림수), 캐리가 있으면 1, 없으면 0 B(N) : 입력된 이진수 O(N) : 배열 B에 대한 1의 보수 T(N) : 배열 B에 대한 2의 보수
먼저 1의 보수 O(N)을 구하기 위해서 B(N)에서 최상위 자리(1)부터 최하위 자리(N)까지 1의 보수를 구해준다(O(i) = 1 - B(i))
2의 보수를 구하기 위해서는 최하위 자리 N부터 최상위 자리까지 캐리 C를 더하면서 2의 보수를 만든다 O(i)와 C가 같은 경우에만 T(i)는 0이고, 나머지는 1이 된다 -> 새로운 캐리 C는 이전 캐리와 O(i) 모두 1일 때만 1이 된다 -> 이러한 방식을 최상위 자리까지 반복문을 돌린 후 2의 보수가 저장된 배열 T를 출력한다
2의 보수는 1의 보수 전체에 1을 더하면 됨(여기서 2진수 덧셈이 필요) 0 + 0 = 0(1의 보수 O(i)와 현재의 캐리 값이같은경우) 0 + 1 = 1 (1의 보수 O(i)와 현재의 캐리 값이다른경우) 1 + 0 = 1(1의 보수 O(i)와 현재의 캐리 값이다른경우) 1 + 1 = 0(1의 보수 O(i)와 현재의 캐리 값
