알고리즘 기초 홍릉과학 출판사 1장 솔루션

소개

홍릉출판사 알고리즘 기초 1장 연습문제 (1,3,5,7,12,14,15,18,22,25,28,34) 솔루션입니다.

목차

없음

본문내용

1.1 알고리즘
알고리즘이란 기법에 따라 문제를 푸는 독특한 단계별 절차이다. 문제를 푸는 기법은 다양하지만, 기법에 따라 알고리즘의 성능 차이가 발생할 수 있다.
리스트란 어떤 원소를 특정 순서로 나열해 놓은 것이다.
파라미터란 문제에서 값이 지정되어 있지 않은 변수를 말한다.
알고리즘을 표현하는 방법
자연어로 표현 -> 복잡한 알고리즘을 말로 설명하기 어렵다, 말로 표현한 알고리즘을 컴퓨터 프로그램으로 어떻게 만들지 불투명하다는 단점이 있다.
의사코드로 표현-> C++과 비슷하지만, C++과 달리 배열을 프로시저의 파라미터로 사용할 때 2차원 배열의 길이를 미리 고정할 필요가 없고, C++에서는 쓰지 않는 데이터 타입을 사용할 수 있다.

1.2 효율적인 알고리즘 개발의 중요성
순차검색과 이분검색
순차검색이란 주어진 배열에서 원하는 데이터를 처음부터 순차적으로 비교하면서 찾는 방법이다.
이분검색이란 찾고자하는 데이터를 배열의 정중앙에 위치한 원소와 비교를 한다. 만약 배열의 정중앙에 위치한 원소와 찾는 데이터가 같으면 알고리즘이 종료되고, 찾는 데이터가 그 원소보다 작으면 배열 전반부에서 중앙에 위치한 원소와 비교를 한다. 찾는 데이터가 그 원소보다 크면 배열 후반부에서 중앙에 위치한 원소와 비교를한다. 이러한 과정을 반복하는 것이 이분검색이다.
순차검색과 이분검색에서 빅오 표기법으로 알고리즘의 복잡도를 나타내면 순차검색은 O(n)이고 이분 검색은 O(log₂)이다. 만약 배열의 크기가 1024인 경우 순차검색을 사용하면 1024번 비교를 해야하지만, 이분검색을 사용하면 11번만 비교를 하면 된다. 따라서 어떻게 알고리즘을 설계하냐에 따라 일을 수행하는 시간이 달라진다.
피보나치 수열
피보나치 수열을 계산하는 알고리즘은 두 가지가 있는데 재귀를 이용하는 방법과 반복을 이용하는 방법이 있다.

int fib(int n){
if(n<=1)
return n;
else
return fib(n-1) + fib(n-2);

참고자료

· 없음