문자열

• 큰 따옴표나 작은 따옴표로 묶으면 문자열이다.

  • 여러 줄을 표현할 때는 끝에 \를 붙이고 줄바꿈을 하거나, 문자열을 삼중 따옴표(''', """)로 묶으면 된다.

• 이스케이프 시퀀스(escape sequence, 확장열)

  확장열	설명
  \n	개행
  \t	탭
  \"	큰따옴표
  \'	작은따옴표
  \	\ 문자

• 아스키 코드

  • 다음과 같은 함수로 아스키 코드와 문자를 서로 변환할 수 있다.

    print(ord('a'))
    print(chr(98))
    for c in range(ord('A'), ord('Z')+1):
        print(chr(c), end='')
    
    ''' stdout
    97
    b
    ABCDEFGHIJKLMNOPQRSTUVWXYZ
    '''

• 문자열 연산

  • 문자열 연결

    기호	설명
    +	문자열 연결
    *	문자열 반복

문자열 관리

문자열 분리

• 인덱싱

  문자열[정수]

  • 인덱스는 앞에서부터 0, 1, 2, 3, ... 순서이다.

  • 뒤에서부터는 -1, -2, -3, ... 순서이다.

    s = "python"
    print(s[2])
    print(s[-2])
    
    ''' stdout
    t
    o
    '''

• 슬라이싱

  문자열[begin:end:step]

메서드

• 예시

  name = "홍길동"
  if name.startswith("홍"):
      print("홍씨입니다.")
  if name.startswith("김"):
      print("김씨입니다.")
  file = "figure.jpg"
  if file.endswith(".jpg"):
      print("JPG 그림 파일입니다.")
  
  ''' stdout
  홍씨입니다.
  JPG 그림 파일입니다.
  '''

  s = "Good morning. my love KIM."
  print(s.lower())
  print(s.upper())
  print(s.swapcase())
  print(s.capitalize())
  print(s.title())
  print()
  s = "    angel    "
  print(s + "님")
  print(s.strip() + "님")
  print(s.lstrip() + "님")
  print(s.rstrip() + "님")
  
  ''' stdout
  good morning. my love kim.
  GOOD MORNING. MY LOVE KIM.
  gOOD MORNING. MY LOVE kim.
  Good morning. my love kim.
  Good Morning. My Love Kim.
  
      angel    님
  angel님
  angel    님
      angel님
  '''

  s = "짜장 짬뽕 탕수육"
  print(s.split())
  s2 = "서울->대전->대구->부산"
  cities = s2.split("->")
  print(cities)
  for city in cities:
      print(city)
  print()
  s ="._."
  print(s.join("대한민국"))
  
  '''stdout
  ['짜장', '짬뽕', '탕수육']
  ['서울', '대전', '대구', '부산']
  서울
  대전
  대구
  부산
  
  대._.한._.민._.국
  '''

포맷팅

• 예시

  name = "길동"
  age = 16
  height = 162.5
  print("이름:{0:$<10s}, 나이:{1:>05d}, 키:{2:!<8.2f}".format(name, age, height))
  
  ''' stdout
  이름:길동$$$$$$$$, 나이:00016, 키:162.50!!
  '''

• 파이썬3부터는 print(f"{number:%.2f}") 이런 식으로 사용한다.

인수

• 함수로 값을 전달했을 때 이를 저장하는 변수

• 함수 내부에서 사용한다.

가변 인수

• 인수의 수가 고정되지 않고 호출 시 원하는 만큼 인수를 지정할 수 있다.

  • 튜플로 받아서 처리한다.

• 일반 인수보다 뒤에 위치해야 한다.

• 함수 당 하나만 사용할 수 있다.

• 예시

  • 인수명 앞에 * 를 붙여서 가변 인수임을 표시한다.

    def intsum(*ints):
        total = 0
        for num in ints:
            total += num
        return total
    print(intsum(1, 2, 3)) # ints = (1, 2, 3)
    print(intsum(5, 7, 9, 11, 13)) # ints = (5, 7, 9, 11, 13)
    print(intsum(8, 9, 6, 2, 9, 7, 5, 8))
    
    ''' stdout
    6
    45
    54
    '''

  • 아래의 scores 리스트를 인자로 넣을 경우 intsum(*scores) 처럼 * 를 붙이면 리스트가 펼쳐진다.

    def intsum(*ints):
        print(type(ints))
        print(ints)
    
        total = 0
        for num in ints:
            total += num
        return total
    
    scores = [20, 30, 40]
    # print(intsum(scores)) # 에러
    print(intsum(*scores)) # 펼침 : [20, 30, 40] -> 20, 30, 40
    print(*scores)
    
    ''' stdout
    <class 'tuple'>
    (20, 30, 40)
    90
    20 30 40
    '''

인수의 기본값

• 함수 호출 시 인수가 지정되지 않았을 때 사용할 기본값이다.

• 함수 정의 시 인수에 값을 대입하면 된다.

• 인수에 값을 지정할 때는 띄어쓰기를 안하는게 암묵적 룰인 것 같다.

  def calcstep(begin, end=1, step=1):
      total = 0
      for num in range(begin, end + 1, step):
          total += num
      return total
  print(f"1 ~ 10 = {calcstep(1, 10, 2)}")
  print(f"1 ~ 100 = {calcstep(1, 100)}")
  print(f"-10 ~ 1 = {calcstep(-10)}")
  
  ''' stdout
  1 ~ 10 = 25
  1 ~ 100 = 5050
  -10 ~ 1 = -54
  '''

키워드 인수

• 인수 명칭으로 변수를 매칭할 수 있다.

  def calcstep(begin, end, step):
      total = 0
      for num in range(begin, end + 1, step):
          total += num
      return total
  
  print(f"3 ~ 5 = {calcstep(3, 5, 1)}")
  print(f"3 ~ 5 = {calcstep(begin=3, end=5, step=1)}")
  print(f"3 ~ 5 = {calcstep(step=1, end=5, begin=3)}")
  print(f"3 ~ 5 = {calcstep(3, 5, step=1)}")
  print(f"3 ~ 5 = {calcstep(3, step=1, end=5)}")
  # print(f"3 ~ 5 = {calcstep(3, step=1, 5)}") # 에러
  
  ''' stdout
  3 ~ 5 = 12
  3 ~ 5 = 12
  3 ~ 5 = 12
  3 ~ 5 = 12
  3 ~ 5 = 12
  '''

키워드 가변 인수

• 키워드 인수를 가변 개수로 전달할 때 사용한다.

• 함수 정의 시 ** 기호를 인수 앞에 붙인다.

  • 사전(Dictionary)으로 받아서 처리한다.

    def calcstep(**args):
        print(type(args))
        print(args)
    
        begin = args.get('begin', 0)
        end = args['end']
        step = args['step']
        total = 0
        for num in range(begin, end + 1, step):
            total += num
        return total
    
    print("3 ~ 5 =", calcstep(begin=3, end=5, step=1), end='\n\n')
    print("3 ~ 5 =", calcstep(step=1, end=5, begin=3), end='\n\n')
    print(" ~ 5 =", calcstep(step=1, end=5))
    
    ''' stdout
    <class 'dict'>
    {'begin': 3, 'end': 5, 'step': 1}
    3 ~ 5 = 12
    
    <class 'dict'>
    {'step': 1, 'end': 5, 'begin': 3}
    3 ~ 5 = 12
    
    <class 'dict'>
    {'step': 1, 'end': 5}
    ~ 5 = 15
    '''

  • 사전도 펼칠 수 있다.

    def calcstep(**args):
        print(type(args))
        print(args)
    
        begin = args.get('begin', 0)
        end = args['end']
        step = args['step']
        total = 0
        for num in range(begin, end + 1, step):
            total += num
        return total
    
    dic = {
        'begin' : 1,
        'end' : 100,
        'step' : 2
    }
    
    # dict의 펼침 : **사전명
    print(calcstep(**dic))
    print(*dic)
    # print(**dic)
    
    ''' stdout
    <class 'dict'>
    {'begin': 1, 'end': 100, 'step': 2}
    2500
    begin end step
    '''

입력 함수

input

변수 = input('출력 내용')

• 리턴 타입이 문자열이다.

  • 숫자 등 다른 형식으로 쓰려면 형변환해야 한다.

• 예제

  age = int(input('몇 살이세요? '))
  print(age)

출력 함수

print

print(출력 내용[, sep = 구분자][, end = 끝 문자])

• sep의 기본값은 ' ', end의 기본값은 '\n'이다.

• 리턴 값이 None이다.

• 예시

  print("ab", "cd", sep = " ---> ", end = "\n")
  
  ''' stdout
  ab ---> cd
  
  '''

pprint

• pprint 모듈

• 리스트 등을 예쁘게 출력해준다.

  from pprint import pprint
  
  dict_list = [{"First": 1, "Second": 2, "Third": 3}, \
              {"Hello": "World"}, {"Python": "Django"}]
  pprint(dict_list)
  
  ''' stdout
  [{'First': 1, 'Second': 2, 'Third': 3},
  {'Hello': 'World'},
  {'Python': 'Django'}]
  '''

멀티캠퍼스 파이썬

함수(Function)

문자열(String)

리스트(List)

튜플(Tuple)

사전(Dictionary)

집합(Set)

컬렉션 관리

표준 모듈

예외 처리

파일

클래스(Class)

모듈과 패키지

고급 문법

그 외

• Underscore(_) : 직접 사용하지는 않지만 필요한 변수에 할당한다.

  • ex. for _ in range(5)

• 소스 형식

  • 들여쓰기로 코드 블록을 구분한다.

  • 대소문자를 구분한다.

  • 주석은 #를 맨 앞에 붙이고, 여러 줄은 각각 앞에 붙여야 한다.

하드웨어

• 메모리

  • DRAM(Dynamic Random Access Memory)

    • 커패시터 기반이기 때문에 자연방전이 발생한다.

      • Dynamic하게 주기적으로 Refresh 해야 하므로 지연이 발생한다.

    • 저렴하여 RAM에 많이 사용한다.

  • SRAM(Static Random Access Memory)

    • 전자식 기반(플립플롭)이므로 Refresh가 필요없어서 빠르다.

    • DRAM에 비해 가격이 비싸서 CPU 캐시에 주로 사용한다.

용어

• 컨텍스트 메뉴(Context Menu) : 마우스 우클릭 시 뜨는 메뉴

• Opcode(Operation Code) : CPU 명령어 코드

• 환경 변수 Path

  • 현재 디렉토리에 실행 파일이 없을 경우 실행 파일을 찾을 디렉토리의 경로이다.

  • 사용자 변수와 시스템 변수가 있는데, 사용자 변수부터 찾기 시작한다.

• SRP(Single Responsibility Principle, 단일 책임 원칙)

  • 모든 클래스는 하나의 책임만 가지며, 클래스는 그 책임을 완전히 캡슐화해야 한다는 의미이다.

• Kebob(케밥) Case

  • 하이픈으로 단어를 구분하는 방법

    ex. print-in-star

참고

• 파이썬 정복 - 김상형

리액트 gh-pages 적용

• 리액트로 만든 사이트를 github에서 호스팅할 경우, gh-pages 패키지를 사용하면 편하다.

• 일반적인 깃허브 페이지는 빌드한 파일들을 해당 브랜치에 넣어두는데, 이 패키지를 사용하면 원격 리포지토리에 gh-pages라는 브랜치가 생기고, 거기에 빌드하게 된다.

적용 과정

• 다음 명령어 중 하나로 gh-pages 패키지를 설치한다.

  $ npm install gh-pages
  $ yarn add gh-pages

  • --save 옵션은 관습적으로 사용하는 것 같다. (https://xtring-dev.tistory.com/entry/NPM-npm-install-%ED%95%A0-%EB%95%8C-save%EB%A5%BC-%ED%95%A8%EA%BB%98-%EC%9E%85%EB%A0%A5%ED%95%98%EB%8A%94-%EC%9D%B4%EC%9C%A0)

• 프로젝트의 package.json 파일을 아래처럼 수정한다.

  {
    "homepage": "도메인주소",
    ...(생략),
    "scripts": {
      ...(생략),
      "predeploy": "npm run build",
      "deploy": "gh-pages -d build"
    }
  }

• 이 후 배포할 때 다음 명령어 중 하나를 실행하면 새로운 브랜치로 pull request를 할 수 있고, 이를 처리하면 gh-pages 브랜치가 생성된다.

  $ npm run deploy
  $ yarn deploy

• 이후 깃허브의 Settings -> Pages 에서 브랜치를 설정하면 페이지가 해당 브랜치에 대해 설정된다.

참고

• https://www.hohyeonmoon.com/blog/react-js-github-pages-deploy/

VSCode No such file or directory 에러

• 윈도우10에서 VSCode의 Code Runner 플러그인을 설치했다.

• 직접 g++로 .cpp 파일을 컴파일할 수 있었는데, Code Runner로 실행하면 에러가 발생했다.

원인

• 찾아보니 디렉토리 경로가 \로 연결되고, 이 경로는 "로 묶여있었다.

• 경로의 마지막 \" 부분에서 escape 처리가 되어서 파싱을 제대로 못하는 문제였다.

해결

• VSCode의 설정(Ctrl + ,)으로 들어가서 오른쪽 위의 Open Settings를 클릭한다.

• 아래 문구를 추가한다.

  {
    ...
    "code-runner.runInTerminal": true,
    "code-runner.terminalRoot": "/",
  }

  • code-runner.runInTerminal : 터미널에서 실행하게 된다.

  • code-runner.terminalRoot : 경로의 구분자를 변경할 수 있다.

Django 채팅 앱 만들기

• channels 공식 문서에 정리가 잘 되어있다.

  • https://channels.readthedocs.io/en/latest/tutorial/part_1.html

장고 기본 페이지 생성

개발 환경

• 윈도우10, Anaconda3 가상환경에서 수행했다.

  $ conda --version
  conda 4.10.1
  $ conda create -n chat python=3.8
  $ conda activate chat
  $ python --version
  Python 3.8.11

• 기본적으로 필요한 라이브러리들을 설치한다.

  $ pip install Django
  $ python -m django --version
  3.2.6
  $ pip install channels
  $ python -c 'import channels; print(channels.__version__)'
  3.0.4

프로젝트 생성

• 작업할 chat 폴더로 들어가서 프로젝트를 생성한다.

  $ django-admin startproject mysite .

  • .은 현재 폴더를 프로젝트의 루트 디렉토리로 구성하라는 의미이다.

    • 생략하면 프로젝트명으로 하위 폴더가 만들어진다.

• chat 앱을 생성한다.

  $ python manage.py startapp chat

• mysite/settings.py 의 INSTALLED_APPS에 방금 생성한 앱을 추가한다.

  mysite/settings.py

  INSTALLED_APPS = [
    'chat',
    'django.contrib.admin',
    'django.contrib.auth',
    'django.contrib.contenttypes',
    'django.contrib.sessions',
    'django.contrib.messages',
    'django.contrib.staticfiles',
  ]

• 제공되는 기본 html 파일을 chat/templates/chat/index.html 에 입력한다.

  chat/templates/chat/index.html

  <!DOCTYPE html>
  <html>
  <head>
      <meta charset="utf-8"/>
      <title>Chat Rooms</title>
  </head>
  <body>
      What chat room would you like to enter?<br>
      <input id="room-name-input" type="text" size="100"><br>
      <input id="room-name-submit" type="button" value="Enter">
  
      <script>
          document.querySelector('#room-name-input').focus();
          document.querySelector('#room-name-input').onkeyup = function(e) {
              if (e.keyCode === 13) {  // enter, return
                  document.querySelector('#room-name-submit').click();
              }
          };
  
          document.querySelector('#room-name-submit').onclick = function(e) {
              var roomName = document.querySelector('#room-name-input').value;
              window.location.pathname = '/chat/' + roomName + '/';
          };
      </script>
  </body>
  </html>

• chat/views.py 에서 index.html을 렌더링하는 함수를 생성하고 URLconf를 설정한다.

  chat/views.py

  from django.shortcuts import render
  
  def index(request):
      return render(request, 'chat/index.html')

  chat/urls.py

  from django.urls import path
  
  from . import views
  
  urlpatterns = [
      path('', views.index, name='index'),
  ]

  mysite/urls.py

  from django.contrib import admin
  from django.urls import path, include
  
  urlpatterns = [
      path('chat/', include('chat.urls')),
      path('admin/', admin.site.urls),
  ]

• 서버를 돌리면 마이그레이션 하라고 뜨는데, 일단 정상적으로 작동하는지 확인한다.

  $ python3 manage.py runserver
  Django version 3.2.6, using settings 'mysite.settings'
  Starting development server at http://127.0.0.1:8000/
  Quit the server with CTRL-BREAK.

  • http://127.0.0.1:8000/chat/ 으로 접속하면 url 매핑이 정상적으로 이루어진 것을 볼 수 있다.

Channels 라이브러리 적용

• Channels의 라우팅은 장고의 URLconf와 비슷하다.

  • HTTP 요청이 들어오면 장고는 root URLconf에서 view 함수를 찾아서 요청을 처리한다.

  • 비슷하게, Channels는 웹 소켓 연결을 받아서 root routing configuration에서 consumer를 찾는다.

    • consumer의 다양한 함수를 통해 연결에서 오는 이벤트들을 처리한다.

• mysite/asgi.py를 다음과 같이 수정한다.

  mysite/asgi.py

  import os
  
  from channels.routing import ProtocolTypeRouter
  from django.core.asgi import get_asgi_application
  
  os.environ.setdefault('DJANGO_SETTINGS_MODULE', 'mysite.settings')
  
  application = ProtocolTypeRouter({
      "http": get_asgi_application(),
      # Just HTTP for now. (We can add other protocols later.)
  })

• Channels 라이브러리를 mysite/settings.py 의 INSTALLED_APPS 에 추가하고, 루트 라우팅 설정도 해준다.

  mysite/settings.py

  INSTALLED_APPS = [
      'channels',
      'chat',
      'django.contrib.admin',
      'django.contrib.auth',
      'django.contrib.contenttypes',
      'django.contrib.sessions',
      'django.contrib.messages',
      'django.contrib.staticfiles',
  ]
  # Channels
  ASGI_APPLICATION = 'mysite.asgi.application'

  • 맨 위에 추가하지 않으면 충돌이 발생한다고 한다.

• 서버를 실행하면 아까와 다른 문구가 뜨는 것을 볼 수 있다.

  python manage.py runserver
  Django version 3.2.6, using settings 'mysite.settings'
  Starting ASGI/Channels version 3.0.4 development server at http://127.0.0.1:8000/
  Quit the server with CTRL-BREAK.

• http://127.0.0.1:8000/chat/ 사이트는 여전히 정상적으로 작동한다.

서버 실행

• 위에서 생성한 http://127.0.0.1:8000/chat/ 페이지에서 방 제목을 입력하면 해당 방으로 들어가서 채팅하는 앱을 만드는 것이 목표이다.

• 방에 해당하는 템플릿과 뷰를 작성하고 URLconf를 설정한다.

  chat/templates/chat/room.html

  <!DOCTYPE html>
  <html>
  <head>
      <meta charset="utf-8"/>
      <title>Chat Room</title>
  </head>
  <body>
      <textarea id="chat-log" cols="100" rows="20"></textarea><br>
      <input id="chat-message-input" type="text" size="100"><br>
      <input id="chat-message-submit" type="button" value="Send">
      {{ room_name|json_script:"room-name" }}
      <script>
          const roomName = JSON.parse(document.getElementById('room-name').textContent);
  
          const chatSocket = new WebSocket(
              'ws://'
              + window.location.host
              + '/ws/chat/'
              + roomName
              + '/'
          );
  
          chatSocket.onmessage = function(e) {
              const data = JSON.parse(e.data);
              document.querySelector('#chat-log').value += (data.message + '\n');
          };
  
          chatSocket.onclose = function(e) {
              console.error('Chat socket closed unexpectedly');
          };
  
          document.querySelector('#chat-message-input').focus();
          document.querySelector('#chat-message-input').onkeyup = function(e) {
              if (e.keyCode === 13) {  // enter, return
                  document.querySelector('#chat-message-submit').click();
              }
          };
  
          document.querySelector('#chat-message-submit').onclick = function(e) {
              const messageInputDom = document.querySelector('#chat-message-input');
              const message = messageInputDom.value;
              chatSocket.send(JSON.stringify({
                  'message': message
              }));
              messageInputDom.value = '';
          };
      </script>
  </body>
  </html>

  chat/views.py

  from django.shortcuts import render
  
  def index(request):
      return render(request, 'chat/index.html', {})
  
  def room(request, room_name):
      return render(request, 'chat/room.html', {
          'room_name': room_name
      })

  chat/urls.py

  from django.urls import path
  from . import views
  
  urlpatterns = [
      path('', views.index, name='index'),
      path('<str:room_name>/', views.room, name='room'),
  ]

• 이대로 서버를 실행해서 http://127.0.0.1:8000/chat/ 에 접속하고 방 제목을 입력해보면 해당 페이지로 이동되는 것을 볼 수 있다.

  • 하지만 이동하는 순간 서버에는 다음과 같은 오류가 발생한다.

    ValueError: No application configured for scope type 'websocket'  

  • 클라이언트에서도 콘솔 창을 열어보면 다음과 같은 오류가 발생한 것을 볼 수 있다.

    WebSocket connection to 'ws://127.0.0.1:8000/ws/chat/asd/' failed: 
    Chat socket closed unexpectedly

  • html 파일의 자바스크립트에서 WebSocket을 연결하는 것에 실패했기 때문이다.

• 해당 URL에 대한 웹 소켓을 받아주는 consumer가 필요하다.

  chat/consumers.py

  import json
  from channels.generic.websocket import WebsocketConsumer
  
  class ChatConsumer(WebsocketConsumer):
      def connect(self):
          self.accept()
  
      def disconnect(self, close_code):
          pass
  
      def receive(self, text_data):
          text_data_json = json.loads(text_data)
          message = text_data_json['message']
  
          self.send(text_data=json.dumps({
              'message': message
          }))

  • receive()

    • 위의 chat/templates/chat/room.html 파일에서 document.querySelector('#chat-message-submit').onclick 이벤트를 설정했었다.

      • 이 함수에서 보낸 json 데이터를 다시 클라이언트에게 되돌려주는 역할을 한다.

    • 클라이언트가 메시지를 다시 받으면 chat/templates/chat/room.html 파일의 chatSocket.onmessage 이벤트에서 로그를 추가하는 방식이다.

  • 이 컨슈머는 동기적(synchronous)이다.

    • 비동기적(asynchronous)으로 구현하는게 훨씬 성능이 좋지만, 장고 모델 접근에서 문제가 발생할 수 있으니 Consumer 문서를 잘 참고하라고 써있다.

• 이 consumer를 이용하기 위해서 routing configuration을 설정해야 한다.

  chat/routing.py

  from django.urls import re_path
  from . import consumers
  
  websocket_urlpatterns = [
      re_path(r'ws/chat/(?P<room_name>\w+)/$', consumers.ChatConsumer.as_asgi()),
  ]

  • 각각의 연결에 consumer의 인스턴스를 생성하기 위해 as_asgi() 클래스메서드를 사용했다.

    • 장고 뷰 인스턴스의 per-request와 같은 역할이라는데 이건 또 공부해봐야겠다.

  • re_path() 함수를 사용한 것은, 만약 내부 라우터가 미들웨어에 감싸져 있을 경우 path() 함수는 제대로 동작하지 않을 수 있기 때문이다.

• 위에서 작성한 설정을 root routing configuration에서 지정한다.

  mysite/asgi.py

  import os
  
  from channels.auth import AuthMiddlewareStack
  from channels.routing import ProtocolTypeRouter, URLRouter
  from django.core.asgi import get_asgi_application
  import chat.routing
  
  os.environ.setdefault("DJANGO_SETTINGS_MODULE", "mysite.settings")
  
  application = ProtocolTypeRouter({
    "http": get_asgi_application(),
    "websocket": AuthMiddlewareStack(
          URLRouter(
              chat.routing.websocket_urlpatterns
          )
      ),
  })

  • 서버로 연결이 생성되면 먼저 ProtocolTypeRouter가 연결의 종류를 탐색한다.

  • ws:// 혹은 wss:// 형식의 웹 소켓 연결이면, 해당 연결은 AuthMiddlewareStack으로 메시지를 group의 모든 channel에게 보낸다.

• chat_message()

  • channel layer의 group으로부터 전달된다.

  • AuthMiddlewareStack은 현재 인증된 유저를 참조하여 연결의 scope를 채운다.

    • 장고의 AuthenticationMiddleware이 현재 인증된 유저를 참조하여 view 함수의 request 객체를 채우는 것과 비슷하다고 한다.

  • 그 후 연결은 URLRouter로 전달된다.

• 여기까지 하고 migration 후 서버를 돌렸더니 오류가 발생했다.

  $ python manage.py migrate
  $ python manage.py runserver
  django.core.exceptions.ImproperlyConfigured: Cannot import ASGI_APPLICATION module 'mysite.asgi'

  • chat/consumers.py 를 chat/consumer.py로 오타내서 발생한 문제여서, 파일명을 변경하여 해결했다.

    • python manage.py shell 로 파이썬 쉘에 진입한 뒤 from mysite.routing import application 로 직접 import 했을 때 뜨는 에러 문구로 어디서 잘못했는지 짐작할 수 있다.

    • 참고 : https://stackoverflow.com/questions/51634522/cannot-import-asgi-application-module-while-runserver-using-channels-2

• 이제 http://127.0.0.1:8000/chat/a 등의 주소로 이동해서 메시지를 입력해보면 해당 메시지가 성공적으로 되돌아오는 것(echo)을 볼 수 있다.

  • 같은 주소로 창을 두 개 열어서 확인해보면 다른 쪽에는 메시지가 전송되지 않는 것을 볼 수 있다.

  • 이를 해결하려면 ChatConsumer의 여러 인스턴스가 서로 통신하도록 해야 한다.

  • Channels는 컨슈머끼리 이런 통신을 할 수 있도록 하는 channel layer를 제공한다.

channel layer 활성화

• channel layer는 다음과 같은 추상화를 제공한다.

  • channel

    • 메시지가 전달될 수 있는 우체통이다.

    • 각 channel은 이름을 가지며, 다른 channel에게 메시지를 전송할 수 있다.

  • group

    • 연관된 channel들의 그룹이다.

    • group은 이름을 가지며, channel의 이름을 통해 추가하고 삭제할 수 있다.

    • 그룹의 모든 channel에게 메시지를 전송할 수 있다.

    • 특정 그룹에 있는 channel들을 나열할 수는 없다.

• 모든 consumer 인스턴스는 자동으로 유일한 channel name을 생성하기 때문에, 서로 channel layer를 통해 통신할 수 있다.

• 지금 진행 중인 앱에서는 같은 방에 있는 ChatConsumer의 여러 인스턴스들끼리 통신하는게 목표이다.

  • 이를 위해 각 ChatConsumer 인스턴스는 room name을 이름으로 하는 group에 channel을 추가한다.

  • 이러면 같은 방에 있는 channel들은 같은 group에 속하므로 서로 통신할 수 있게 된다.

• 도커의 redis 컨테이너를 backing store로 사용하는 channel layer를 생성할 것이다.

  $ docker run -p 6379:6379 -d redis:5

  • redis컨테이너는 6379 포트를 사용한다.

  • redis 5.0 버전을 사용하는 이유는 아마...

    https://redis.io/download#other-versions

    Redis 5.0 is the first version of Redis to introduce the new stream data type with consumer groups, ...

• Channels와 redis를 연결하기 위해 라이브러리를 설치한다.

  $ pip install channels_redis

• channel layer를 사용하기 위해 mysite/settings.py 의 ASGI_APPLICATION 밑에 다음과 같이 백엔드와 호스트에 대한 설정을 추가한다.

  # Channels
  ASGI_APPLICATION = 'mysite.asgi.application'
  CHANNEL_LAYERS = {
      'default': {
          'BACKEND': 'channels_redis.core.RedisChannelLayer',
          'CONFIG': {
              "hosts": [('127.0.0.1', 6379)],
          },
      },
  }

• channel layer와 redis의 연결을 확인하기 위해 다음과 같이 입력해본다.

  $ python manage.py shell
  >>> import channels.layers
  >>> channel_layer = channels.layers.get_channel_layer()
  >>> from asgiref.sync import async_to_sync
  >>> async_to_sync(channel_layer.send)('test_channel', {'type': 'hello'})
  >>> async_to_sync(channel_layer.receive)('test_channel')
  {'type': 'hello'}
  >>> exit()

• 이제 channel layer가 있으므로, ChatConsumer를 수정하여 group 내의 channel에게 보내도록 설정한다.

  chat/consumers.py

  import json
  from asgiref.sync import async_to_sync
  from channels.generic.websocket import WebsocketConsumer
  
  class ChatConsumer(WebsocketConsumer):
      def connect(self):
          self.room_name = self.scope['url_route']['kwargs']['room_name']
          self.room_group_name = 'chat_%s' % self.room_name
  
          # Join room group
          async_to_sync(self.channel_layer.group_add)(
              self.room_group_name,
              self.channel_name
          )
  
          self.accept()
  
      def disconnect(self, close_code):
          # Leave room group
          async_to_sync(self.channel_layer.group_discard)(
              self.room_group_name,
              self.channel_name
          )
  
      # Receive message from WebSocket
      def receive(self, text_data):
          text_data_json = json.loads(text_data)
          message = text_data_json['message']
  
          # Send message to room group
          async_to_sync(self.channel_layer.group_send)(
              self.room_group_name,
              {
                  'type': 'chat_message',
                  'message': message
              }
          )
  
      # Receive message from room group
      def chat_message(self, event):
          message = event['message']
  
          # Send message to WebSocket
          self.send(text_data=json.dumps({
              'message': message
          }))

  • connect()

    • 연결 시 channel layer의 group에 channel을 추가한다.

    • self.room_name은 chat/urls.py에서 지정한 변수명을 AuthMiddlewareStack가 scope에 kwargs 형태로 채워준 것을 꺼내서 사용한다.

    • 실제로 channel layer에서 사용하는건 self.room_group_name이다.

      • 굳이 이렇게 변환하는 이유는..?

  • disconnect()

    • 연결 해제 시 channel layer의 group에서 channel을 삭제한다.

  • receive()

    • 웹 소켓으로부터 메시지를 받을 시 메시지를 channel layer의 group 내 모든 channel에게 보낸다.

  • chat_message()

    • channel layer의 group으로부터 메시지를 받을 시 메시지를 클라이언트로 전달한다.

    • 전과 마찬가지로 chatSocket.onmessage 이벤트에 의해 처리된다.

• 서버를 실행하고 클라이언트 두 개로 통신해보면 정상적으로 작동하는 것을 볼 수 있다.

Github 계정 2개 SSH 연결

• 기존에 사용하던 ssh key로 깃허브의 다른 계정에 연결하려 했으나 key is already in use 에러가 발생했다.

  • 깃허브에서 ssh key의 중복을 허용하지 않아서 발생하는 문제이다.

  • 따라서 ssh key를 하나 더 만들어서 등록해야 하는데, 여기서 따로 설정해야 하는 부분이 있다.

ssh 키 생성

• ssh key를 하나 더 만들 때 기존의 키와 겹칠까봐 아래와 같은 과정을 거쳤다. 단순히 새로 만들 키의 이름을 ssh-keygen 명령어 실행 시 처음에 설정해줘도 된다.

  • ~/.ssh 폴더에서 기존에 사용하던 키의 이름을 변경하고(백업), 다시 ssh 키를 생성한다.

    • id_rsa, id_rsa.pub의 이름을 id_rsa.backup, id_rsa.pub.backup 이런식으로 변경해둔다.

  ssh-keygen -C 이메일

  • 새로 생성한 key들의 이름을 변경하고, 백업했던 key들을 다시 복원한다.

    • id_rsa, id_rsa.pub를 id_rsa_new, id_rsa_new.pub로 변경하고 위에서 백업한 것들을 다시 원래대로 복원한다.

  • 2번째 계정 깃허브에 ssh key 등록

    • 깃허브의 Settings - SSH and GPG keys 탭에 들어가서 New SSH key를 클릭하고 ~/.ssh/id_rsa_new.pub의 내용을 복붙한다.

.ssh/config 파일 수정

• 아래와 같이 github.com-new로 연결했을 때 다른 개인키를 사용하도록 등록한다.

  # Github
  Host github.com
    HostName github.com
    User git
    IdentityFile ~/.ssh/id_rsa
  Host github.com-new
    HostName github.com
    User git
    IdentityFile ~/.ssh/id_rsa_new

클론, 푸쉬, 연결할 때

• 이제 평소와 같이 작업을 하면 되는데, 신경써야 할 부분이 몇가지 있다.

  • URL을 위의 config에서 새로 추가한 Host로 쓸 것

    • git clone이나 git remote add를 할 때 URL 자리에 github.com이 아닌 github.com-new 이런 식으로 써야 한다.

  • 다른 계정으로 사용할 레포에서는 이름과 이메일을 따로 설정할 것

    • git config user.name 유저명 이렇게 따로 설정해주지 않으면 --global 설정을 따라가기 때문에 다른 이름으로 커밋이 된다는 점을 신경써야 한다.

참고

• https://yosuniiiii.com/github-%EA%B3%84%EC%A0%95-%EC%97%AC%EB%9F%AC%EA%B0%9C-%EC%82%AC%EC%9A%A9%ED%95%98%EA%B8%B0-on-mac-6588237f9671

• https://velog.io/@jay/multiplegithubaccounts

팟플레이어 검은 화면

• 서피스 프로7에서 팟플레이어를 실행하니 검은 화면에 소리만 재생되는 현상이 발생했다.

해결 방법

• 환경 설정(F5)를 눌러 영상 탭의 영상 출력 장치를 Video Renderer 등 다른 렌더러로 변경, 종료 후 다시 실행한다.

• 만약 이렇게 했는데 공포스러운 재생 화면이 나올 경우(굉장히 어둡고 빨간 색만 나옴) Q를 눌러 설정을 초기화한다.

VSCode Settings.json에서 인덴트 설정

• Ctrl + ,로 설정에 들어간 뒤 우측 상단의 Open Settings(JSON) 클릭 후 아래 내용 삽입

{
    "[markdown]": {
        "editor.tabSize": 2,
        "editor.insertSpaces": true,
    },
    "[html]": {
        "editor.insertSpaces": true,
        "editor.tabSize": 2
    },
    "[css]": {
        "editor.insertSpaces": true,
        "editor.tabSize": 2
    },
    "[javascript]": {
        "editor.insertSpaces": true,
        "editor.tabSize": 2
    },
}

참고

• https://stackoverflow.com/questions/45806965/auto-indent-rules-for-file-extension-in-visual-studio-code-vscode

윈도우10 갑자기 업데이트

• 켜놓고 딴짓을 하는데 갑자기 컴퓨터가 종료되더니 업데이트를 시작했다.

• 서비스에서 윈도우 업데이트를 사용안함으로 해도 소용없다.

  • https://answers.microsoft.com/ko-kr/windows/forum/windows_10-update/%EC%9C%88%EB%8F%84%EC%9A%B010-home/e7f6ce54-eeb7-4cdf-baf6-e80199a70797

• 윈도우10 홈 에디션은 로컬 그룹 정책 편집기를 지원하지 않는데, 이를 직접 설치해도 적용되지 않는다고 한다.

• 결국 홈 에디션에서 자동 업데이트 기능을 끌 수는 없는 것 같다.

• 대신 활동 시간을 변경하여 자동으로 컴퓨터가 꺼지는 상황은 예방할 수 있는 것 같다.

  

  
  

  

ㅎㅏㄴㄱㅡㄹㅇㅣ ㅇㅣㅅㅏㅇㅎㅏㄱㅔ ㅊㅕㅈㅣㄹㄸㅐ

• 윈도우10에서 Win + H 키를 누르면 음성 받아쓰기 모드로 전환된다.

• 한국어의 경우 지원되지 않는데, 이 기능이 계속 활성화되어 자음과 모음이 분리되는 현상이 발생하는 것 같다.

해결 방법

• 받아쓰기 모드를 해제하려면 소프트웨어적으로 타이핑을 하면 되는 듯하다.

  • Win + . 를 누르면 이모지 창이 뜨는데, 이걸 꺼주면 원래대로 돌아온다.

  • 혹은 Win + R로 실행 창에 들어가서 tabtip을 입력하면 가상 키보드가 뜨는데, 이걸 꺼주면 원래대로 돌아온다.

    • 한 번 실행하면 백그라운드에서 계속 켜져있기 때문에, 두 번째부터는 작업관리자에서 프로세스를 종료하고 다시 켜야 한다.

VirtualBox "가상머신의 세션을 열 수 없습니다" 에러

• 오랜만에 가상머신을 작동시키는데 에러가 발생했다.

  The virtual machine has terminated unexpectedly during startup with exit code -1073741819 (0xc0000005). More details may be available in ~
  결과 코드 : E_FAIL (0x80004005)
  구성 요소 : MachineWrap
  인터페이스 : IMachine

  

• 원인은 Fasoo DRM Client for NHN Mobile Wix였다.

  

  • 네이버 e-book을 볼 때 설치했던 프로그램같다.

  • 닫아야하는 프로세스들을 종료하고 삭제 후 리부팅하면 된다.

    

• 참고 : https://besttech.tistory.com/27

• 알기쉬운 알고리즘(양성봉 저, 생능 출판) 책을 바탕으로 작성한 내용이다.

04. 그리디(Greedy) 알고리즘

• 최적화 문제를 해결하는 알고리즘이다.

• 입력 데이터 간의 관계를 고려하지 않고, 수행 과정에서 최솟값 또는 최댓값을 가진 데이터를 선택한다.

  • 근시안적 선택으로 부분적인 최적해를 찾고, 이를 모아서 문제 전체의 최적해를 찾는다.

• 한번 선택하면 번복하지 않아서 알고리즘들이 비교적 단순하다.

4.1 동전 거스름돈

• 거스름돈의 동전 개수를 가장 적게 받는 방법

• 남은 액수를 초과하지 않는 조건에서 가장 큰 액면의 동전을 취하는 방법을 사용한다.

  Pseudo Code

  int CountCoin(int change)
  {
    int n500 = n100 = n50 = n10 = n1 = 0;
    while (change >= 500)
    {
      change -= 500;
      n500++;
    }
    while (change >= 100)
    {
      change -= 100;
      n100++;
    }
    while (change >= 50)
    {
      change -= 50;
      n50++;
    }
    while (change >= 10)
    {
      change -= 10;
      n10++;
    }
    while (change >= 1)
    {
      change -= 1;
      n1++;
    }
    return (n500 + n100 + n50 + n10 + n1);
  }

• 만약 160원짜리 동전이 추가된다면, 이 알고리즘은 최적해를 보장하지 못한다.

  • 어떤 경우에도 최적해를 찾고 싶으면 동적 계획 알고리즘을 사용해야 한다.

4.2 최소 신장 트리(Minimum Spanning Tree)

4.3 최단 경로 찾기(Shortest Path)

4.4 부분 배낭 문제(Fractional Kanpsack Problem)

4.5 집합 커버 문제(Set Cover Problem)

4.6 작업 스케줄링(Task Scheduling)

4.7 허프만 압축(Huffman Coding)

허프만 압축(Huffman Coding)

• 문자를 0과 1로 표현하여 압축하는 방법이다.

• 접두부 특성(Prefix Property)가 존재한다.

  • 압축된 이진 코드가 다른 이진 코드의 접두부가 되지 않는 특성을 의미한다.

  • https://ko.wikipedia.org/wiki/%EC%95%9E%EC%9E%90%EB%A6%AC_%EB%B6%80%ED%98%B8

  • 예를 들면, 변환된 이진 코드가 {1, 10} 두 가지라면 "1"은 "10"의 앞부분에 포함되므로 이는 접두부 특성이 없는 것이다.

  • 반면에 {0, 10} 의 경우 "0"과 "10"은 반드시 구분되므로 접두부 특성을 가진다.

알고리즘

• 각 문자의 출현 빈도수에 따라 이진 코드를 할당한다.

  • 빈도수가 많을수록 짧은 이진 코드를 할당하는게 효율적이다.

  • 이진 트리와 우선순위 큐를 사용한다.

    Pseudo Code

    HuffmanTree HuffmanCoding(문자 각각에 대한 빈도수)
    {
      각 문자에 대해 빈도수를 저장하는 노드를 생성한다.
      빈도수에 대한 우선순위 큐를 만들고 모든 노드를 큐에 넣는다.
      while (큐에 노드가 2개 이상일 경우)
      {
        빈도수가 가장 작은 2개의 노드를 큐에서 pop한다.
        새 노드를 만들어 위에서 pop한 2개의 노드를 자식 노드로 만든다.
        새 노드의 빈도수는 각 노드의 빈도수의 합이다.
        새 노드를 우선순위 큐에 삽입한다.
      }
      return (Q에 남은 노드);
    }

예제

• 문자 A, G, C, T에 대한 빈도수가 각각 450, 120, 270, 90일 경우 다음과 같은 순서를 따른다.

  

• 결과적으로 A, G, C, T는 각각 허프만 코드로 0, 100, 11, 101이 된다.

• 이진 트리의 특성에 따라 빈도수가 높을 수록 루트 노드와 가까우므로 짧은 코드에 대응되고, 접두부 특성을 지님을 알 수 있다.

• 압축비

  • 허프만 코드로 변환하기 전 문자들의 용량은 (450 + 120 + 270 + 90) * 1byte * 8bit/1byte = 7440bit이다.

  • 변환 후의 용량은 (450 * 1) + (120 * 3) + (270 * 2) + (90 * 3) = 1620bit이다.

  • 따라서 압축비 = (압축 전 크기) / (압축 후 크기) = 7440 / 1620 = 4.593 이다.

    • 약 1/4.6의 크기로 압축된 것을 알 수 있다.

시간 복잡도

• 각 빈도수를 노드에 저장할 때 O(n) 시간이 걸린다.

• 우선순위 큐로 힙 자료구조를 사용하면 O(n) 시간이 걸린다.

• 루프는 (n - 1)번 반복된다.

  • 큐에서 최소 빈도수 노드 2개를 삭제 후 새 노드를 큐에 다시 삽입하는 과정에서 O(logn)이 걸린다.

  • 즉 루프의 시간 복잡도는 O(nlogn)이다.

• 따라서 허프만 코딩의 시간 복잡도는 O(nlogn)이다.

작업 스케줄링(Task Scheduling)

• 기계에서 수행되는 n개의 작업들을 수행 시간이 중복되지 않도록 가장 적은 수의 기계에 배정하는 문제이다.

  • 각 작업은 시작시간과 종료시간이 정해져있다.

  • 발표 시간이 정해진 학술대회에서 발표자들을 강의실에 배정하는 문제와 같다.

알고리즘

• 다음과 같은 그리디 알고리즘이 존재한다.

  • 빠른 시작 시간 작업 우선 (Earliest Start Time First)

  • 빠른 종료 시간 작업 우선 (Earliest Finish Time First)

  • 짧은 작업 우선 (Shortest Job First)

  • 긴 작업 우선 (Longest Job First)

  • 여기서는 최적해를 찾기 위해 첫 번째 방법을 선택한다.

• 빠른 시작 시간 작업 우선 (Earliest Start Time First)

  Pseudo Code

  JobScheduling(Task *arr)
  {
    Task list[] = arr를 시작 시간을 기준으로 오름차순 정렬한 배열
    while (list에 원소가 존재하면)
    {
      t_i = (가장 이른 시작 시간을 가진 작업);
      if (t_i를 수행할 기계가 존재하면)
        t_i를 해당 기계에 배정한다.
      else
        새로운 기계에 t_i를 배정한다.
      t_i를 list에서 제거한다.
    }
    return 각 기계에 배정된 작업 순서
  }

예제

• 시작 시간과 종료 시간을 [start time, end time]이라고 표기한다.

  t₁ = [7, 8]

  t₂ = [3, 7]

  t₃ = [1, 5]

  t₄ = [5, 9]

  t₅ = [0, 2]

  t₆ = [6, 8]

  t₇ = [1, 6]

• 시작 시간을 기준으로 오름차순 정렬하여 list에 저장하면 다음과 같다.

  list = { [0, 2], [1, 5], [1, 6], [3, 7], [5, 9], [6, 8], [7, 8] }

  

시간 복잡도

• 배열을 정렬할 때 O(nlogn) 시간이 걸린다.

• 사용된 기계의 수를 m이라고 하면, 루프 내부에서 기계를 찾을 때의 시간 복잡도는 O(m)이다.

  • 루프가 n번 반복되므로 총 O(mn)이다.

• 따라서 총 시간 복잡도는 O(nlogn) + O(mn)이다.

집합 커버 문제 (Set Cover Problem)

• 전체 집합 U와, 그 부분 집합 S_i들을 원소로 갖는 집합 F가 있다고 하자.

• F의 원소인 S_i들을 합집합하여 전체 집합 U와 같아지는 집합 S_i들의 최소 개수를 찾는 문제이다.

• F에 있는 집합들의 모든 조합을 하나씩 찾을 경우

  • 만약 F의 원소의 개수가 n개이면 나올 수 있는 경우의 수는 (2ⁿ - 1)개이고, n이 증가함에 따라 이 방식으로 최적해를 찾는 것은 실질적으로 불가능하다.

• 따라서 최적해 대신 최적해에 근접한 근사해(Approximation Solution)을 찾아야 한다.

  • U에 있는 원소를 가장 많이 커버하는 S_i를 반복적으로 찾아서 포함시키는 방식을 사용한다.

알고리즘

• 입력에 전체 집합 U와 그 부분 집합 S_i들을 포함한 집합 F가 주어진다.

  Pseudo Code

  SetCover(Set u, Set f)
  {
    Set cover;
    while (u.size() != 0)
    {
      u의 원소들을 가장 많이 포함하는 집합 s_i를 f에서 선택한다.
      u에서 s_i를 뺀다. (차집합)
      s_i를 cover에 추가한다.
      s_i를 f에서 제거한다.
    }
    return cover;
  }

  ---

예제

신도시를 계획하는데 10개의 마을에 학교를 배치해야 한다.

• 각 점은 마을을 의미하고, 선분은 15분 이내의 거리를 뜻한다.

• 학교는 마을에 위치해야 하고, 등교 거리는 15분 이내여야 한다.

  

• 집합 커버 문제로 변환시키면 다음과 같다.

  U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

  F = {S₁, S₂, S₃, S₄, S₅, S₆, S₇, S₈, S₉, S₁₀}

  S₁ = {1, 2, 3, 8}

  S₂ = {1, 2, 3, 4, 8}

  S₃ = {1, 2, 3, 4}

  S₄ = {2, 3, 4, 5, 7, 8}

  S₅ = {4, 5, 6, 7}

  S₆ = {5, 6, 7, 9, 10}

  S₇ = {4, 5, 6, 7}

  S₈ = {1, 2, 4, 8}

  S₉ = {6, 9}

  S₁₀ = {6, 10}

• 위의 알고리즘을 적용하는 순서는 다음과 같다.

  • 첫 번째 루프

    • 집합 U의 원소를 가장 많이 커버하는 집합인 S₄를 F에서 선택한다.

    • U에서 S₄를 빼면 U = {1, 6, 9, 10}이 된다.

    • S₄를 cover에 추가하고 F에서 제거한다.

  • 두 번째 루프

    • 집합 U의 원소를 가장 많이 커버하는 집합인 S₆를 F에서 선택한다.

    • U에서 S₆를 빼면 U = {1}이 된다.

    • S₆를 cover에 추가하고 F에서 제거한다.

  • 세 번째 루프

    • 집합 U의 원소를 가장 많이 커버하는 집합인 S₁를 F에서 선택한다.

    • U에서 S₁를 빼면 U는 공집합이 된다.

    • S₁를 cover에 추가하고 F에서 제거한다.

  • S₁, S₄, S₆이 담긴 cover를 리턴한다.

시간 복잡도

• 루프를 반복하는 횟수는 최대 n번이다.

• 전체 집합 U의 원소를 가장 많이 포함하는 집합 S_i를 찾을 때 걸리는 시간 복잡도는 O(n²)이다.

• 집합 U에서 집합 S_i를 뺄 때 O(n)이 걸린다.

• S_i를 cover에 추가하고 F에서 뺄 때 O(1)이 걸린다.

• 따라서 전체 시간 복잡도는 O(n³)이다.

  • 이는 지수 시간(2ⁿ)에 비해 굉장히 짧은 시간이다.

근사 비율 (Approximation Ratio)

• 근사 알고리즘에서 근사해가 최적해에 얼마나 가까운지를 나타내는 척도이다.

• SetCover 알고리즘의 근사 비율은 Klogn이라고 한다.

  • K는 최적해의 집합의 수이다.

  • 위의 예제에서는 최적해의 개수 K = 2이므로 Klogn = 2log10 < 8이다.

  • 즉 SetCover 알고리즘의 근사해의 집합 수가 8개를 초과하지 않는다는 것이다.

부분 배낭 문제 (Fractional Kanpsack Problem)

• 배낭 문제

  • n개의 물건이 각 무게와 가치를 가지고 있을 때, 한정된 용량의 배낭에 최대의 가치를 갖도록 넣는 방법에 대한 문제이다.

• 부분 배낭 문제는 물건을 부분적으로 담는 것이 허용된다.

알고리즘

• 물건을 부분적으로 담을 수 있으므로, 단위 무게당 가치가 제일 높은 것부터 배낭에 넣는다.

  • 만약 통째로 넣을 수 없다면, 넣을 수 있는 만큼만 부분적으로 넣는다.

• 입력으로 각 물건의 무게와 가치, 배낭의 용량을 받는다.

• 출력은 배낭에 담은 물건 리스트와 배낭에 담은 가치의 총합이다.

  Pseudo Code

  FractionalKnapsack(Item *arr, int capacity)
  {
    각 물건의 단위 무게당 가치를 계산한다.
    단위 무게당 가치를 기준으로 내림차순 정렬하여 저장한다.
    int weight = 0; // 배낭에 담긴 무게
    int value = 0; // 배낭에 담긴 가치의 총합
    Item highest = 단위 무게당 가치가 가장 큰 물건;
    Item *list; // 배낭에 담긴 물건의 리스트
    while (weight + highest.weight <= capacity)
    {
      highest를 list에 추가한다.
      weight += highest.weight;
      value += highest.value;
      highest를 arr에서 제거한다.
      새로운 highest를 선정한다.
    }
    if (capacity > weight)
    {
      highest를 (capacity - weight)만큼만 list에 추가한다.
      value += capacity - weight;
    }
    return list, value;
  }

시간 복잡도

• 각 물건의 단위 무게당 가치를 계산할 때 O(n) 시간이 걸린다.

• 정렬할 때 O(nlogn) 시간이 걸린다.

• 반복문에서 최대 O(n) 시간이 걸린다.

• 따라서 시간 복잡도는 O(nlogn)이다.

0-1 배낭 문제

• 부분 배낭 문제의 원형이다.

• 0/1 배낭 문제라고도 표기한다.

  • 0은 물건을 배낭에 넣지 않는다는 뜻이고, 1은 넣는다는 뜻이다.

• 그리디 알고리즘으로 해결할 수 없고, 다음 알고리즘들로 해결 가능하다.

  • 동적 계획(Dynamic Programming) 알고리즘

  • 백트래킹(Backtracking) 기법

  • 분기 한정(Branch-and-Bound)

최단 경로 찾기(Shortest Path)

• 가중치 그래프의 어느 한 출발점에서 도착점까지의 최단 경로를 찾는 문제이다.

• 대표적으로 다익스트라 최단 경로 알고리즘이 있다.

다익스트라(Dijkstra) 최단 경로 알고리즘

• 프림의 최소 신장 트리(MST) 알고리즘과 비슷하다.

• 주어진 출발점에서부터 최단 거리인 점을 하나씩 확정해가며 각 점까지의 최단 거리를 점차 업데이트하는 방식이다.

• 입력으로 주어지는 그래프에는 각 점과 선분에 대한 정보가 있다고 가정한다.

  Pseudo Code

  ShortestPath(Graph g, Node start)
  {
    int dist[n];  // 최단 거리를 저장한 배열
    dist[start] = 0;
    start를 제외한 나머지는 inf로 초기화시킨다.
    while (최단 거리가 확정되지 않은 점이 있다면)
    {
      start로부터 최단 거리가 확정되지 않은 점들 중 최소 거리인 점 v_min에 대해 dist[v_min]을 확정시킨다.
      start로부터 v_min을 통해 갈 수 있는 각 점 w에 대해 dist[w]를 갱신한다.
    }
    return dist;
  }

  

시간 복잡도

• 반복문이 (n - 1)번 반복되고, dist 배열에서 v_min을 찾을 때 O(n) 시간이 걸리므로 시간 복잡도는 O(n²)이다.

최소 신장 트리(Minimum Spanning Tree)

• 가중치 그래프에서, 사이클 없이 모든 점을 연결시킨 트리들 중에 가중치 합이 최소인 트리를 의미한다.

• 그래프의 점의 수가 n이면, 신장트리에는 (n - 1)개의 선분이 존재한다.

  • n개 이상의 선분이 존재할 경우 사이클이 생기고, 이는 트리라고 할 수 없다.

• 대표적인 그리디 알고리즘으로 크러스컬(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 존재한다.

  • 입력으로 받는 그래프 G에는 점의 집합 V와 선분 집합 E에 대한 정보가 포함되어 있다.

  • 점의 개수를 n, 선분의 개수를 m이라고 가정한다.

크러스컬(Kruskal) 알고리즘

• 최소 가중치를 가진 선분을 하나씩 뽑아서, 트리에 사이클을 형성하지 않는지 검사하고 추가하는 방식이다.

  Pseudo Code

  KruskalMST(Graph g)
  {
    가중치의 오름차순으로 선분들을 정렬하여 L에 저장한다.
    Tree t;
    while (t의 선분 수 < (점의 개수 n) - 1)
    {
      선분 e = 가장 작은 가중치를 가진 선분을 가져오고 L에서 제거한다.
      if (선분 e가 사이클을 형성하지 않으면)
        선분 e와 그를 구성하는 점들을 T에 추가시킨다.
    }
    return t;
  }

시간복잡도

• 선분들을 정렬하는 데에 걸리는 시간은 O(mlogm)이다.

• 반복문은 최대 m번 수행되고, 각각의 루프 내에서 선분이 사이클을 형성하는지 검사하는데 O(log*m) 시간이 걸리므로 반복문에서는 총 O(mlog*m)의 시간이 걸린다.

  • log*m은 반복 로그를 의미하는데, 굉장히 느리게 증가하는 함수이다.

  • 참고 : https://ko.wikipedia.org/wiki/%EB%B0%98%EB%B3%B5_%EB%A1%9C%EA%B7%B8

• 따라서 크러스컬 알고리즘의 시간 복잡도는 O(mlogm)이다.

프림(Prim) 알고리즘

• 최소 가중치의 점을 트리에 포함시키며 계속해서 점과 점 사이의 가중치를 업데이트하는 방식이다.

  Pseudo Code

  PrimMST(Graph g)
  {
    최소 가중치를 저장해둘 배열을 D로 설정하고, 임의의 점 p를 골라서 D[p] = 0로 놓는다.
    for (점 p가 아닌 각 점 v에 대하여)
    {
      if (p와 v를 잇는 선분이 있으면)
        D[v] = 선분(p, v)의 가중치
      else
        D[v] = inf
    }
    Tree t = { p };
    while (t.size() < n)
    {
      트리 t에 속하지 않은 각 점 v들에 대하여, D[v]가 최소인 v_min을 선분과 함께 t에 추가한다.
      for (트리 t에 속하지 않은 각 점 w에 대하여)
      {
        D[w] = min(선분(v_min, w)의 가중치, D[w]);
      }
    }
    return t;
  }

  

  ---

시간복잡도

• while 루프가 (n - 1)번 반복되고, 각 루프 내에서 D[v]가 최소인 점 v_min을 찾을 때 O(n) 시간이 걸리므로 시간복잡도는 O(n²)이다.

  • 단, 배열 D를 힙 자료구조로 구현하면 시간 복잡도는 O(mlogn)이 될 수 있다고 한다.

크러스컬과 프림 알고리즘 비교

• 크러스컬 알고리즘에서는 선분이 하나씩 트리에 추가되는데, 이는 n개의 점들이 각각의 트리인 상태에서 점점 하나의 트리로 합쳐지는 것과 같다.

  • 즉 n개의 트리들이 점차 합쳐져서 1개의 신장 트리를 구성한다.

• 프림 알고리즘에서는 점 1개인 트리에서 시작되어 선분을 하나씩 추가시킨다.

  • 즉 1개의 트리가 자라나서 신장 트리가 된다.

SSH 접속 시 WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that a host key has just been changed.
The fingerprint for the ECDSA key sent by the remote host is
SHA256:~~~.
Please contact your system administrator.
Add correct host key in ~/.ssh/known_hosts to get rid of this message.
Offending ECDSA key in ~/.ssh/known_hosts:4
Host key for IP has changed and you have requested strict checking.
Host key verification failed.

• 이미 known_hosts 파일에 등록된 IP에 대해 다른 공개키를 전송받은 경우 발생하는 문제이다.

• .ssh/known_hosts 파일에서 해당 IP를 지워주면 된다.

라즈베리파이 USB 부팅

• 라즈베리파이3B에서 테스트했다.

• USB 부트 모드를 설정해야 하므로 일단 micro sd카드에서 부팅해야 한다.

USB에 라즈베리파이 OS 올리기

• 컴퓨터에 USB를 꽂고 아래 사이트에서 Raspberry Pi Imager를 다운받는다.

  • https://www.raspberrypi.org/software/

  

  
  

  

• 받는 동안 라즈베리파이에서 아래 설정을 변경한다.

라즈베리파이 설정 변경

• USB 부트 모드를 활성화해야 한다.

  sudo apt update
  sudo apt upgrade
  echo program_usb_boot_mode=1 | sudo tee -a /boot/config.txt
  sudo reboot

  • program_usb_boot_mode = 1 이런 식으로 띄어쓰기를 하면 적용이 되지 않는다.

• 리부팅 후 정상 적용이 되었는지 확인한다.

  vcgencmd otp_dump | grep 17

  17:3020000a

• 확인됐으면 종료한 다음 sd카드를 빼고 usb를 꽂아서 부팅하면 정상적으로 작동한다.

• 알기쉬운 알고리즘(양성봉 저, 생능 출판) 책을 바탕으로 작성한 내용이다.

03. 분할 정복 알고리즘

• 주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘이다.

• 분할된 입력의 문제(부분문제, Subproblem)에 대해 동일한 알고리즘을 적용하여 부분해를 얻으며, 이를 취합해서 원래 문제의 해를 얻는다.

  • 더 이상 분할할 수 없을 때까지 계속 부분문제로 분할한다.

• 문제 : 크기가 n인 입력을 3개로 분할하고, 각각 분할된 부분문제의 크기가 n/2이라고 할 때, 총 몇 번 분할하여야 더 이상 분할할 수 없는 크기인 1이 될까?

  • 총 분할 횟수를 k라고 하면, n/2^k = 1이므로 k는 log₂n이 된다.

분할 정복 알고리즘의 분류

• 문제가 a개로 분할되고, 부분문제의 크기가 1/b로 감소하는 알고리즘

  a	b	알고리즘
  2	2	합병 정렬(3.1절), 최근접 점의 쌍 찾기(3.4절), 공제선 문제(연습문제 25번)
  3	2	큰 정수의 곱셈(연습문제 21)
  4	2	큰 정수의 곱셈(연습문제 20)
  7	2	스트라센의 행렬 곱셈(연습문제 22)

• 문제가 2개로 분할되고, 부분문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘

  • 퀵 정렬(3.2절)

• 문제가 2개로 분할되나, 그중에 1개의 부분문제는 고려할 필요가 없고 부분문제의 크기가 1/2로 감소하는 알고리즘

  • 이진탐색(1.2절)

• 문제가 2개로 분할되나, 그중에 1개의 부분문제는 고려할 필요가 없고 부분문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘

  • 선택 문제 알고리즘(3.3절)

• 부분문제의 크기가 1, 2개씩 감소하는 알고리즘

  • 삽입 정렬(6.3절)

  • 피보나치 수의 계산(3.5절)

3.1 합병 정렬 (Merge Sort)

3.2 퀵 정렬 (Quick Sort)

3.3 선택 문제 (Selection Problem)

3.4 최근접 점의 쌍 찾기(Closest Pair)

3.5 분할 정복을 적용하는 데 있어서 주의할 점

• 만약 분할될 때마다 분할된 부분문제의 입력 크기의 합이 기존의 입력 크기보다 매우 커진다면 분할 정복 알고리즘을 적용하는게 부적절할 수 있다.

  • 예를 들어 n번째 피보나치 수를 구할 때 재귀 호출을 사용하면, 분할 후 입력 크기가 거의 2배씩 늘어나므로 반복문을 사용하는게 효율적이다.

• 분할 뿐만 아니라 취합 과정에도 신경을 써야 효율적인 알고리즘이 탄생한다.

최근접 점의 쌍 찾기(Closest Pair)

• 2차원 평면 상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제

• 모든 점에 대하여 각각의 두 점 사이의 거리를 계산하는 방법의 시간 복잡도는 O(n²)이다.

• 분할 정복을 이용하면 시간 복잡도는 O(n(logn)²)이다.

  • 책에서는 O(n(logn)²)이라고 하는데, 아직 y좌표에 대해 반드시 정렬해야 하는건지 잘 모르겠고, 찾아보니 O(nlogn)이라는 정보도 있다.

  • https://en.wikipedia.org/wiki/Closest_pair_of_points_problem

분할 정복

알고리즘

• 2개나 3개의 점이 남을 때까지 분할한다.

• 최근접 쌍을 찾고 분할한 부분문제들을 합칠 때, 합치는 경계를 기준으로 좌우의 점들에 대해 다시 검증을 해야 한다.

  • 중간 영역에 속하는 점들을 판별하는 방법은 다음과 같다.

    • 각 부분문제의 최근접 점 사이의 거리 중 작은 값을 택하고 이를 d라고 하자.

    • 왼쪽 부분문제의 가장 오른쪽 점의 x좌표에서 d만큼 뺀 x좌표부터, 오른쪽 부분문제의 가장 왼쪽 점의 x좌표에서 d만큼 더한 x좌표 사이에 포함되는 점들이 바로 중간 영역에 속하는 점들이라고 할 수 있다.

• arr는 x좌표 기준 오름차순으로 정렬된 좌표(x, y)들의 배열이다.

  Pseudo Code

  ClosestPair(arr)
  {
    if (arr.size() <= 3)
      return (2개 또는 3개의 점들 사이의 최근접 쌍);
    arr를 반으로 나눠서 arr_left와 arr_right로 분할한다.
    closest_pair_left = ClosestPair(arr_left);
    closest_pair_right = ClosestPair(arr_right);
    d = min(closest_pair_left, closest_pair_right); 를 통해 중간 영역에 속하는 점들을 판별한다.
    중간 영역에 속하는 점들 중에서 최근접 점의 쌍을 closest_pair_center로 저장한다.
    return (closest_pair_left, closest_pair_right, closest_pair_center 중에 최근접 점의 쌍);
  }

  ---

시간 복잡도

• 처음 배열을 정렬할 때의 시간 복잡도는 O(nlogn)이다.

• 분할해서 계산하는건 모두 O(1)이라고 생각되고, 층 수가 O(logn)인 것 같다.

• 따라서 시간 복잡도는 O(nlogn)인데.. 처음 정렬하는게 제일 영향이 크다는게 의아하다.

코드

#include <iostream>
#include <vector>
#include <cmath>
#include <limits>

class vec2;

float GetDistance(const vec2& v1, const vec2& v2);

class vec2
{
public:
    int x_;
    int y_;

    vec2()
    {
        x_ = rand() % 100;
        y_ = rand() % 100;
    }

    vec2(int x_in, int y_in)
    : x_(x_in), y_(y_in)
    {}

    vec2 operator - (const vec2& v) const
    {
        return (vec2(x_ - v.x_, y_ - v.y_));
    }

    friend std::ostream& operator << (std::ostream& out, const vec2& v)
    {
        out << '(' << v.x_ << ", " << v.y_ << ')';
        return out;
    }
};

class ClosestPair
{
public:
    vec2 v1_;
    vec2 v2_;
    float dist_;

    ClosestPair()
    {
        dist_ = std::numeric_limits<float>::max();
    }
    ClosestPair(const vec2& v1, const vec2& v2)
    {
        v1_ = v1;
        v2_ = v2;
        dist_ = GetDistance(v1, v2);
    }

    friend std::ostream& operator << (std::ostream& out, const ClosestPair& cp)
    {
        out << "Point1 : " << cp.v1_ << "\tPoint2 : " << cp.v2_ << "\tDistance : " << cp.dist_ << std::endl;
        return out;
    }
};

float GetDistance(const vec2& v1, const vec2& v2)
{
    return std::sqrt(std::pow((v1 - v2).x_, 2) + std::pow((v1 - v2).y_, 2));
}

void QuickSort(std::vector<vec2>& arr, int left, int right)
{
    if (left >= right)
        return ;

    int    pivot = (left + right) / 2;
    int    high = left + 1;
    int    low = right;

    std::swap(arr[pivot], arr[left]);
    while (high <= low)
    {
        while ((high <= right) && (arr[high].x_ <= arr[left].x_))
            high++;
        while ((low > left) && (arr[low].x_ >= arr[left].x_))
            low--;
        if ((high > right) || (low == left) || (high >= low))
            break;
        std::swap(arr[high], arr[low]);
    }
    std::swap(arr[left], arr[low]);

    QuickSort(arr, left, low - 1);
    QuickSort(arr, low + 1, right);
}

ClosestPair GetUnderThreeCase(const std::vector<vec2>& v, int left, int right)
{
    if (right == left + 2)
    {
        float dist1 = GetDistance(v[left], v[left + 1]);
        float dist2 = GetDistance(v[left], v[right]);
        float dist3 = GetDistance(v[left + 1], v[right]);

        if (dist1 < dist2 && dist1 < dist3)
            return ClosestPair(v[left], v[left + 1]);
        else if (dist2 < dist1 && dist2 < dist3)
            return ClosestPair(v[left], v[right]);
        else
            return ClosestPair(v[left + 1], v[right]);
    }
    else
        return ClosestPair(v[left], v[right]);
}

ClosestPair CheckCenter(const std::vector<vec2>& v, int left, int right, float d)
{
    float x_leftside = v[(left + right) / 2].x_ - d;
    float x_rightside = v[(left + right) / 2 + 1].x_ + d;
    ClosestPair closest_pair_center;

    for (int i = 0; i <= (left + right) / 2; ++i)
    {
        if (v[i].x_ < x_leftside)
            continue ;
        for (int j = (left + right) / 2 + 1; j <= right; ++j)
        {
            if (v[j].x_ > x_rightside)
                continue ;
            if (GetDistance(v[i], v[j]) < closest_pair_center.dist_)
                closest_pair_center = ClosestPair(v[i], v[j]);
        }
    }
    return closest_pair_center;
}

ClosestPair GetClosestPair(const std::vector<vec2>& v, int left, int right)
{
    if (right <= left + 2)
        return GetUnderThreeCase(v, left, right);
    ClosestPair closest_pair_left = GetClosestPair(v, left, (left + right) / 2);
    ClosestPair closest_pair_right = GetClosestPair(v, (left + right) / 2 + 1, right);

    float d = std::min(closest_pair_left.dist_, closest_pair_right.dist_);
    ClosestPair closest_pair_center = CheckCenter(v, left, right, d);

    if (closest_pair_left.dist_ < closest_pair_right.dist_ && \
        closest_pair_left.dist_ < closest_pair_center.dist_)
        return closest_pair_left;
    else if (closest_pair_right.dist_ < closest_pair_left.dist_ && \
        closest_pair_right.dist_ < closest_pair_center.dist_)
        return closest_pair_right;
    else
        return closest_pair_center;
}

int main()
{
    using namespace std;

    srand(time(NULL));

    vector<vec2> v(10);
    QuickSort(v, 0, v.size() - 1);
    for (const auto &e : v)
        cout << e << '\n';

    ClosestPair closest_pair;
    closest_pair = GetClosestPair(v, 0, v.size() - 1);
    cout << closest_pair << endl;
}

• 코드를 완벽히 하려면 sqrt를 제외하고 비교하는 등의 최적화를 하고, 예외처리도 해서 좀 더 정리해야 한다.

• 그래픽 요소 추가하면 좋을 듯

• 책에서는 부분문제를 합칠 때 y좌표를 기준으로 정렬한 뒤 d와 비교하라고 하는데, 굳이 정렬해야 하는 이유를 찾지 못해서 그냥 비교했다.

선택 문제 (Selection Problem)

• n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제이다.

• 간단한 해결 방법

  • 최소인 숫자들 찾아서 제거하는 방법을 k번 반복한다.

    • 최악의 경우 시간 복잡도 : O(kn)

  • 오름차순으로 정렬한 뒤 k번째 숫자를 찾는다.

    • 최악의 경우 시간 복잡도 : O(nlogn)

  • 간단하지만 비효율적이다.

• 이진 탐색과 퀵 정렬을 섞으면 원하는 숫자를 효율적으로 찾을 수 있다.

• 데이터 분석에서 중앙값(median)을 찾는 데 활용된다.

아이디어

• 퀵 정렬에서 처럼 피벗을 정하고 피벗보다 작은건 왼쪽, 피벗보다 큰건 오른쪽에 위치하도록 정렬한다.

• 작은 그룹의 크기와 큰 그룹의 크기는 피벗의 인덱스를 통해 알 수 있다.

• 분할

  • 찾고자하는 k번째로 작은 숫자가 피벗인 경우 그대로 반환한다.

  • 찾고자하는 k번째로 작은 숫자가 작은 그룹에 있을 경우, 작은 그룹에서 k번째 작은 숫자를 찾는다.

  • 찾고자하는 k번째로 작은 숫자가 큰 그룹에 있을 경우, 큰 그룹에서 (k - (작은 그룹의 크기 + 1))번째로 작은 수를 찾는다.

• 2개의 부분문제로 나눠지지만, 그중에 1개만 고려하면 되고, 부분문제의 크기가 일정하지 않은 크기로 감소하는 형태이다.

  pseudo code

  int Selection(int* arr, int left, int right, int k)
  {
    피벗을 선택하고 arr[left]와 자리를 바꾼다.
    피벗보다 작은 숫자는 arr[left] ~ arr[p - 1]로 이동한다.
    피벗보다 큰 숫자는 arr[p + 1] ~ arr[right]로 이동한다.
    피벗은 arr[p]에 위치시킨다. 여기서의 p는 위의 과정이 끝난 후 피벗보다 작은 그룹의 가장 오른쪽 인덱스이다.
    small_group_size = p - left;
    if (k <= small_group_size) return Selection(arr, left, p - 1, k);
    else if (k == small_group_size + 1) return arr[p];
    else return Selection(arr, p + 1, right, k - (small_group_size + 1));
  }

  

시간복잡도

• 피벗을 정할 때 완벽하게 절반으로 나누는 분할은 불가능하다.

• 시간 복잡도 계산을 위해 다음과 같은 조건을 설정했다.

  • 분할했을 때 큰 쪽의 크기가 입력 크기의 3/4 이상일 경우 bad 분할, 이하인 경우 good 분할이라고 정의한다.

• 분할했을 때 good 분할이 될 확률은 1/2이다.

  • 평균 2회 연속해서 랜덤하게 피벗을 정하면 good 분할이 한번 나오는 것이다.

• 따라서 평균 경우 시간 복잡도를 구하려면, 연속으로 good 분할이 됐다고 가정한 다음 해당 시간 복잡도에 2를 곱하면 되는 것이다.

• 시간 복잡도를 구하는 과정은 다음과 같다.

  • 1번째 분할

    • 입력의 크기가 n일 때 두 그룹을 분할하는 데 걸리는 시간은 O(n)이다.

    • 분할 후 큰 부분의 최대 크기는 (3n - 1)/4 인데, 편의상 (3/4)n 이라고 생각한다.

  • 2번째 분할

    • 큰 부분의 입력 크기가 3n/4이고, 분할 시간은 O(3n/4)이다.

    • 분할 후 큰 부분의 최대 크기는 (3/4)²n이다.

  • 이를 반복하면 시간 복잡도는 다음과 같다.

    O(n + (3/4)n + (3/4)²n + ... + (3/4)ⁱn) = O(n)

  • 여기에 2를 곱한 평균 경우 시간 복잡도는 O(n)이다.

코드

#include <iostream>
#include <vector>

void PrintArr(const std::vector<int>& arr)
{
    for (const auto &e : arr)
        std::cout << e << ' ';
    std::cout << std::endl;
}

int Selection(std::vector<int>& arr, int left, int right, int k)
{
    if (left == right)
        return (arr[left]);

    int    pivot = (left + right) / 2;
    int    high = left + 1;
    int    low = right;

    std::swap(arr[pivot], arr[left]);
    while (high <= low)
    {
        while ((high <= right) && (arr[high] <= arr[left]))
            high++;
        while ((low >= left) && (arr[low] >= arr[left]))
            low--;
        if (high > low)
            break;
        std::swap(arr[low], arr[high]);
    }
    std::swap(arr[left], arr[low]);

    int small_group_size = low - left;
    if (k <= small_group_size)
        return Selection(arr, left, low - 1, k);
    else if (k == small_group_size + 1)
        return (arr[low]);
    else
        return Selection(arr, low + 1, right, k - (small_group_size + 1));
}

int main()
{
    using namespace std;

    vector<int> arr{ 6, 3, 11, 9, 12, 2, 8, 15 };
    int k = 7;

    PrintArr(arr);
    cout << k << "th number : " << Selection(arr, 0, arr.size() - 1, k) << endl;
}

/* stdout
6 3 11 9 12 2 8 15 
7th number : 12
*/

퀵 정렬 (Quick Sort)

• 분할 정복 알고리즘이지만 사실은 정복하고 분할한다.

• 입력의 크기가 클 경우 가장 좋은 성능을 보이는 정렬 알고리즘이다.

  • 생물 정보 공학(Bioinformatics)에서 특정 유전자를 찾을 때 접미 배열(Suffix Array)와 함께 사용된다고 한다.

• 피벗(pivot) 숫자를 기준으로 피벗보다 작은 숫자를 왼쪽으로, 큰 숫자를 오른쪽으로 이동시킨 다음 피벗을 사이에 놓고 분할하는 방식이다.

  • 피벗은 부분문제에 포함되지 않는다.

  pseudo code

  QuickSort(int *arr, int left, int right)
  {
    if (left < right)
    {
      피벗을 arr[left] ~ arr[right] 중에 선택한다.
      피벗을 arr[left]와 자리를 바꾼다.
      피벗보다 작은 숫자의 인덱스를 low, 피벗보다 큰 숫자의 인덱스를 high라고 하자.
        low = right, high = left + 1부터 시작하여 가운데쪽으로 이동하며 검사한다.
      arr[low]와 arr[high]를 비교하여 작은 수는 arr[left + 1] ~ arr[p]로, 큰 숫자는 arr[p + 1] ~ arr[right]로 서로 맞교환해가며 진행한다.
      low < high일 때는 정복이 끝난 것이므로 arr[left]와 arr[low]의 값을 바꾼 뒤 분할한다.
      QuickSort(arr, left, p - 1);
      QuickSort(arr, p + 1, right);
    }
  }

  • 11, 9, 2, 12, 8, 15, 18, 10의 정렬 예제

    • 피벗을 (right - left) / 2로 잡았다.

    • 먼저 피벗을 맨 왼쪽의 값과 바꾼다.

    • 반복문

      • high는 left + 1부터 시작하여 피벗의 값보다 큰 값이 나올 때까지 우측으로 이동한다.

        • 피벗의 값과 같은 값은 패스하는데, 이는 부분문제에서 해결 가능하기 때문이다.

      • low는 right부터 시작하여 피벗의 값보다 작은 값이 나올 때까지 좌측으로 이동한다.

      • 인덱스 low가 high보다 낮으면 정복이 끝났으므로 피벗과 low를 교체하고 부분문제로 분할한다.

      • 그렇지 않으면 low의 값과 high의 값을 바꾼다.

      

시간 복잡도

• 최악 경우 시간 복잡도는 O(n²)이다.

  • 예를 들면 피벗이 계속해서 가장 작은 값만 선택될 경우, 부분문제로 들어가도 입력의 크기만 1씩 줄어들 뿐 문제가 분할되지 않는다.

  • 입력의 크기가 n일 때 비교하는 횟수를 보면 (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2 = O(n²) 이다.

• 최선의 경우 시간 복잡도는 O(nlog₂n)이다.

  • 피벗이 계속해서 입력의 중앙값으로 선택되면, 항상 1/2로 분할되고 층마다 n번씩 비교를 하게된다.

  • 총 비교 횟수 = 층 수 * 각 층마다의 비교 횟수 = log₂n * O(n) = O(nlog₂n)

피벗 선정 방법

• 랜덤하게 선정하는 방법

• 3 숫자의 중앙값으로 선정하는 방법

  • 가장 왼쪽, 중앙, 가장 오른쪽의 값 중에 2번째의 값으로 피벗을 설정한다.

성능 관련 팁

• 입력의 크기가 매우 클 경우, 삽입 정렬을 같이 사용한다.

  • 입력의 크기가 작으면 퀵 정렬은 재귀 호출이기에 삽입 정렬보다 느리므로, 이 점을 보완한다.

코드

#include <iostream>
#include <vector>

void PrintArr(const std::vector<int>& arr)
{
    for (auto& e : arr)
        std::cout << e << ' ';
    std::cout << std::endl;
}

void QuickSort(std::vector<int>& arr, int left, int right)
{
    if (left >= right)
        return ;

    int    pivot = (left + right) / 2;
    int    high = left + 1;
    int    low = right;

    std::swap(arr[pivot], arr[left]);
    while (high <= low)
    {
        while ((high <= right) && (arr[high] <= arr[left]))
            high++;
        while ((low > left) && (arr[low] >= arr[left]))
            low--;
        if ((high > right) || (low == left) || (high >= low))
            break;
        std::swap(arr[high], arr[low]);
    }
    std::swap(arr[left], arr[low]);

    QuickSort(arr, left, low - 1);
    QuickSort(arr, low + 1, right);
}

int main()
{
    std::vector<int> arr{ 11, 9, 2, 12, 8, 15, 18, 10 };

    PrintArr(arr);
    QuickSort(arr, 0, arr.size() - 1);
    PrintArr(arr);
}

합병 정렬 (Merge Sort)

• 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘

• 연결 리스트에 있는 데이터를 정렬할 때 퀵 정렬이나 힙 정렬보다 훨씬 효율적이라고 한다.

  pseudo code

  MergeSort(int arr[], int p, int q)
  {
    if (p < q)
    {
      int k = (p + q) / 2;
      MergeSort(arr, p, k);
      MergeSort(arr, k + 1, q);
      arr[p] ~ arr[k]와 arr[k + 1] ~ arr[q]를 합병한다.
    }
  }

  

시간 복잡도

• 분할하는 부분

  • 배열의 중간 인덱스 계산과 재귀 호출 2번으로 O(1) 시간이 걸린다.

• 합병하는 부분

  • 두 정렬된 배열 A, B의 크기가 각각 n과 m이고 이를 합병하여 새로운 배열 C를 만드는 부분

    • (n + m - 1)번의 비교를 통해 배열 C를 채우므로 시간 복잡도는 O(n + m)이다.

  • 층 별 비교

    • 각 층에서 수행되는 비교 횟수는 분할된 크기 * 분할된 개수로, 항상 O(n)이다.

    • 층 수는 log₂n이다.

    • 즉, 모든 층에서 수행되는 비교 횟수는 O(nlog₂n)이다.

  • 각 층에서 비교 후에 새로운 배열로 이동시키는 과정의 시간복잡도는 O(nlog₂n)이다.

• 모두 더하면 O(nlog₂n)이다.

공간 복잡도

• 입력과 같은 크기의 공간이 별도로 필요하므로 O(n)이다.

C++ 코드

#include <iostream>
#include <vector>

void PrintElements(const std::vector<int>& arr)
{
    for (const auto& e : arr)
        std::cout << e << " ";
    std::cout << std::endl;
}

void Merge(std::vector<int>& arr, int low, int mid, int high)
{
    int i = low;
    int j = mid + 1;
    int temp_idx = low;
    static std::vector<int> temp(arr);

    while ((i <= mid) && (j <= high))
    {
        if (arr[i] < arr[j])
            temp[temp_idx++] = arr[i++];
        else
            temp[temp_idx++] = arr[j++];
    }
    while (i <= mid)
        temp[temp_idx++] = arr[i++];
    while (j <= high)
        temp[temp_idx++] = arr[j++];

    while (low <= high)
    {
        arr[low] = temp[low];
        low++;
    }
}

void MergeSort(std::vector<int>& arr, int low, int high)
{
    if (low == high)
        return ;

    int mid = (low + high) / 2;

    MergeSort(arr, low, mid);
    MergeSort(arr, mid + 1, high);
    Merge(arr, low, mid, high);
}

int main()
{
    using namespace std;

    vector<int> arr = { 37, 10, 22, 30, 35, 13, 25, 24 };

    PrintElements(arr);
    MergeSort(arr, 0, arr.size() - 1);
    PrintElements(arr);
}

/* stdout
37 10 22 30 35 13 25 24 
10 13 22 24 25 30 35 37
*/

참고

• 알기쉬운 알고리즘 (양성봉 저, 생능 출판)

• 알기쉬운 알고리즘(양성봉 저, 생능 출판) 책을 바탕으로 작성한 내용이다.

02. 알고리즘을 배우기 위한 준비

2.1 알고리즘이란

• 유래 : 페르시아 수학자인 알콰리즈미(al-Khwarizmi)(서기 780~850년)

• 알고리즘은 문제를 해결하는 단계적 절차 또는 방법이다.

  • 이는 컴퓨터로 해결할 수 있어야 하며 입력과 출력이 존재한다.

• 알고리즘의 일반적인 특성

  • 정확성

    • 주어진 입력에 대해 올바른 해를 준다.

  • 수행성

    • 컴퓨터에서 수행이 가능해야 한다. (애매모호한 표현이 없어야 한다.)

  • 유한성

    • 현실적인 시간 내로 종료되어야 한다.

  • 효율성

    • 시간적, 공간적인 효율성을 최대한 고려해야 한다.

2.2 최초의 알고리즘

• 기원전 300년경에 만들어진 유클리드(Euclid)의 최대공약수를 찾는 알고리즘이 최초이다.

• 유클리드의 최대공약수 알고리즘

  a >= b >= 0 일 때,

  pseudo code

  int Euclid(int a, int b)
  {
    if (b == 0) return a;
    return Euclid(b, a mod b);
  }

2.3 알고리즘의 표현 방법

• 알고리즘의 각 단계는 보통 말로 서술할 수 있지만, 일반적으로 의사 코드(pseudo code)로 표현된다.

• 1장의 "1.1 최대 숫자 찾기"의 의사 코드는 다음과 같다.

  pseudo code

  max = Array[0]
  for i = 1 to 9
    if (Array[i] > max) max = Array[i]
  return max

• 이외에도 플로우차트(flow chart) 형태로 표현하기도 한다.

2.4 알고리즘의 분류

• 알고리즘은 문제의 해결 방식에 따라 대략 다음과 같이 분류된다.

  • 분할 정복(Divide-and-Conquer) - 3장

  • 그리디(Greedy) - 4장

  • 동적 계획(Dynamikc Programming) - 5장

  • 근사(Approximation) - 8장

  • 백트래킹(Backtracking) - 9장

  • 분기 한정(Branch-and-Bound) - 9장

  • 랜덤(Random)

  • 병렬(Parallel)

  • 분산(Distributed)

  • 양자(Quantum)

  • 유전자(Genetic)

• 문제에 기반하여 분류한 알고리즘들

  • 정렬 - 6장

  • 그래프(Graph)

  • 기하(Geometry)

2.5 알고리즘의 효율성 표현

• 일반적으로 시간 복잡도가 알고리즘의 비교 척도로 사용된다.

• 시간 복잡도(Time Complexity)

  • 알고리즘의 수행 시간

    • 실제로 수행되는 시간이 아닌, 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현하는 것이다.

  • 알고리즘의 복잡도를 분석하는 방법은 다음과 같다.

    • 최악 경우 분석(Worst Case Analysis)

      • 어떤 입력이 주어지더라도 넘지 않는 시간을 분석한다.

    • 평균 경우 분석(Average Case Analysis)

      • 입력이 균등 분포(Uniform Distribution)일 경우를 가정하고 분석한다.

    • 최선 경우 분석(Best Case Analysis)

      • 최적(Optimal) 알고리즘을 고안할 때 참고 자료로 활용된다.

• 공간 복잡도(Space Complexity)

  • 알고리즘이 수행되는 동안 사용되는 메모리 공간의 크기

2.6 복잡도의 점근적 표기

점근적 표기(Asymptotic Notation)

• 복잡한 식을 간단히 표현하기 위해 사용되는 표기법

• 일반적으로 빅오 표기법이 사용된다.

• O(Big-Oh) 표기

  • 복잡도의 점근적 상한을 나타낸다.

    • 점근적 상한

      • 단순화된 함수에 임의의 양수를 곱하여 나온 함수가, n이 증가함에 따라 f(n)의 상한이 되는 경우

  • 다항식의 최고 차항만 계수 없이 취하면 된다.

• Ω(Big-Omega) 표기

  • 복잡도의 점근적 하한을 나타낸다.

    • 점근적 하한

      • 단순화된 함수에 임의의 양수를 곱하여 나온 함수가, n이 증가함에 따라 f(n)의 하한이 되는 경우

  • 다항식의 최고 차항만 계수 없이 취하면 된다.

• θ(Theta) 표기

  • 복잡도의 상한과 하한이 동시에 적용되는 경우를 나타낸다.

    • n이 증가함에 따라 복잡도와 동일한 증가율을 가진다는 것을 의미한다.

  • 즉 빅오 표기법과 빅오메가 표기법의 복잡도가 같은 경우 사용한다.

  ---

예제

• 복잡도가 f(n) = 2n²-8n+3 일 때

  • O(n²)

    • 임의의 양수 c를 곱한 cn²은 n이 증가함에 따라 f(n)의 상한이 된다. (예를 들면 c = 5인 경우)

  • Ω(n²)

    • 임의의 양수 c를 곱한 cn²은 n이 증가함에 따라 f(n)의 하한이 된다. (예를 들면 c = 1인 경우)

  • θ(n²)

    • f(n)은 n이 증가함에 따라 n²과 동일한 증가율을 가진다.

  ---

자주 사용되는 O 표기

2.7 왜 효율적인 알고리즘이 필요한가?

• 입력 크기가 커질 수록 수행 시간의 차이가 엄청나며, 하드웨어 기술 개발보다는 효율적인 알고리즘 개발이 훨씬 경제적이다.

보간 탐색(Interpolation Search)

• 이진 탐색이 무조건 가운데를 검사한다는 것을 개선한 방법이다.

• 가장 높은 값과 가장 낮은 값을 통해 인덱스를 보간한다.

• 데이터가 균등하게 분포되어 있는 자료에 사용하기 적합하다.

  data : 데이터의 집합
  low : 가장 낮은 인덱스
  high : 가장 높은 인덱스
  mid : 비교할 값의 인덱스

  mid = low + (high - low) * (value - data[low]) / (data[high] - data[low]) 

  

참고

• https://jackpot53.tistory.com/35