yongmin

분류(classification)와 예측(prediction)

분류 : 데이터들을 특정 기준으로 나눌 수 있는 ‘선형구분자’를 설정하여 분류. 오차를 이용하여 구분자의 기울기를 조정하는 것을 ‘학습’이라고 한다.

- Error = target – actual

Learning rate(L) : 학습률은 업데이트의 정도를 저장

update parameter : new A = A + dA = A + L(E/x).

예측 : 새로운 data가 들어오면 구분자에 의해 어떤 output으로 분류될지 판단 => 예측과 분류는 다른 것이 아님

XOR 문제의 경우 선형분류자는 하나가 아니다 -> 여러개의 선형 분류자를 이용 -> 인공신경망은 여러개의 분류자가 함께 동작

인공신경망

인공뉴런은 X1부터 Xn까지 입력 값에 각각 W1부터 Wn까지의 가중치를 곱하고 그 모든 합이 임계치(threshold)가 초과되면 출력값이 발생

activation functoin(활성화 함수) : 여러 입력신호를 받아 특정 threshold를 넘어서는 경우에 출력 신호를 생성하는 함수 -> sigomoid 함수(=logistic 함수)가 대표적이다. => y = 1 / (1+ e^-x)

인공신경망 : 상호연결된 생물학적 뉴런을 인공적으로 모델화 한 것으로, 다수의 인공뉴런을 가지고 있는 layer를 여러 층으로 쌓은 후 이전 layer와 이후 layer의 모든 인공뉴런들이 연결되어 있다. 이때 각각의 연결에 weight(가중치)가 존재하는데 학습과정을 통해 weigjt값들을 조정함으로써 input에 대해 올바른 output이 나올 수 있도록 한다.

신경망에서 신호를 전달하는 연산은 행렬곱을 통해 표현

forward propagation : output = sigmoid(X1*W1 + X2*W2 + ... + Xn*Wn)

인공신경망에서의 학습

- 입력 값을 이용하여 인공 뉴런의 출력 값을 계산

- 인공 뉴런이 계산한 출력 값과 사용자가 기대하는 출력 값을 비교. => Error = target – actual

back propagation : error 정보가 뒤쪽으로 계속 전파

중간 계층에 존재하는 노드들의 오차는 출력계층 노드들의 오차를 가중치에 크기에 비례해 나눠서 back propagation

back propagation은 행렬곱으로 표현 : Error(hidden) = W.T(hidden-output) * Error(output)

가중치 업데이트 : 함수의 최저점을 구하는 Gradient Descent 기법을 학습 목표 값과 실제 값 간의 차이를 구하는 Error function에 적용 -> error function = (target-actual)^2인 이차함수 이므로 error function의 최저점은 error function의 기울기(dE/dw)가 가장 작은 지점 -> dE/dw =
-> new W = old W – (LearningRate * (dE/dw))

AI를 engineering과 science의 관점에서 비교

-AI : 사고과정 + 추론을 통한 지능적 행동에 관련된 연구를 하는 학문

-AI in engineering : 실제 지능적으로 사고, 행동할 수 있는 intelligence machine을 만들기 위해 요구되는 개념이나 이론, 실습 등에 관련된 연구 분야. => 뇌의 작동원리를 모델로 하여 프로그래밍

- AI in science : 사람이나 동물이 자연생태에서 사고하고 행동하는 일련의 과정들을 탐구하고 분석하여 관련된 개념이나 원리를 연구하는 분야 (예-인지과학) => 뇌의 학습, 인지과정의 원리를 이해

분야별 AI

인지과학의 AI : 어떻게 자연상태의 생각과 정신적현상이 동작하는지 이해 => 뇌의 학습, 인지과정의 원리를 이해

철학의 AI : 기본적이고 중요한 철학적인 문제들을 탐험하기위한 방법

AI 구현의 패러다임

Symbolic AI : 고전적인 AI 구현방식. 여러 symbolic knowledg들 사이의 관계와 문법을 연구하고 symbolic 추론을 연구

Connectionist AI : mental state은 neural units을 가지고 있는 n차원 벡터들로 표현되는데, 이런 neural units간의 연결을 matrix를 이용하여 계산한다.

Turing Test

- 기계가 생각하고 있는가를 판정하는 시험 (Alan Turing)

사람과 기계가 대화하는 상황에서, 사람은 대화 상대방이 기계인지 사람인지 알아챌 수 있는지 시험

- 어떻게 해서 지능적인 판단과 행동을 할 수 있는가가 주요 연구 대상 => 인간이 그것이 기계임을 구분하지 못하는 것이 중요한 것이 아니라 인간이 하는 말과 행동에 반응하고 이를 바탕으로 새로운 사실을 추론하는 등, 인간에게 유용하게 사용할 수 있어야 함

Video Turing Test

비디오를 컴퓨터에게 보여주고 비디오의 내용을 컴퓨터에게 물어봤을 때, 캄푸타기 사람만큼 잘 대답하는지 알아보는 시험

AI system

ELIZA : 인공지능 채팅 프로그램

ALICEBOT : 인공지능 채팅 프로그램

Deep blue : IBM이 개발한 chess-playing computer

Watson : IBM이 개발한 퀴즈 답변 인공지능 시스템. 자연어처리, 정보검색, 지식표현, 지식추론, 기계학습 응용시스템

AlphaGo : google deepmind가 개발한 바둑 인공지능 프로그램. 실시간 decision-making 기능. MinMax 알고리즘, Monte Calro Tree Search, CNN 기술사용

Amazon Go : 체크아웃이 필요없는 상점. 컴퓨터비전, sensor fusion, deep learning을 이용하여 구현됨

인공지능 vs 머신러닝 vs 인공신경망 vs 딥러닝

- 인공지능 : 사람의 지능을 모방하여 사람처럼 복잡한 일(인지, 추론, 결정 등)을 할 수 있는 기계를 만드는 것

- 머신러닝 : 인공지능을 구현하기 위한 기법으로, 컴퓨터가 명시적으로 프로그램되지 않고도 대량의 데이터와 알고리즘으로 학습할 수 있도록 하는 것.

- 인공신경망 : 생물학적 뉴런 모델을 수학적으로 모델링한 인공뉴런을 여러개 쌓아서 만든 네트워크.

- 딥러닝 : 머신러닝을 구현하기 위해 사용되는 기술로, 인공신경망을 활용하여 데이터를 학습. => 입력값의 결과와 정답의 차이인 에러를 구하고, 에러를 이용하여 가중치를 업데이트 함으로써 스스로 학습

오류 발생하는 경우

• 디렉터리 안에 없는 파일을 열려고 시도했을 때 발생
• 0으로 다른 숫자를 나누는 경우
• 선형자료형의 범위 밖을 참조하는 경우

예외처리기법

1. try, except문

• try 블록 수행 중 오류가 발생하면 except 블록이 수행된다. 하지만 try 블록에서 오류가 발생하지 않는다면 except 블록은 수행되지 않는다.

try:
    ...
except [발생 오류[as 오류 메시지 변수]]:
    ...

2. try, finally 문

• try문에는 finally절을 사용할 수 있다. finally절은 try문 수행 도중 예외 발생 여부에 상관없이 항상 수행된다. 보통 finally절은 사용한 리소스를 close해야 할 때에 많이 사용한다.

f = open('foo.txt', 'w')
try:
    # 무언가를 수행한다.
finally:
    f.close()

3. 여러개의 예외 처리

• try문에서 여러 개 except문을 작성하여 여러개의 오류 처리 가능

try:
    ...
except 발생 오류1:
   ... 
except 발생 오류2:
   ...
finally : 
   실행문장

오류 회피

• 프로그래밍을 하다 보면 특정 오류가 발생할 경우 그냥 통과시켜야 할 경우,  pass를 사용하여 오류를 그냥 회피하도록 작성

try:
    f = open("나없는파일", 'r')
except FileNotFoundError:
    pass

예외만들기

• 프로그램 수행 도중 특수한 경우에만 예외 처리를 하기 위해서 종종 예외를 만들어서 사용
• 예외는 파이썬 내장 클래스인 Exception 클래스를 상속하여 만든다

class MyError(Exception):
    pass

출처 : https://wikidocs.net/30

1. 클래스

2. 모듈과 패키지

클래스

• 클래스 : 똑같은 무엇인가를 계속해서 만들어 낼 수 있는 설계, 틀
• 객체 : 클래스로 만든 인스턴스
• 클레스 구조
• 메소드 : 클래스 안에 구현된 함수
  • 파이썬 메서드의 첫 번째 매개변수 이름은 관례적으로 self를 사용한다. 객체를 호출할 때 호출한 객체 자신이 전달되기 때문에 self를 사용한 것이다. 물론 self말고 다른 이름을 사용해도 상관없다.
• 생성자 : Constructor란 객체가 생성될 때 자동으로 호출되는 메서드를 의미한다.
  • 파이썬 메서드 이름으로 __init__를 사용하면 이 메서드는 생성자가

• 상속 : 어떤 클래스를 만들 때 다른 클래스의 기능을 물려받을 수 있게 만드는 것
  • class 클래스 이름(상속할 클래스 이름)

• 오버라이딩 : 부모 클래스(상속한 클래스)에 있는 메서드를 동일한 이름으로 재정의 하는 것. 메서드를 오버라이딩하면 부모클래스의 메서드 대신 오버라이딩한 메서드가 호출된다.
• 오버로딩 : 매개변수에 따라 다르게 기능하는 메서드를 중복 정의
• 예시) 4칙연산 클래스와, 거듭제곱 클래스

# 사칙연산 클래스
>>> class FourCal:
...     def __init__(self, first, second):
...         self.first = first
...         self.second = second
...     def setdata(self, first, second):
...         self.first = first
...         self.second = second
...     def add(self):
...         result = self.first + self.second
...         return result
...     def mul(self):
...         result = self.first * self.second
...         return result
...     def sub(self):
...         result = self.first - self.second
...         return result
...     def div(self):
...         result = self.first / self.second
...         return result
...
>>>
# 거듭제곱 클래스
>>> class MoreFourCal(FourCal):
...     def pow(self):
...         result = self.first ** self.second
...         return result
...
>>>

모듈과 패키지

모듈

• 정의 : 함수, 변수, 클래스등을 모아 놓은 파일. 파이썬 확장자 ".py"로 만든 파이썬 파일은 모두 모듈이다.

• 모듈만들기 

# mod1.py
def add(a, b):
    return a + b

def sub(a, b): 
    return a-b

위와 같이 add와 sub 함수만 있는 파일 mod1.py를 만들고 C:\디렉터리에 저장. 이 mod1.py 파일이 바로 모듈이다

• 모듈 불러오기

C:\>python
>>> import mod1
>>> print(mod1.add(3, 4))
7
>>> print(mod1.sub(4, 2))
2

반드시 mod1.py를 저장한 C:\ 디렉터리로 이동해야 모듈을 읽을 수 있다. 

• if __name__ == "__main__" 의미

# mod1.py 
def add(a, b): 
    return a+b

def sub(a, b): 
    return a-b

if __name__ == "__main__":
    print(add(1, 4))
    print(sub(4, 2))

if __name__ == "__main__"을 사용하면 C:\>python mod1.py처럼 직접 이 파일을 실행했을 때는 __name__ == "__main__"이 참이 되어 if문 다음 문장이 수행된다. 반대로 대화형 인터프리터나 다른 파일에서 이 모듈을 불러서 사용할 때는 __name__ == "__main__"이 거짓이 되어 if문 다음 문장이 수행되지 않는다.

• 모듈에 있는 변수 클래스 사용

#mod2.py 작성
PI = 3.141592

class Math: 
    def solv(self, r): 
        return PI * (r ** 2) 

def add(a, b): 
    return a+b 

모듈 안에 있는 변수 및 클래스를 사용하려면 "."(도트 연산자)로 클래스 이름 앞에 모듈 이름을 먼저 입력해야 한다.

>>> import mod2
>>> print(mod2.PI)
3.141592
>>> a = mod2.Math()
>>> print(a.solv(2))
12.566368

• 다른 파일에서 모듈 불러오기 : 동일한 디렉토리에 있는 서로 다른 파일은 "import 모듈이름"으로 다른 파일의 모듈을 불러와 사용할 수 있다.

패키지

• 정의 : 패키지(Packages)는 도트(.)를 사용하여 파이썬 모듈을 계층적(디렉터리 구조)으로 관리할 수 있게 해준다. 예를 들어 모듈 이름이 A.B인 경우에 A는 패키지 이름이 되고 B는 "A 패키지의 B모듈"이 된다.

• 패키지 만들기

1. C:/디렉터리 밑에 game 및 기타 서브 디렉터리를 생성

C:/game/__init__.py
C:/game/sound/__init__.py
C:/game/sound/echo.py
C:/game/graphic/__init__.py
C:/game/graphic/render.py

2. 각 디렉터리에 __init__.py 파일을 만들어 놓기만 하고 내용은 일단 비워 둔다.

3.  echo.py 파일은 다음과 같이 작성.

# echo.py
def echo_test():
    print ("echo")

4. render.py 파일은 다음과 같이 작성

# render.py
def render_test():
    print ("render")

5. game 패키지를 참조할 수 있도록 명령 프롬프트 창에서 set 명령어로 PYTHONPATH 환경 변수에 C:/ 디렉터리를 추가

C:\> set PYTHONPATH=C:/
C:\> python
Type "help", "copyright", "credits" or "license" for more information.
>>> 

• 패키지 안의 함수 실행

1.  echo_test 함수를 실행

# echo 모듈을 import하여 실행
>>> import game.sound.echo
>>> game.sound.echo.echo_test()
echo

# echo 모듈이 있는 디렉터리까지를 from ... import하여 실행
>>> from game.sound import echo
>>> echo.echo_test()
echo

#  echo 모듈의 echo_test 함수를 직접 import하여 실행
>>> from game.sound.echo import echo_test
>>> echo_test()
echo

2. import game을 수행하면 game 디렉터리의 모듈 또는 game 디렉터리의 __init__.py에 정의한 것만 참조

>>> import game
>>> game.sound.echo.echo_test()
Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
AttributeError: 'module' object has no attribute 'sound'

3. 도트 연산자(.)를 사용해서 import a.b.c처럼 import할 때 가장 마지막 항목인 c는 반드시 모듈 또는 패키지여야만 한다.

>>> import game.sound.echo.echo_test
Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
ImportError: No module named echo_test

• __init__.py : __init__.py 파일은 해당 디렉터리가 패키지의 일부임을 알려주는 역할을 한다. 

1. 제어문

2. 함수

3. 입출력

1. 제어문

if 문

• 기본구조
  • if 조건문 1 : 
        수행할 문장 1
        수행할 문장 2
    elif 조건문 2 :
        수행할 문장 1
        수행할 문장 2
    else :
        수행할 문장 a
        수행할 문장 b

while문

• 기본구조
  • while 조건문 : 
        수행할 문장 1
        수행할 문장 2
        수행할 문장 3
        if 조건문 1 :
            수행할문장 1
            continue
        if 조건문 2 :
            break

for문

• 기본구조
  
  • for 변수 in 리스트|튜플|문자열 : 
        수행할 문장 1
        수행할 문장 2
        if 조건문 1 :
            continue
        if 조건문 2 :
            break
• for문+ range( )
  
  • for 변수 range(시작숫자, 끝 숫자)
        수행할 문장 1
        수행할 문장 2
        if 조건문 1 :
            continue
        if 조건문 2 :
            break
• 리스트내포 (list comprehension) : 리스트 안에 for문을 포함하는 것
  
  • a = [1,2,34]
    result = [num*3 for num in a] // [3,6,9,12]

2. 함수

• 함수의 구조
  • def 함수이름(매개변수) : 
        수행할문장1
        수행할문장2
        return 결과값
• 매개변수(parameter) : 함수에 입력으로 전달된 값을 받는 '변수'
• 인수(arguments) : 함수를 호출할 때 실제 전달하는 입력'값'
• 입력값이 몇개가 될지 모를때
  • 여러개의 입력값을 받는 함수 : 매개변수 앞에 * 을 붙이면 입력값을 모아서 튜플로 만든다
    
    • def 함수이름( * 매개변수) 
          수행할문장1
          수행할문장2
          return 결과값

• 매개변수 초깃값 설정 // 초깃값설정시 맨 오른쪽 매개변수부터 차례대로 설정
  
  • def 함수이름(매개변수1, 매개변수2=값2) 
        수행할문장1
        수행할문장2
        return 결과값

• 스코프 : 변수의 효력범위
  • 함수 안에서 사용할 변수의 이름을 함수 밖에서도 동일하게 사용하여도 함수 밖의 변수는 함수의 영향을 받지 않는다
  • 함수 안에서 함수 밖의 변수를 변경하는 방법
    • return 사용하여 결과값을 함수 밖의 변수에 할당
    • global 키워드 사용
• 람다 : 함수생성시 사용하는 예약어로 함수를 매우 간단하게 생성하게 한다
  
  • lamda 매개변수1, 매개변수2, ... : 매개변수를 사용한 표현식 ( 반환값)
  • ex) add = lamda a, b : a+b; add(3,4) // 7
          or (lamda a,b : a +b)(3,4) // 7

3. 입출력

• 사용자입력 : input( ) 
• 프롬프트 출력 : print( )
  • 문자열 띄어쓰기 : print('aa', 'bb', 'cc') // aa bb cc
  • 한줄에 결과값 출력 : for i in range(10) : print( i, end=' ') // 0 1 2 3 4 5 6 7 8 9
• 파일열기
  • 파일객체 = open(파일이름, 파일열기모드)
    • f = open('file.txt', r)
  • 파일열기모드
    • r : 읽기모드
    • w : 쓰기모드
    • a : 추가모드 (파일 마지막에 새로운 내용 추가)
• 파일 객체 닫기 : f.close( )
• 파일쓰기
  • f.write(data)
• 파일 읽기
  • line = f.readline( ) // 파일의 첫번째 줄을 읽는다
  • lines = f.readlines( ) // 파일의 모든 줄을 읽어서 각각의 줄을 요소로 갖는 리스트 반환
  • data = f.read( ) // 파일의 내용 전체를 문자열로 반환
• with 키워드
  • with 키워드를 사용하여 with 블록을 지정하고, 그 안에서 파일을 열고 작업한다. 이후 with 블록을 벗어나게 되면 해당 파일 객체를 자동으로 close( ) 한다
  • ex) with open("foo.txt", "w") as f :
             f.write("this is data")
         // 이후 with 블록 벗어나므로 자동으로 f.close 가 된다

1. 숫자형

2. 문자열

3. 리스트

4. 튜플

5. 딕셔너리

6. 집합(set)

7. 불

8. 변수

1. 숫자형

• 정수형 
  • >>> a = 123
• 실수형 
  • >>> a = 1.7
• 8진수
  • >>> a = 0o777
• 16진수
  • >>> a = 0xCDE
• 연산 (a=3, b=2)
  • a + b // 5
  • a - b // 1
  • a * b // 6
  • a / b // 1.5
  • a ** b // 9
  • a % b // 1
  • a // b // 1

2. 문자열

• 문자열 생성
  • "string"
  • 'str'
  • """string""" // 여러줄인 문자열 입력시
  • '''string''' // 여러줄인 문자열 입력시
• 문자열 연산
  • "abc" + "def" // "abcedf"
  • "abc" * 2 // "abcabc"
  • len("abc") // 3
• 문자열 인덱싱
  • a = "this is string" // a[5] = 'i' , a[-2] = 'n' 
• 문자열 슬라이싱
  • a = "this is string"
  • a[0:5] = "this i"
  • a[3:] = " s is string"
  • a[:-2] = "this is stri"
• 문자열 포매팅(formatting)
  • "this is %s" %string // 'this is string'
  • "%d is three" %3 // '3 is number'
  • "{0} is {1}" .format(3, "number") // '3 is number'
• 문자열 내장함수
  • a = "apple"; a.count('p') // 2 : p의 갯수
  • a = "apple"; a.find('p') // 1 : 첫번째 p의 인덱스
  • "," .join('abcd') // 'a,b,c,d' : 문자열 의 각각의 문자 사이에 "," 삽입
  • a = "     bc"; a.lstrip() // a="bc" : 문자열의 가장 왼쪽 공백 제거
  • a = "bc      "; a.rstrip() // a="bc" : 문자열의 가장 오른쪽 공백 제거
  • a = "  bc  ";  a.strip() // a="bc" : 문자열 양쪽 공백 제거
  • a = "abc"; a.replace("bc", "ee") // a= "aee" : 문자열 바꾸기
  • a = "this is string"; a.split() // ["this", "is", "string"] 공백을 기준으로 문자열 나눔

3. 리스트

• 리스트생성
  • a = [ 1, "abc", [ 2, "def"]]
• 리스트 인덱싱
  • a[2][1] // "def"
  • a[0] + a[2][0] // 3
• 리스트 슬라이싱
  • a[1: ] // ["abc", [2,"def"]]
• 리스트 연산
  • a = [1,2,3]; b[4,5,6]; a+b // [1,2,3,4,5,6]
  • a = [1,2,3]; len(a) // 3
• 리스트 수정
  • a = [1,2,3]; a[1] = 4 // [1,4,3]
• del함수 - 요소삭제
  • a = [1,2,3]; del a[1] // [1,3]
• 리스트내장함수
  • a = [1,2,3]; a.ppend(4) // [1,2,3,4]
  • a = ['c', 'a', 'a']; a.sort() // ['a', 'b', 'c']
  • a = [1,2,3]; a.index(2) // 1
  • a = [1,2,3]; a.insert(1, 'a') // [1,'a',2,3]
  • a = [1,2,3,4,3]; a.remove(3) // [1,2,4,3]
  • a = [1,2,3]; a.pop() // 3, a = [1,2]

4. 튜플

• 특징 : 요소값의 수정이 불가능
• 튜플 생성
  • a = (1, 'a', ( 2, 'bc'))
• 튜플 인덱싱
  • a[1] // 'a'
  • a[2][0] // 2
• 튜플 슬라이싱
  • a[1:] // ('a',(2,'bc'))
• 튜플 연산
  • a[0] + a[2][0] // 3
  • len(a) // 3

5. 딕셔너리

• 정의 : '키-값'의 쌍으로 이루어진 자료형
• 딕셔너리 생성
  • a = { 'name' : 'kim', 'age' : 22, 'list' : [1,2,3] }
• 딕셔너리 쌍 추가
  • a['job'] = 'police' // a = { 'name' : 'kim', 'age' : 22, 'list' : [1,2,3], 'job' : 'police' }
• 딕셔너리 쌍 삭제
  • del a['age'] // a = { 'name' : 'kim', 'list' : [1,2,3], 'job' : 'police' }
• 딕셔너리 요소 접근
  • a['list] // [1,2,3]
• 내장함수
  • 키 리스트 만들기 1 : a.keys() // dict_keys(['name', 'age', 'list']) : 키값을 가지고 있는 "객체" 반환
  • 키 리스트 만들기 2 : list(a.keys()) // ['name', 'age', 'list'] : 키 값을 가지고 있는 "리스트"반환
  • 값 리스트 만들기 1 : a.values() // dict_values(['kim', 22, [1,2,3]]) 객체반환
  • 리스트 만들기 2 :  list(a.values()) // ['kim', 22, [1,2,3] ]
  • 키-값 쌍 얻기 1 : a.items() // dict_items( [ ('name', 'kim'), ('age', 22), ('list', [1,2,3] ) ] )
  • 키-값 쌍 얻기 2 : list(a.items()) // [('name', 'kim'), ('age', 22), ('list', [1,2,3] ) ]
  • 키-값 쌍 모두 지우기 : a.clear()
  • 키로 값 얻기 : a.get('name') // 'kim'
  • 해당 키가 딕셔너리 안에 있는지 검사 : 'name' in a // true 

6. 집합(set)

• 정의 : 집합 관련 연산을 쉽게 처리하기 위해 만들어진 자료형으로 고유한 특징을 가진다.
• 특징 
  • 중복을 허용하지 않는다
  • 순서가 없다 -> set자료형에 저장된 값을 인덱싱으로 접근하려면 리스트나 튜플로 변환 후 접근
• 생성
  • s1 = set([1,2,3]); s2 = set([3,4,5])
•  연산
  • 교집합 : s1 & s2 or s1.intersection(s2) // { 3 }
  • 차집합 : s1- s2 or s1.difference(s2) // { 1, 2 }
  • 합집합 : s1 | s2  or s1.union(s2) // { 1, 2, 3, 4, 5 }
• 내장함수
  • 값 추가 : s1.add(4) // { 1, 2, 3, 4 }
  • 값 여러개 추가 : s1.update([4,5]) // { 1, 2, 3, 4, 5 }
  • 특정값 제거 : s1.remove(2) // { 1, 3 }
• 활용법
  • 리스트로 변환 :  l1 = list(s1); l1[1] // 2
  • 튜플로 변환 : t1 = tuple(s1); t1[1] // 2

7. 불

• 정의 : 침과 거짓을 나타내는 자료형
• 생성
  • a = True
  • b = False
• 자료형의 참과 거짓 : 문자열, 리스트, 튜플, 딕셔너리 등의 값이 비어 있으면 거짓이 되고, 비어 있지 않으면 참
  • False : "", [], (), {}, 0, None
  • True : "a", [0], (1), {2:3}, -1 (영이 아닌 숫자)
• 불연산
  • bool([]) // False
  • bool((0)) // True

8. 변수

• 정의 : 객체(자료형)가 저장된 메모리 주소를 가리키는 것
• 메모리 주소 확인 : id(a) // 123123243
• 복사
  • 단순 복사 : 동일한 객체를 가리킴
    • a = [ 1,2,[1,2]]; b= a; id(a) == id(b) // True 
  • 얕은 복사 : 복합객체(껍데기)만 복사, 그 내용은 동일한 객체
    • import copy; b = copy.copy(a); b[0] =3; b[2].append(3);
    • print(a) // [1,2,[1,2,3]]
    • print(b) // [3,2,[1,2,3]]
  • 깊은 복사 : 복합객체 복사 + 그 내용도 재귀적으로 복사
    • import copy; b = copy.deepcopy(a); b[0] = 3; b[2].append(3);
    • print(a) // [1,2,[1,2]]
    • print(b) // [3,2,[1,2,3]]

1. 단순 문자열 매칭
2. KMP (Knuth-Morris-Pratt) 알고리즘
3. Boyer-Moore 알고리즘

단순 문자열 매칭 알고리즘

• 문자 하나씩 확인하는 알고리즘으로 가장 간단한 형태의 알고리즘
• 의사코드
  • 전체 문자열의 첫번째 문자에서 시작하여 찾을 문자열의  첫번째 문자를 비교
  • 매칭이 이루어지면 찾을 문자열의 다음 문자를 비교
  • 매칭이 이루어지지 않으면 전체 문자열의 두번째 문자에서 다시 시작
  • 위의 과정을 반복하여 문자열을 찾는다
• 시간 복잡도 : O(N*M) // N = 전체 문자열 길이, M = 찾을 문자열 길이

KMP (Knuth-Morris-Pratt) 알고리즘

• 접두사와 접미사의 개념을 활용하여 '반복되는 연산을 얼마나 줄일 수 있는지 판별'하고 매칭할 문자열을 빠르게 점프하는 기법
• 접두사 : 찾을 문자열의 앞에 있는 문자열
• 접미사 : 찾을 문자열의 뒤에 있는 문자열
• 경계(border) : 접두사와 접미사가 일치하는 쌍
• 의사코드
  • 전체 문자열의 첫번째 문자부터 찾을 문자열과 비교시작
  • 매칭이 이루어지지 않은 문자가 발견되면, 발견되기 전까지 전체 문자열과 일치했던 찾을 문자열의 경계를 구한다.
  • 찾을 문자열의 접두사를 전체 문자열의 접미사로 점프하여 비교를 재개
• 시간 복잡도 : O(N) // N = 전체 문자열 길이
• 경계를 찾는데 소요되는 비용은 공짜가 아니므로, 검색을 수행하는 중간에 매번 경계를 찾는것은 고비용
  => 검색을 수행하기 전에 미리 찾을 문자열로 부터 경계의 정보를 갖는 "테이블"을 생성
  • 테이블 인덱스 : 일치 접두부의 길이
  • 테이블 원소 : 일치 접두부의 최대 경계 너비 (첫번째 문자는 일치 접두부가 존재하지 않으므로 항상 -1)
  • 매칭 불일치시 이동 거리 = 일치 접두부의 길이 - 최대경계너비

Boyer-Moore 알고리즘

• 오른쪽에서 왼쪽으로 비교하고 이동은 왼쪽으로 오른쪽으로 하는 방식
• 오른쪽 끝에 문자가 일치 하지 않고 해당 본문 문자가 패턴에 존재하지 않으면 패턴 길이만큼 이동

Greedy Algorithm, 탐욕알고리즘

• 정의 : 당장 눈 앞에 보이는 최적의 상황만을 쫒는 알고리즘
• 특징 : 탐욕알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.

예시코드

// boj - 5585 : greedy algorithm

#include<iostream>
using namespace std;

int main() {
	int monney;
	cin >> monney;
	monney = 1000 - monney;
	int res = 0;

	// 500
	int p = monney / 500;
	res += p;
	monney -= (500 * p);

	// 100
	p = monney / 100;
	res += p;
	monney -= (100 * p);

	// 50
	p = monney / 50;
	res += p;
	monney -= (50 * p);

	// 10
	p = monney / 10;
	res += p;
	monney -= (10 * p);

	// 5
	p = monney / 5;
	res += p;
	monney -= (5 * p);

	// 1
	p = monney / 1;
	res += p;
	monney -= (1 * p);

	cout << res << endl;
	return 0;
}