이상학의 개발블로그

분할 정복(Divide and Conquer)step : Divide, 문제를 하나 또는 둘 이상의 인스턴스로 나눈다.step : Conquer, 나눠진 문제가 충분히 작고 해결가능 하다면 해결하고, 그렇지 않으면 다시 나눈다.step : Combine, 필요하다면, 나눠진 문제들을 다시 하나로 합친다. 이진 검색의 분할 정복step 0 : If x = S[mid], find x and quitstep 1 : Divide, 배열을 두개의 하위 배열로 나눈다. If x > S[mid], 오른쪽 배열을 선택하고 다시 찾는다. If x Best(h,m) = min(h,m) h 또는 m의 선형 시간, 즉 작은 배열이 기준이 되어서 비교하는 경우 가장 시간 복잡도가 좋다. 하나가 먼저 끝나는 경우 Worst ca..

Order (차수) 선형 시간 알고리즘선형 시간 입력( 1차, n 크기). ex) 순차검색 2차 시간 알고리즘ex) 버블 정렬( n^2 ) An inturitive introduction to "Order"입력의 크기가 아주 클 때, 알고리즘의 복잡도는 최고차 항에 의해 결정된다.최고차 항이 제일 중요하다. 점근적 표기법( Asymptotic Notation)알고리즘을 만들고 해당 알고리즘이 잘 만들었는지 평가하는 성능분석은 매우 중요하다.해당 알고리즘이 잘 만들어진 것인지 판단할수 있는 척도가 된다. 그러나 만약 해당 알고리즘이 문제를 해결하는 절대적 시간을 기준으로 하면 문제가 발생하는데만약, A 알고리즘은 슈퍼컴퓨터에서 B 알고리즘은 스마트폰에서 실행한 시간을 기준으로 A 알고리즘이 더 좋다고 평가..

알고리즘 : 효율, 분석 그리고 순서효율적인 개념의 알고리즘 소개 ex) 크기 n인 배열 S에서 x 라는 숫자가 있나?S [10, 7, 11, 5, 13, 8] x = 11 사람은 한번에 11이 있다는걸 찾을 수 있지만 이것을 컴퓨터에게 어떻게 명령할 것인가?step-by-step으로 문제를 해결해야한다. 순차검색input : int n ( >0), S [1...n], xoutput : location of x, if x is in S 0 , if x isn't in S슈도 코드 이진 검색가정 : 입력 배열 S[] 는 non-decreasing 이다. ( increasing 이라 표기하지 않는 이유는 increasing은 1,2,3,4,4 처럼 같은 값이 있을때를 포함하지 않는다)슈도코드 피보나치 수열T..

이진 탐색 트리 트리노드는 최대 2개의 자식부모가 왼쪽 자식보다 크고 오른쪽보다 작다 그래프 V정점과 E간섭으로 이루어짐정점은 독립된 개체로 동그라미로 표현directed graph : 방향성이 있다un directed graph : 방향성이 없다. 인접(Adjacency) : 두 정점이 서로 연결되어 있는 경우. 도착점을 기준으로 설명한다. 차수(Degree) 정점으로 나가고 들어오는 간선의 수진출차수, 진입차수차수는 진출과 진입의 합무방향성 그래프는 진출, 집입 차수가 없다. 그냥 차수만 존재 경로(Path) 정점 u로부터 정점 v까지 도달가능 하기 위해 거치는 정점의 순서를 나열한 것.경로의 길이 : 경로에 있는 간선의 수경로가 존재할 때 거치는 간선 +1 이 경로의 길이(시작,끝 제외) 단순경로(..

알고리즘 : 문제를 해결하는 최적화된 방법 컴퓨터 알고리즘 : 컴퓨터를 이용한 알고리즘 컴퓨터 언어 : 컴퓨터와 대화하기 위한 언어 컴퓨터 알고리즘 : 컴퓨터를 이용하여 주어진 문제를 풀기 위한 절차 컴퓨터 프로그램 : 컴퓨터가 특정 작업을 수행하기 위해 짜여진 명령의 순서 친구 A가 택시로 T아카데미에 가는 과정 택시가 있는 도로로 나간다손을 들어 택시를 부른다목적지를 말한다돈을 낸다내린다 컴퓨터 알고리즘 설명 4단계 문제 정의(Problem Definition) : 문제를 정의하고 이를 컴퓨터가 이해할 수 있는 형태로 변경. 입력, 출력알고리즘 설명(Algorithm Description) : 컴퓨터가 수행해야 할 내용을 하나씩 차례대로 정의한 것정확성 증명(Correctness Proof) : 과정..