개발공부 기록지

19 강 알고리즘과 평가

알고리즘이란?

Algorithm 은 어떤 값 또는 값의 집합을 입력으로 하고 어떤 값 또는 값의 집합을 출력으로 하는,
명확하게 정의된(well-defined) 계산 절차다.

넓은 의미의 알고리즘

• 특정 문제를 해결하기 위한 일반적인 절차나 규칙의 모음
  (예시: 도메인 로직의 처리의 흐름, DB에서 레코드를 얻ㅇ어서 적절하게 처리한 후 결과를 출력하는 것)

좁은 의미의 알고리즘

• 명확하게 정의된 계산문제에 대해 정의된 계산 절차를 수행하는 것 (주로 책에서 다루는 내용)

알고리즘을 배우는 의의

알고리즘은 엔지니어에게 공통언어 → 커뮤니케이션을 위해서 알아둘 필요가 있음

유한한 컴퓨터 자원을 효과적으로 활용

알고리즘을 이용하여 새로운 문제에 대처가능

알고리즘의 평가

아래로 갈수록 계산량이 많아진다. 

대규모 데이터를 대상으로 할 경우 O(n log n) 까지가 실용적이다.

계산량 개념 적용

• 시간 계산량(실행시간, 단계 횟수)
• 공간계산량 (메모리 사용량)

계산량과 상수항

계산량의 Order 표기에서는 "상수항" 을 무시한다.

상수항?

함수 호출, 함수로 부처 값을 반환하기 위한 처리, 일차변수를 확하는 처리, if 문으로 분기시키는 처리 등이 이에 해당

→ 실질적으로는  복잡해질 수록 상수항이 계산량에 영향을 미친다. 경우에 따라서 상수항을 줄이는 최적화도 필요하다.

최적화시 유의할 점

• 처음부터 상수항을 줄이는 최적화를 하지 않는다.
• 현재 프로그램에 무엇이 문제인지를 정확하게 파악 후 최적화 실행

개선시 문제 해결을 위해 규명해야할 사항

• 알고리즘을 교체해서 개선할 것인가
• 상수항을 줄여서 개선할 것인가
• 물리적으로 리소스가 부족하므로 하드웨어를 교환해서 성능을 개선 할것 인가

알고리즘의 실제 활용 → 예측과 측정이 중요

* 단순한 알고리즘이 더 나은 경우도 있다.

* 고전적인 알고리즘이 좋은 경우도 있다.

써드파티 소스를 잘 활용하자

정평이 난 알고리즘은 제 3자 이용하기 쉽도록 이미 구현된 소스가 공개되어 있는 경우가 많다.

하지만, 이러한 라이브러리를 바로 사용할 수가 없을 수도 있다.

해당 알고리즘이 어떻게 구현이 되어있는지 알아야 한다.

→ 우리가 원하는 사양으로 변경가능

→ 불필요한 구현을 줄여 성능, 유지보수, 테스트, 유연성, 자원 사용 등의 측면에서 다양한 문제를 방지가능

앞번의 암호 강도 측정기능의 테스트 예시 에서 보면,

테스트 코드를 작성한 순서는 다음과 같다.

1. 모든 규칙을 충족하는 경우
2. 길이만 8글자 미만이고 나머지 조건은 충족하는 경우
3. 숫자를 포함하지 않고 나머지 조건은 충족하는 경우
4. 값이 없는 경우
5. 대문자를 포함하지 않고 나머지 조건을 충족하는 경우
6. 길이가 8글자 이상인 규칙만 충족하는 경우
7. 숫자 포함 조건만 충족하는 경우
8. 대문자 포함 조건만 충족하는 경우
9. 아무 조건도 충족하지 않는 경우

위의 순서는 다음 규칙을 따른 것이다.

• 쉬운 경우 → 어려운 경우
• 예외적인 경우 → 정상적인 경우

초반에 복잡한(어려운) 테스트부터 시작하면 안 되는 이유

만약에 테스트 코드 작성 순서를 다음과 같이 진행했다고 하자. 

1. 대문자 포함 조건만 충족하는 경우
2. 모든 규칙을 충족하는 경우
3. 숫자를 포함하지 않고 나머지 규칙은 충족하는경우

이렇게 진행하다보면 첫 번째 테스트는 쉽게 넘어가지만, 두 번째는 모든 규칙을 검증하는 코드를 구현해야 할것 같은 느낌이 든다.

한번에 완벽한 코드를 만들다 보면

▶ 나도 모르게 버그를 만든다.

    → 버그를 잡는데 많은 시간을 허비한다.

    → 테스트 통과 시간도 길어진다

→ 집중력이 떨어진다

구현하기 쉬운 테스트부터 시작하기

암호 강도 측정기능의 테스트 를 한다고 하면 가장 쉬워보이는 것은 다음과 같다.

• 모든 조건을 충족하는 경우
• 모든 조건을 충족하지 않는 경우

두 가지 경우다 그냥 단순히 해당 값을 리턴하면 되기 때문이다.

• 모든 조건을 충족하는 경우  → return STRONG
• 모든 조건을 충족하지 않는 경우 → return WEEK

먼저 "모든 조건을 충족하는 경우"  부터 시작했다고 하면, 다음으로 생각해 볼수 있는 테스트는 다음과 같다.

• 모든 조건을 충족하지 않는 경우 → 모든 조건을 검증하는 코드 필요
• 한 가지 조건만 충족하는 경우 → 한 가지 규칙을 충족하는지 검증하는 코드 필요
• 두 가지 조건을 충족하는 경우 → 두 가지 규칙을 충족하는지 검증하는 코드 필요

이렇게 보면 "한 가지 조건만 충족하는 경우" 가 더 구현하기 쉽다.

이런 식으로 한 가지 테스트를 통과했으면 그 다음으로 구현하기 쉬운 테스트를 선택하여 진행해야 한다.

예외 상황을 먼저 테스트해야 하는 이유

초기 설계 단계에서 예외 처리를 고려하는 것은 프로그래밍의 중요한 부분

예외 처리를 무시하고 코드를 작성할 경우,

→ 나중에 예외 상황을 반영하기 위해 코드 전체를 개편해야 할 수도 있음

→ 복잡한 조건문을 추가 해야 할 수도 있음

→ 코드의 복잡성을 증가시키고 버그 발생 가능성 상승

완급 조절

한번에 얼마만큼의 코드를 작성할 것인가?

1. 정해진 값을 리턴
2. 값 비교를 이용해서 정해진 값을 리턴
3. 다양한 테스트를 추가하면서 구현을 일반화

뻔한 구현이라도 위 단계를 거쳐서 연습을 하면,

구현이 막막해도 조금씩 기능을 구현해 나갈 수 있다.

리팩토링?  ▶  코드의 가독성 향상

코드 중복 발생, 코드가 길어진다

▶ 메서드 추출과 같은 기법을 이용하여 리팩토링  

▶ 메서드 이름으로 코드의 의미 표현

팁

리팩토링

1. 동작하는 코드를 먼저 작성

2. 변경하기 쉬운구조로 코드를 구성

3. 필요한 부분은 리팩토링

4. 메서드의 구조에 영향을 주는 리팩토링은 큰 틀에서 구현 흐름이 눈에 들어오기 시작한 뒤에 진행 (코드의 의미와 구조가 명확해지만 리팩토링 진행)

5. 범위가 큰 리팩토링은 시간이 오래 걸리므로 먼저 테스트를 통과 시키는데 집중

테스트

1. 테스트할 목록을 미리 정하기

2. 정한 테스트 목록중 구현이 쉽고 예외적인지 예측

3. 새로운 테스트 사례는 바로 목록에 기록

4. 목록을 하나씩 통과하면서 진행한다.

구현이 막막할때

1. 검증하는 코드부터 작성해 본다.

구현이 막힐때

1. 과감하게 지우고 다시 시작해보자

검사할 규칙

• 길이가 8글자 이상
• 0부터 9사이의 숫자를 포함
• 대문자 포함
• 세 규칙을 모두 충족하면 암호는 강함이다.
• 2개의 규칙을 충족하면 암호는 보통이다.
• 1개 이하의 규칙을 충족하면 암호는 약함이다.

첫 번째 테스트: 모든 규칙을 충족하는 경우

Test 코드

package chap02;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class PasswordStrengthMeterTest {

    @Test
    void meetsAllCriteria_Then_Strong(){
        PasswordStrengthMeter meter = new PasswordStrengthMeter();
        PasswordStrength result = meter.meter("ab12!@AB");
        assertEquals(PasswordStrength.STRONG, result);
    }
}

암호검사기 코드

PasswordStrength

package chap02;

public enum PasswordStrength {
    STRONG
}

PasswordStrengthMeter

1 ) PasswordStrengthMeter 클래스를 작성하여 컴파일 에러를 먼저 해결

package chap02;

public class PasswordStrengthMeter {
    public PasswordStrength meter(String s) {
        return null;
    }
}

▶▶ 테스트 실행시 null 을 반환하므로 실패 

2) 테스트를 성공시키기 위해서 STRONG 을 반환하도록 수정

package chap02;

public class PasswordStrengthMeter {
    public PasswordStrength meter(String s) {
        return PasswordStrength.STRONG;
    }
}

▶▶ 테스트 성공

3) 테스트 코드에 모든 규칙을 충족하는 예를 하나 더 추가

package chap02;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class PasswordStrengthMeterTest {

    @Test
    void meetsAllCriteria_Then_Strong(){
        PasswordStrengthMeter meter = new PasswordStrengthMeter();
        PasswordStrength result = meter.meter("ab12!@AB");
        assertEquals(PasswordStrength.STRONG, result);

        PasswordStrength result2 = meter.meter("abc1!ABD");
        assertEquals(PasswordStrength.STRONG, result2);
    }
}

▶▶ 테스트 성공

위와 같은 방식을 따라

아래와 같이 (가능한 모든)조건을 추가해가면서

즉, 검증하는 범위를 추가해가면서 코드를 완성하면 된다.

• 두 번째 테스트 - 길이만 8글자 미만이고 나머지 조건은 충족하는 경우
• 세 번째 테스트 - 숫자를 포함하지 않고 나머지 조건은 충족하는 경우
• 네 번째 테스트 - 값이 없는 경우
• 다섯 번째 테스트 - 대문자를 포함하지 않고 나머지 조건을 충족하는 경우
• 여섯 번째 테스트 - 숫자 포함 조건만 충족하는 경우
• 일곱 번째 테스트 - 숫자 포함 조건만 충족하는 경우
• 여덟 번째 테스트 - 대문자 포함 조건만 충족하는 경우
• 아홉 번째 테스트 - 아무 조건도 충족하지 않는 경우

※ 테스트 하는 도중에 지속적으로 코드 정리(리팩토링)도 필요하다.

• 테스트 성공 후 리펙토링할 대상이 보이면 ▷ 리팩토링
• 테스트 성공 후 리펙토링할 대상이 안보이면 ▷ 다음 테스트 진행

※ 리팩토링시 가독성을 높이는 것이 목표

• 처음보는 개발자도 알 수 있게 수정
• 전반적인 로직을 알기 쉽게 수정

TDD 란?

먼저 테스트를 하고 그다음에 구현하는 방식.

테스트를 먼저 작성하고 테스트에 실패하면
테스트를 통과 시킬 만큼 코드를 추가하는 과정을 반복하면서
점진적으로 기능을 완성해 나가는 방식을 추구한다.

TDD 기본흐름 예시

덧셈 기능을 검증하기 위한 테스트

CalculatorTest.java

package chap02;

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

public class CalculatorTest {
    @Test
    void plus() {
        int result = Calculator.plus(1, 2);
        assertEquals(3, result);
    }
}

step 1 ) 클래스 생성하고 0을 리턴하는 plus() 메서드를 추가

Calculator.java

package chap02;

public class Calculator {
    public static int plus(int a1, int a2) {
        return 0;
    }
}

 → CalculatorTest.java 실행 → return 값이 0 이여서 테스트 실패 

step 2 ) 테스트를 통과하기 위해 3 을 return 

Calculator.java

package chap02;

public class Calculator {
    public static int plus(int a1, int a2) {
        return 3;
    }
}

 → CalculatorTest.java 실행 → 테스트 성공

step 3) 추가 검증코드를 추가

CalculatorTest.java

package chap02;

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

public class CalculatorTest {
    @Test
    void plus() {
        int result = Calculator.plus(1, 2);
        assertEquals(3, result);
        assertEquals(5, Calculator.plus(4, 1));
    }
}

Calculator.java

package chap02;

public class Calculator {
    public static int plus(int a1, int a2) {
        return a1 + a2;
    }
}

 → CalculatorTest.java 실행 → 테스트 성공

문제(출처: 프로그래머스)

(문제 내용)
문자열 my_string과 is_prefix가 주어질 때, is_prefix가 my_string의 접두사라면 1을, 아니면 0을 return 하는 solution 함수를 작성해 주세요.

▶ 내가 푼 방식

//내가 작성한 코드
function solution(my_string, is_prefix) {
    return my_string.startsWith(is_prefix) ? 1: 0;
}

▶ 다른 유저가 푼 방식

// 유저 1  
function solution(my_string, is_prefix) {
    return my_string.slice(0, is_prefix.length) === is_prefix ? 1 : 0;
}

// 유저 2
function solution(my_string, is_prefix) {
    return my_string.substring(0, is_prefix.length) === is_prefix ? 1 : 0;
}

// 유저 3

▶  배운 것들

     - 문자열.startWith('특정 문자열') : 문자열이 특정 문자열로 시작하는지 여부를 확인해주는 메서드

     -