18~19. 알로리즘과초콜릿 케이크 레시피, 반에서 가장 키 큰 사람 찾기: 선형 알고리즘

 알고리즘과 레시피

소프트웨어르 설명할 때 음식을 만드는 레시피에 자주 비유하곤 하는데 그건 적절하지 못하다.

• 그 이유는 레시피에서는 '표면 위에 손바닥을 살짝 올려서 확인하세요.' 라는 표현이 나오는데 살짝이 얼마나 살짝일까? 이런 명확하지 못한 표현들은 소프트웨어에서 사용하면 안된다.

소프트웨어는 요리 레시피보다 납세 신고서에 비유하는 것이 적절하다.

• 납세 신고서에 무엇을 해야 하는지 극도록 상세하게 설명돼 있다. 완벽힌 비유는 아니지만 요리 레시피보다 계산적 측면을 훨씬 더 잘 담아낸다
• 그렇지만 이 방법도 좋지가 않다. 납세 신고서도 용어가 항상 명확하지는 않고 설명도 모호하며, 어떤 데이터 값을 사용해야 하는지 불확실할 때가 자주 있다.

알고리즘이란 ?

• 어떠한 문제를 해결하기 위한 일련의 절차나 방법을 공식화한 형태로 표현한 것을 의미한다.

알고리즘의 조건

• 입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
• 출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.(즉 모든 입력에 하나의 출력이 나오면 안 됨)
• 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
• 유한성(종결성) : 유한 번의 명령어를 수행 후(유한 시간 내)에 종료한다.
• 효율성 : 모든 과정은 명백하게 실행 가능(검증 가능) 한 것이어야 한다.

반에서 가장 키 큰 사람 찾기: 선형 알고리즘

반에서 키가 제일 큰 사람이 누구인지 알고 싶다고 해본다 그냥 둘러봐도 알 수 있겠지만, 알고리즘은 바보 같은 컴퓨터도 이해할 수 있을 정도로 실행 단계를 명확하고 상세하게 설명해야 한다. 

• 제일 큰 사람을 알아볼 수 있는 방법은 한명 한명 물어보면 된다. 하지만 다른 조건이 추가되면 상황이 복잡해진다.
• 두 명 이상의 학생이 키가 같다면 먼저 물어본 사람을 기록해야 할지 나중에 물어본 사람을 기록해야 할지 키가 같은 사람들의 무리 중에서 사람 수가 가장 많은 무리를 찾는 일이 훨씬 어려운 문제라는 점을 주목한다
• 왜냐하면  키가 같은 사람 모두의 이름을 기억해야 하기 때문이다.
• 이런 문제를 해결 하려면 자료 구조가 필요하다

자료 구조란 ?

• 자료구조란 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것이다.

자료구조를 사용하는 이유

•  데이터를 체계적으로 저장하고, 효율적으로 활용하기 위해서 자료구조를 사용한다.

데이터(data)는 무엇일까?

• 데이터는 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값이다.
• 이름, 나이, 키, 집 주소, 목소리, 유전자 DNA까지 데이터로 분류할 수 있다.
• 데이터는 그 자체만으로 어떤 정보를 가지기 힘들다.예를 들어 나이라는 데이터만 알고 있다면, 사람의 나이인지, 강아지의 나이인지, 나무의 나이인지 알 수 없다.
• 데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있다.
• 데이터를 사용하려는 목적에 따라 형태를 구분하고, 분류하여 사용한다. (https://lesil.tistory.com/m/42)

자주 등장하는 Stack, Queue, Tree, Grap

선형 알고리즘

• 알고리즘에서 중요한 특성 하나는 얼마나 효율적으로 작동하느냐이다 
• 컴퓨터가 이 작업을 하는데 걸리는 시간은 처리해야 하는 데이터의 양에 정비례한다. 만약 방 안에 있는 사람의 수가 두 배이면 계산하는데 두 배의 시간이 걸릴 것이고, 사람의 수가 10배라면 처리하는 시간도 10배가 걸릴 것이다
• 계산 시간이 데이터의 양에 정비례하거나 선형적으로 비례할 때, 그 알고리즘은 선형 시간 또는 단순히 선형이라고 한다

• 데이터 항목의 수를 x축으로 놓고 실행 시간을 y축으로 해서 그래프를 그려 보면 오른쪽 위를 향하는 직선이 될 것이다.
• 일상생활에서 접하는 많은 알고리즘은 선형이다 왜냐하면 어떤 데이터에 대해 동일한 기본 연산을 수행해야 하는데, 데이터 수가 많아지면 곧 그의 정비례하게 많은 일이 필요 하기 때문이다

선형 탐색 알고리즘(Linear Search)

순차 검색 알고리즘이라고도 부르는 선형 탐색은 찾고자 하는 값을 리스트의 맨 앞부터 끝까지 차례대로 찾아 나가는 것

• 시간복잡도: O(n)
• 장점: 검색 방법 중 가장 단순하여 구현이 쉽고 정렬되지 않은 리스트에서도 사용
• 단점: 검색 길이가 길면 비효율적

시간 복잡도를 더 알고 싶다면 ?

(https://velog.io/@junyong92/TIL-Time-Complexity)