[Software] #1 소프트웨어와 선형 알고리즘

Chapter 2 : 소프트웨어 

해당 게시물은 [1일 1로그 100일 완성 IT 지식] 책을 기반으로 진행한 스터디 내용을 정리합니다. 😎

Chapter 1에서 Hardware에 대해서 다뤘습니다.

Capter2 에서는 Software라는 상반된 개념에 대해서 배워봅시다.

---

소프트웨어는 컴퓨터가 뭔가 유용한 일을 하게 해주는 일련의 명령어를 의미하는 일반적인 용어이다.
*컴퓨터에게 동작 방법을 지시하는 명령어 집합의 모임

딱딱한(Hard) 하드웨어와는 대조적으로 부드러운(Soft) 것 즉, 형체가 없다. 하드웨어는 형체가 있어서 노트북을 떨군다면 바로 알아챌 수 있지만 소프트웨어는 그렇지 않다. 2부는 "소프트웨어" 다른 말로 컴퓨터에게 무엇을 해야할 지 알려주는 방법에 대해 얘기한다. 

프로그램 소프트웨어는 컴퓨터 하드웨어에 직접 명령어를 주거나 다른 소프트웨어에 입력을 제공함으로써, 명령어의 기능을 수행한다. (소프트웨어는 구현된 기능을 수행하는 것이 목적이다.)
컴퓨터 소프트웨어는 컴퓨터 하드웨어의 반대 의미로, 컴퓨터 하드웨어는 해당 일을 실제로 수행하는 시스템이다. 쉽게 설명하자면 생명체를 하드웨어라고 가정한다면, 그를 구성하는 유전자가 소프트웨어라고 생각할 수 있다.

소프트웨어 상세내용 참고 자료: http://kocw-n.xcache.kinxcdn.com/data/edu/document/cuk/songhyunjoo1206/1.pdf

 

서론 : 소프트웨어의 불완전성

최신 기술 시스템은 범용 하드웨어(프로세서, 메모리, 외부 환경과의 연결 장치)를 더 많이 사용하고 구체적인 작동 방식은 소프트웨어로 구현하는 추세이다.

소프트웨어가 하드웨어보다 더 저렴하고, 유연하고, 바꾸기 쉽다는 통념이 있다. 이에 따라 기차, 선박, 항공기 등 여러 곳에서 소프트웨어가 차지하는 비중도 더 커졌다. 하지만, 시스템의 물리적 작동 방식을 바꾸는데 소프트웨어를 사용하는 일은 항상 간단하지만은 않다. 

예시로 "보잉 737 MAX"가 있다. 기존 비행기에 새 엔진이 탑재되면서 해당 비행기의 특성이 크게 달라졌고 사측은 비용절감을 위해 자동화된 비행 제어 소프트웨어 시스템을 개발하는 방법을 택했다(비행기 모델이 재인증을 받거나 조종사가 재훈련을 받을 필요가 없기 때문에). 하지만 새로 개발된 소프트웨어는 조종사의 명령을 무시하고 오작동을 일으켜 2 차례의 대형 추락사고로 이어졌다. 

https://www.hani.co.kr/arti/international/international_general/962551.html

346명 숨진 보잉 737맥스 추락, ‘설계 결함 은폐’ 탓

결론적으로 완전히 신뢰가능한 소프트웨어는 작성하기는 어렵다. 논리나 구현에서 간과한 부분이 있다면 프로그램이 오작동하거나 정상적인 사용 시나리오에는 문제가 없더라도 보안 측면에서 떨어질 수 있다.

---

 

[Chapter 18] 알고리즘과 초콜릿 케이크 레시피 

'파인만'의 문제 해결 알고리즘:
(1) 문제를 쓴다.
(2) 매우 깊게 생각한다.
(3) 답을 쓴다.
-물리학자 리차드 파인만이 썼다는 문제해결 알고리즘.
오직 파인만에게만 적용되기 때문에 '파인만 알고리즘'이라 한다.(?)

 

소프트웨어를 음식을 만드는 레시피에 비유하곤 하는데 음식을 만드는 레시피와 소프트웨어의 유사점은 아래와 같다. 

• 필요한 요리재료 / 연산에 필요한 데이터 
• 요리사가 수행해야하는 작업 순서 / 데이터에 대해 수행할 작업 설명
• 요리 결과물  / 예상 결과 

하지만 말 그대로 유사한 것 뿐이지 요리 레시피의 경우 프로그램에 필요한 수준보다 훨씬 모호한 설명이 많기 때문에 적절한 비유가 아니다. e.g.) 잘 익으면 표면 위에 손바닥을 살짝 올려 확인하세요. (잘 익은 기준은..? 뭘 확인하라는 것인가?)

그래서 현실에서 굳이 비교를 하자면 레시피보단 납세 신고서가 더 적절하다고 저자는 말한다. 

• 납세 신고서가 더 적절한 이유: 레시피보다 계산적 측면을 더 잘 담아냄 -> 납세 신고서는 산술 연산이 필요하고, 데이터 값을 한 곳에서 다른 곳으로 복사하고, 조건을 검사하고, 차후의 계산은 기존 계산 결과에 달려있음 

그렇지만 결론적으로 납세 신고서도 레시피와 마찬가지로 용어가 명확하지 않고 설명이 모호하며 데이터 값이 불확실할 때가 자주 있기 때문에 소프트웨어는 컴퓨터과학 버전의 레시피인 "알고리즘"에 비유하는 것이 적절하다.

알고리즘이란?

정의: 결과를 정확하게 계산하도록 보장된 일련의 단계이다. 

*알고리즘(라틴어, 독일어: Algorithmus, 영어: algorithm )이란 어떠한 문제를 해결하기 위한 여러 동작들의 모임이다. 유한성을 가지며, 언젠가는 끝나야 하는 속성을 가지고 있다. 수학과 컴퓨터 과학에서 알고리즘이란 작동이 일어나게 하는 내재하는 단계적 집합이다. 알고리즘은 연산, 데이터 진행 또는 자동화된 추론을 수행한다.

알고리즘의 각 단계는 기본 연산으로 표현되며 의미는 명확하게 명시돼야 한다. 알고리즘 내 모든 구성 요소의 의미는 모호함이 있어선 안된다. 데이터의 유형 명시까지 표시해야 하며 모든 가능한 상황을 다루어야 한다.  만족 조건은 아래와 같다.

 

알고리즘 만족 조건 

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

알고리즘의 효율성

개념: 처리 데이터 양에 따라 계산에 소요되는 시간을 표현하는 방법 (= 시간 복잡도)

-시간복잡도는 Big O표기법을 사용해 나타낸다.

• 효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 이야기이다. = 처리할 데이터가 커도 처리하는 소요 시간은 적은 알고리즘이 효율적인 알고리즘

시간복잡도 & Big O 표기법 상세 설명: 

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

[알고리즘] Time Complexity (시간 복잡도) - 하나몬

 

 

 

---

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

선형 알고리즘

반에서 가장 키 큰 사람을 찾을 때, 기본적인 접근 방법은 한명씩 키를 물어보고 이전 값과 현재 값을 비교하여 모든 반 학생의 키를 다 물어보고(각각 동일한 절차를 수행) 가장 큰 값을 도출해내는 방법이다. (for문을 배열의 길이만큼 돌리는 거랑 같은 거라고 생각하시면 될듯)

-> 해당 예시처럼 계산 시간이 데이터의 양에 정비례하거나 선형적으로 비례할 때, 그 알고리즘은 선형 시간(linear-time) 또는 선형(linear)이라고 한다. 여기서 선형은 '직선'을 생각하시면 됩니다. 

만약 각 항목에 대한 연산이 거의 같은 시간이 걸린다면 전체 시간은 항목 수에 비례한다. 

 

아래 그림을 보시면 x축이 입력값(데이터 양)이고 y축이 계산시간입니다. 직선(linear)으로 정비례한 것을 알 수 있습니다. 

*Big O표기법으로 선형 시간(linear time)은 O(n)으로 표시합니다. 

 

선형 = O(n) 

선형(linear) 시간 = O(n)

Big O 표기법 선형시간 포함 다른 것들

가파를수록 좋지않은 알고리즘

여기서 다른 조건이 추가되면 상황이 복잡해지는데 (중복값 처리, 키가 같은 무리 중 가장 사람 수가 많은 무리 찾기 등) 이런 문제를 해결하려면 자료구조(Data Structure)가 필요하다. 자료구조는 간단히 말하면 계산 과정에서 필요한 정보를 표현하는 방법이다.  

자료구조(資料構造, 영어: data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.[1][2][3] 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다.[4] 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다.

자료구조 예시 - 배열(Array), 연결리스트 등

알고리즘과 컴퓨터는 모든 가능한 상황을 처리해야 한다. (코드에서 오류가 날 경우를 대비하여 예외처리하는 것처럼)

-> 알고리즘은 처리하기 곤란한 경우를 명시적으로 검사함으로써 잠재적으로 발생할 수 있는 문제를 해결한다.