알고리즘
문제를 해결할 수 있는 잘 정의된 유한시간 내에 종료되는 계산적인 절차
알콰리즈미가 아라비아 숫자를 곱하는 방법에 대한 책을 집필 대수학의 아버지
문제를 해결하는 절차
•
분할정복
•
동적계획
•
탐욕 알고리즘
•
백트래킹
•
분기한정법
문제의 분야에 따라서 방법이 다르다
sorting, searching, cryptography, optimization 등..
예시: 정수의 곱셈 일반화
n자리수 곱하기 n자리수의 프로그램 만들기
O(n2)만큼의 시간이 필요한데
더 빠르게 하는 방법?
divide and conquer
네자리수를 두자리수로 만든다.
두자리수 곱하기 두자리수 4개로 만든다 인수분해
두자리수 곱도 한자리수로 쪼개고..
각 1의 자리수 곱셈은 기억하고 있는다
근데 결국 n제곱번 연산이 필요함 나아지는게 없음
점화식으로 풀어보면 계산가능
더 빠르게 할수있는 알고리즘 존재함
카라츠바 알고리즘
n의1.6승까지 줄일수있다
결론 알고리즘을 통해서 약간의 아이디어로 더 빠르게 풀 수 있는 방법을 알게된다
말도안되는 방법으로 빠르게 푸는 경우도 있다
문제와 매개변수 파라미터
입력 - 파라미터 특정 값 지정
출력 = 해답
알고리즘 표기
자연어로 표기
자연어 알고리즘 어떻게 문제를 풀것인지를 자연어로 기술
pseudocode로 표기
flowchart로 표기 이런게 있다 정도.. 복잡해지면 이해하기가 쉬움 한스텝씩 시각화하니까
프로그래밍 언어로 표기
자연어는 정확히 기술이 어렵고 프로그래밍언어는 문법에 종속되고 그래서
대부분은 의사코드를 이용해서 나타내게 된다
특정언어에는 없는 타입도 사용가능하고 인덱스같은것도 자유로움
알고리즘 효율, 분석,차수
비네의 공식
부동소수점은 매우 정확해야 N이 커져도 결과가 정확함
그래서 결국 오차가 많이 발생해서 안씀
피보나치 수열 = 황금비
원래 정의를 사용한다면 재귀적으로 풀어야함
하지만 매우 수행속도가 느림
중복계산이 너무 많이 일어나서
똑같은 문제를 해결할때도 좋은 알고리즘을 만드는게 중요하다!
재귀법 = 분할정복방법
어떤 문제에서는 매우 효율적임
반복법 = 동적계획법 (dynamic programming)
문제에 따라 효율적인 방법이 다를 수 있다
알고리즘 분석
메모리가 비교적 풍부하기 때문에 시간이라는 리소스가 훨씬 중요한 요소임. 메모리는 늘리면 되고
레이턴시를 줄이는게 중요함
측정기준은 개념적인 연산단계를 이용해서 고려한다
연산 한 단계는 비교연산 대입연산 등
몇 개의 기계 명령어로 변환되는지는 중요하지 않다
시간복잡도의 종류
일정 시간 복잡도
입력크기에만 종속, 입력값과는 무관함
입력값과는 무관하게 결과값은 항상 일정
최악시간복잡도
입력크기와 입력값 모두에 종속됨
단위연산이 수행되는 횟수가 최대인 경우 선택
비관적인 시각으로 최악의 상황에도 효율성이 좋도록 해야함
평균시간 개념은 안좋음
평균 시간복잡도는 어렵다 확률 따져야해서
bogosort
보고 정렬
랜덤하게 셔플에서 될때까지 하는거
시간분석해보자…
최선 시간복잡도는 1임. 운이 극히 좋으면
최악은 n이 커질수록 극도로 줄어듬
느릴 수록 좋은 경우도 있다
암호화
복잡도가 높은 함수 특성 기반
암호키같은 정보 모르는 사람이 풀려면 높은 복잡도
실제로 그런게 있음
asymptotic 점근적 특성
n이 매우 커질때 함수가 갖는특성
n이 커지면 어떤 특성을 보일거냐
복잡도 함수 표기법이 3가지 빅오, 오메가 ,세타
f(n)에 c를 곱했을때 항상 g(n)보다 큰 N이 존재한다
오메가 표기법
세타 표기법
점근적 상한이랑 하한을 동시에 만족
