제 4장: 기본적인 알고리즘(6)

46. 두 변수의 값을 교환할 때는 임시 변수를 사용한다.

• 변수 X와 Y의 값을 교환 하려면, 아래 순서대로 하면 교환할 수 없다.
  • 변수 Y에 변수 X 값 대입
  • 변수 X에 변수 Y 값 대입(이미 변수 X의 값은 Y값으로 덮어씌워짐)
• 임시변수를 이용해 값을 임시로 저장해야한다.
  • 1단계: 변수 W에 변수 Y 값 대입
  • 2단계: 변수 Y에 변수 X 값 대입
  • 3단계: 변수 X에 변수 W 값 대입

47. 두 수의 최대공약수는 유클리드 호제법으로 구한다

• 최대공약수: 0이 아닌 정수들의 공통된 약수 중 가장 큰 수

• 유클리드 호제법으로 구하면 된다.

  • 호제법: 2개의 수가 서로 나누는 것
  • 정수 X와 Y(X ≥ Y)가 주어졌을 때 X를 Y로 나눈 나머지를 R이라고 하면, X와 Y의 최대공양수는 Y와 R의 최대공약수와 같다. 그러나 X와 0이 남았을 경우 최대공약수는 X로 한다.

• 정수 X와 Y(X ≥ Y)의 최대공약수를 변수 GCD에 구하는 알고리즘

  1단계: 변수 R에 X/Y의 나머지 값을 대입

  2단계: 변수 R이 0이 아니라면 다음 3~5단계를 반복

  3단계: 변수 X에 변수 Y의 값을 대입한다.

  4단계: 변수 Y에 변수 R의 값을 대입한다.

  5단계: 변수 R에 X/Y의 나머지 값을 대입한다.

  6단계: 변수 GCD에 변수 Y값을 대입한다.

칼럼: 코드와 데이터는 어디에 있을까?

• 알고리즘을 컴퓨터에서 실제로 작동시키는 것 ⇒ 프로그램

• 이 코드와 데이터들은 모두 컴퓨터의 기억장치인 메모리 공간에 배치
• 메모리는 셀이라는 단위로 관리
• 각 셀에는 주소(어드레스)가 붙어있다.
  • 주소를 요소번호라고 하면, 메모리 공간을 큰 배열이라 생각할 수 있다.