'language/알고리즘'에 해당되는 글 5건

1.1. 알고리즘

알고리즘: 어떤 문제에 대한 해답을 찾는 단계적인 절차

시간(time), 저장용량(storage)의 관점에서 얼마나 효율적인지 효율성(efficiency) 강조

컴퓨터 프로그램: 어떤 특정한 일을 수행하기 위해서 컴퓨터가 이해할 수 있는 개별적인 모듈(module)로 구성

문제(problem): 어떤 특정한 일

파라미터(parameter): 문제에 특정한 값이 지정되어 있지 않은 변수

사례(instance): 파라미터에 지정하는 특정한 값(이 주어진 문제의 여러 사례들 중 하나)

알고리즘(algorithm): (어떤 문제의) 모든 사례에 대한 해답을 찾는 일반적인 단계별 절차

의사코드(pseudocode): 알고리즘을 표현하는 여러 방식들 중 한가지 (자연어와 프로그램 언어의 중간적 성격)

알고리즘 1.1: 순차검색

알고리즘 1.2: 배열의 수 더하기

알고리즘 1.3: 교환정렬

함수(function): 결과값을 넘겨줘야하는 경우 사용.

프로시져(procedure): 결과값을 넘겨줄 필요가 없는 경우 사용.

알고리즘 1.4: 행렬곱셈

1.2. 효율적인 알고리즘 개발의 중요성

1.2.1 순차검색 대 이분검색

효율성(efficiency)의 문제는 알고리즘의 최우선 고려사항

알고리즘 1.5: 이분검색

순차검색과 이분검색의 최대 비교횟수 비교

순차검색: n회 비교

이분검색: (logn + 1)회 비교

1.2.2 피보나찌 수열(Fibonacci Sequence)

피보나찌 수열의 n번째 항을 계산하는 알고리즘

알고리즘 1.6: n번째 피보나찌 항 구하기(재귀적 방식, recursively)

재귀 트리(recursion tree)

T(n) > 2^(n/2)의 귀납적 증명(n>=2인 모든 n에 대해서) 

재귀 알고리즘의 문제점: 같은 값을 중복해서 계산하는 문제

알고리즘 1.7: n번째 피보나찌 항 구하기(반복적 방법)