Algorithmic Problem Solving Strategies
프로그래밍 대회에서 배우는 알고리즘 문제해결전략
(Part1 내용은 추후 보완할 예정)
chap1. 문제 해결과 프로그래밍 대회
1.1 도입
프로그래밍은 문제 해결이다.
1.2 프로그래밍 대회
현업과는 다르지만 다음과 같은 사항을 배울 수 있다.
- 프로그래밍 대회에서 작성하는 프로그램들은 그래픽 인터페이스등을 전혀 사용하지 않으며 단순히 텍파로 읽어들이고 출력한다. 군더더기가 없으므로 문제 해결에만 집중할 수 있다
- 명시적인 시간 제한과 메모리 제한이 있다. 또한 계산집중적이므로 적절한 알고리즘과 자료구조를 사용하지 않으면 시간 제한 내에 동작하지 않는다.
- 정답과 오답 여부가 훨씬 명확히 가려진다. 현업에서는 대개 코드의 정당성을 단위 테스트나 상호 간 코드 리뷰로 검증하는데 이런 방법으론 잘해봐야 한두 개 입력으로 프로그램을 시험해 보기 마련. 그러나 대회에선 훨씬 크고 다양한 입력에 대해 정답을 계산해 확인해본다.
- 제출한 프로그램의 실행 시간이나 메모리 사용량 관련 정보가 실시간으로 제공되므로 프로그램을 고쳐가며 작은 변경이ㅣ 프로그램의 효율성에 미치는 영향을 직접 체험해볼 수 있다.
- 규모가 작아 각 문제를 풀 때마다 첨부터 다시 짜게 된다. 평소 대형 플젝에서 간과했던 작은 부분에 집중할 수 있는 계기를 만들어준다.
- 여러 사람이 경쟁하는 환경에서 코드를 작성한다.
1.3 이 책을 읽는 방법
전체 7부, 1부와 2부는 후반부에서 다루는 주제들을 공부하기 위해 필요한 지식들을 다룬다.
이 책의 문제들은 모두 온라인 채점 사이트 알고스팟(http://algospot.com)에서 실제 대회와 비슷한 환경에서 채점받을 수 있다.
1.5 대회 준비를 위한 조언
- 가능한 한 많은 문제 풀기
- 온라인 채점 사이트 이용하기
algospot.com :: 알고스팟에 오신 것을 환영합니다!
algospot.com
알고스팟 온라인 채점 사이트
acmicpc.net
http://train.usaco.org/usacogate
USACO Training Gateway
train.usaco.org
USACO Training Program
| Design & Build High-Quality Software with On-Demand Talent
The Topcoder Community is the world’s largest network of designers, developers, and data scientists. Start getting more work done today!
www.topcoder.com
TopCoder
http://livearchive.onlinejudge.org
ICPC Live Archive - Home
icpcarchive.ecs.baylor.edu
ACM-ICPC Live Archive
About - Project Euler
About Project Euler What is Project Euler? Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficie
projecteuler.net
Project Euler
SPOJ Online Judge
- 가능한 한 많은 프로그래밍 대회에 참가하기
Chapter2. 문제 해결 개관
2.2 문제 해결 과정
- 문제를 읽고 이해하기
- 재정의와 추상화
- 계획 세우기
- 꼐획 검증하기
- 계획 수행하기
- 회고하기
2.3 문제 해결 전략
- 직관과 체계적인 접근
- 체계적인 접근을 위한 질문들
비슷한 문제를 풀어본 적이 있던가?
단순한 방법에서 시작할 수 있을까?
내가 문제를 푸는 과정을 수식화할 수 있을까?
문제를 단순화할 수 없을까?
그림을 그려볼 수 있을까?
수식으로 표현할 수 있을까?
문제를 분해할 수 있을까?
뒤에서부터 생각해서 문제를 풀 수 있을까?
순서를 강제할 수 잇을끼?
특정 형태의 답만을 고려할 수 있을까?
Chap3. 코딩과 디버깅에 관하여
3.1 도입 : 코딩의 중요성을 간과하지 말라.
3.2 좋은 코드를 짜기 위한 원칙
- 간결한 코드 작성
- 적극적으로 코드 재사용하기
- 표준 라이브러리 공부하기
- 항상 같은 형태로 프로그램을 작성하기
- 일관적이고 명료한 명명법 사용하기
- 모든 자료를 정규화해서 저장하기
- 코드와 데이터를 분리하기
3.3 자주 하는 실수
- 산술 오버플로
- 배열 범위 밖 원소에 접근
- 일관되지 않은 범위 표현방식 사용
- Off-by-one 오류 : >를 >=로 쓰는 등의 사소한 오류
- 컴파일러가 잡아주지 못하는 상수 오타
- 스택 오버플로
- 다차원 배열 인덱스 순서 바꿔 쓰기
- 잘못된 비교 함수 작성
- 최소, 최대 예외 잘못 다루기
- 연산자 우선순위 잘못 쓰기
- 너무 느린 입출력 방식 선택
- 변수 초기화 문제
3.4 디버깅과 테스팅
디버깅에 관하여 : 프로그래밍 대회에선 디버거를 쓰기 좋지 않을 경우가 많다
- 작은 입력에 대해 제대로 실행되나 확인하기
- 단정문을 쓴다
- 프로그램의 계산 중간 결과를 출력한다
테스트에 대하여
- 입력을 자동 생성해주는 함수를 만들어 test input량을 늘릴 수 있다.
3.5 변수 범위의 이해
- 산술 오버플로
- 너무 큰 결과
64bit 정수를 사용해야 하지만 습관적으로 32bit를 쓰는 경우가 많다
- 너무 큰 중간 값
프로그램의 출력 값의 범위는 작지만 중간 과정에서 큰 값을 일시적으로 계산해야 하는 경우.
- 너무 큰 무한대 값
애매하게 설정한 무한대 값(단순한 큰 값)이 서로 더해지거나 곱해지는 경우가 없는지 잘 살펴보기.
저자는 987654321을 자주 사용함.
- 오버플로 피해가기
- 자료형의 프로모션
이항 연산자에서 피연산자의 자료형이 다르거나 범위가 작은 경우 컴파일러가 대개 같은 자료형으로 변환해 계산하는데, 이것이 프로모션.
오버플로가 일어나거나 값이 강제로 부호 없는 정수로 캐스팅되는 과정에서 오류가 일어나기도 한다.
3.6 실수 자료형의 이해
- 실수 연산의 어려움
- 실수와 근사 값
컴퓨터가 사용하는 실수 표현 방식과 그 장단점을 이해해야만 함
- IEEE754 표준
이진수로 실수룰 표기하며, 부동 소수점 표기법이다. 무한대, 비정규 수, Nan(Not a Number) 등의 특수한 값이 존재한다.
- 실수의 이진법 표기
예를 들어 1011.101(2)의 경우, 소수부의 첫 자리의 크기는 1/2, 세 번째 자리는 1/8이다. 그러므로 더하면 소수부의 크기는 0.625가 된다
- 부동 소수점 표기
정수부에 너무 많은 비트를 사용하면 소수부의 정확도가 떨어지고 소수부에 너무 많은 비트를 배정하면 큰 수 표현이 힘듦.
이문제 해결을 위해 IEEE754를 포함한 대부분의 실수 표준에선 소수점을 옮길 수 있도록 함. 어떤 형태의 숫자건 소수점을 적절히 옮겨 소수점 위에 한자리만 남도록 한 뒤. 최상위 비트에서부터 표현할 수 있는만큼 표시하고 나머지는 반올림 처리하는 것. 1101.101(2)는 소수점을 왼쪽으로 세 칸 옮기면 1.011101이 되고, 이 수를 맨 아펭서부터 저장 공간이 허락하는 만큼 저장하는 것
- 실수 비교하기
- 하나. 비교할 실수의 크기들에 비례한 오차 한도를 정한다.
- 둘 상대 오차를 이용한다
- 대소 비교
- 정확한 사칙연산
- 코드의 수치적 안정성 파악하기
- 경고
'개발 공부 > Algorithm' 카테고리의 다른 글
| [LeetCode] 2390. Removing Stars From a String (1) | 2024.12.10 |
|---|---|
| [LeetCode] 338. Counting Bits (1) | 2024.12.10 |
| [LeetCode] 435. Non-overlapping Intervals (1) | 2024.12.08 |
| it 취업을 위한 알고리즘 문제풀이 - 1. 코드 구현력 기르기 (1) | 2020.09.16 |
| 알고리즘 문제 해결 전략 Part02. 알고리즘 분석 (1) | 2020.07.09 |
