1. 문제 해결과 프로그래밍 대회

  • 문제 해결 능력: 제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력

2. 문제 해결 개관

  • 문제 해결 능력을 수련하는 법: 문제를 푸는 것이 아니라 문제를 푸는 기술을 연마

2.1 문제 해결 과정

  1. 문제를 읽고, 이해하기

  2. 재정의와 추상화

    • 자신의 언어로 풀어쓰기
    • 추상화: 현실 세계의 개념을 우리가 다루기 쉬운 저난학적 개념으로 옮겨 표현하는 과정 / 현실의 본질만 남겨두고 축약하여 표현하기

  3. 계획 세우기

    • 사용할 알고리즘과 자료구조 선택

  4. 검증하기

    • 시간 과 공간(메모리) 확인

  5. 구현하기

  6. 회고하기

    • 자신이 푼 문제 과정을 돌이켜 보고 개선하기
    • 기록하기
    • 다른 사람의 코드 보기

2.3 문제 해결 전략

직관과 체계적인 접근

체계적인 접근: 백제에서부터 시작해 문제를 해결하기 위한 기반을 점진적으로 전진하는 것

체계적인 접근을 위한 질문들

  1. 비슷한 문제플 풀어본 적이 있는가?

  2. 단순한 방법에서 시작할 수 있을까?

    • 시간, 공간 제약을 생각하지 않고 문제를 해결하는 가장 단순한 알고리즘 만들기
    • 무식하게 풀 수 있을까? => 기준선 정해줌 => 최적화
      • 완전 탐색, 브루트 포스

  3. 내가 문제를 푸는 과정을 수식화할 수 있을까?

    • 손으로 문제를 풀어 보자

  4. 문제를 단순화 할 수 없을까?

    • 좀 더 쉬운 변형판
    • 제약 조건 없애기, 변수의 수 줄이기, 다차원 -> 1차원으로 변환

  5. 그림으로 그려볼 수 있을까?

  6. 수식으로 표현할 수 있을까?

  7. 문제를 분해할 수 있을까?

    • 문제에 주어진 복잡한 조건을 더 단순한 형태를 갖는 조건의 집합으로 분해

  8. 뒤에서부터 생각해서 문제를 풀 수 있을까?

    • A->B 를 B->A 로 변형

  9. 순서를 강제할 수 있을까?

    • 순서가 없는 문제를, 순서를 강제해서 문제를 푼다.
    • 어떤 순서로 해도 상관 없다: 시도한 횟수만 결과에 영향을 준다
      • 특정 순서대로 한다는 제약 추가
    • 경우의 수 문제에서 중복하여 세는 경우를 방지할 때 유용

  10. 특정 형태의 답만을 고려할 수 있을까?

    • 순서 강제하기 기법의 연장선으로 정규화 기법이 있다.
    • 정규화란 고려해야 할 답들 중 형태가 다르지만 결과적으로 똑같은 것들을 그룹으로 묶은 뒤, 각 그룹의 대표들 만 고려하는 방법
    • 무한개의 모든 후보 => 유한한 부분 집합

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

3.1 코딩(구현)의 중요성

  • 간결, 일관된 코드 => 가독성 증가

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

  • 적극적으로 코드 재사용, 모듈화

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

    • 이분 탐색, BFS 등등

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

    • 시간 표현(h, m, s), 각도 표현 등등, 한 가지 형태로 저장해야 함

  • 코드와 데이터 분리하기

    • 알파벳 모음을 따로 변수화, dy, dx 등등

3.3 자주 하는 실수

  • 산술 오버플로

  • indexOutof Range Error, 항상 0<=i<n 형태 지키기

  • 하나 더 많거나, 하나더 모자르거나: Off-by-one 오류

    • 최소 입력 (ex. 0,1 인 경우) 인 경우 테스트, 예외 처리

  • 컴파일러가 잡아주지 못하는 오타

  • 스택 오버플로: 함수 재귀, 재귀 호출 깊이

  • 다차원 배열 인덱스 순서 바꿔 쓰기

  • 잘못된 비교 함수

  • 최소, 최대 예외 잘못 다루기

    • 가장 작은 입력, 가장 큰 입력에 대해 테스트

  • 자료형의 프로모션: 실수, 정수 혼합 연산

3.6 실수 자료형

  • 정수는 컴퓨터가 정확하게 표현가능

  • 실수는 불가능, 실수는 무한의 세계, 컴퓨터 메모리는 유한

  • 실수는 근사 값으로 표현, 정확도가 제한된 근사 값

  • 부동 소수점 (floating-point)

    • 소수점이 둥둥 떠다닐 수 있다는 의미

    • 정수부와 소수부

    • 부호 비트: 양수인지 음수인지

    • 지수(exponent): 소수점을 몇 칸 옮겼나?

    • 가수(mantissa): 소수점을 옮긴 실수의 최상위 X 비트

  • 좋은 방법: 실수 연산을 아예 하지 않기

    • 적절한 변형으로 실수 연산 제거
    • 양변 제곱, x배 확대

Reference