알고리즘 문제해결 전략 1권 정리(CH-2,3 문제 해결 개관)

RisingJade의 개발기록·2022년 2월 15일
1

2.2 문제 해결 과정

  1. 문제를 이해한다.

    • 문제를 자세히 읽고 이해하는 것은 기본 중 기본으로, 조급한 마음에 문제를 곁눈질 하고 푸는 일이 없도록 하자.

  2. 재정의와 추상화

    • 제정의: 자신이 다루기 쉬운 개녕을 이용해서, 문제를 자신의 언어로 풀어 쓰는 것.
    • 문제가 요구 하는 바를 직관적으로 이해하기 위해 꼭 필요하며, 요구하는 바가 복잡한 문제일수록 그 중요성이 더해진다.
    • 추상화: 현실 세계의 개념을 우리가 다루기 쉬운 수학적/ 전산학적 개념으로 옮겨 표현하는 과정
    • 문제의 본질을 어떤 방식으로 재구성하느냐에 따라 같은 일을 하는 프로그램이라도 전혀 다른 문제로 받아들여질 수 있다. 그러므로 실질적으로는 추상화 과정이 프로그래밍이 나아갈 방향을 결정한다고 볼 수 있다. 따라서, 어떤 부분을 추상화할 것인지, 문제를 어떻게 재정의 할지 충분히 고찰해보자

  1. 계획 세우기

    • 문제를 어떻게 해결할지 계획을 세우는 단계
    • 문제를 어떤 방식으로 해결할지 결정하고, 사용할 알고리즘과 자료구조를 선택한다.
    • 실질적으로 PS에서 가장 중요한 부분

  1. 계획 검증하기

    • 계획을 세웠다고 바로 코딩을 하는 것이 아니라 구현을 하기 전에 계획을 검증하는 과정을 거쳐야 한다.
    • 설계한 알고리즘이 모든 경우에 요구 조건을 정확히 수행하는지를 증명하고, 수행에 걸리는 시간과 사용하는 메모리가 문제의 제한 내에 들어가는지 확인해야 한다.

  1. 계획 수행하기

    • 이제 검증된 알고리즘을 기반으로 프로그램을 작성하면 된다.
    • 구현은 정확하고 효율적이여야 한다.

  1. 회고하기

    • 자신이 문제를 해결한 과정을 돌이켜 보고 개선해나가자
    • 한번 푼 문제를 다시 봄으로써 더 효율적인 알고리즘을 찾거나 간결한 코드를 작성할 수 있다.
    • 같은 알고리즘을 유도할 수 있는 더 직관적인 방법을 찾을 수 도 있으며, 자신이 기술들을 어떻게 사용하고 있는지를 돌아보고 개선하자.
    • 문제를 풀 때마다 코드와 함께 자신의 경험을 기록으로 간단한 해번과 함꼐 어떤 방식으로 접근했고, 문제의 해법을 찾는 데 결정적이었던 깨달음은 무엇이었는지를 기록하자.
    • 한 번에 맞추지 못한 경우에는 오답 원인도 꼭 적자. 틀린 부분 자주 틀린다.

2.3 문제 해결 전략

  1. 직관과 체계적인 접근

    • 비슷한 문제를 풀어본 적이 있는지 확인
    • 단순한 방법에서 시작할 수 있을까?
    • 내가 문제를 푸는 과정을 수식화 할 수 있을까?
    • 문제를 단순화 할 수 없을까?
    • 그림으로 그려볼 수 있을까?
    • 수식으로 표현 할 수 있을까?
    • 문제를 분해 할 수 있을까?
    • 뒤에서부터 생각해서 문제를 풀 수 있을까?
    • 순서를 강제 할 수 있을까?
    • 특정 형태의 답만을 고려 할 수 있을까(정규화)

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

  1. 간결한 코드 작성하기

    • 코드가 짧으면 짧을수록 오타나 단순한 버그가 생길 우려가 줄어들고, 디버깅도 쉬워진다.
  2. 적극적으로 코드 재사용하기

    • 코드를 모듈화 하자, 같은 코드가 반복된다면 이들을 함수나 클래스로 분리해 재사용하는 것이 편하다.
    • 항상 코드를 깔끔하게 작성하고 유지하는데 신경을 쓰자.
  3. 표준 라이브러리 공부하기

    • 모든 코드를 직접 작성하는 것은 대표적인 시간 낭비의 하나이다.
    • 표준 라이브러리인 문자열, 동적 배열, 스택, 큐, 리스트, 사전, 등의 자료구조, 그리고 정렬 등의 표준적인 알고리즘 구현 사용법을 반드시 잘 알아두자
  4. 항상 같은 형태로 프로그램을 작성하기

    • 여러 종류의 코드를 반복적으로 짜게 될텐데 그런 자료구조나 알고리즘등은 같은한번 검증이 되었으면 왠만하면 고정해서 쓰자. 그래야 나중에 문제에만 집중하기 편하다.
  5. 일괄적이고 명료한 명명법 사용하기

    • 자신이 쓰는 언어의 네이밍 컨벤션을 익혀두어라
  6. 모든 자료를 정규화해서 저장하기

    • 같은 자료를 두 가지 형태로 저장하지 말아라(ex. 9/6과 3/2는 같은 기약분수인 3/2로 통일시키자)
  7. 코드와 데이터를 분리하자

    • const String monthName[] = { "January", "~", ~~, } 와 같이 쓰자

3.3 자주 하는 실수

  1. 산술 오버플로

  2. 배열 범위 밖 원소에 접근

    • int array[10], t; 이런게 있으면 a[10]에 접근해서 값 수정 시 t가 바뀐다...
  3. 일관되지 않는 범위 표현 방식 사용하기

    • [2,3,4,5,6,7,8]-> [2,8]인데 [2,8) 으로 잘못 쓰지 말자
    • 보통 플밍 언어는 반 열린 구간을 사용한다. 이는 첫 번째 값은 집합 안에 포함하고, 다른 하나는 포함하지 않는다.
      [1, 100) 이런 꼴이다.
  4. Off-by-one 오류

    • 계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 많아서 틀리는 코드 <, <=, >,>=를 잘 구별하자
  5. 컴파일러가 잡아주지 못하는 상수 오타

    • 문자열 같은거 철자 조심하자, 배열로 데이터를 만들때 하나하나 잘 확인하자
  6. 스택 오버플로

    • C++의 경우 지역 변수로 선언한 배열이나 클래스 인스턴스가 기본적으로 스택 메모리를 사용하기 때문에 특히나 스택 오버플로를 조심해야 한다.
    • 배열 등의 큰 지역 변수를 스택에 잡으면 재귀 호출이 몇 번 없어도 곧장 스택 오버플로가 나기 쉽다.
    • 자동으로 힙에 메모리를 할당하는 STL 컨테이너를 사용하거나 전역 변수를 적극 사용하자.
  7. 다차원 배열 인덱스 순서 바꿔 쓰기

    • 4,5차원 이상의 고차원 배열을 쓰게 될 시 인덱스 순서를 헷갈리지 마라
  8. 잘못된 비교함수 작성

    • 이건 직접 한번 operator 오버로드를 잘 알아보자
  9. 최소, 최대 예외 잘못 다루기

    • 소수에서의 1과 2 같은거 조심
  10. 연산자 우선순위 잘못 쓰기

    • 비트 연산자를 쓸때 조심하자... &나 |는 우선순위가 == 보다 낮을 정도 낮다.
  11. 너무 느린 입출력 방식 선택

    • cin같은 거 쓸때, cin.tie(0)같은거 잘쓰자
  12. 변수 초기화 문제

    • 전역 변수 같은거 테스트 케이스 여러개 돌릴 때 잘 초기화시켜주자

3.4 디버깅과 테스팅

  1. 디버깅

    • 디버거 없이 프로그램의 버그를 찾아내는 연습을 할 필요가 있다.
    • 작은 입력에 대해 제대로 실행되나 확인하기
    • 단정문(assertion)을 쓴다.
    • 프로그램의 계산 중간 결과를 출력한다.
  2. 테스트에 관하여

    • 제출 전에 예제 입력을 만들어 가능한 한 많이 프로그램을 테스트하는 것이 좋다.
    • 스케폴딩을 이용해보는 것도 방법 중 하나다.

3.5 변수 범위의 이해

  1. 산술 오버플로

    • 대부분의 프로그래밍 언어들은 사칙연산 과정에서 오버플로가 나더라도 별다른 경고를 해 주지 않는다.
    • 프로그램의 정당성을 검증 할 때 프로그램 논리의 정확성에만 집중하다 보면 산술 오버플로가 등장할 수 있다는 사실을 잊기 쉽다.
  2. 너무 큰 결과

    • 64비트 정수를 이용하면서 중간 계산 값을 32비트 정수로 전달하는 실수하지 말자.
  3. 너무 큰 중간 값

    • 중간에 계산하는 값이 오버플로가 일어나지 않는지 체크해보자
  4. 너무 큰 '무한대' 값

    • 무한대 값을 사용시 이 무한대 값들이 서로 더해지거나 곱해지는 경우가 없는지 잘 살펴보고 이럴 때도 오버플로가 나지 않을 크기의 값을 선택하자
    • 987654321과 같은 무한대 값을 사용하자.
  5. 오버플로 피해가기

    • 미리 큰 값은 나누어 주거나 점화식을 이용해서 숫자 크기를 낮추자
  6. 자료형의 프로모션

    사칙연산이나 대소 비교 등의 이항 연산자들은 두 개의 피연산자를 받는다.이떄, 만약 피연산자의 자료형이 다르거나 자료형의 범위가 너무 작은 경우 컴파일러들은 대개 이들을 같은 자료형으로 변환해서 계산하는데, 이를 프로모션이라 한다.

    • C++기준 한쪽은 정수형이고 한쪽은 실수형일 경우: 정수형이 실수형으로 변환된다.
    • 양쪽 다 정수형이거나 양쪽 다 실수 형인 경우: 보다 넓은 범위를 갖는 자료형으로 변환된다.
    • 양쪽 다 int형보다 작은 정수형인 경우: 양쪽 다 int형으로 변환된다.
    • 부호 없는 정수형과 부호있는 정수형이 섞여 있을 경우: 부호 없는 정수형으로 변환된다.
profile
언제나 감사하며 살자!

0개의 댓글