01 문제 해결 시작하기

시작 이유

알고리즘 테스트에 대한 공부의 필요성을 느낌.

 

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략이라는 책으로 시작.

구종만씨가 지음.

 

개관

개발자의 실력에 따른 생산성의 차이가 크다.

그 이유는 교육과정이 프로그래밍 기술과 지식만 가르치고, 응용할 수 있는 능력을 기르지 못하고 있다.

 

알고리즘이 생겨난 배경과 설계 시 필요한 통찰을 얻어야한다.

알고리즘의 원칙을 이해하고 변형할 수 있어야 프로그래밍 문제를 풀 수 있다.

 

이 책은 프로그래밍 대회 문제를 풀며 알고리즘 설계 기법과 자료구조를 직관적으로 이해하고, 알고리즘 문제 해결 능력을 키울 수 있도록 구성되어 있다.

문제를 풀어가면서 개념과 구조를 경험적으로 이해하는 것이 이 책의 목표이다.

 

요약: 문제를 풀어 알고리즘의 개념을 이해하고 변형할 수 있는 능력을 기르자.

 

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

1.1 도입

프로그래머는 다양하다. 분야간 차이를 뛰어넘는 좋은 개발자의 기준이 있을까?

 

 

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

프로그래밍을 할 때 여러가지 지식이 사용된다.

언어의 특성

작동 환경에 대한 특성(프로그램이 동작할 하드웨어와 운영체제에 관한 지식)

라이브러리 관련 지식(사용하고 있는 라이브러리들에 대한 유의사항)

가용 메모리

동작 시간 제한

재사용성이 좋은 코드 작성법

 

많은 제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력은 좋은 프로그래머가 되기 위해 필수적이다.

 

이 책에서는 이런 능력을 문제해결 능력이라고 한다.

사용 언어나 라이브러리, 알고리즘에 대한 지식을 이용해 시스템을 만들어 내는 것이 문제해결능력이다.

 

1.2 프로그래밍 대회

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

 

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

1. 문자열 데이터를 입력하고, 문자열 데이터를 출력한다. 문제해결에만 집중할 수 있다.
2. 시간제한과 메모리 제한이 있다. 알고리즘 설계기법과 자료구조를 사용하는 계기가 된다.
3. 정답과 오답 여부가 명확하다. 정확한 프로그램을 짜는 훈련이 된다.
4. 제출한 코드의 실행 시간이나 메모리 사용량 관련 정보가 제공되어 효율성을 확인할 수 있다.
5. 개발의 작은 부분에 집중해, 좋은 코드 작성에 도움이 된다.
6. 다른 개발자와의 공유로 성장의 계기가 된다.

1.3 책 읽는 방법

7부로 이루어져있다.

1~2부는 기초 지식.

나머지 부분은 알고리즘 설계 기법과 자료구조등 문제 해결에 필요한 기술을 소개한다.

 

책의 문제는 알고 스팟에서 실제 대회와 비슷한 환경에서 채점 가능.

https://algospot.com/

 

컴퓨터 공학과 학부생을 타겟.

C++과 STL사용

 

 

02 문제 해결 개관

2.1 도입

무작정 풀면 안된다.

 

2.2 문제 해결 과정

문제 해결 연구의 고전 '어떻게 풀 것인가'에서의 네 단계 문제해결 과정

1. 문제를 이해한다.
2. 어떻게 풀지 계획을 세운다.
3. 계획대로 수행하여 문제를 해결한다.
4. 어떻게 풀었는지 돌아보고, 개선방법을 찾는다.

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

1. 문제를 읽고 이해한다.
2. 문제를 익숙한 용어로 재정의한다.
3. 어떻게 해결할지 계획을 세운다.
4. 계획을 검증한다.
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.

1단계: 문제를 읽고 이해하기

문제의 요구사항과 제약조건을 정확히 파악해야한다.

 

2단계: 재정의와 추상화

자신이 다루기 쉬운 개념으로, 문제를 자신의 언어로 풀어 쓰는 것.

문제의 요구를 직관적으로 이해하기 위해 필요하다.

 

3단계: 계획 세우기

문제를 어떻게 해결할지 결정하고, 사용할 알고리즘과 자료구조를 선택한다.

 

4단계: 계획 검증하기

바로 구현하는 것이 아니라, 계획 검증이 필요하다.

설계한 알고리즘이 요구조건을 만족시키는지 확인해야한다.

 

5단계: 계획 수행하기

프로그램을 작성한다.

 

6단계: 회고하기

장기적인 성장에 영향을 미치는 단계다.

문제를 해결한 과정을 돌아보고 개선하는 과정이다.

문제 해결의 더 좋은 방법을 발견하는 기회이다.

 

문제를 풀 때마다 코드와 경험을 기록으로 남겨라.

어떻게 접근했는지, 어떻게 풀었는지, 어떤 깨달음이 문제 푸는데 도움을 주었는지 기록하자.

 

풀지 못한 경우 오답 원인도 작성하자.

오답 기록을 작성하면서 틀리는 부분과 원인을 파악할 수 있다.

 

그리고 다른 사람의 풀이도 참고, 분석하라.

 

문제를 풀지 못할 때

초보 수준의 경우 한 문제에 너무 매달려 있지 말라.

단, 다른 사람의 풀이를 참조하는 경우 반드시 복기를 동반해야 한다.

왜 내가 풀지 못 했는가를 살펴봐야한다.

 

2.3 문제 해결 전략

직관과 체계적인 접근

문제와 답의 구조에 대한 직관의 중요성.

직관은 문제 해결의 알고리즘이 어떤 형태를 가질지 예측할 수 있게 한다.

막막한 문제를 해결하며 경험을 쌓아가야 한다.

 

막막한 문제는 어떻게 해결해야할 것인가.

체계적으로 백지에서 시작해 해결을 위한 기반을 차근차근 쌓아 올리면서 전진하는 것.

 

비슷한 문제를 풀어본 적이 있던가?
이전 경험을 활용해 문제를 풀 수 있다.

그러기 위해서 원리를 이해하고 변형할 수 있어야 한다.

 

문제에 맞는 알고리즘을 적용하기 위해서는 알고리즘의 동작 과정과 원리를 완전히 이해해야 한다.

 

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

가장 단순히 문제를 해결할 수 잇는 방법을 만들어 본다.

이 방법을 개선하고 참고해서 문제를 풀 수 있다.

위 알고리즘으로 문제를 풀 수 없다 하더라도, 효율성을 파악하는 기준선이 될 수 있다.

 

예) 완전 탐색->너비우선 탐색->요소 중복 제거 -> 순서 중복 제거 를 통해 경우의 수를 구하는 알고리즘이 개선 될 수 있다.

 

문제 푸는 과정을 수식화할 수 있을 까?

새로운 방향에서 접근해야 풀리는 문제도 만나게 된다.

손으로 간단한 입력을 직접 해결해 보며 방법을 찾을 수 있음.

 

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

제약조건을 없애거나, 계산해야할 변수를 줄이거나, 차원 수를 낮추거나 하는 방법으로 접근할 수 있음.

 

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

문제에 관련된 그림을 그려 직관적으로 받아들일 수 있다.

 

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

수식으로 표현하는 하는 것이 도움이 되는 경우도 있음.

 

문제를 분해할 수 있을까?

더 다루기 쉬운 형태로 문제를 변형.

 

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

거꾸로 하면 해결이 쉬운 경우가 있음.

 

순서를 강제할 수 있을까?

순서를 특정지어 중복이 사라진다면 강제할 수 있다.

 

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

순서 강제 기법의 연장선으로 정규화 기법이 있습니다.

정규화란 우리가 고려해야 할 답들 중 형태가 다르지만 결과적으로는 똑같은 것을 그룹으로 묶은 뒤, 각 그룹의 대표들만 고려하는 방법이다.

 

2.4 더 읽을거리

어떻게 문제를 풀 것인가 (How to solve it)은 문제해결의 고전으로 문제 해결에 있어 다양한 전략들을 나열합니다.

시간나면 읽기.

 

 

03 코딩과 디버깅에 관하여

3.1 도입:코딩의 중요성을 간과하지 말라

읽기 쉬운 코드를 작성하라.

가독성이 좋아야 디버깅도 쉽고, 정확하게 작성할 수 있다.

자신의 코드 스타일을 간결하고 일관되게 다듬으려 노력하라.

 

간결하고 효율적인 프로그램을 작성하는 능력이 중요

 

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

간결한 코드를 작성하기

코드가 짧을 수록 오타나 버그가 생길 가능성이 줄고, 디버깅도 쉬워진다.

 

일반적인 프로그래밍과 다르게 테스트에서는 전역변수를 사용하는 경우가 많다.

 

C/C++ 매크로를 사용해 간결한 코드를 작성하기도 한다.

 

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

간결한 코드를 위한 직접적인 방법은 코드를 모듈화 하는 것이다.

 

반복되는 코드를 함수나 클래스로 분리해 재사용.

 

이상적인 세계에서는 한 함수가 두 가지 이상의 일을 해서는 안된다고 한다.

입력을 읽어들이는 함수, 입력을 처리하기 쉬운 형태로 바꾸는 함수, 실제 문제를 푸는 함수가 분리되어야 한다는 말이다.

 

그러나 프로그래밍 대회에서는 엄격히 원칙을 따르지 못한다.

 

표준 라이브러리 공부하기

기초적인 자료구조를 직접 작성하는 것은 시간낭비이다.

문자열, 동적배열, 스택, 큐, 리스트, 딕셔너리 등의 자료구조와 정렬 등의 표준 라이브러리 사용법을 익히자.

 

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

검증된 코드는 같은 형식대로 작성한다.

도구가 아닌 문제에 집중.

 

일관되고 명료한 명명법 사용하기

네이밍 컨벤션.

함수 이름도 기능을 의미하도록 작성.

 

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

같은 자료를 다른 형태로 저장하지 말아야한다.

자료를 표현하는 클래스 생성자나 데이터를 입력받자마자 정규화를 수행하라.

 

3.3 자주 하는 실수

산술 오버플로우

변수의 표현 범위를 넘어서는 경우

 

버퍼 오버플로우

배열 범위 밖 원소에 접근하는 오류

 

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

대부분의 프로그래밍 언어는 반열린 구간을 사용한다.

첫번째 값은 집합에 포함하고, 다른하나는 포함하지 않는다.

 

Off-by-one 오류

계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 많아서 틀리는 코드의 오류를 말한다.

오류를 방지하는 방법은 최소 입력이 주어졌을 때 이 코드가 어떻게 동작할 지를 되새겨 보는 것이다.

 

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

값 자체를 잘못 써서 생기는 문제.

 

스택 오버플로우

재귀 호출의 깊이가 너무 깊어지는 경우 생긴다.

지역변수로 선언한 배열이나 클래스 인스턴스가 너무 큰경우 발생할 수도 있다.

 

때문에 자동으로 힙에 메모리를 할당하는 STL컨테이너를 쓰거나 전역변수를 사용한다.

 

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

평소에는 잘 사용하지 않는 다차원 배열을 사용하면서 순서를 헷갈리는 경우가 있음.

가능한 배열에 접근하는 위치를 통일하는 것이 좋음.

 

3.4 디버깅과 테스트

디버깅에 관하여

대회에서는 디버거보다 직접 검증하는 것이 더 빠르다.

 

-작은 입력에 대해 잘 작동되는지 확인하기

-assertion을 쓴다. 주어진 조건이 거짓인 경우 오류를 내고 프로그램이 종료된다.

-프로그램의 계산 중간 결과를 출력한다.

 

테스트에 관하여

가장 작은 입력, 가장 큰 입력, 예제 입력의 변형 등을 통해 테스트 해보는 것이 좋다.

 

스캐폴딩 기법.

코드를 개발할 때 뼈대를 잡기 위해 임시로 사용하는 코드.