자료구조 추상화를 통해 자료의 논리적 관계를 구조화한 것자료의 추상화와 구조화가 적절히 이루어지지 못하면 소프트웨어는 비효율적으로 수행되거나 소프트웨어의 확장성에 문제가 생길 수 있음 자료구조와 알고리즘의 협동 자료구조는 입력값의 추상화된 상태라면, 알고리즘은 컴퓨터가 수행해야 할 명령의 추상화 자료구조의 두 가지 측면 자료구조는 입력값의 추상화된 상태라면, 알고리즘은 컴퓨터가 수행해야 할 명령의 추상화 자료구조와 알고리즘의 추상화/구체화 입력될 값을 머릿속에서 추상화된 형태(자료구조)로 구조화하고, 수행되어야 할 명령어를 머릿속에서 추상화된 형태(알고리즘)로 체계화 자료구조의 종류와 관계
추상화 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것 추상화를 통해 간결하게 말하는 사람의 의사를 전달할 수 있게 되는 것 - ex) 차 : 버스, 택시, 승합차 자료의 추상화 다양한 객체를 컴퓨터에서 표현하고 활용하기 위해 필요한 자료의 구조에 대해서 공통의 특징만을 뽑아 정의한 것자료의 추상화에는 컴퓨터 내부의 이진수의 표현 방법, 저장 위치 등은 포함되지 않고 단순하게 개발자의 머릿속에 그림을 그리는 것처럼 개념화하는 것
자료(data)란? 현실 세계에서 관찰이나 측정을 통해서 수집된 값(value)이나 사실(fact) - 값 ex ) 기온, 강수량 - 사실 ex) 태양은 동쪽에서 떠서 서쪽으로 진다. 지구는 둥그렇다. - 현실 속에 널려져 있는 것들 이라고 생각하면 된다. 풀어서 이야기하면 물리적인 단위로 표현해서 얻을 수 있는 내용들 우리의 생활에서 실제로 만질 수 있거나 볼 수 있거나 하는 것(길이, 무게, 부피 등을 측정할 수 있는 대상)에 대해서 물리적인 단위로 표현하여 얻어낼 수 있는 내용 - ex) 점수, 성적, 이름, 학번 정보란? 어떤 상황에 대해서 적절한 의사결정(decision)을 할 수 있게 하는 지식(knowledge)으로서 자료의 유효한 해설(interpretation)이나 자료 상호 간의 관계..
알고리즘 분석?정확성 분석- 유효한 입력, 유한 시간 → 정확한 결과 생성 ＊ 다양한 수학적 기법을 사용한 이론적 증명이 필요 ＊ 다양한 입력 상황을 가정한 테스트 데이터를 통한 실용적 방법 → 제한적 효율성 분석- 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정- 공간 복잡도 → 메모리 양- 시간 복잡도 → 수행 시간 시간 복잡도알고리즘의 수행 시간- 알고리즘에서 사용된 단위 연산들의 수행 횟수의 합 ＊ 실제 수행되는 시간을 측정하지 않음 → 컴퓨터 및 프로그래밍 언어 등에 의존- 입력의 크기 ＊ 단순히 단위 연산의 개수가 아닌 입력 크기의 함수로 표현 - 입력 데이터의 상태에 따라 달라짐 ＊ 평균 수행 시간, 최선 수행 시간, 최악 수행 시간 점근 성능입력 데이터의 크기 n이 충분히 커짐에 따라 결정..
최소값 찾기 최소값 찾기에서 알고리즘1과 알고리즘2 중에서 어떤 것이 더 효율적인가? 뒤섞인 카드에서 원하는 카드 찾기 카드를 섞어서 뒤집어 놓았다. 이 카드 중에서 K를 찾아라! 순차 탐색 순서대로 나열된 카드에서 원하는 카드 찾기 이진 탐색 알고리즘 설계 기법문제와 제반 조건이 매우 다양 → 일반적인 기법은 없음 대표적인 설계 기법- 분할정복 방법- 동적 프로그래밍 방법- 욕심쟁이 방법 분할정복 방법순환적으로 문제를 푸는 방법- 문제를 더 이상 나눌 수 없을 때까지 작은 문제로 나누고, 이렇게 나누어진 문제들을 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 하향식 접근 방법- 분할 ＊ 주어진 문제를 여러 개의 작은 문제로 분할- 정복 ＊ 작은 문제들을 순환적으로 분할. 만약 작은 문제..
알고리즘?주어진 문제를 풀기 위한 명령어들을 단계적으로 나열한 것 (입출력) 입출력 - 0개 이상의 외부 입력, 1개 이상의 출력(명확성) 각 명령은 모호하지 않고 단순 명확해야 함 ＋ (실용적 관점) 알고리즘의 효율성(유한성) 한정된 수의 작업 후에는 반드시 종료(유효성) 모든 명령은 수행 가능해야 함 → 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 일련의 유한개의 명령들을 순서적으로 구성한 것 알고리즘의 생성 단계 알고리즘 기술 방법일상 언어(자연어)① 계산할 숫자를 입력 받음② 입력 데이터를 모두 더해 합을 계산함③ 결과를 출력함 의사코드 123456sum ← 0 while ( 데이터 존재 ) sum ← sum + i번째_데이터end 결과(sum) 출력cs ..