[도서] 1일 1로그 100일 완성 IT지식 #소프트웨어(18~26, 34~35)

✅ 소프트웨어 18번 : 알고리즘과 초콜릿 케이크 레시피

 

👌 소프트웨어란?

 

컴퓨터가 무언가 유용한 일을 하게 해주는 일련의 명령어 집합의 모임. 컴퓨터 소프트웨어는 컴퓨터 하드웨어의 반애 의미로, 컴퓨터 하드웨어는 해당 일을 실제로 수행하는 시스템이다. 쉽게 설명하자면 생명체를 하드웨어라고 가정한다면 그를 구성하는 유전자가 소프트웨어라고 생각할 수 있다.

 

👌 알고리즘이란?

 

수학과 컴퓨터 과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다. 계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 즉, 문제 풀이에 필요한 계산 절차 또는 처리 과정의 순서를 뜻한다.

 

👌 알고리즘의 조건

 

🔹 입력(Input) : 알고리즘 수행에 필요한 자료가 외부에서 제공되어야 한다.

🔹 출력(Output) : 알고리즘 수행 후 하나 이상의 결과가 출력되어야 한다.

🔹 명확성(Definiteness) : 수행할 작업의 내용과 순서가 명확해야한다.

🔹 유한성(finiteness) : 문제 해결뒤엔 반드시 종료되어야 한다.

🔹 효과성(effectiveness) : 모든 명령어들은 실행이 가능해야한다.

 

 

👌 자료구조란?

 

자료구조는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 장을 예로 들어보면 책장에 꽂아 넣으려고 하는데 책을 알파벳 순서로 꽂아둘 것인지 아니면 책상에 쌓아 올려둘 것인지를 결정하는 것, 즉 이런 데이터가 저장된 형태를 결정하는 것이 자료구조이다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다.

 

 

✅ 소프트웨어 19번 : 반에서 가장 키 큰 사람 찾기 - 선형 알고리즘

 

👌 선형 알고리즘(선형 검색)

 

데이터가 모인 집합의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘이다.

데이터를 정렬하거나 따로 건드릴 필요가 없고 난이도가 쉬운 편이나, 데이터의 양이 많아지면 검색에 소요하는 시간도 비례하여 많아지므로 하나씩 일일이 비교하기 때문에 비효율적이라는 단점이 있다.

 

데이터가 모인 집합(배열, 링크드리스트 등)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘이다.

 

참고 출처 : https://andrew0409.tistory.com/143

 

 

✅ 소프트웨어 20번 : 10억 개 전화번호에서 이름 찾기 : 이진 검색

 

1️⃣ 이진 검색(binary search)

 

각 확인 또는 비교 단계를 거치면서 항목들이 두 그룹으로 나뉘고 그중 한쪽 그룹은 다음 고려 대상에서 제외될 수 있다. 

 

이진 검색은 분할 정복 divide and conquer이라는 일반적인 전략의 한 가지 예이다.

 

log를 생각해보면 되는데 log에는 밑수가 2가 있으므로 log 1024는 10이 된다. 1024가 2의 10승이므로,

 

그럼 10억을 계산할 때는 log 10억 = 30이 된다. 10억이 2의 30승이므로

 

 

✅ 소프트웨어 21번 : 검색을 쉽게 만드는 정렬 : 선택 정렬 vs 퀵 정렬

 

1️⃣ 정렬(sorting)

 

항목을 순서대로 배열해서 검색이 빨리 실행될 수 있도록 해준다.

 

 

👌 선택 정렬(selection sort)

 

알파벳 순으로 여러가지 단어를 배치해두었을 때, 앞 부분부터 시작해서 배치를 하기 시작한다. 두 번째 이름을 찾기 위해 과정을 반복한다. 정렬되지 않은 무리 중 첫 번째 이름부터 시작해서 자리를 빼앗고 첫 번째 요소가 된다.

 

남아 있는 항목들 전체를 반복하여 검사하면서 매번 알파벳순으로 다음에 오는 이름을 찾는다.

 

이름을 훑어보는 횟수는 원래 항목의 수에 정비례한다.

 

N + (N-1) + (N-2) + (N-3) + ... + 2 + 1

 

이 수열의 합계는 N X (N+1) / 2이 되고 풀어서 계산하면 N의 제곱 / 2+N / 2이 된다. 2로 나누는 걸 무시하면 N의 제곱 + N에 비례한다. N의 제곱은 금방 N보다 훨씬 큰값이 되므로 결과적으로 일의 양은 N의 제곱에 거의 비례하게 되는데 이러한 증가율을 2차 quadratic라고 한다.

 

 

👌 퀵 정렬(Quick sort) 알고리즘

 

선택 정렬과 달리 먼저 이름을 한 번 훑어보면서 첫 글자가 A에서 M까지인 이름을 한 그룹으로 모으고 N에서 Z까지인 이름을 다른 그룹으로 모은다. 이렇게 하면 그룹이 두 개 생기고 각각에 절반 정도의 이름이 들어가 있다. 이런 과정을 반복해서 단계를 줄인다.

 

퀵 정렬은 매번 거의 같은 크기의 두 그룹으로 나눌 수 있도록 중간 데이터 값을 추측해야만 한다. 퀵 정렬로 N개 항목을 정렬하려면 약 NlogN번의 연산이 필요하다. 즉, 작업의 양은 N x log N에 비례한다.

 

모든 단계에서 선택 정렬은 퀵 정렬보다 성능이 압도적으로 뒤처지며, 경쟁이 되지 않는 수준이다.

 

 

✅ 소프트웨어 22번 : 10개 도시를 최단거리로 여행하는 법

 

1️⃣ 복잡도

 

🔹 N : 데이터의 양

🔹 복잡도 : 여기서 말하는 복잡도란 알고리즘 복잡도, 알고리즘을 위해 필요한 연산의 횟수, 작업량, 작업시간 등 다양한 의미를 지닌다.

 

 

👌 logN의 복잡도

 

이진 검색이 이에 해당되며, 데이터량(N)의 증가대비 일의 양(logN)은 천천히 늘어난다. 따라서, 효율이 높은 알고리즘이다.  .log₂2 = 1log₂4 = log₂2² = 2

 

🔹 N의 복잡도

 

데이터량과 일의 양이 정비례한다.

 

🔹 NlogN의 복잡도

 

단순 선형인 "N" 보다는 일의 양이 더 빨리 증가하기 때문에, 효율이 낮지만 로그인자가 상당히 느리게 증가하며 매우 큰 N값에 대해서도 효과적으로 활용 가능하다.

 

🔹 N² 복잡도

 

일의 양이 매우 빨리 늘어난다.

 

 

👌 지수(exponential) 복잡도

 

N²과는 다른, 2ⁿ과 같은 지수(exponential) 복잡도도 있다. logN 과 정반대로 일의 양이 두 배씩 늘어난다.

 

 

🔹 왜 발생할까 ?

 

이러한 지수 알고리즘은 모든 가능한 경우의 수를 하나씩 시도해야 하는 경우에 발생한다.

 

 

🔹 어디에 필요할까 ? 

 

일의 양이 너무 급속히 늘어나기 때문에, 오히려 장점으로 쓰이는 경우가 있다(ex> 암호 기법).

암호 기법에서는 지수 복잡도에서 N의 값을 계산상 실행 불가능한 수준까지 높인다. 그러면, 해당 꼐산을 실행하는데 너무 오래 소요되므로 적의 공격에 대해 방어할 수 있다.

 

 

👌 다항

 

쉬운 문제는 복잡도 면에서 "다항"이다? 실행시간이 N² 같은 다항식인 경우 컴퓨터 과학자들은 이러한 부류의 문제를 다항을 의미하는 p(polynomial)라고 부른다.

 

 

2️⃣ NP 문제

 

실제로 발생하는 문제, 예를 들어 10개의 도시를 최단거리로 여행하는 법 같은 경우 우리가 아는 다항 알고리즘으로 풀수 없다. 이를 NP문제라고 한다.

 

 

 

🔹 경로의 수를 구하는 공식 : (n-1)! / 2 = 181,440

 

 

여행하는 외판원 문제(Traveling Salesman Problem)를 줄여서 TSP라고도 하는데 대표적인 NP(Nondeterministic Polynomial time problem)문제이다.

 

NP problem은 컴퓨터로 답이 되는 경우를 찾을 수는 있지만, 완벽하게 답을 빠르게 찾을 수 없는 문제를 말한다. N의 값이 작을 때는 상관없지만 커지게 되면 계산 시간이 지수 함수적으로 증가하기 때문에 답을 구하는 시간이 기하급수적으로 증가하기 때문이다.

 

 

▶️ 책에서 첫번째 (그림II.2) 최근적 이웃 해법, 휴리스틱으로 찾은 해법이 표시되었다. 방문하지 않은 도시 중에서 가장 가까운 도시로 이동하는 방식이다.

 

▶️ 책에서 두번째( 그림 II.3) 경로의 수를 구하는 공식 : (n-1)! /2 = 181,440에 따라, 약 18만개 전체 경로를 일일히 탐색해서 최단 경로를 찾은 것이다. 최근접 이웃법 보다 약 8% 짧다.

 

 

나름 효율적인 최근접 이웃법, 휴리스틱 방법으로 계산해도, 이러한 오차가 난다.

NP 문제를 푸는데 있어서 가능한 모든 경우를 완전 탐색하는 것보다 더 정확하고 효율적으로 풀 방법이 없다는 의미이다.

 

 

✅ 소프트웨어 24번 : 알고리즘은 이상, 프로그래밍은 현실

 

1️⃣ 알고리즘은 이상

 

알고리즘은 추상적이고 이상적인 절차를 기술한 것으로, 구현에 필요한 세부 사항과 현실적인 고려 사항을 무시한다.

 

 

▶️ 1단계 : 의미가 완전히 알려져 있고 구체적으로 명시된 기본 연산으로 표현

▶️ 2단계 : 기본 연산을 사용하여 각 단계를 상세히 설명

▶️ 3단계 : 알고리즘은 결국 멈춰야 한다.

 

2️⃣ 프로그래밍은 현실

 

프로그램은, 하나 이상의 알고리즘이 컴퓨터가 직접 처리할 수 있는 형태로 표현된 것으로 생각해볼 수 있다.

 

❓ 위에 내용에서 알고리즘은 "세부 사항과 현실적인 고려 사항을 무시한다" 라고 되어 있다.

 

❓ 프로그램 : 불충분한 메모리, 제한된 프로세서 속도, 유효하지 않거나 악의적으로 잘못된 입력 데이터, 하드웨어 결함, 네트워크 연결 불량, 인간적인 약점 등까지 고려해야 한다.

 

 

👌 왜 프로그래밍 언어가 논의 되는지 : 자바스크립트, 파이썬 등

 

프로그래머가 충분히 많지 않아서, 모든 것을 컴퓨터가 수행하도록 프로그래밍할 수 없다. 그러다 보니, 컴퓨터가 프로그래밍 세부 사항을 더욱 많이 처리할 수 있도록 논의하였고 프로그래밍 언어까지 논의가 이어진 것

 

 

✅ 소프트웨어 25번 : 다른 프로그램을 처리하기 위한 프로그램

 

1️⃣ 어셈블러(assembler)

 

👌 ADD와 Sum

 

이전에는, 의미있는 단어를 사용해서 작업을 처리했다. 5,14 처럼...

 

 

🔹 5 = 지금의 ADD

🔹 14 = 지금의 Sum

 

 

1950년대 초, 단순 반복 작업을 처리하기 위해 프로그램이 몇 가지 만들어졌고 위 예시처럼 5를 ADD로, 14를 Sum 으로 사용할 수 있게 되었다.

 

이처럼 특정한 처리를 수행하는 프로그램을 어셈블러라고 한다.

 

 

▶️ 어셈블리 언어(assembly language) : 어셈블러 프로그램 작성에 사용되는 언어

▶️ 어셈블리 언어 프로그래밍(assembly language programming) : 어셈블러, 어셈블리 언어 수준의 프로그래밍

 

 

2️⃣ 어셈블러의 어려운 점

 

👌 프로세서에 따라 달라진다!

 

🔹 특정 종류 프로세서, 예를 들어 맥이나 PC의 인텔 프로세서의 어셈블리 언어로 작성된 프로그램은 다른 프로세서, 예를 들어 휴대전화의 ARM  프로세서에 맞춰 작성된 프로그램과는 다르다.

 

🔹 즉, 다른 프로세서용으로 변환하고 싶다면 프로그램을 완전히 새로 작성해야 한다.

 

 

▶️ 모형 컴퓨터에서 두 개의 수를 더하고 결과를 메모리 위치에 저장하려면 세 개의 명령어가 필요하다.

 

LOAD X
ADD Y
STORE Z

 

 

▶️ 누산기를 사용하지 않고 메모리 위치에 접근하는 두 개의 명령어로 처리할 수도 있다.

 

COPY X, Z
ADD Y, Z

 

즉, 다른 프로그램에서 실행되도록 변환하려면 프로그래머는 두 프로세서의 세부 사항을 모두 잘 알고 한쪽 명령어 집합을 다른 쪽으로 변환할 때 주의를 기울어야 해서, 어려운 일이다.

 

 

✅ 소프트웨어 26번 : 고수준 언어에서 프로그램 실행까지

 

1950년대 말, 1960년대 초 프로그래밍 역사상 가장 중요한 발걸음

 

1️⃣ 고수준 언어

 

특정 프로세서 아키텍처에 독립적긴 고수준 프로그래밍 언어의 개발

 

- 사람이 표현하는 방식에 가까운 용어로 계산 과정을 작성할 수 있다.

- 고수준 언어로 작성된 코드 → 대상 프로세서의 어셈블리 언어로 된 명령어로 변환(번역기 프로그램) → 어셈블러에 의해 비트로 변환되어 메모리에 로드, 실행

- 사람들이 생각하는 방식에 더 가까워 배우고 사용하기 더 쉽다.

- 프로그램을 효율적으로 짜기 위해 특정 프로세서의 명령어 레퍼토리를 알아야 할 필요가 없다.

- 특정 아키텍처에 종속되지 않는다 => 같은 프로그램이 여러 아키텍처상에서 실행될 수 있다.

 

 

🔷 번역기 프로그램 : 보통 컴파일러 compiler라고 불린다.

 

Z = X + Y

연산자 '='는 '같다'가 아니라 '대체하다' 또는 '저장하다'라는 뜻으로 쓰인다.

 

- 컴파일 단계는 몇 가지 명백한 에러를 미리 점검하게 해준다.

- 철자 오류, 괄호 불일치 같은 구문 오류, 정의되지 않은 변수에 대한 연산 같은 것들이 포함되며 프로그래머가 이러한 에러를 반드시 고쳐야 한다.

 

 

🔷 고수준 프로그래밍 언어 여섯 가지 : 포트란, C, C++, 자바, 자바스크립트, 파이썬

 

 

👌 포트란 FORTRAN

 

- 초창기 언어 중 하나

- 수식 변환(Formula Translation)에서 유래

- IBM팀에서 개발, 과학자 공학 분야에서 계산을 표현하는데 성공적으로 사용

 

 

👌 코볼 COBOL

 

- 특히 사무 데이터 처리 목적으로 사용

- 재고 관리, 송장 작성, 급여 계산 등에 사용되는 자료 구조와 계산을 쉽게 표현할 수있는 언어적 특성이 있다.

 

 

👌 베이직 BASIC

 

- 프로그래밍 교육을 위한 쉬운 언어로 만들어졌다.

- 간단하면서 컴퓨팅 자원을 적게 필요로 해서 개인용 컴퓨터에서 사용할 수 있는 첫 번째 고수준 언어

- 빌 게이츠와 폴 앨런, 1975년 알테어 Altair 마이크로컴퓨터용 베이직 컴파일러를 만들면서 사업 시작

- 베이직의 주요한 변종인 마이크로소프트 비주얼 베이직은 오늘날에도 활발하게 지원되고 있다.

 

2️⃣ 어셈블러

 

- 각자의 어셈블리 언어 명령어를 실제 명령어의 비트 패턴으로 변환

- 변수 X, Y, Z 를 저장할 메모리 위치를 확보하는 일 담당

 

 

✅ 소프트웨어 34번 : 가상 운영체제와 가상 머신

 

1️⃣ 초기 운영체제

 

- 메모리도 더 작고 작업이 더 단순해 크기가 작았다.

- 한 번에 한 개의 프로그램만 실행했으므로 스와핑이 제한적으로 이루어졌다.

- 할당한 메모리 : 100KB 미만으로 많지 않았다.

- 다뤄야 할 외부 장치가 적었으며 오늘날처럼 종류가 다양하지 않았다.

 

2️⃣ 오늘날 프로그램

 

- 다양하고 복잡한 일을 처리하기 때문에 운영체제가 매우 크고 복잡하다.

- 프로그램 하나가 차지하는 메모리는 MB, GB 단위로 훨씬 크다.

 

3️⃣ 리눅스

 

- 리누스 토르발스가 1991년 유닉스를 자신만의 버전으로 만들기로 결심하면서 시작했다.

- 10,000행이 조금 안 되는 초안을 게시했고 다른 이들에게 써보고 도움을 달라고 요청하면서 그때 이후 소프트웨어 산업에서 막대한 영향력을 가진 운영체제가 되었다.

- 오픈소스이므로 누구든 사용하고 기여하며 전업 개발자들이 중심에 있으나, 토르발스가 여전히 전반적인 통제권을 유지하고 있으며 기술적 결정의 최종 결정권자이다.

 

 

👌 멀티 부트(multiple boot) 기능

 

- 애플에서도 부트 캠프라는 이름으로 지원한다.

- 맥이 맥 OS 대신 윈도우를 실행하면서 시스템을 시작할 수 있도록 한다.

- 다른 운영체제의 관리하에 어떤 운영체제를 가상 운영체제로 실행할 수도 있다.

 

👌 가상 운영체제 관련

 

▶️ 소유권 문제 : 마이크로소프트의 윈도우 라이선스는 비용을 내지 않고 합법적으로 실행할 수 있는 가상 인스턴스 사본의 총 개수를 제한하고 있다.

 

▶️ 가상 머신 : 컴퓨터인 것처럼 작동하는 프로그램, 소프트웨어로만 작동하지만 마치 하드웨어인 것처럼 그 작동 방식을 모방하는 프로그램

 

- 가상 머신이 사용되는 이유는 물리적 장비를 만들어서 출하하는 것보다 프로그램을 작성해서 배포하는 것이 더 쉽고 유연하기 때문이다.

 

- 클라우드 컴퓨팅 : 해당 서비스 제공 업체는 저장 공간과 네트워크 대역폭이 충분한 물리적 컴퓨터를 대량으로 보유하고 있고 이런 자원을 이용해 고객에게 컴퓨팅 성능을 제공한다.

 

 

🔹 AWS : 아마존 웹 서비스

 

최대 클라우드 컴퓨팅 제공 업체이며, 마이크로소프트 애저와 구글 클라우드 플랫폼이 그 뒤를 잇는다.

 

 

✅ 소프트웨어 35번 : 운영체제가 일하는 법

 

1️⃣ 부팅

 

1. 컴퓨터가 켜졌을 때 영구 기억 장치에 저장된 약간의 명령어를 실행해서 작동하도록 구성

2. 이 명령어로 플래시 메모리에서 명령어를 읽고(위치, USB 메모리 등)

3.  더욱더 많은 명령어를 읽는다.

 

즉, 컴퓨터가 작동을 시작하는 과정을 의미하며 원래 '자력으로 해내다'의 오래된 표현에서 나온 부트스트래핑'이라고 불렸으나, 지금은 부팅이라고 한다.

 

 

👌 시간 조각

 

1. 실행할 준비가 됐거나 관심이 필요한 각 애플리케이션에 차례로 통제권을 준다.

2. 웹 서핑을 하거나, 음악을 재생하면 운영체제는 이 프로세서 각각에 관심을 갖고 처리하게 한다.

3. 필요에 따라 프로세스 간에 초점을 전환한다.

4. 각 프로그램은 짧은 시간 조각을 할당받는다.

5. 프로그램이 시스템 서비스를 요청하거나 할당된 시간이 다 되면 끝난다.

 

 

2️⃣ 시스템 콜

 

1. 운영체제는 애플리케이션에 제공하는 작업이나 서비스의 집합을 정의한다.

2. 파일로 데이터를 저장하거나 데이터 가져오기, 마우스 움직임 등이 포함된다.

3. 운영체제는 표준화된 방식 또는 합의된 방식으로 서비스를 이용하게 한다.

4. 애플리케이션은 운영체제의 특정 부분에 통제권을 넘겨주는 명령어를 실행함으로써 서비스를 요청한다.

5. 운영체제는 요청에 포함된 어떤 일이든 처리하고 통제권과 처리 결과를 애플리케이션에 돌려준다.

6. 운영체제에 서비스를 요청하는 이 진입점을 시스템 콜이라 한다.

 

3️⃣ 디바이스 드라이버

 

운영체제와 프린터나 마우스 같은 특정 종류의 하드웨어 장치 간에 가교 역할을 하는 코드

 

4️⃣ 다양한 디지털 장치와 운영체제

 

EX) 디지털 카메라 : 렌즈가 달린 컴퓨터

 

정교한 사용자 인터페이스를 제공하기도 하고 다른 시스템과 통신할 수 있도록 네트워크 연결도 가능해지면서, 별도의 운영 체제를 만들기보다는 범용 운영체제를 사용하는 방식이 더 타당해졌다.

 

👌 리눅스를 쓸 경우

 

▶️ 장점

 

- 자신만의 전용 시스템을 개발하거나 값비싼 사용 제품의 라이선스를 얻는 것보다는 리눅스에서 불필요한 부분을 뺀 버전을 사용하는 편이 더 쉽고 저렴하다.

 

- 견고하고 개조하기 용이하고 이식 가능하고 무료이기 때문이다.

 

 

▶️ 단점

 

- GPL 같은 라이선스에 따라 결과물 코드 일부를 공개해야 될 수 있다.