프로그래밍 및 잡담

 - 그래프란 정점(Vertex, 또는 Node)과 간선(Edge)으로 이루어진 자료구조이다. 네트워크 망이나 전철 노선도를 떠올리면 된다.

 - 유향 그래프와 무향 그래프가 있다. 유향 그래프는 간선에 방향이 있어서 간선의 방향으로만  갈수 있는 그래프이고, 무향 그래프는 간선에 방향이 없어서 양방향으로 갈수 있는 그래프이다.

 - 그래프 관련 알고리즘으로는 DFS(Depth First Search, 깊이 우선 탐색), BFS(Breadth First Search, 너비 우선 탐색), 다익스트라(Dijkstra) 알고리즘 등이 있다.

- DFS는 깊이 우선 탐색으로, 일단 간선을 따라서 방문하지 않은 정점을 방문한다. 방문할 이웃이 없으면, 다시 뒤로 돌아가서 다른 이웃 정점을 같은 방식으로 방문한다. 일단 깊게 들어간 뒤에 다시 나와서 탐색하기 때문에 깊이 우선 탐색이라고 한다.

 - BFS는 너비 우선 탐색으로, 일단 자기 주변에 방문할수 있는 정점을 모두 방문한다. 그 다음 방문한 정점을 하나 선택해서 다시 그 정점에서 방문할수 있는 정점을 방문한다. 깊게 들어가지 않고 한 단계씩 탐색하기 때문에 너비 우선 탐색이라고 한다.

 - 다익스트라(Dijkstra) 알고리즘은 한 정점에서 다른 정점으로 가기 위한 최소 비용(또는 거리)을 구하는 알고리즘이다. 알고리즘의 동작을 간략히 설명하자면

1. 시작 정점의 거리를 0으로 초기화 하고, 시작 정점부터 나머지 정점까지의 거리를 무한(적당히 큰 값)으로 설정한다.

2. 방문하지 않은 정점 중 최소 거리인 정점을 선택한다. (A 정점이라고 하자)

3. A 정점을 방문한 정보를 기록한다.

4. 선택된 정점에서 방문할수 있는 정점 (B 정점이라고 하자) 의 거리를 계산해서, A 정점을 거쳐서 가는게 더 가까울 경우에, B 정점의 거리를 갱신한다.

( 즉, '시작 정점 -> B의 거리' > '시작 정점 -> A의 거리 + A -> B의 거리'일 경우, B 정점의 거리를 '시작 정점 -> A의 거리 + A -> B의 거리'로 갱신한다.)

5. 모든 정점을 방문할 때까지 2, 3 과정을 반복한다.

말로 하니 좀 복잡해 보일수 있는데, 코드는 무척 단순하다.

 - 이제 위에서 설명한 알고리즘을 파이썬으로 구현한 코드를 공개하겠다.

 - 데이터 표현 방식

(그래프 이미지 참고 주소)

- DFS

- BFS

- Dijkstra

- 전체 코드

간단한 매크로 프로그램을 만드는 중,
바탕화면을 캡처해서 처리해야 하는 일이 필요했다.

 맨 처음에는 pillow 라이브러리에 있는 ImageGrab이나 pyscreenshot을 사용했다.
하지만, 내가 하고 싶은 일을 처리하는 시간보다, 바탕화면을 가져오는 데
더 많은 시간이 들어서 프로그램이 비효율적이였다.

 더 좋은 방법이 없나 찾아 보다가, wx를 알게 되었다.
원래 wx는 C++에서 시작된 GUI 프로그램 개발 라이브러리이다.
기능중에 바탕화면 정보를 가져오는 함수가 있어서 써 보니,
월등히 빠른 속도로 캡처를 해서 프로그램이 훨씬 빨라졌다.

 단, pillow 함수를 이용해서 wx가 캡처한 이미지를 픽셀 단위로 처리하려 할 때,
이미지 확장자명이 png면 오류가 발생했다. 이 문제의 원인은 잘 모르겠지만,
wx에서 이미지를 저장할 때 bmp으로 저장하면 에러가 발생하지 않는다.

아래는 참고 코드이다.

import time
import pyscreenshot as ImageGrab
import wx
from PIL import Image


def main():
    count = 10
  
    start = time.time()
    for i in xrange(count):
        im = ImageGrab.grab(bbox=(0, 0, 100, 100))
        im.save('ImageGrab.png')
      
    print time.time() - start

    start = time.time()
    app = wx.App()
    screen = wx.ScreenDC()
    for i in xrange(count):
        bmp = wx.EmptyBitmap(100, 100)
        mem = wx.MemoryDC(bmp)
        mem.Blit(0, 0, 100, 100, screen, 0, 0)
        del mem
        bmp.SaveFile('wx.bmp', wx.BITMAP_TYPE_BMP)
      
    print time.time() - start


if __name__ == '__main__':
    main()


각각 모니터에서 0, 0에서 100, 100 부분을 캡처한 뒤 파일로 저장하는 과정을
10번 반복한다.

아래는 실행 결과이다.

17.631000042
0.203000068665

내 컴퓨터 환경에서 wx 는 pyscreenshot 보다 대략 80배 정도 빠르다.
빠른 캡처가 필요하다면, wx를 사용하는게 좋을 것이다.

wx 설지 url:

https://wxpython.org/download.php

GPIO(General Purpose Input Output - 범용입출력)

센서에 따라서 브레드 보드(일명 빵판)이 필요할 수도 있다.

가장 기본적인 센서 사용법은 센서에 5V 전압과 GND를 연결한 뒤,

데이터를 전송하기 위해 적당한 번호에 선을 연결하면 된다.

(위에서는 #4, #17, #18... 등)

라즈베리파이에서 python의 RPi.GPIO 모듈을 이용하여 GPIO를 사용할 수 있다.

python 코드

# -*- coding: utf8 -*-

from RPi.GPIO as GPIO

GPIO.setmode(GPIO.BCM)

GPIO.setup(4, GPIO.IN, pull_up_down=GPIO.PUB_UP)

print GPIO.input(4)

위의 예제는 #4로 부터 정보를 읽어들여서 출력하는 예제이다.

어떤 센서를 연결했느냐에 따라 온도 값이나 화재 상황등

다양한 정보를 입력 받아서 처리할 수 있다.

내가 프로그래밍을 하는 방식으로, 좋은 방법인지는 모르겠지만 이 방식이 현재의 나에게
맞는것 같아서 써본다.

1. 일단 먼저 만들것을 정한다(테트리스 던 원카드 던 전화번호 관리프로그램 등...).
  -원카드를 예를 들어서 설명하겠다.

2. 그 후 그 프로그램이 완성된 모습을 대충 머릿속에 그린다(80% 정도는 그려져야 함).
 -원카드를 하는 모습을 상상해 본다.

3. 프로그램에서 필요한 부품들을 작게 나눈다.
 -일단은 트럼프 카드가 필요하고, 원카드를 할 사람이 필요하다.

4. 부품들의 속성을 파악해서 자료형으로 간단하게 나타낸다.
 -트럼프 카드는 모양과 숫자가 있으니 카드 하나에는 2가지 정보를 담기 위한 변수 2개가 필요하다.
 -사람은 이름과 갖고있는 카드 숫자, 가지고 있는 카드 등의 정보가 필요하니 3개의 변수가 필요하다.

5. 그 부품들이 할 행동들을 함수로 만든다.
 -카드를 대상으로 할 행동들은 카드를 섞고, 카드를 한장 뽑는 행위 등이 있다.
 -사람이 할 행동을 낼 카드가 있으면 내고, 아니면 카드 한장(혹은 그 이상)을 받는 행위가 있다.
 -그 외 낸 카드에 따라서 다음에 낼 카드가 정해지는 등 낼 수 있는 카드의 제한이 필요하다.

6. 위에서 정리한 내용을 바탕으로 자료형을 구성하고, 함수들을 구성해서 메인 함수(반드시 main함수를 일컫는 것은 아니고, 다른 이름의 함수도 게임을 진행시키는 메인 함수가 될 수 있다.)에서 변수를 생성하고, 내가 생각한 순서 대로(2번 단계에서 생각한 순서) 함수를 호출하고 제어문등을 사용해서 게임의 흐름을 제어한다.

7. 6번 과정을 진행하면서 자료형에서 부족한 점이라거나, 필요한 함수가 있으면 추가하거나 수정하면서 프로그래밍을 진행해 간다.

8. 최초로 생각한 모습대로 완성되면 그것이 프로토 타입이라고 할 수있다. 제작 날짜는 프로토 타입이 제작된 날짜를 기준으로 한다.

9. 그 뒤 내가 플레이 하면서 발견한 오류등을 수정하거나 게임 내용을 변경하면서 게임을 수정해 나간다. 그리고 수정한 내용과 날짜를 소스코드에 적어서 수정되는 과정을 알 수 있도록 한다.

이상이 내가 프로그램을 개발하는 과정이다. 머릿속에만 있는 지식을 글로 쓰려니 꽤 힘들었다. 다른 사람에게 도움이 될지는 모르겠다. 아무튼 프로그래밍을 시작한뒤 얼마 안된 사람이나 많은 프로그램을 작성해본 사람이 아니라면 내 방식을 참고하는것도 좋을 것이다.