yubin

I am an amazing person.

카테고리 (펼쳐보기)

2장. 문제 해결 개관

이 장을 읽으며 알고리즘 문제를 풀이할 때 나의 문제점을 찾아 낼 수 있었다.

알고리즘은 결국 문제의 해결을 요구하는것인데 나는 코딩에 너무 급급해서 코딩과 문제해결을 한번에 해결하려고 하다 결국 두마리 토끼를 모두 놓치는 것이라는 생각이 들었다.

여기서 나오는 몇가지 안좋은 사례 중 디버깅을 하며 뭔가 잘못됐음을 깨닫고 처음으로 되돌아가는게 너무 나인것 같아서 급할수록 돌아가라는 문구가 더욱 와 닿았다.😓


🤔 문제 해결 과정

  1. 문제를 읽고 이해하기
    • 문제에 대한 설명을 공격적으로 읽고 문제가 원하는 바를 완전히 이해한다.
    • 사소한 제약 조건을 놓치지 않는다.
  2. 재정의와 추상화
    • 문제를 자신이 다루기 쉬운 개념을 이용해 자신의 언어로 풀어 쓴다.
    • 문제를 추상화(현실의 개념을 수학,전산적 개념으로 옮겨 표현)하여 다루기 쉽게 만든다.
  3. 계획 세우기
    • 문제 해결을 위한 방식, 알고리즘, 자료구조를 결정한다.
  4. 계획 검증하기
    • 3에서 설계한 알고리즘이 모든 경우에 요구 조건을 정확히 수행하는지 증명한다.
    • 수행 시간과 메모리가 제한에 부합하는지 확인한다.
  5. 계획 수행하기(코딩)
  6. 회고하기
    • 자신이 문제를 해결한 과정을 돌이켜보고 개선한다.
    • 문제를 풀 때마다 코드와 함께 경험(해결법, 접근법, 결정적 깨달음)을 기록으로 남긴다.
    • 한번에 맞추지 못했다면 오답의 원인도 반드시 적는다. (오답 노트)
    • 다른 사람의 코드를 본다.


🌟 나의 경우에는 코딩 전에 손으로 문제의 해결 과정을 정리하고 검증하는 것이 필요할 듯 하다!


🤔 문제 해결 전략

  • 직관과 체계적인 접근이 필요하다.

  • 체계적 접근을 위한 질문

    1. 비슷한 문제를 풀어본 적이 있었나?
      • 이를 위해 알고리즘의 원리를 이해하며 문제를 풀어야 함
    2. 단순한 방법에서 시작할 수 있을까?
      • 문제를 과대평가해서 어렵게 푸는 실수를 예방
      • 알고리즘 효율성의 기준선을 정해줌
      • 가장 간단한 방법으로부터 점진적으로 사고를 발전시켜 해결법을 개선할 수 있음
    3. 내가 문제를 푸는 과정을 수식화 할 수 있나?
      • 수식화를 통해 답을 찾거나 알고리즘의 고려점을 파악
      • 손으로 문제를 푸는 습관을 통해 알고리즘에 간과한 점이 없는지 미리 확인
    4. 문제를 단순화 할 수 없나?
      • 문제의 제약 조건 삭제, 저차원화(ex: 2차원→1차원) 등을 통해 문제를 단순화하여 통찰을 얻을 수 있음
    5. 그림으로 그려볼 수 있나?
    6. 수식으로 표현할 수 있나?
      • 평문으로 쓰인 문제를 수식으로 표현
    7. 문제를 분해할 수 있나?
      • 문제의 복잡한 조건을 단순한 여러 개의 조건으로 분해
    8. 뒤에서부터 생각해서 문제를 풀 수 있나?
      • 예를 들어 사다리 게임
    9. 순서를 강제할 수 있나?
      • 순서가 없는 문제에, 답에 관계없는 순서를 강제해 문제를 단순화함
    10. 특정 형태의 답 만을 고려할 수 있나? (정규화)
      • 고려해야 할 답 중 형태가 다르지만 결과적으로 같은 것들을 그룹으로 묶고, 각 그룹의 대표들만을 고려


3장. 코딩과 디버깅에 관하여

위에서 코딩보다 문제 해결이 중요한 것 같다고 한지 얼마 되지 않았지만, 이 장에서는 코딩의 중요성에 대해 말하고 있다. 나의 경우에 이 부분은 경험으로 연습이 좀 되어있어서 문제 해결 부분이 더 중요했지만 읽다 보니 코딩도 중요하긴 하다.

코딩은 내가 푼 문제를 표현하는 수단이니 방법을 정확히 익혀서 내가 표현하고자하는것을 정확히 표현해야한다.

🤔 코드 스타일을 일관되게 결정하는 게 좋겠다!


🔤 좋은 코드를 짜기 위한 원칙

  • 간결한 코드 작성하기

    : 짧고 간결한 코드로 오류 발생 가능성 줄임

  • 적극적으로 코드 재사용

    : 여러 번 쓰이는 함수는 모듈화 해서 재사용

  • 표준 라이브러리 공부

    : 간결하고 가독성 높은 코드를 만들기 위해 검증된 표준 라이브러리 사용

  • 항상 같은 형태로 프로그램 작성

    : 자주 작성하는 알고리즘, 코드 등은 한번 검증된 코드를 만들면 이것만 꾸준히 사용하여 도구가 아닌 문제에 집중

  • 일관적이고 명료한 명명법 사용

  • 모든 자료를 정규화 해서 저장

    : 예를 들어 분수는 모두 기약 분수로 정규화, 각도는 0~359도 사이로 정규화

  • 코드와 데이터 분리

    : 오타를 주의


🔤 자주 하는 실수

  • 산술 오버플로
  • 배열 범위 밖 원소에 접근
  • 일관되지 않은 범위 표현 방식 사용
    • 일반적으로 [low,high)로 범위 사용
  • Off-by-one오류
    • 계산의 흐름은 맞지만 하나가 모자라거나 많아서 틀리는 코드의 오류
  • 컴파일러가 잡아주지 못하는 상수 오타
  • 스택 오버플로
    • 대개 재귀 호출의 깊이가 깊어질 때 발생
  • 다차원 배열 인덱스 순서 바꿔쓰기
    • 특정 배열에 접근하는 위치를 하나로 통일하는 것을 권장
  • 잘못된 비교 함수 작성
    • 사용하는 언어의 연산자의 성질을 익혀서 검토
    • 예를 들어 c++의 경우 ‘<’연산자는 아래 성질을 가짐
      1. a<a는 항상 거짓 (비반사성)
      2. aa는 거짓 (비대칭성)
      3. a<b, b<c 참이면, a<c도 참 (전이성)
      4. a<b, b<a에 모두 거짓이면 a=b (상등 관계의 전이성)
    • 정렬 시 위 연산자 성질에 모순되는 정렬 기준이 생성되면 정렬 실패
  • 최소, 최대 예외 잘못 다루기
    • 가장 작은 입력과 가장 큰 입력에 대한 동작을 고려하기
  • 연산자 우선순위 잘못 쓰기
  • 너무 느린 입출력 방식 선택
  • 변수 초기화 문제
    • 전역변수를 초기화 하지 않고 사용시 두번째 케이스 부터는 답이 틀릴 수 있음
    • 같은 입력 예제를 두 번 반복해서 입력하여 초기화 여부 확인 가능


🔤 디버깅과 테스팅

🐞 디버깅

  • 디버거 사용은 지양
  • 대안이 되는 검증 단계
    1. 작은 입력에 대해 제대로 실행되나 확인
    2. 단정문(조건이 거짓일때 오류를 내고 프로그램 종료시키는 함수)을 통해 조건 확인
    3. 프로그램 계산 중간 결과 출력
  • 런타임 오류의 경우 디버거를 사용해 스택기록 확인


✔️ 테스트

  • 제출 전 가능한 많은 예제 입력으로 테스트
  • 스캐폴딩
    • 답안을 검증하기 위해 짜는 임시코드
    • 코드의 정당성 확인 , 반례 탐색에 유용
    • 더 느리고 간단한 알고리즘으로 스캐폴딩을 만들고 나오는 답과 비교 하며 테스트 가능


🔤 변수 범위의 이해(산술 오버플로)

  • 계산된 값이 자료형의 표현가능 범위를 벗어난 경우를 의미
  • 대부분 사전에 경고를 해주지 않으므로 주의


🤯 산술 오버플로가 일어나는 경우

  • 너무 큰 결과
    • 큰 정수를 다룰 때는 항상 변수의 형태에 주의
  • 너무 큰 중간값
    • 계산 중간에 큰값을 일시적으로 계산 해야하는 경우 계산 결과가 이상해 짐
  • 너무 큰 무한대 값
    • 자료형이 처리 할 수 있는 가장 큰값을 무한대 값으로 쓰는 실수
    • 무한대 값이 서로 더해지거나 곱해지는 경우를 고려하여 적당한 값으로 무한대 값을 설정해야함.


🤯 오버플로를 피해가는 법

  1. 더 큰 자료형 사용하기
  2. 연산의 순서를 바꾸기
  3. 계산 방법을 바꾸기 ex) 이항계수의 경우 팩토리얼을 사용한 계산 → 점화식을 사용한 계산


🔤 실수 자료형의 이해

자료형의 bit수가 제한되어 있으므로 근사값을 사용해 실수를 표현하게 된다.

따라서 실수 자료형을 사용할때는 근사로 인한 오차를 고려해야한다.

  • IEEE 754 표준
    • 대부분의 컴퓨터,컴파일러에서 사용 되는 실수 표기방식
    • 특징
      • 이진수로 실수표기
      • 부동 소수점 표기법 : 소수점을 움직일수 있음
      • 무한대, 비정규 수,NaN 등 특수값이 존재


  • 실수의 이진법 표기

    1011.101

    → 정수부 1011 : $2^3+2^1+2^0$

    → 소수부 001 : $(1/2)^1+(1/2)^3$


  • 부동 소수점 표기
    • 정수부와 소수부에 비트 배분을 자유롭게 하기 위해 소수점을 옮길 수 있도록 함
    • 이게 소수점이 둥둥 떠다니는것 같다고 ‘부동’이라는 이름 붙음

    • 32bit 실수 표기의 경우 아래와 같은 구조로 이루어짐

      구분 MSB(most significant bit) 지수부 가수부
      bit 1 8 32
      설명 부호 비트 소수점을 몇 칸 옮겼나 소수점을 옮김 실수의 최상위 X비트

    • 자료형 별 부동소수점 표기

      자료형 MSB(bit) 지수부(bit) 실수부(bit) 지수 범위 유효 자릿수(십진수)
      32bit 실수형 1 8 23 -2^7+2 ~ 2^7-1 6
      64bit 실수형 1 11 52 -2^10+2 ~ 2^10-1 15
      80bit 실수형 1 15 64 -2^14+2 ~ 2^14-1 18
    • 웬만하면 그냥 64비트 이상 실수형 사용을 권장


  • 실수 비교하기

    위와 같이 컴퓨터는 실수를 근사하여 표현하므로 실수를 비교할때는 근사에서 오는 오차를 고려해야함.

    1. 비교할 실수의 크기들에 비례한 오차한도 설정
      • 단위가 있을경우 사용

      • 같다고 판단할 큰 값 두개를 비교할 경우 고려

        : 가능한 오차의 최대치를 가늠하여 오차 한도의 하한 설정

      • 다르게 판단할 작은 값 두개를 비교할 경우 고려

        : 다르다고 처리되야할 두 값이 오차때문에 가까워지는 경우

        : 가능한 오차의 하한를 가늠하여 오차 한도의 상한 설정

    2. 상대 오차 이용
      • 단위가 없거나 일반적인 경우에 사용
      • 비교하려는 숫자의 크기에 비례하여 오차를 정하는 방식
      • \[상대오차(a,b)=\frac{|a-b|}{max(|a|,|b|)}\] 
          //a,b의 오차가 더 큰수의 0.000001%이하면 true 반환
            
  boolean relativeEqual(double a, double b){
  	return Math.abs(a-b) <= 1e-8*Math.max(Math.abs(a),Math.abs(b));
  }

      • 0에 매우 가까운 작은 수를 비교하려 할때는 주의해야함 → 작은수가 0으로 표현되어 상대오차가 1이 될 수 있음 → 따라서 절대오차와 상대오차를 적절히 혼용

          boolean doubleEqual(double a, double b){
  	double diff=Math.abs(a-b); // 절대오차 계산
  	if(diff<1e-10) return true; // 절대 오차가 허용범위 내라면 true반환
  	return diff<=1e*max(Math.abs(a),Math.abs(b)); // 이외의 경우 상대오차 사용
  }


      • 대소비교
        • 오차로 인한 이상한 결과를 피하려면 두값이 같은경우(두 값이 아주 가까운경우)를 먼저 처리해줘야함


      • 정확한 사칙연산
        • 가수부 안에 들어가는 정수들, 분모가 2의 거듭제곱인 유리수 등 정확히 표현 가능한 범위의 숫자 사용
        • 추가적인 자료구조 도입( ex) java의 BifDecimal )


      • 코드의 수치적 안정성 파악

        • 코드의 수치적 안정성(numerically stable)

          : 프로그램 실행 과정에서 발생하는 오차가 더 커지지 않는것

          : 수치적으로 안정된 프로그램에서는 중간의 작은 연산 오차가 큰 오차를 야기시키지 않음

        • 실수연산이 필요하다면 수치적으로 안정된 알고리즘을 짜야함


      • 실수 연산 하지 않기
        • 실수 연산을 제대로하는것은 어려움
        • 실수 연산을 아예 하지 않는것이 가장 좋은 방법!
        • 적절한 변형을 통해 실수 연산을 피하자!

댓글남기기

참고