gyeo-ri.com

*한국기술대학교 원격평생교육원에서 수강중인 학점은행제 컴퓨터공학 학사 과정의 알고리즘 요약 자료(시험 대비)입니다. 정렬 순서 없이 배열되어 있는 자료를 오름차순이나 내림차순으로 나열하는 것 정렬의 대상 : 레코드(Record) 레코드는 필드(Field)로 구성되어 있음, 키(Key) 필드로 레코드 식별 정렬 방식 구분 주요 기준에 따른 분류 기준 정렬방식 설명 실행 방법 비교식 정렬 비교할 키값을 한 번에 두 개씩 비교하고, 교환하여 정렬하는 방식 분배식 정렬 키값을 기준으로 하여 자료를 여러개 부분집합으로 분해하고 각 부분집합을 정렬함으로써 전체를 정렬하는 방식 (분할과 정복 : Divide and Conquer) 정렬 장소 내부 정렬 컴퓨터의 주기억장치에서 정렬 입력 크기가 주기억장치의 공간보다 크..

*한국기술대학교 원격평생교육원에서 수강중인 학점은행제 컴퓨터공학 학사 과정의 알고리즘 요약 자료(시험 대비)입니다. 점화식 명시적으로 자기 호출을 사용하지 않더라도 그 속에서 자신(n)과 똑같지만 크기가 다른(n-1) 문제를 발견할 수 있는 경우 재귀적 성질을 포함하는 알고리즘의 복잡도는 점화식을 이용하여 접근이 가능함 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현 점화식의 점근적 복잡도를 구하는 방법 반복 대치 : T(n)의 식을 T(1)이 될 때 까지 반복하여 치환함 추정 후 증명 : 귀납적으로 가설을 설정, 가설을 만족함을 증명 시간 복잡도(빅오표기법 등)의 증명 과정 마스터 정리 : 특정한 모양을 가진 재귀식에 대해 바로 결과를 알 수 있는 정리 T(n) = aT(n/b) + f..

*한국기술대학교 원격평생교육원에서 수강중인 학점은행제 컴퓨터공학 학사 과정의 알고리즘 요약 자료(시험 대비)입니다. 복잡도의 점근적 표기 점근적 분석 : 입력의 크기가 충분히 큰 경우에 대한 분석 입력 크기가 작은 문제 : 알고리즘의 효율성이 중요하지 않음(비효율적인 알고리즘도 큰 문제가 없음) 입력 크기가 충분히 큰 문제 : 알고리즘의 효율성이 중요(비효율적인 알고리즘이 치명적) 복잡도는 입력 크기에 대한 함수로 표기하며, 이 함수는 주로 여러 개의 항을 가지는 다항식 다항식을 단순한 함수로 표현하기 위해 점근적 표기법 도입 n의 크기가 커짐에 따라 최고차항을 제외한 나머지 항의 비중이 줄어들기 때문에, 일반적으로 최고차항만을 표기 O(Big-Oh) 표기법 점근적 상한선, 최악의 경우의 알고리즘 수행 ..

지난 7월부터 학점은행제 학습자등록을 마치고 컴퓨터공학 학사 취득을 준비중이다. 타전공학사(기존 학사 학위 보유자)인 경우 교양 학점 없이 전공 48학점만 이수하면 학사 학위를 취득할 수 있는데, 그 중 일부를 수업이 아닌 독학사(독학학위제) 시험 합격으로 대체할 수 있다. 독학학위제 독학학위제는 1~4과정으로 구성되며, 각 과정당 매년 1회의 응시 기회가 있다. 1과정의 경우 교양, 2~4과정의 경우 일반적으로 전공 학점으로 인정받을 수 있으며, 일부 과목은 교양 과목으로 인정받을 수 있는데, 인정받을 수 있는 교양 과목은 다음과 같다. 자세한 사항은 (링크) 확인 1단계(과정)의 경우 4학점, 2~4단계눈 5학점을 인정받을 수 있는데, 2~4 단계 간의 인정 학점 차이가 없기 때문에 상대적으로 수월(..