[Java 알고리즘 기초] 알고리즘 워밍업 & 유클리드 호제법/최소공배수 (1장/ 1103)

 

- 독학 교재: <알고리즘 첫걸음 C&자바 편>

오늘은 알고리즘의 정의를 다시 내려보면서 알고리즘을 떠올리는 방법을 생각해보고,

문제를 만났을 때 그 처리를 분해하고 흐름을 나누어 실행하는 방법에 대해 공부했다.

보면 당연한 내용인데, 문제를 풀 때 이런 과정들을 따로 의식하지 않고도 자연스럽게 수행할 수 있을 때까지 연습하는 게 포인트일 것 같다.

요즘 기초에 대한 생각을 많이 한다.... 개발은 하지 않고 인터넷강의만 듣고 있거나 하는 것도 실력 향상에 걸림돌이 될 수 있지만, 개발을 하면서 가끔 기초 사항을 모르면 그것도 개발에 구멍이 나 있는 것 같단 느낌을 받아서이다. 

그래서 이 책을 빠르게 공부하며 한 번은 개념을 짚고 가고 싶었다.

전에 보았던 <한권으로 합격하는 취업 코딩테스트>에 따르면 알고리즘 문제 해결에 필요한 요소는 독해력, 배경지식, 문제해결력, 구현력, 검증&디버깅 이렇게 다섯 가지인데, 문제를 보고 그 처리와 흐름을 나누는 습관을 들이면

이 중 독해력과 문제해결력을 기르는 데 도움이 될 것 같다.

 

---

컴퓨터과학(CS)에서 알고리즘의 정의

수에 대한 문제가 주어지면, 이를 풀기 위해 명확하며 유한한 방법을 생각하는 것.

수에 대한 어떤 문제가 주어졌을 때, 연산을 수행하는 여러 단계를 거쳐 원하는 출력을 얻는 것.

이를 프로그램으로 작성하고 컴퓨터에서 실행해 답을 얻는다.

 

알고리즘을 떠올리는 방법

1. 차근차근 처리를 거듭하기 위해 처리할 내용을 구분한다. (입력, 연산, 출력을 분리하고, 분기/반복을 찾는다. *아래 설명 있음)
2. 서두르지 말고 침착하게 천천히 생각한다.
3. 처리가 진행될 때 꾸준하게 숫자 변화를 추적(trace)한다.(*디버깅할 때를 생각해보면 이해가 쉽다)
4. 더 나은 절차를 고려한다.(연산을 적게 하는 등)

 

컴퓨터 알고리즘

- 프로그램에 작성하는 처리는 제어, 입력, 기억, 연산, 출력의 5대 장치(기능)가 있음.

- 이 중 제어 장치는 CPU가 담당함. 또 기억은 결과를 저장하고 출력하려면 당연히 필요하므로, 우리는 데이터의 입력/연산/출력을 중점적으로 생각한다.

- 즉 우리는 어떠한 문제가 있을 때 입력, (기억), 연산, 출력의 세 가지 처리로 분해하고,

분기와 반복을 찾아 세 개의 흐름(순차적, 분기, 반복)으로 실행하는 사고력을 기르는 게 좋다.

• (순차적: 보통 대부분의 프로그램은 순차적)
• 분기(선택): ~중 하나를 표시
• 반복: 다시 승부

예) 가위바위보 프로그램 분기/반복 구분

*의사코드에서는 반복 표기를 ■, ▲등의 기호와 함께 선으로 묶어 작성하는데, 티스토리에서는 의사코드 작성이 불편하여 선을 제외하고 표기함.

O 정수형: com, user, judgement

· user <- 유저 입력 받음

· com <- 1,2,3 중 랜덤

- if(user == com) 

   · judgement  <- "무승부"

} else if((user == 1 && com == 2) || (user == 2 && com == 3) || (user == 3 && com == 1))

   · judgement <- "사용자 승리"

  else 

   · judgement <- "사용자 패배"

· judgement 표시

 

유클리드 호제법

- 두 정수의 최대공약수를 구하는 알고리즘

1. 두 정수의 큰 쪽에서 작은 쪽을 빼는 것을 양쪽이 같아질 때까지 반복한다.
2. 같아진 값이 최대공약수가 된다.

=> (일반적인 방법) 양쪽이 동일하지 않으면 / 두 정수의 큰 쪽에서 작은 쪽을 빼는 것을 반복한다

=> (효율적인 방법) 양쪽이 동일하지 않으면 / 두 정수의 큰 쪽에서 작은 쪽을 나누는 것을 반복한다

 

1장 문제 및 풀이

- 유클리드 호제법(최대공약수, GCD)

- 최소공배수(LCM)를 구하는 알고리즘

효율적인 방법

< 유클리드 호제법(최대공약수) >

입력: 수1, 수2(사용자로부터 입력받음)

출력: 수1과 수2의 최대공약수

연산: while 두 수가 같지 않으면 반복한다

  if 수1>수2 면

    수1 = 수1 % 수2

  else 수2>수1이면

    수2 = 수2 % 수1

answer <- 수1(수2여도 동일)

static int getLargestCommonMultiple(int a, int b) {
        while(a != b && (b != 0)) {
            if(a > b){
                a = a % b;
            } else {
                b = b % a;
            }
        }
        return a;
    }

 

< 최소공배수를 구하는 알고리즘 >

입력: 수1, 수2(사용자로부터 입력받음)

출력: 수1과 수2의 최소공배수

연산: 먼저 위의 최대공약수 알고리즘을 이용해 수1, 수2의 최대공약수 구한 후 이용

  answer = (수1*수2) / (수1과 수2의 최대공약수)

static int getGreatestCommonDivisor(int a, int b) {
        int lcm = getLargestCommonMultiple(a, b);
        return (a * b)/lcm;
    }

 

덜 효율적인 방법

< 유클리드 호제법(최대공약수) >

먼저 입력, 출력, 연산에 대해 생각해보았다.

입력: 수1, 수2(사용자로부터 입력받음)

출력: 수1과 수2의 최대공약수

연산: while 두 수가 같지 않으면 반복한다

   if 수1>수2 면

     수1 = 수1-수2

   else 수2>수1이면

     수2 = 수2-수1

  answer <- 수1(수2여도 동일)