알고리즘 문제 해결 전략 I (3)

알고리즘 문제 해결 전략 I  (3)

알고리즘은 객과적이어야 하며 본질적으로 모호하지 않아야 한다.

컴퓨터 공학에서의 알고리즘은

컴퓨터가 따라할 수 있도록 자세히 설명한 과정을 나타낸다.

 

알고리즘의 평가기준 

시간과 공간

적은 시간사용 : 빠르게 동작

적은 공간사용 : 적은 메모리에도 동작

본 두 기준은 서로 상충하는 경우가 큼.

 

알고리즘의 시간 복잡도

반복문이 알고리즘 수행시간의 가장 큰 영향

선택정렬과 삽입정렬

1. 선택정렬 : 모든 원소들에서 가장 작은 원소를 찾고 그것을 새로운 배열에 넣는 방식

최악의 경우와 최선의 경우의 시간복잡도가 같다.

2. 삽입정렬 : 전체 배열중 정렬되어 있는 부분 배열에 새 원소를 끼워넣는 일을 반복하는 방식

입력이 임의의 순열이라고 할 때 대부분 삽입정렬이 빠름.

 

알고리즘의 증명을 위해 흔히 사용하는 기법들

수학적 귀납법 - ex) 사다리게임

처음에 아무 가로줄을 그리지 않았을 때, 세로줄이 모두 1:1 대응임을 알 수 있다. 

가로줄을 하나 넣어보고 두개 넣어보아도 1:1 대응이다. 

따라서 가로줄의 개수에 상관없이 모두 1:1 대응을 한다는 사실을 알 수 있다.

 

반복문 불변식 - 반복문이 실행될때마다 우리가 원하는 답으로 가는 길 위에 잘 있는지를 명시하는 조건.

반복문이 정답을 계산하기 위해선 항상 이 식이 변하지 않고 성립 (그래서 불변식)

 

1. 반복문 진입시 불변식이 성립을 보임.

2. 반복문 내용이 불변식을 바꾸지 않음을 보임.

3. 반복문 종료시 불변식이 성립을 보임.

 

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

책장쌓기 / 기차에 최대한 많은 사람 태우기

 

비둘기집의원리 

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

 

동전뒤집기

잘 이해 안감. 

 

구성적 증명과 비구성적 증명

비 구성적 증명 : 비행기를 만들기 위해 양력의 법칙과 지구의 물리법칙 등 하나하나 열거하는 가정을 통해 비행기가 하늘을 날 수 있음을 증명함

구성적 증명 : 비행기를 만들어서 나는것을 보여주거나, 비행기를 만드는법이 적힌 설명서를 건내주는것. 

구성적 증명의 내용은 사실상 알고리즘인 경우가 많다. 

 

안정적 결혼 문제 : n명의 남성과 여성이 단체 미팅에서 만났을 때, 프로포즈를 받은 사람은 현재 결혼을 생각했던 사람과 새로이 프로포즈를 받은 사람 중 한명을 선택하게 되므로 무조건 한 상대를 갖게 됨. 모든 사람들이 짝을 갖게 되는 원리.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

알고리즘 문제 해결 전략 I 中 

2020.07.09