컴사SW 파이썬 정리본

고대의 컴퓨터

- 컴퓨터의 역사는 주판, 계산자, 계산판 등에서 시작

- 가장 오래된 기계적인 아날로그 컴퓨터:  Antikythera(고대 그리스)

 

소프트웨어 등장

- 직조기 (최초의 프로그램이 가능했음)

- 찰스 배비지: 해석기관(총 4가지의 핵심적인 컴포넌트: 중앙처리장치, 메모리, 출력장치, 입력장치)

   feat. 해석기관은 영국의 수학 교수 찰스 배비지가 고안한 기계적 범용 컴퓨터의 설계이다. 1837년에 처음으로 발표되었으며, 설계는 1871년 그가 죽기 전까지 계속되었다. 해석기관은 경제적, 정치적, 법적 문제로 인해 실제 만들어지지는 않았다.

 

현대적인 컴퓨터

(1) 기계보다도 전자장치를 사용해서 계산

(2) 아날로그가 아닌 디지털 방식

(3) 내장 프로그래밍 방식

 

전자식 숫자 적분 및 계산기(Electronic Numerical Integrator And Computer; ENIAC, 에니악)는 1943년에서 3년에 걸쳐서 1946년 2월 14일에 펜실베이니아 대학의 모클리와 에커트가 제작한 전자 컴퓨터이다.

 

현대 컴퓨터의 프로그램 실행 방법

1. Fetch : CPU의 레지스터로 명령어를 가져온다.

2. Decode : 가져온 명령어를 컨트롤 유닛에서 해석한다.

3. Execution : 해석된 명령어대로 ALU에서 CPU가 실행한다.

 

ALU : CPU에서 논리연산이나 산술연산과 같은 실제 연산을 담당하는 부분

컨트롤 유닛 : ALU는 명령어 자체 이해 및 수행 X,  명령어를 해석 ->  ALU에게 알려줌

레지스터 : CPU에 명령어가 왔지만, ALU와 컨트롤유닛이 다른 작업 중일 수 있음. 이때 임시로 데이터를 저장하는 CPU내의 작은 메모리(CPU에 여러 개 존재)

Bus Interface(Adapter) : I/O Bus의 통신을 가능하게 해주는 장치, CPU가 데이터를 버스에 주거나 버스로부터 데이터를 받고 오게 해 줌. (통신방식에 맞게 데이터의 입출력을 도와줌)

 

"하드웨어" 때문에 2진수 사용

- 전자공학 관점에서 볼 때, 10개의 전압레벨보다 2개의 전압레벨을 구별하는 회로를 설계하는 것이 더욱 쉬움

- 컴퓨터 내부에 데이터를 저장하려면 10진수 보다 2진수가 더욱 효율적

 

bit(binary digit)

- 1 or 0

- 8 bit = 1 byte

 

컴퓨팅적 사고를 통한 문제해결

  1단계: 컴퓨팅적 사고기법

  2단계: 컴퓨터처럼 생각하기

  3단계: 컴퓨터를 사용한 문제 해결

 

컴퓨팅적 사고: 문제를 해결할 때, 필요한 자료를 추출하고 분석하고 일정한 경향을 파악해 컴퓨터로 문제를 해결하기 위한 절차를 만드는 것

 

컴퓨팅적 사고의 6가지 개념

(1) 논리: 논리적으로 사고하는 것

 

(2) 분해: 복잡한 문제를 좀 더 작고 처리가 가능하도록 부분 문제로 분해

  (2-1) 분석: 주어진 문제를 작은 부분으로 어떻게 분해할 것인지에 초첨을 맞추는 과정

  (2-2) 합성: 부분을 모아서 주어진 문제에 대한 해답을 만드는 과정

  (2-3) 병렬처리: 작은 문제들을 해결하는데 다중작업을 사용하는 것

 

(3) 패턴인식: 부분 문제들 중 유사성(패턴) 탐색

  (3-1) 중요성: 패턴 발견-> 문제해결을 도와줌 && 동일한 문제 발생 -> 동일한 해결책 사용가능

 

(4) 추상화: 오직 중요한 정보에만 집중, 관련 세부사항은 무시, 복잡한 시스템의 구체적인 예로부터 공통적인 특성을 추려내 일반적인 개념을 형성

  (4-1) 데이터를 목적에 맞게 사용: 자료구조 사용

  (4-2) 눈에 띄는 특징을 찾아서 표현: 일반화, 공식화, 모델화, 함수 만들기

 

(5) 알고리즘:

  (5-1) 분할된 작은 문제의 해법을 찾고, 이러한 해법을 모아서 알고리즘으로 만드는 작업

  (5-2) 알고리즘을 작성할 때 자세하게 컴퓨터의 수준에서 생각

 

알고리즘의 요구사항

  - 명령은 순차적으로 잘 정렬되어야 함

  - 명령에는 모호함이 없어야 함

  - 실행 가능

  - 요구되는 결과물을 생산

  - 명령에는 끝이 있어야 함

 

알고리즘의 조건

  - 입력: 외부에서 제공하는 0개 이상의 입력 존재

  - 출력: 1개 이상의 출력 존재

  - 명백성: 각 명령어의 의미가 모호하지 않고 명확할 것

  - 유한성: 무한하지 않고 한정된 명령어가 실행된 후에는 반드시 종료될 것 

  - 유효성: 각 명령어는 실행가능하며 유한한 시간 안에 수행할 정도로 단순할 것

  - 올바른 순서 정의

 

알고리즘을 구성하는 핵심요소

  - 처리

  - 순서

  - 결정

  - 반복

 

알고리즘을 기술하는 방식

  ① 순서도(flowchart)

    - 알고리즘 작업 순서를 그림으로 표현

    - 단순한 기하학적 기호 사용

  

  ② 의사코드(수도코드)

 

     - 기존 프로그래밍 언어와 유사한 형태

     - 프로그래밍 언어와 상관없이 독립적 작성가능

     - 자연어보다는 더 체계적이고 프로그래밍 언어보단 덜 엄격한 언어

     - 주로 알고리즘의 표현에 사용, 알고리즘을 기술하는데 선호되는 표기법

     - 사전 정의된 키워드를 숙지하고 있어야 함

 

(6) 평가: 개발된 알고리즘의 정확도나 효율성을 평가

  - 처리속도나 정확도 평가

  - 알고리즘 이해가 쉬운가(가독성)

  - 알고리즘의 모든 면을 해결했는가

  - 가능한 자원을 최대한 활용해 문제를 해결했는가

  - 주어진 설계 기준을 충족했는가

 

컴퓨팅 사고가 아닌 경우

  - 소프트웨어를 사용하는 방법을 배우는 것

  - "프로그래밍" 자체를 배우는 것

 

프로그래밍 언어: 프로그램을 작성하는 도구의 일종

 

컴파일 언어

  - 모든 명령을 일괄 번역, 실행

  - 속도 빠름, 구조 복잡

 

인터프리터 언어

  - 명령 -> 즉시 번역

  - 속도 느림, 단순하고 쉬움

 

파이썬

  - 1991년 귀도 반 로섬 이 개발

  - 현재는 2.x와 3.x 세대 공존

  - 여러 가지 변형 존재

 

파이썬의 특징

  - (매우) 고급 언어(추성화 정도가 매우 높음) -> no static typing language, 최적화 용이 x (성능저하 발생)

  - no static typing 언어(묵시적 타입 언어   (<-> 명시적 타입 언어, static typing language))

  - 스크립트 언어 -> 쉽고 기능 많고 특정 용도가 있는 경우가 많음 -> 성능이 중요한 큰 프로그램을 만들 때는 잘 쓰이지 않음

  - C언어와의 접착성이 좋아 혼합 프로그래밍 가능 

  - 범용적으로 사용하는 고수준 언어, 읽기 쉽게 설계

  - 객체지향적, 클래스 지원

  - 쉬움

  - 호환성 좋음

  - 비용 x

  - 기본패키지로도 많은 걸 할 수 있음

  - 모든 컴퓨터에 설치 x, 계산이 많을 경우 속도가 느림

    -> 알고리즘을 단계적으로 개선, C로 확장해 개선, 다른 언어로 개발(C, C++, Java 또는 파이썬과 비슷한 Go, 러스트 등)

 

파이썬 실행 모드: 대화식 모드(Interactive Mode) , 스크립트 모드(Script Mode)

 

선형탐색 알고리즘

  - 앞에서부터 순차적으로 탐색

  - 숫자들이 정렬되어 있을 필요 X

 

이진탐색 알고리즘 

  - 숫자들의 리스트를 반으로 나눠가면서 탐색

  - 숫자들이 크기순으로 정렬되어 있어야 함

  - 총 시행 횟수의 최댓값 k에 대하여 k=log2N이다.

  - 여기서 k는 탐색 횟수로 N에 따른 시행 횟수는 logN. 즉 시간 복잡도는 big-O표기법에 따라 O(logN)으로 나타냄.

 

해시탐색 알고리즘

  - 값과 index를 미리 연결해 둠으로써 짧은 시간에 탐색할 수 있는 알고리즘

  - 숫자들을 특정 알고리즘에 의해 그룹으로 나누어져 저장되어 있음

  - 해당하는 숫자가 속한 그룹을 순차적으로 비교해 원하는 숫자를 찾음

 

 

버블정렬

 

sol 1)

l = [5, 7, 1, 3, 9, 2, 6, 8, 4]
k = 0


while k+1 < len(l):
    if l[k] > l[k+1]:
        l[k], l[k+1] = l[k+1], l[k]
        k = 0
        continue
    k += 1

print(l)

설명: 자리를 바꿀 필요가 있는 인덱스를 발견할 때마다 자리 바꾼 후 다시 처음부터 탐색한다. 처음부터 끝까지 즉 배열의 크기가 n이라고 했을 때 최대로 탐색해야 하는 횟수는 n-1번이고, 해당 알고리즘은 0부터 시작하므로 k가 7일 때 마지막으로 확인하며, k가 7일 때 자리를 바꿀 필요가 없다고 생각되면 k가 8이 되며 반복문을 마무리한다.

 

sol2)

l = [5, 7, 1, 3, 9, 2, 6, 8, 4]

for i in range(len(l)):
    for j in range(len(l) - 1 - i):
        if l[j] > l[j+1]:
            l[j], l[j+1] = l[j+1], l[j]

print(l)

설명: 처음부터 끝까지 큰 수를 오른쪽 작은 수를 왼쪽으로 나열했을 때, 한번 시행 시 가장 큰 수는 맨 오른쪽에 온다. 이를 이용해 처음에는 (배열의 크기)-1만큼 자리를 바꾸고, 다음 시행에서는 맨 오른쪽에 있는 수는 어차피 가장 큰 수이기 때문에 확인할 필요가 없으므로 (배열의 크기)-2만큼 자리를 바꾼다. 

 

 

피보나치수열

 

sol1) 재귀함수 이용

import time as t
k = 35

ssv = t.time()

def fibo(n):
    return fibo(n-2) + fibo(n-1) if n >= 2 else n

print(f"함숫값: {fibo(k)}")
print(f"걸린시간: {t.time() - ssv:.5f}")


<result>
함숫값: 9227465
걸린시간: 2.12638

설명: 다음 소스는 아주 전형적인 방법으로, 피보나치수열을 재귀함수로 나타낸 것이다. 이 경우 정말로 많은 경우의 수를 계산해야 하기 때문에 코드가 정말로 비효율적이다.

 

 

sol2) 재귀함수 이용 X

import time as t
k = 35

ssv = t.time()

def fibo(n):
    if n < 2: return n

    a, b = 0, 1
    for _ in range(n-1):
        a, b = b, a+b

    return b

print(f"함숫값: {fibo(k)}")
print(f"걸린시간: {t.time() - ssv:.5f}")


<result>
함숫값: 9227465
걸린시간: 0.00004

설명: 다음은 재귀함수를 이용하지 않고 반복문을 이용해 피보나치수열 정의 그대로 이용해 함숫값을 구하는 것이다. 변수 a, b를 각각 피보나치 함수 F에 대하여 F(0)과 F(1)을 뜻한다. 한번 반복이 진행됨에 따라 a는 F(0)에서 F(1)로, b는 F(0)과 F(1)을 합친 F(2)를 갖는다. 이 과정을 반복함으로써 피보나치수열을 구현했다. 해당 방법은 재귀함수를 이용하는 것보다 계산이 정말로 최소화되었기 때문에 프로그램 작동시간이 가장 짧다.

 

sol3) 재귀함수 + 딕셔너리 저장

import time as t
k = 35

def fibo(n, memory = dict()):
    if n == 1 or n == 2:
        return 1
    if n in memory:
        return memory[n]
    
    memory[n] = fibo(n-1, memory) + fibo(n-2, memory)
    
    return memory[n]


print(f"함숫값: {fibo(k)}")
print(f"걸린시간: {t.time() - ssv:.5f}")


<result>
함숫값: 9227465
걸린시간: 0.00006

설명: 다음은 교수님이 칭하신 "메모라이제이션(?)"을 이용한 방법이다. memory = dict()는 디폴트 인자로 해당 파라미터가 매개변수로 전달받지 않을 경우 비어있는 딕셔너리 형태로 전달받는다. 두 번째 조건문에서 n값의 피보나치 함숫값이 있는지 없는지 판단하고 없을 경우 그 값을 구하기 위해 재귀함수를 계속 돌린다. 즉 사실상 n부터 가감되면서 구해지는 느낌으로 보일지라도 사실은 n이 3일 때부터 딕셔너리가 차곡차곡 쌓이게 되며, 한 번 쌓인 값들은 저장되기 때문에 쓸데없는 계산 과정을 생략한다. 즉 속도가 매우 향상되어 sol2와 거의 비슷한 속도가 나타남을 알 수 있다.