[알고리즘 문제해결전략 1권] 1, 2장 필요한 것만 간단 정리

머리말

처음부터 완전한 체계를 갖추고 발전하는 학문은 없으므로, 발전 과정에서 학자들은 모두 어둠 속에서 직관에 의존해 헤매게 된다.(삽질한다.)

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

1.1 도입

메모리, 시간 제한, 재사용성, 간결성 을 고려해야함

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

1.2 프로그래밍 대회

1. 그래픽 인터페이스 x

   텍스트 => 텍스트

2. 시간 제한, 메모리 제한 존재

   다양한 알고리즘 설계기법, 자료구조 사용

3. 정답, 오답의 여부가 명확

   빠르고 객관적인 피드백을 주기 때문

4. 제출한 프로그램의 실행 시간, 메모리 사용량이 제공

   작은 변경이 어떻게 영향을 끼치는지 볼 수 있음

5. 작은 작업이라 완벽하게 작성할 수 있음

6. 경쟁하는 환경

   경쟁은 동기가 되기도 함

   제출된 소스를 모두 공개하는 대회가 많음

1.4 국내 프로그래밍 대회

ACM-ICPC

대학생 대상 (3인 1조)

탑코더

온라인 대회가 잦음

코드포스

바야돌리드 대학교 온라인 채점 사이트

구글 코드 잼

1.5 대회 준비를 위한 조언

가능한 많은 문제

온라인 채점 사이트 이용

개인 노트북 준비 ( 여기서 노트북은 유용한 코드를 옮겨적어둔 것 )

2. 문제 해결 개관

2.2 문제 해결 과정

파이만 알고리즘

1. 칠판에 문제를 적는다.
2. 골똘히 생각한다.
3. 칠판에 답을 적는다.

문제 해결 과정을 단계별로 나누었다 *

문제를 적어보았다 *

현재 쓰이는 알고리즘

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

1단계 문제 읽고 이해하기

문제의 궁극적인 목적과 사소한 제약 조건까지 이해하기

2단계 재정의와 추상화

다루기 쉬운 개념으로 자신의 언어로 풀어쓰기

문제의 추상화

현실세계의 개념을 수학적/ 전산학적 개념으로 표현하는 과정

어떤 부분을 추상화할 것인지 훈련하기!

3단계 계획 세우기

사용할 알고리즘, 자료구조 결정

4단계 계획 검증하기

요구조건을 정확히 수행하는지

시간과 메모리가 조건에 부합한지

5단계 계획 수행하기

프로그램 작성

6단계 회고하기

장기적으로 가장 큰 영향을 미침

• 기록하기
• 다른 사람의 코드 보기

2.3 문제 해결 전략

직관과 체계적인 접근

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

막막하면 체계적인 접근을 해야함

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

비슷한 문제를 풀어본 적이 있는가?

이전에 적용했던 접근 방법과 비슷한 방법을 사용

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

무식하게 풀 수 있을까?

가장 단순한 알고리즘 만들어보기

알고리즘 효율성의 기준선이 되어 새로운 알고리즘이 얼마나 개선되었는지 재는 용도로 유용함

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

문제에 주어진 예제 입력을 직접 해결해보는 것

손으로 문제 풀기

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

문제를 쉽게 변형해서 풀어보기

• 제약조건 없애기
• 변수의 수 줄이기
• 다차원 => 1차원

그림으로 그릴 수 있을까?

직관을 얻는 또 다른 방법

사고 체계가 숫자의 나열보다 기하학적 도형을 직관적으로 받아들임

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

직관은 아니지만 문제 해결에 도움을 줄 수도 있다.

문제 분해 가능?

제약조건을 분해

뒤에서부터 생각?

사다리타기

순서를 강제할 수 없을까?

답들을 중복하여 세지 않게 해줌

특정형태의 답만 고려

순서 강제의 연장선으로 정규화기법이 있음

답들 중 형태가 다르지만 결과적으로 같은 것들을 묶은 뒤, 대표들만 고려

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

3.1 코딩의 중요성

읽기 쉬운 코드를 작성해야 디버깅도 쉽고, 한 번에 정확히 작성하기 쉬움

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

간결한 코드 작성

전역변수사용

대회에서 작성하는 코드는 구조가 단순, 변수를 읽고 쓰는 부분이 어디인지가 명확해서 전역 변수를 쓰더라도 잃는 것이 많이 않음

매크로 사용

코드 재사용

코드 모듈화

같은 코드가 3번 이상이면 함수로 분리해 재사용

라이브러리

표준 라이브러리 사용

자료구조, 기초적 알고리즘을 직접 작성x

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

자주 작성하는 알고리즘, 코드에 대해서는 한 번 검증된 코드를 작성하고 꾸준히 사용

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

모호하지 않은 변수명, 함수명 사용

사용하는 언어의 표준 라이브러리에서 사용하는 명명 규약 익히기

함수도 선언만 보고 용도를 파악할 수 있도록

judge => isInside (참을 반환하는 순간이 언젠지 알 수 있음)

모든 자료 정규화 후 저장

같은 자료를 두가지 형태로 저장하지 말기

ex_ 분수, 인코딩, 각도, 시간...

자료를 입력받거나 계산하자마자 바로 이루어져야 하는 것이 정규화

코드와 데이터 분리

데이터를 별도의 상수 배열에 저장

3.3 자주하는 실수

산술 오버플로

계산 과정에서 변수의 표현범위를 벗어나는 값 사용

배열 범위 밖 원소 접근

배열 크기를 정할 때 계산을 신중히 해야함

찾기 어려운 버그임 (에러도 내지 않음)

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

여러 가지의 범위 표현 방식 섞어 쓰는 경우 피하기

닫힌 구간, 열린 구간 을 융합해서 오른쪽 열린구간 사용

ex_ a[n]의 인덱스 범위는 0<=i<n [0,n)

• 텅빈 구간 표현이 쉬워짐
• 두 구간이 연속해 있는지 쉽게 알 수 있음
• 구간의 크기를 쉽게 알 수 있음

Off-by-one 오류

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

간단한 예제로 직접 손 계산 해보기

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

사용하는 언어에서 상수의 타입을 어떻게 지정하는지

지정하지 않을 때는 어떤 형태로 강제되는지 알아두기

python
정수가 들어가면 int로
실수가 들어가면 
나눗셈 연산이 들어가면 float로
""가 들어가면 str로
[]가 들어가면 list로
{}가 들어가면 dict로
input()은 str로

강제된다.

스택 오버플로

재귀 호출의 깊이가 깊어져서 옴

스택 허용량에 대해 미리 알아두기

메모리 구조

1. 코드 영역

   실행할 프로그램의 코드

2. 데이터 영역

   전역 변수, 정적 변수

3. 스택 영역

   동적할당 (런 타임에 크기 결정)

4. 힙 영역

   지역변수, 매개변수 (컴파일 타임에 크기 결정)

참고 : http://tcpschool.com/c/c_memory_structure

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

특정 배열에 접근하는 위치를 하나로 통일

잘못된 비교 함수 작성

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

최대, 최소 입력에 대해 제대로 동작할지 생각해보기

연산자 우선순위 잘못쓰기

괄호사용

너무 느린 입출력 방식 선택

고수준의 입출력 방식 이용 => 코드는 간단하지만 속도 저하가 큼

입력, 출력 변수의 수가 1만 개를 넘어가면 생각해보기

변수 초기화 문제

한 번의 실행에 여러 testcase 출력을 구하라는 문제에서

이전 입력에서 사용한 전역 변수 값을 초기화하지 않고 그대로 사용하는 실수를 할 수 있음

testcase를 한번 더 실행하게 해보기

여러 testcase를 실행시켜보기

3.4 디버깅과 테스팅

디버깅

소스코드가 그리 길지 않기 때문에 눈으로 디버깅하는 쪽이 더 빠른 경우가 많음

재귀 호출, 중복 반복문은 디버거 사용 시 적절 x

디버거 없이 버그를 찾아내는 연습하기

• 작은 입력에 대해 제대로 실행되나 확인

• 단정문 쓰기

  단정문 : 주어진 조건이 거짓일 때 오류를 내고 프로그램을 강제종료 시키는 함수, 구문

• 계산 중간 결과 출력

런타임 오류를 내고 종료하는 경우 디버거를 사용하면 좋음!

프로그램이 어디서 왜 죽는지 간단히 확인 가능하기 때문

테스트

제출 전에 예제 입력을 만들어 가능한 한 많은 예제를 테스트

• 스캐폴딩

  건물을 짓거나 보수할 때 이동하기 위해 설치하는 임시 구조물

  프로그래밍에서는 다른 코드 개발 시 뼈대를 위해 임시로 사용하는 코드

  임의의 입력을 자동 생성해 프로그램을 돌려서 답안을 검증하는 프로그램을 짜기

3.5 변수 범위의 이해

산술 오버플로

식의 계산 값이 반환되는 자료형의 표현 범위를 벗어나는 경우

컴퓨터의 제한 중 하나 : 유한성

• 대부분의 PL들은 오버플로가 나도 경고 x

  연산 시 오버플로를 확인하는 것이 비효율적이기 때문

• 논리의 정확성에만 집중하면 오버플로를 생각하지 못할 수 있음

너무 큰 결과

default가 아닌 큰 정수를 다룰 때는 항상 변수의 형태에 주의하기

너무 큰 중간 값

중간에서 큰 값을 일시적으로 계산해야 하는 경우

너무 큰 '무한대' 값

무한대에 해당하는 큰 값을 이용할 때, 이 값들이 서로 더해지거나 곱해지는 경우가 없는지 살펴보고

있다면 오버플로가 나지 않을 크기의 값 선택하기

ex_ 공배수, 이항계수 계산 시 많이 발생

오버플로 피해가기

• 더 큰 자료형 사용
• 연산의 순서 변경

자료형의 프로모션

프로모션 : 이항 연산자들의 피연산자 자료형이 다를 때 같은 자료형으로 변환해서 계싼

언어마다 적용되는 규칙이 다름

대개 부호있는 정수형, 부호없는 정수형이 섞였을 때 문제 발생

ex_ for(int i=0; i<seq.size()-1; ++i) 일 때, seq.size가 unsigned로 반환되므로 배열이 비어있을 경우 -1을 계산할 수 없어서 굉장히 큰 수가 나올 수 있음

3.6 실수 자료형의 이해

실수 연산의 어려움

컴퓨터의 메모리는 유한하므로 무한한 수를 표현할 수 없어서 근사값으로 표현하게 됨

실수의 계산은 다양한 이유에 의해서 계속 바뀔 수 있음

IEEE 754 표준

실수의 이진법 표기

부동 소수점 표기 (소수점이 떠다닌다는 의미)

사용가능한 bit들을 소수점 위, 아래에 어느정도 배분할 것인가

해결 방법 : 소수점의 위치를 옮길 수 있도록 하기

ex_ 11011.101 => 1.1011101

부호: 양수/음수, 지수: 소수점 옮긴 칸 수, 가수: 실수의 최상위 X비트

지수는 상대적으로 작더라도 많은 수를 표현할 수 있음, 가수는 그냥 수

부호는 1bit 부여, 가수 지수 중에는 지수에 더 많은 bit 부여

자료형	부호비트	지수비트	가수비트	십진수 유효자릿수
32비트 실수형	1	8	23	6
64비트 실수형	1	11	52	15
80비트 실수형	1	15	64	18

실수는 되도록 64비트의 실수 자료형 사용하기 (정확도를 위해)

실수 비교하기

어느 정도의 오차를 염두에 두고 그것보다 작으면 통과

1. 비교할 실수의 크기들에 비례한 오차 한도 정하기

   입력으로 들어올 최대, 최소 값을 대략 예측하여 오차한도 값으로 사용가능

2. 상대오차 이용

   비교하는 숫자들의 크기에 비례하여 오차를 정하는 방식

   

절대오차, 상대오차 모두 이용해서 결정하는 것이 좋음

대소 비교

정확한 사칙연산

ex_ 유리수 계산시 분모, 분자 나누어서 계산

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

수치적으로 안정적인 프로그램 : 작은 오차가 불어나지 않는 프로그램

오차의 범위를 가지고 여러번 반복문을 돌려서 계산하기

실수연산 하지 않기

실수연산은 지금까지 배운 것만으로도 확실히 커버할 수 없을 만큼 어려움

변형을 가해서 실수 연산을 최대한 쓰지 않도록 하기

알고리즘

: 주어진 문제를 해결하는 한 가지 방법을 명료하게 써놓은 것

알고리즘을 평가하는 기준

• 시간 (빠르게 동작) *
• 공간 (적은 용량의 메모리)

둘이 상충하는 경우가 많음

ex_ 다이나믹 프로그래밍(동적 계획법): 메모리 사용 늘리고 수행 시간을 줄이기

04 알고리즘의 시간 복잡도 분석

4.1 도입

알고리즘의 속도 측정

사실 '프로그램의 수행 시간'으로 보는 것이 가장 적합하지만, 척도로 사용할 수 없는 이유

1. 여러가지 환경에 의해 바뀔 수 있기 때문에 외적요소를 통일 시켜서 측정해야함

2. 입력에 대한 실행 시간을 반영하지 못함

   입력의 크기, 특성에 따라 수행시간이 달라짐

반복문의 지배

지배한다 : 한 가지 항목이 전체의 대소를 좌지우지하는 것

알고리즘의 수행 시간을 지배하는 건 반복문

수행 시간 = 입력의 크기에 대한 반복문의 수행 횟수

4.2 선형 시간 알고리즘

다이어트 현황 파악 : 이동 평균 계산하기

이동 평균 : 시간에 따라 변화하는 값들을 관찰할 때 유용하게 사용할 수 있는 통계적 기준

M 이동 평균 : 마지막 M개의 관찰 값의 평균

수행 시간이 변수에 정비례하는(시간 복잡도가 N인) 알고리즘을 선형 시간 알고리즘 이라고 함

가장 좋은 알고리즘인 경우가 많음

한번씩 보기만 해도 (가장 간단한 작업조차도) 선형 시간이 걸리기 때문

4.3 선형 이하 시간 알고리즘

성형 전 사진 찾기

입력으로 주어진 자료에 미리 알고 있는 지식을 더하면 한번씩 보지도 않아도 됨

선형 시간보다 적은 시간의 알고리즘 가능

이진 탐색 알고리즘을 이용하여 시간 복잡도가 log N인 알고리즘을 선형 이하 시간 알고리즘이라고 함

이 알고리즘은 구현하기 복잡함

'존 벤틀리가 프로그래머 수십 명에게 구현하도록 했지만, 버그 없는 코드를 작성한 사람이 절반도 되지 않았다는 일화가 있음'

4.4 지수 시간 알고리즘

다항 시간 알고리즘

어떤 변수에 대한 거듭제곱들의 선형 결하으로 이루어진 식이 다항식

반복문의 수행 횟수가 입력 크기의 다항식으로 표현되는 알고리즘 : 다항 시간 알고리즘

선형 시간 알고리즘도 다항 시간 알고리즘에 속함

여러 개의 답이 있고 가장 좋은 답을 찾는 문제는 모든 답을 고려해보는 것이 가장 좋은 방법

이런 경우에 재귀 호출을 이용한 방법이 유용함

지수시간 알고리즘

지수 함수는 알고리즘의 수행 시간에 엄청난 영향을 미침

아직까지 지수시간 알고리즘보다 나은 알고리즘을 찾지 못한 문제들이 많음

효율적으로 해결할 수 있음의 경계가 되고 있음

'다항시간 알고리즘'이 있다 => 효율적 해결 가능

소인수 분해의 수행 시간 (?)

N이 주어지고 만약 소수이면 N-1번 나누는 연산을 해보기 때문에 선형 시간 알고리즘으로 볼 수 있음

하지만 N이 큰 수가 되면 차지하는 bit 수 (메모리)가 많아지기 때문에 그 크기에 비례해서 알고리즘 수행 시간이 최대 2배 증가함

지수 시간이 걸린다고 볼 수 있음

4.5 시간 복잡도

시간 복잡도 : 가장 널리 사용되는 알고리즘의 수행 시간 기준

알고리즘 실행 중 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현

시간 복잡도가 높다 == 입력의 크기가 증가할 때 알고리즘 수행시간이 더 빠르게 증가한다

입력의 크기에 따라 적합한 알고리즘이 다를 수 있음

입력 종류에 따른 수행 시간의 변화

입력은 크기뿐 아니라 어떤 형태인지도 수행 시간에 영향을 미침

이렇게 입력의 종류에 따라 수행 시간이 달라지는 경우는 최선/최악/평균의 수행시간을 따로 계산

대부분 '최악의 수행시간'과 '수행시간 기대치'가 비슷하기 때문에 최악의 수행시간을 씀

점근적 시간 표기: O 표기

Big-O Notation

주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 버리는 표기법

반복문이 몇 번 수행되는지만 보면 손쉽게 구할 수 있음

상수 시간 알고리즘 => O(1)

O 표기법의 의미

상수를 떼어내지 않은 식 과 O 표기법으로 떼어낸 식 은 적당히 큰 수가 되면 별 차이가 없어진다.

이 때 전자에 적절한 수 C를 곱해주면 항상 후자보다 크다는 성질을 만족할 수 있다.

함수의 상한을 나타낼 수 있음

최악의 수행시간과 관련이 있는 것은 아님

시간 복잡도 분석 연습

선택 정렬 : 주어진 입력의 순서에 상관없이 일정

삽입 정렬 : 주어진 입력의 정렬 상태에 따라 복잡도가 달라짐

최선 : O(N)

최악 : O(N^2)

시간 복잡도의 분할 상환 분석

반복문을 세는 것보다 더 정확한 계산

큰 작업에서의 시간이 일정할 때, 구성하는 작은 작업에서의 시간이 각각 달라도 작은 작업의 갯수로 나누어주어 평균을 내면 항상 소요시간이 같음

4.6 수행 시간 어림짐작하기

주먹구구 법칙

프로그래밍 대회의 시간 제한 : 시간 복잡도x, 수행시간 o

입력의 최대 크기, 시간 복잡도를 보고 수행시간을 어림짐작해야함

입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초 당 반복문 수행 횟수가 1억을 넘어가면 시간 제한을 초과할 가능성이 있다.

맹신하면 안되지만 거의 이런 기준을 씀

고려해야할 다른 요소

• 반복문 내부가 복잡한지
• 메모리 사용 패턴이 복잡한지
• 언어와 컴파일러
• 구형 컴퓨터

실제 적용

4.7 계산복잡도 클래스 : P,NP,NP-완비

계산복잡도이론

이론컴퓨터과학의 분야

각 문제에 대해 이를 해결하는 얼마나 빠른 알고리즘이 존재하는지 문제를 분류, 특성 연구

문제의 특성 공부

무엇이 더 어려운가?

어려운 것은 알고리즘이 느리다는 것

빠른 알고리즘 = 다항시간이나 그 이상의 알고리즘

다항시간알고리즘이 존재하는 문제들의 집합 : P문제

집합들 하나하나를 '계산복잡도 CLASS'라고 함

난이도의 함정

P문제, NP문제

NP문제는 다항시간 알고리즘이 없는 문제가 아니다

이는 증명하기 어렵기 때문

NP문제는 답이 주어졌을 때 정답인지 다항시간 내에 확인할 수 있는 문제

어려운 문제 판단

1. 기준이 되는 문제 1개 정하기

2. 나머지는 비교를 통해 판단

   난이도 비교는 '환산'이라는 개념을 이용

   환산 : 한 문제를 다른 문제로 바꾸어 푸는 기법

   EX_ 최소치는 비교정렬 후 구할 수 있으므로 비교정렬로 환산해서 구할 수 있음

   비교정렬 <=환산= 최소치

   비교정렬 >= 최소치

   비교정렬이 더 어려움

NP문제, NP난해문제

기준 문제

SAT문제

N개의 boolean값 변수로 된 논리식을 참으로 만드는 변수 값 조합 찾기

SAT문제는 모든 np문제 이상으로 어려움

SAT를 다항시간 내에 풀 수 있으면 NP도 풀 수 있음

NP난해 문제 : NP문제 중 SAP가 풀린 NP문제

NP완비문제 : NP문제와 NP난해문제의 교집합

ex_ 부분집합의 합 문제

P=NP?

NP의 문제 하나를 다항시간에 풀 수 있음

=> NP의 모든 문제를 다항시간에 풀 수 있음

=> P=NP

(아직까지 미해결)

05. 알고리즘의 정당성 증명

5.1 도입

알고리즘의 정당성 증명

알고리즘이 정당한가?

=> 수학적 기법이 동원되어야 함

문제가 없음은 증명해야하기 때문, 예제로 보여줄 수 없음

증명을 공부하면

1. 새로운 알고리즘 개발 시 증명 가능
2. 자신이 설계한 알고리즘의 정당성 쉽게 증명 가능

5.2 수학적귀납법과 반복문 불변식

수학적 귀납법 : 반복적인 구조를 갖는 명제 증명에 좋음

1. 단계 나누기

2. 첫단계 증명

3. 귀납 증명

   한 단계가 성립하면 그 다음 단계에서도 성립함을 증명

반복문 불변식

반복문의 내용이 한 번 실행될 때마다 중간결과가 원하는 최종결과로 가는 길 위에 있는지 명시하는 조건

불변식이기 때문에 마지막까지 계속 성립해야함

1. 반복문 진입시 불변식 성립 증명

2. 반복문 내용이 불변식을 깨뜨리지 않음을 증명

   반복문 시작과 끝에서 모두 성립

3. 반복문 종료시 불변식 성립 증명 (1,2로 부터 증명됨)

ex_)
// 1.
whlie(){
// 내용 시작
// 내용 끝
// 2. 
}

삽입 정렬과 반복문 불변식

삽입 정렬 시 불변식 (A[0,i-1]은 정렬되어있다.)을 만족하려면

반복문 안에서

불변식 1. A[j+1,i]의 모든 원소는 A[j]보다 크다.

불변식 2. A[0,i]의 모든 구간은 A[j]를 제외하고 정렬되어있다.

이 두 불변식을 만족하면 처음 불변식을 만족한다고 볼 수 있음

단정문 이용

단정문으로 불변식이 깨졌을 때 프로그램을 강제종료 시키면 불변식에 문제가 있다는 사실을 알 수 있음

5.3 귀류법

: 우리가 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못댔음을 찾아내는 증명 기법

어떤 선택이 최선임을 증명하기 좋음

책장쌓기

귀납법과 귀류법

각 단계의 최선의 선택을 하는 것을 귀류법으로 증명

그렇다면 다음 단계에서도 최선을 선택을 할 수 있음을 귀납법으로 증명

5.4 다른 기술들

비둘기 집의 원리

10마리의 비둘기가 9개의 비둘기 집에 모두 들어갔다면, 2마리 이상이 들어간 ㅣ둘기집이 하나는 있기 마련이다.

동전 뒤집기

보너스 문제 : 100개의 동전 중 앞면이 보이는 동전이 57개, 한번에 2개의 동전만 뒤집을 수 있다면, 모든 동전의 앞면이 보이게 뒤집는 답의 상한은? 어떻게 증명?

가능하지 않다. 홀수이기 때문.

귀납

불변식 : 동전을 2번 이상 뒤집지 않는다.

순환 소수 찾기

a = (a%b)*10일 때, a%b의 값은 항상 [0,b-1]의 범위를 갖음

while문이 b+1번 이상 반복되었다면, b+1번 중 똑같은 소수가 나온 경우가 발생하므로 순환 소수이다.

구성적 증명

우리가 원하는 답이 존재한다는 사실을 증명

실제 예를 들거나 답을 만드는 방법을 제시

EX_ 하늘을 날 수 있다.

• 비구성적 증명 : 법칙, 밀도, 강도 등등을 열거해서 증명
• 구성적 증명 : 비행기를 만들어서 보여줌. 설명서를 건네 줌

구성적 증명의 내용은 사실상 알고리즘

알고리즘이 항상 완벽한 상태로 종료한다는 것을 보이면 됨

안정적 결혼 문제

참고 : 생각하는 프로그래밍(인사이트)

 

---

 1,2장 총 5단원을 보면서 간단히 읽어나갈 수 있을거라고 생각했는데, 생각보다 어렵고 처음 접하는 내용이 꽤 있었다. 문제를 푸는 파트가 아니라 흥미를 잃기 쉬웠지만 다 읽어서 다행이다 ㅠㅠ 현재 읽고도 이해 안되는 부분이나 벌써 까먹은 것도 많지만 다시 보기보다는 이러한 내용이 있었음을 기억하고 다음에 필요할 때 이 게시물을 다시 봐야겠다. 시간 복잡도 계산이나 계산 복잡도 이론은 전공 학습 중에 배운 기억이 있지만, 완벽하게 이해하지 못했었는데 다시 한 번 보고 이해가 된 것 같아서 기쁘다. 이제부터는 문제 풀이!