1일 1로그 100일 IT지식

내가 읽은 글을 생각하고 정리해본 것 (사람마다 생각이 다를 수 있음)

 

소프트웨어(software)란? 

컴퓨터가 뭔가 유용한 일을 하게 해주는 일련의 명령어를 의미하는 일반적인 용어다.

---

Chapter 18  :  알고리즘과 초콜릿 레시피

알고리즘(algorithm)이란?

수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다.

 

알고리즘 이름의 유래

https://ko.wikipedia.org/wiki/%EC%BD%B0%EB%A6%AC%EC%A6%88%EB%AF%B8

콰리즈미 - 위키백과, 우리 모두의 백과사전

 

파인만 알고리즘이란?

미국의 유명한 물리학자인 리처드 파인만이 제시한 '일반적인' 문제 해결법이다.

 

1. 문제를 적는다.
2. 골똘히 생각한다.
3.  답을 적는다.

 

ex)

1. spring 입문 고민 
2. 고민하면 해결할 수 있는 문제인가? 골똘히 생각해 본다.
3. 고민한 결과는 적는다. 문제가 해결되면 OK 안되면 문제가 잘못 됬을 수 있으니 다시 1번을 간다.

 

 

알고리즘은 

결과를 정확하게 계산하도록 보장된 일련의 단계~ 즉, 어떤 일을 해결하려는 방법과 절차이다.

알고리즘을 이루고 있는 모든 구성요소의 의미에 한치의 모호함도 있어서는 안된다.

또한, 알고리즘은 결국 언제가는 멈취야 한다. 끝나지 않게 구현한 알고리즘은 '알고리즘'이 아니다.

 

 

 

알고리즘의 조건

알고리즘은 결과가 정확하게 계산되어야 하기에 5가지의 조건을 만족해야 한다.

1. 입력 : 외부에서 제공되는 자료가 0개 이상 존재해야 한다. (입력되는 자료가 없으면 알고리즘이 실행되지 않는다.)
2. 출력 : 입력을 받아 적어도 1개 이상의 출력이 있어야 한다. (입력이 있다면 반드시 출력도 있어야 한다.)
3. 명확성 : 각 단계가 단순해야 하며, 모호하지 않아야 한다. (케이크 레시피를 들자면.. '오븐에서 30분, 또는 반죽이 자리 잡을 때까지 구우세요' 라고 말했다면 굽는 시간은 반드시 30분이어야 하나? 30분을 넘기면 안되나? 라고 조건이 모호해 진다. )
4. 유한성 : 한정된 수의 작업 후에는 반드시 끝나야 한다. (알고리즘이 멈추어야 한다.)
5. 효율성 : 알고리즘이 효율적이어야 한다. (모든 과정은 명백하게 실행 가능, 검증 가능한 것이어야 한다. 주어진 양의 데이터를 처리하는데 얼마나 시간이 걸리나)

 

그림 참조 : 휴몬랩 메이커

---

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

반에서 가장 키 큰 사람 찾기~ 한명만 찾고 싶을때는 일일이 물어보고 가장 큰 사람만 기억하면 된다.

하지만 가장 큰 키가 같은 사람이 있다면??? 누구를 기록해야 하지?????

 

이런문제를 해결하려면 '자료구조'가 필요하다.

자료구조는 계산 과정에서 필요한 정보를 표현하는 방법이다. (지금은 이정도만 알아두자!)

 

예를 들어 전체 키의 평균을 계산하고 싶다면

종이에 N명의 키(height) 목록이 쓰여 있다고 가정할때

---

진짜진짜 너무너무 하기싫어

---

이 예시는 알고리즘의 조건인 입력, 출력, 명확성, 유한성, 효율성을 모두 만족한다.

 

하지만, 만약 종이에 아무런 정보가 없다면? 알고리즘 조건에 부합하지 않는다.

사람이라면 할 일이 없다는 것을 금방 알아차릴 수 있지만, 컴퓨터는 그렇지 못하다.

 

때문에, 데이터 항목이 없을 경우를 대비해서 컴퓨터에게 알려주어야 한다.

 

---

---

알고리즘에서 중요한 특성 중 하나는 아까 언급했던 얼마나 효율적으로 작동하느냐 이다.

 

방안의 사람의 수가 10명일때 이를 계산하는 알고리즘이 1초 걸리고,

20명일때 2초,

30명일때 3초,

x축을 데이터 항목의 수, y축을 실행시간이라고 했을때

이렇게 계산시간이 정비례하거나 선형(직선처럼 똑바른 도형)적으로 비례하는 것을 선형 알고리즘이라고 한다.

 

 

 

 

 

 

 

 

 

 

선형 알고리즘의 기본형태

1. 먼저 초기화가 필요하다. (예를 들면 누적합계를 0으로 설정하거나, 가장 큰 키를 어떤 작은 값으로 설정하는 것이다.)
2. 각 항목을 차례로 검사하고, 항목에 대해 간단한 계산을 수행한다. (수를 세거나, 비교하거나, 변환하거나)
3. 작업을 끝내기 위한 어떤 단계가 필요하다 (예를들면 출력하는 것~!)