[알고리즘 문제 해결 전략] 1. 문제 해결 시작하기

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

프로그래밍에서의 문제해결과 프로그래밍 대회 및 참고 사이트에 다룹니다.

- 프로그래밍은 문제 해결이다.

프로그래밍을 하기 위해선 많은 것을 알아야한다.
자신이 사용하는 언어의 특성, 프로그램이 동작할 하드웨어와 운영체제에 관한 지식, 사용하고 있는 라이브러리들에 대한 유의사항, 프로그램이 사용할 수 있는 최대 메모리와 사용자가 답답하지 않게 하기 위한 시간 제한, 재사용성이 높은 간결한 코드를 작성하기 위한 노력등이 필요하다.
이런 제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력은 분야를 막론하고 좋은 프로그래머가 되기 위해 필수적이다. 이 책에서는 이런 능력을
문제 해결 능력
이라고 부른다.
하지만 문제 해결 능력을 훈련하기란 굉장히 어렵다. 추상적인 기술이기 때문이다.
자기 계발을 하고 싶은 프로그래머는 새로운 언어와 프레임워크, 개발 방법들을 계속 배워 나가지만 이들을 조합하는 방법에 대해서는 배울 곳이 없다.
좋은 프로그래머가 되기 위한 좀더 나은 방법은 없을까?

- 프로그래밍 대회

프로그래밍 대회에 참가하는 것은 문제 해결 기술을 연마하기에 가장 좋은 방법이라 할 수 있다.

다양한 종류의 프로그래밍 대회들이 있지만, 이 책에서 다루는 프로그래밍 대회들은 주로 짧은 요구사항을 제시하고, 이에 맞는 프로그램을 시간 안에 빠르게 작성하는 능력을 겨루는 대회이다.

프로그래밍 대회에서 배울 수 있는것들

GUI 사용하지 않고 텍스트 파일을 읽고 텍스트 파일을 출력하기에 다른 데 정신을 빼앗기지 않고 문제 해결에 집중가능
명시적인 시간 제한과 메모리 제한이 있다. 제약 안에서 문제를 해결할 수 있는 알고리즘을 신중히 설계해야 한다. 때문에 다양한 알고리즘 설계 기법과 자료 구조를 직접 사용해 볼 수 있는 계기가 되고, 알고리즘에 사용된 원칙들을 이해하고 변형해야 풀 수 있는 문제들이 많이 출제 되기에 깊이 이해하는데 큰 도움이 된다.
정답과 오답의 여부가 훨씬 명확히 가려진다. 자신이 작성한 코드에 대해 빠르고 객관적인 피드백을 받을 수 있어 예외 없고 정확한 프로그램을 짜는 아주 좋은 훈련이 된다.
제출한 프로그램의 실행 시간이나 메모리 사용량 관련 정보가 실시간으로 제공 되기 때문에, 프로그램을 고쳐 가며 작은 변경이 프로그램의 효율성에 미치는 영향을 직접 체험해 볼 수 있다. 논리적 구조가 복잡한 프로그램의 수행 성능을 예측하는 데 익숙해지기 때문에 실무에서 퍼포먼스가 중요한 프로그램을 짜는데도 큰 도움이 된다.
문제를 처음부터 짜게 되는데 대형 프로젝트에서 간과했던 프로그램의 작은 부분에 집중할 수 있는 계기를 만들어 준다.
경쟁하는 환경에서 코드를 작성하기에 내적 동기를 이끌어 낼 수 있고 다른 사람의 코드와 자신의 코드를 비교 가능하다.

- 국내에서 참가할 수 있는 프로그래밍 대회

한국 정보 올림피아드
ACM-ICPC ( ACM 대학생 프로그래밍 경시대회)
탑코더 (TopCoder)
구글 코드 잼 (Google Code Jam)
기타 온라인 대회와 모의고사들
- 탑코더(https://www.topcoder.com/)
- 코드포스(https://codeforces.com/)
- 바야돌리드 대학교 온라인 채점 사이트(https://onlinejudge.org/)

- 대회 준비를 위한 조언

가능한 많은 문제 풀기
온라인 채점 사이트 이용하기
- 알고스팟 온라인 채점 사이트(https://www.algospot.com/)
- 백준(https://www.acmicpc.net/)
- USACO Training Program
- TopCoder(https://www.topcoder.com/)
- ACM-ICPC Live Archive
- Project Euler (https://projecteuler.net/)
- SPOJ Online Judge(https://www.spoj.com/)

2. 문제 해결 개관

프로그래밍 대회에서 문제를 해결하는 방법에 대해 다룹니다.

- 문제 해결 과정

인류에게 알려진 가장 강력한 일반적인 문제 해결 알고리즘 [ 리처드 파인만 (Richard Feyn-man) ]

1. 칠판에 문제를 적는다.

2. 골똘히 생각한다.

3. 칠판에 답안을 적는다.

프로그래밍 대회를 위한 여섯 단계 문제 해결 알고리즘

1. 문제를 읽고 이해한다.

2. 문제를 익숙한 용어로 재정의한다.

3. 어떻게 해결할지 계획을 세운다.

4. 계획을 검증한다.

5. 프로그램으로 구현한다.

6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.

1. 문제를 읽고 이해하기

제한 시간에 조급해서 입출력 예제를 보고 단편적으로 이해하지 말고, 문제 설명을 공격적으로 읽으며 문제가 원하는 바를 완전히 이해하는 과정이 필요하다. 사소한 제약 조건을 잘못 이해하면 산으로 간다.

2. 재정의와 추상화

자신이 다루기 쉬운 개념을 이용해, 문제를 자신의 언어로 풀어쓰기

문제가 요구하는 바를 직관적으로 이해하기 위해 꼭 필요하며, 요구하는 바가 복잡한 문제일 수록 그 중요성이 더해짐

현실 세계의 개념을 어느정도의 본질만 남기고 비교적 다루기 쉬운 수학적/전산학적 개념으로 다루기 쉽게 옮겨 표현하기.

3. 계획 세우기

어떤 방식으로 해결할지 결정하고, 사용할 알고리즘과 자료구조를 선택하기.

4. 계획 검증하기

설계한 알고리즘이 모든 경우에 요구 조건을 정확히 수행하는지 증명하고, 수행에 걸리는 시간과 사용하는 메모리가 문제의 제한 내에 들어가는지 확인하기.

5. 계획 수행하기

아무리 천재적인 알고리즘을 구현했더라도 그 구현이 부정확하거나 비효율적이면 프로그램은 정확히 동작할 수 없으니 알잘딱으로 구현하기.

6. 회고 하기

자신이 문제를 해결한 과정을 돌이켜보고 개선하는 과정 갖기.

효과적인 회고를 위해 문제를 풀 때마다 코드와 함께 자신의 경험을 기록으로 남기는 것.

이때 간단한 해법과 함께 어떤 방식으로 문제에 접근했는지, 그리고 문제의 해법을 찾는데 결정적이었던 깨달음은 무엇인지 기록하기.

맞추지 못한 경우 오답 원인 및 접근방법을 적는 오답 노트를 적어서 반복되는 실수 줄이기

다른 사람의 코드를 보며 자신이 생각하지 못했던 통찰얻기

문제를 풀지 못할때

일정 시간이 지나도록 고민해도 답을 찾지 못할 때는 다른 사람의 소스 코드나 풀이를 참조하기

단 참조했다면 반드시 복기를 동반하기

주의

문제 풀이 알고리즘에 자신을 맞추지 말고 적합하게 활용하기.

- 문제 해결 전략

직관과 체계적인 접근

직관은 해당 문제를 해결하는 알고리즘이 대략적으로 어떤 형태를 가질지 짐작하게 해준다.

다만 직관은 얼핏 보기엔 막막한 문제들을 해결하며 차곡차곡 경험을 쌓아 나가야 한다.

그렇다면 막막한 문제는 어떻게 해결해야 하는가?

백지에서 부터 시작해 문제를 해결하기 위한 기반을 차근차근 쌓아올리며 점진적으로 접근하는 체계적인 방법을 통해 접근할 수 있다.

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

1. 비슷한 문제를 풀어 보기 (문제에 사용된 알고리즘의 동작 과정, 원리를 완전히 이해하고 비슷한 응용 문제 대응)

2. 단순한 방법에서 시작하기 (무식하게 풀 수 있을까? -> 단순한 동작과정을 가정하고 조건을 점차 줄여나가기)

3.문제를 푸는 과정을 수식화 하기 ( 손으로 여러 간단한 입력을 해결해보며 공식화)

4. 문제를 단순화 시키기 ( 제약 조건을 없애거나, 변수를 줄이거나, 다차원을 1차원으로 변경)

5. 그림 그려보기 ( 시각적으로 직관을 얻을 수 있는 방법)

6. 수식으로 표현해보기 ( 평문으로 쓰인 문제를 수식으로 변경)

7. 문제 분해하기 ( 문제에 주어진 복합한 조건을 더 단순한 형태로 갖는 조건의 집합으로 분해하기)

8 . 뒤에서 부터 생각해보기 ( 문제에 내재된 순서를 바꿔보기 ) ex) 사다리 타기

9. 순서를 강제시키기 ( 순서가 없는 문제에 순서 강제 해보기 )

10. 특정 형태의 답만을 고려해보기 ( 수 많은 답안의 범위를 축소 시켜 특정 형태의 답만 나오도록 가정하기 ) ex) 원 덮기 문제

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

코딩과 디버깅의 중요성 및 권장하는 사용법에 대해 다룹니다.

코딩의 중요성을 간과하지 말라

당장 빨리 코드를 작성하기 보다, 읽기 쉬운 코드 작성하기, 즉 간결하고 효율적인 프로그램을 작성하는 능력을 기르자.

그리고 이를 자신만의 코드 스타일로 다듬자.

좋은 코드를 짜기 위한 원칙

간결한 코드를 작성하기

전역변수의 광범위한 사용 지양하기
foreach 구문등의 사용으로 짧고 한눈에 보이는 코드

적극적으로 코드 재사용하기

모듈화하기 ( 3번 이상 재사용한 기능은 메서드로 빼기)
한 함수가 한가지 일을 하는것이 이상적이지만 적절한 선에서 타협하기.

표준 라이브러리 공부하기

검증된 라이브러리를 적극적으로 사용하기
문자열, 동적배열, 스택, 큐, 리스트, dict등의 자료구조, 정렬등의 표준 알고리즘 구현법을 숙지할 것

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

동일한 기능의 코드에 대해 개선할 점을 고민하기
자주 작성하는 알고리즘이나 코드 등은 한번 검증된 코드로 작성하고 꾸준히 사용하기
도구가 아닌 문제에 집중하기 위함

일관적이고 명료한 명명법 사용하기

함수명은 의도를 명확하고 단순하게
ex) bool judge(int y, int x, int cy, int cx, int cr) -> bool (int y, int x, int cy, int cx, int cr)
naming Convention 생각하기

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

같은 자료를 두 가지 이상의 형태로 저장하지 않기 ex) 9/6 ... 3/2로 기약분수화 하여 저장
정규화 시점 일관화 => 자료표현 클래스 생성자에서 정규화 또는 외부 자료 입력시 정규화

코드와 데이터 분리하기

날짜를 다루는 프로그램일 경우
month 정보를 가진 문자열을 코드와 혼재하지 말고 month 배열로 따로 저장하여 사용하기
다른 예로는 달의 날짜를 배열화, 체스판의 기본정보 등

자주 하는 실수

산술 오버플로 (이후 따로 다룸)

배열 범위 밖 원소에 접근

배열 크기를 정할 때 계산을 신중히 하라.

일관되지 않은 범위 표현 방식 사용하기

부등호 사용시 일관된 사용하여 스스로 오해의 소지를 만들지 말자.

닫힌 구간(closed interval) - 범위내 첫 번째 값과 마지막 값으로 해당 범위를 표현하는 방식

공집합을 우아하게 표현할 수 있는 방법이 없는 단점

열린 구간(open interval) - 양 끝의 경계를 포함하지 않는 집합

열린구간에서 0부터 시작하는 경우 음수를 사용해 부자연스러움

이를 해소하고자 반 열린 구간을 사용 (0 <= idx < n) -> 자연어세서 사용하는 범위와 다르다는 이유 때문에 문제가 생기는 경우가 종종 있음. -> 프로그램 내에서 한 가지 방법으로만 범위를 표현할 필요가 있다. 프로그래밍 언어가 지원하는 범위 표현 방식을 따르는 것이 가장 효율적.

Off-by-one 오류

1을 간과해서 생기는 오류

ex) 100미터 담장에 10m 간격으로 기둥 박기 (0m라도 기둥 한개를 박아야 한다.)

i부터 j까지의 평균을 구하려면 avg(j - i + 1) | A[1] 부터 A[1] 평균을 구하려면 0이 아닌 1이다.

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

'오타주의'

스택 오버플로

재귀 호출의 깊이가 깊어지면 고려하기 힘듬 -> 스택 최대 크기를 고려하자.

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

4, 5차원의 고차원 배열 사용시 인덱스 순서를 헷깔리기 쉬우니 주의

memoization시 주의

잘못된 비교 함수 작성

1. a < a는 항상 거짓이다. 이 성질을 비반사정(irreflexivity)라고 한다.

2. a < b 참이면 b < a는 거짓이다. 이 성질을 비대칭성(asymmetry)이라고 한다.

3. a < b 참이고 b < c 가 참이면 a < c 이다. 이 성질을 전이성(transitivity)이라고 한다.

4. a < b 와 b < a가 모두 거짓이면 a와 b는 같은 값으로 간주한다. a와 b가 같고, b와 c가 같다면 a와 c도 같아야 한다.

이 성질을 상등 관계의 전이성 (transitivity of equivalence)라고 한다.

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

가장 작은 입력과 가장 큰 입력에 대한 고려

Example Code

bool isPrime(int n) {
	if(n % 2 == 0) return false;
    for(int i = 2; i < n; ++i)
    if(n % i == 0)
    	return false;
    return true;
}// 2는 짝수이며 소수인데 이를 간과

bool isPrime(int n) {
	if(n == 2) return true;
    if(n % 2 == 0) return false;
    for(int i = 2; i < n; ++i)
    if(n % i == 0)
    	return false;
    return true;
}// 2를 챙겼지만 1을 간과

연산자 우선순위 잘못 쓰기

ex) if(b & 1 == 0) != if(b & (1 == 0)

너무 느린 입출력 방식 선택

ex) String으로 문자열 조작 대신 StringBuffer나 StringBuilder를 사용

System.out.println() 대신 BufferedWrite 사용

변수 초기화 문제

대회에선 보통 프로그램 1회 실행하여 여러 입력에 대해 답처리를 요구한다.

이전 입력에서 사용된 전역 변수의 값이 초기화 없이 사용되는것에 주의

이를 방지하기 위해 예제 입력 파일을 두 번 이상 반복해 사용해 봄으로서 방지 할 수 있다.

디버깅과 테스팅

디버깅에 관하여

대회에서 디버거의 사용은 유용성이 제한된다.

간결한 코드를 작성하기 때문에 눈으로 디버깅하는 것이 빠를 경우도 있고

재귀 호출이나 중복 반복문을 사용하여 디버거의 효용성이 떨어진다.

ACM - ICPC등 3명이 출전하는 대회에서 디버거를 사용하면 나머지 두명은 손빨고 있어야 한다.

디버거를 사용하는 대신 다음 과정을 통해 디버깅을 하면 좋다.

작은 입력에 대해 실행여부를 확인하기
단정문(assertion)을 쓴다.
- 주어진 조건이 거짓일 때 오류를 내고 프로그램을 강제 종료 시키는 함수 또는 구문
프로그램 계산 중간에 결과를 출력해보기
- 자신의 예상 결과와 대조하며 문제코드를 소거법으로 줄여 범위를 좁힐 수 있다.

테스트에 관하여

답안 작성 이후 제출 전에 예제 입력을 만들어 가능한 한 많이 프로그램을 테스트 하는 것이 좋다.

예제 입출력 외에도 몇 가지 간단한 입력을 직접 만들어 넣어보면 오답률을 줄일 수 있다.

가장 작은 입력이나, 가장 큰 입력 등등

스캐폴딩 기법을 활용

스캐폴딩이란 건물을 짓거나 보수시 공사인원이 걸어다니기 위해 설치하는 임시 구조물을 의미한다.

프로그래밍에서의 스캐폴딩기법이란 개발 뼈대를 잡기 위한 임시 코드 등을 의미한다.

이는 코드의 정당성이나 반례 찾기에 유용하다.

변수 범위의 이해

산술 오버플로

너무 큰 결과
- 큰 정수를 다룰 시 변수의 형태에 주의(자료형)
너무 큰 중간 값
- 중간 과정에서 큰 값을 임시적으로 계산주의 / ex) lcm, gcd -> lcm(50000, 100,000) -> 5 * 10^9 (21억 초과) int 범위 벗어남
너무 큰 '무한대' 값
- 문제를 풀다보면 무한대에 해당하는 큰 값을 이용하는 것이 편리할 때가 있다.
- 이 값을 더해지거나 곱하는 경우가 생기므로 이를 확인 할 수 있는
- 987,654,321 값이 적절하다. (오버플로 내지 않고 오타 났는지 확인이 쉬움)
오버플로 피해가기
- 자료형을 더 큰 자료형으로 캐스팅
- 오버플로가 나지 않도록 연산 순서를 변경
자료형의 프로모션
- 피 연산자의 자료형이 다르거나 자료형의 범위가 너무 작은 경우 같은 자료형으로 자동적으로 변경하는것
- 부호 없는 정수와 부호 있는 정수가 섞였을 때 주로 문제가 되니 주의

실수 자료형의 이해

실수 연산의 어려움

컴퓨터의 실수 표현방식은 사람들의 표현 방식과 다르기에 연산이 어렵다.

실수와 근사값

컴퓨터는 일상생활에서 사용하는 정수의표현은 정확히 표현 가능하다.

하지만 일상생활에서 사용하는 실수값 (20000원을 3명이 더치페이 -> 6666.666666.... / pie) 등은 무한대

IEEE 754 표준

이진수 실수표기
부동소수점(floating-point) 표기
무한대, 비정규수, Nan(숫자아님) 등의 특수값이 존재

실수의 이진법 표기

소수점 밑 i번째 자리의 크기는 1/2^i

이진법으로 쓴 실수 1011.101의 경우 정수부는 2^3 + 2^1 + 2^0 = 8 + 2 + 1 = 11이 된다.

소수부의 경우 1/2^0 + 1/2^3 = 0.625 => 11.625가 된다.

부동 소수점 표기

https://ko.wikipedia.org/wiki/%EB%B6%80%EB%8F%99%EC%86%8C%EC%88%98%EC%A0%90

실수 비교하기

비교할 실수의 크기들에 비례한 오차 한도를 정한다.
상대 오차를 이용한다.
- 입력값이 미지수일때 비교할 두 수의 크기에 비해 그 차이가 작다면 두 수가 같다고 판정

대소 비교

비교할때 항상 두 값이 같은 경우, 즉 두 값이 아주 가까운 경우를 먼저 확인하고 처리해주기

정확한 사칙연산

BigDecimal 등을 이용 ( 큰 정수 변수에 소숫점 위치 옮기기 )

코드의 수치적 안정성 파악하기

numerically stable ( 연산 오차가 요구치보다 아주 미미해서 결과에 큰 영향을 끼치지 않는 것 ) 파악하기

경고

컴퓨터에서 실수의 표현은 매우 복잡하고 방대한 주제이다.

위의 주의점등은 IEEE 754가 표현할수 있는 특수 수 (NaN, 무한대)에 대해 다루지 않는 등 한정적이므로

실수 연산에 대한 모든 것을 알았다고 생각하지 않기

실수 연산 아예 하지 않기

곱셈과 나눗셈의 순서를 바꾸기
- 세 정수 (a / b * c) 를 계산할때 이 값이 항상 정수라고 가정한다면
- ((a * c) / b) 형태로 수식을 변경한다면 실수 사용 없이 계산 할 수 있다.
양변에 제곱하기
실수 좌표가 있는 기하문제일 경우 좌표계 가로, 세로에 정수배로 늘리면 정수만으로 문제 풀이 가능

저작자표시

'Algorithm > 개념 정리' 카테고리의 다른 글

[알고리즘 문제 해결 전략] 알고리즘 분석 (0)	2022.12.14
[알고리즘 문제 해결 전략] 시작하기 (0)	2022.12.04
클래스란? (0)	2022.11.11
배열 복제하기 (0)	2022.11.11
소수 나열하기 (0)	2022.11.11

티스토리툴바