728x90 Computer Science14 [Algorithm] 정렬 알고리즘,내부정렬, 외부정렬 ■ 정렬 알고리즘 여러 알고리즘 중 가장 기본이 되는 알고리즘 [특징] 1. 대부분의 정렬 알고리즘은 키값을 비교하는 비교 연산과 자료의 위치를 바꾸는 이동 연산으로 이루어짐 2. 비교 연산의 횟수와 이동 연산의 횟수로 정렬의 효율성을 판단 3. 정렬을 수행해야 하는 데이터의 크기가 크면 이동 연산이 적을수록 좋음 (데이터의 크기가 크면 그만큼 이동해야 하는 데이터의 크기가 증가하여 이동 연산을 수행하는데 더 많은 시간이 필요) 4. 연산의 횟수가 같더라도 비교 연산이 많은 알고리즘이 이동 연산이 많은 알고리즘보다 성능이 더 우수 5. 컴퓨터 메모리 내부에서 정렬하는 '내부 정렬 알고리즘'과 보조기억 장치에서 정렬하는 '외부 정렬 알고리즘'이 있음 [시간복잡도] 1. 대부분 O(n^2)과 O(nlogn).. 2024. 2. 7. [Algorithm] 완전 탐색 (Exaustive Search) ■ 완전 탐색 (Exaustive Search) 고지식한 방법 (Brute-Force)의 의미를 갖고 있음. - 모든 경우의 수를 나열한 후 그 중에서 최선의 해결책을 찾는 방법으로 가장 좋은 결과를 확실히 추출할 수 있음 - brute-force는 문제를 해결하기 위한 간단하고 쉬운 접근법 [개념] 1. 완전탐색은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법 2. brute-force 혹은 generate-and-test 기법이라고도 부름 [특징] 1. 모든 경우의 수를 테스트한 후 최종 해법을 도출 2. 문제에 포함된 자료 (요소, 인스턴스)의 크기가 작다면 유용 3. 학술적 또는 교육적 목적을 위해 알고리즘의 효율성을 판단하기 위한 척도로 사용됨 4. brute-for.. 2024. 2. 7. [Algorithm] 분석 종류, 설계 기법, 표기법 ■ 알고리즘의 조건 조건 설명 입력 0개 이상의 데이터 입력이 있어야한다. 출력 적어도 하나 이상의 결과를 출력해야한다. 명확성 각 단계와 명령은 모호하지 않고 명확해야한다. 유한성 유한한 단계를 거친 후, 반드시 종료해야한다. 유효성 각 명령어들은 실행 가능해야 한다. ■ 알고리즘의 표현 방법 1. 자연어 2. 순서도 (Flow Chart) 3. 의사코드 (Pseudo Code) 4. 프로그래밍 언어 (C, C#, C++ ...etc) ■ 알고리즘 분석 종류 종류 설명 최악의 경우를 분석 (★★) 어떤 입력이 주어지더라도 알고리즘의 수행 시간이 이 이상은 넘지 않는다는 '상한(Upper-Bound)'의 의미. * 수행시간이 가장 늦은 경우를 뜻함 평균의 경우를 분석 입력의 확률 분포를 가정하여 분석. .. 2024. 2. 7. [자료구조] 순환적, 반복적 피보나치 수열 구현 및 성능 비교, 순환문과 반복문 비교, 하노이탑 ■ 구현 ■ Main ■ 성능 비교 이로 인하여 피보나치 수열은 Iterative 기법이 더욱 효과적인 것을 알 수 있었다. ■ 순환 (Recursive) vs 반복 (Iterative) 순환 (Recursive) 반복 (Iterative) [장점] 가독성 증대 및 코딩도 간단해짐 [단점] 함수 호출의 오버헤드 발생으로 수행속도가 느림 (스택 저장 공간에 함수 파라미터 스택을 저장할 기억 공간이 더필요하고 이와 관련된 작업을 함에 있어서 오버헤드가 발생함) [특징] 1. 어떤 경우는 순환이 아니면 프로그램 구현이 어려운 경우가 있음 2. 시간 복잡도 (Time Complexity)는 순환 호출 1번에 1번의 곱셈을 수행하므로 n번 발생시 O(n)이다. [장점] 수행속도가 빠름 [단점] 가독성을 악화시킬 .. 2024. 2. 3. [자료구조] 자료구조의 이해와 자료 표현 (수치 및 진수) ■ 정의 자료구조란 계산에 쓰이는 여러가지 자료들을 조직화 및 구조화(organize)한 것을 의미한다. ■ 일상생활과의 비교 일상생활 자료구조 물건을 쌓아두는 것 스택 (LIFO; Last In First Out) 영화관 매표소의 줄 큐 (FIFO; First In First Out) 할 일 리스트 리스트 영어 사전 (알파벳 순서) 사전, 탐색구조 지도 그래프 조직도 트리 ■ SW코딩 [의미] 대부분의 SW코딩은 자료(data)를 처리하며, 이 자료들은 자료구조(data structure)를 사용하여 표현되고 저장된다. 이는 여러 가지 측면으로 SW코딩이 무엇인지를 나타낼 수 있다. 측면 정의 이론적 그래프이론, 집합이론, 조합적 분석의 이산수학과 확률이론을 기초로 알고리즘을 분석하여 검색, 정렬방법을.. 2024. 1. 21. 이전 1 2 다음 728x90
