018. 알고리즘과 초콜릿 케이크 레시피
소프트웨어를 초콜릿 케이크 레시피에 비유하는건 잘못됐다. 납세신고서다.
컴퓨터 프로그램은 정교한 알고리즘들의 집합이라고 간주할 수 있다. 수학이나 컴퓨터 과학에서 말하는 알고리즘은, 보통 반복되는 문제를 풀기 위한 작은 프로시저를 의미한다.
알고리즘은 지능이나 상상력이 없는 개체가 수행하더라도 연산의 의미와 수행 방법에 의심의 여지가 없을 정도로 상세하고 정확하게 일련의 연산을 명시해야 한다.
알고리즘 :
'특정 문제를 풀기 위한 단계적인 절차', '문제 해결 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서'
특정 작업을 수행하기 위한 유한 개의 명령어의 집합
알고리즘의 조건
입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.(즉 모든 입력에 하나의 출력이 나오면 안됨)
명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
유한성(종결성) : 유한 번의 명령어를 수행 후(유한 시간 내)에 종료한다.
효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다.
📎 알고리즘과 프로그램, 같은 뜻 아니다? [코딩월드뉴스]
019. 반에서 가장 키 큰 사람 찾기 : 선형 알고리즘
알고리즘이 얼마나 효율적으로 작동하느냐?
계산 시간이 데이터의 양에 정비례하거나 선형적으로 비례할 때, 선형 알고리즘(linar algorithm) 이라고 함
찾고자 하는 값을 리스트의 맨 앞에서부터 끝까지 차례대로 찾아 나가는 방식
선형 탐색은 결과를 얻기 위해 배열의 모든 요소를 살펴봐야함.
일상생활에서 접하는 많은 알고리즘은 선형이다. 어떤 데이터에 대해 동일한 기본 연산을 수행해야 하는데, 데이터 수가 많아지면 곧 그에 정비례하게 많은 일이 필요하기 때문이다.
▲ 데이터 크기와 탐색 시간에 따른 시간 복잡도의 그래프
자료구조(data structure) :
계산과정에서 필요한 정보를 표현하는 방법
📎 알고리즘과 데이터 구조 [2010 데이터로 표현하는 세상 요약본]
데이터를 알고리즘과 분리하여 보자. 자주 변경되는 세율은 간단한 형태의 테이블에 적어 놓고, 그 테이블은 데이터 구조로 변경하여 정의하고, 알고리즘에서는 그 데이터 구조만 사용하면 된다. 세율이 변경되어도 그 변경된 값은 데이터 구조에서만 바꿔주면 될 뿐, 알고리즘은 손 댈 필요가 없다.
