오식랜드

다형성 다양한 형태가 존재한다는 의미 프로그램을 유연하게, 단순하게 만들어 준다 업 캐스팅 super class와 그 클래스를 상속받은 sub class 들이 있을 때, sub class를 super class형 참조변수로 저장 Object : 모든 class의 super class이므로, 모든 객체에 사용 가능 다만, super class에는 존재하지 않고, sub class에서 추가된 멤버는 사용이 불가능하다 SuperObject sub1 = new SubObject(); SuperObject sub2 = (SuperObject) (new SubObject); sub1.subClassMethod(); --> err! sub1.superClassMethod(); --> ok Object sub3 = n..

Single source shortest path 문제 (단일 출발점 최단 경로 문제) 질문 A에서 D까지의 경로가 있나? A에서 D까지의 경로가 하나 이상 있다면, 어느 경로가 최단인가? 경로의 길이: 경로에 있는 연결선의 가중치(weight)들의 합 소스(source): 경로에서의 첫 시작 노드(vertex) ⇒ S라고 한다 도착점(destination): 경로에서의 마지막 노드 Dijkstra 알고리즘 방향 그래프 : G=(V, E) 가중치 함수 (cost 함수) : W(e) 시작 노드 : S (Source) 방안 : 시작 노드 S를 기준으로, 다른 모든 노드로의 최단 거리를 구한다 (Greedy) ⇒ 어떠한 정점을 거쳐가는게 빠른지, S에서 직접 가는게 빠른지 비교가 필요하다 Dijkstra 과정..

Greedy Method 탐욕적인 알고리즘 최적화 문제 해결에 용이 : 최대, 최소를 구하는 문제 ( “가장 ~~한 것”을 고르는 문제) 결정의 순간 가장 좋다고 생각하는 것을 선택 ⇒ 번복 X ! 결정의 순간에는 가장 좋았다고 해도 최종 해답에서는 좋지 않을 수 있다. 최적의 해를 주는지 반드시 검증해줘야 한다! 과정 선정 과정 (selection procedure) : 최단 거리 / 최소 시간 등의 기준을 잡고 그에 맞추어 선택 적정성 점검 (feasiblity check) : 새로 구한 해답이 적절한지 점검. 적절하다면, solution set에 포함시킨다 해답 점검 (solution check) : 해답 모음이 최적의 해인지 결정한다 solution = null for i=1 to n do // ..

정렬 알고리즘 합병 정렬 (Merge sort) : O(nlogn) 퀵 정렬 (Quick sort) : O(n^2) 립 정렬 (Heap sort) : O(nlogn) 합병 정렬 (Merge sort) 입력을 2개의 부분 문제로 분할하며 크기가 1/2 씩 감소하는 분할 정복 알고리즘(DC) 이다 정렬이 안되어있는 배열 S를 비내림차순으로 정렬하는 과정 S를 반으로 나누어 A와 B로 명명 나눠진 배열을 각각 정렬 (이 때 A가 끝날 때 까지 B는 정렬하지 않음) 배열이 1개씩 남을 때 까지 반복 (분할) A와 B에 각각 비내림차순 정렬 A와 B의 앞 index의 수를 비교하며 병합 진행 (정복) 시간 복잡도 최선의 경우 : A와 B가 이미 정렬이 이미 되어있던 경우 ⇒ A번 또는 B번 최악의 경우 : 모든 ..

DC : Divaide-and-Conquer Divaide and Conquer : 분할정복식 분할 : 최대한 작게 문제를 분해 정복 : 나눈 문제를 각각 해결 통합 : 필요 시 해결한 문제를 합침 ⇒ 재귀적 방법으로 해결 (분할-정복 반복) ⇒ top-down 접근 방법이라고도 한다 (반대는 bottom-up) top-down (하향식) 접근 소프트웨어 개발 시 기능 / 구조 위주로 바라본다 모듈 단위의 관점 문제를 나누어 구체화 유지보수가 어렵다 절차지향적 프로그래밍에 사용 분할정복 설계 bottom-up (상향식) 접근 소프트웨어 개발 시 데이터를 위주로 바라본다 객체 단위의 관점 데이터들 간의 상호관계를 정의하며 해결 유지보수가 쉽다 객체지향적 프로그래밍에 사용 상호관계 정의 설계 Divaide ..

점근적 표기 입력 크기(n)가 무한대로 커질 때의 복잡도를 간단히 표기하기 위한 표기법 보통은 다항식이나 간단한 함수로 표기 복잡도의 상한선을 표기 Big-Oh 충족 조건 cf(n) ≥ g(n) c > 0 n ≥ 1 타이트한 값으로 설정 cf(n^2)이나 cf(n^3)도 g(n) 보다 클테지만, 타이트한 cf(n)을 사용 다양한 표기법 Big-Oh : 상한선 오메가 : 하한선 세타 : 빅오-오메가 사이에 속하는 식