Chap.0 UI(User Interface, I/O)와 알고리듬

Programming/Coding

Problem/Work

Solution

Libraries (이미 만든 함수들 제공)

e.g. standard I/O: scanf(), printf(), ...

curses I/O: scanw(), printw(), ...

math: sin(), cos(), ...

SW

HW

Flow Chart

Input Data (Structure)

Output Data (Structure)

Local Data (Structure)

Algorithm

(Processing)

"Program"

User

Interface

ex) Android App programming

UI (*.xml)                        process (*.java)

Data(numbers/character/string/multimedia)

Data Structure(linked list/stack/

table/tree/graph)

UI (User Interface)

- Input/Output data inside the computer for humans

Algorithm

UI (I/O)

- http://ko.wikipedia.org/wiki/단말기 (terminal): TUI와 GUI

• Text-based Screen

- http://ko.wikipedia.org/wiki/텍스트 사용자 인터페이스 (TUI)

e.g., http://en.wikipedia.org/wiki/VT100

http://en.wikipedia.org/wiki/Televideo

• Graphic Window

- http://ko.wikipedia.org/wiki/그래픽 사용자 인터페이스 (GUI)

e.g., http://ko.wikipedia.org/wiki/매킨토시

http://ko.wikipedia.org/wiki/마이크로소프트 윈도

http://ko.wikipedia.org/wiki/X 윈도 시스템

UI Library

• MS-DOS

- http://en.wikipedia.org/wiki/Conio.h

• ‘curses’ library

- Text User Interface 지원

- 출력창(screen)의 크기와 위치: 세로(y): 24줄 * 가로(x):80자

(0,0)                  (0,79)

좌표: (y, x)

(23,0)                (23,79)

• p.104: 3-1-1.c

#include <curses.h>

int main(void)

{

int i;

initscr();

move(0, 0);   printw("A");	printf("\a"); // beep 소리 출력

refresh();	sleep(5);

move(0, 79);  printw("B");	printf("\a");

refresh();	sleep(5);

move(23, 0);  printw("C");	printf("\a");

refresh();	sleep(5);

move(23, 79); printw("D");	printf("\a");

refresh();	sleep(5);

endwin();

return 0;

}

-  $ /sbin/ifconfig	// 자신의 IP address

$ telnet ********.knue.ac.kr	// 원격 server 사용

(ID: test PW: *****test)

$ ftp ********.knue.ac.kr	// 원격 server와 file 송신(put)/수신(get)

- compile시 사용자가 curses library를 링크하여 줌

e.g. $cc test.c -o test -lcurses

• Unix/Linux ‘curses’ library

http://en.wikipedia.org/wiki/Curses_(programming_library)

http://heather.cs.ucdavis.edu/~matloff/UnixAndC/CLanguage/Curses.pdf

e.g., http://ko.wikipedia.org/wiki/Dialog (셸스크립트)

http://ko.wikipedia.org/wiki/MySQL

http://blog.naver.com/neutrino37/110009868351

• p.105: 3-1-2.c

#include <curses.h>

int main(void)

{

int i;

initscr();

for(i=1;i<=9;i++){

move(5+i,15);

printw("%d * %d = %2d",3,i,3*i);

}

refresh();

sleep(5);	// 5 secs...

endwin();

return 0;

}

- initscr() 함수: 모든 curses 함수에 앞서 수행시키며, 이 루틴은 curses의 자료구조를 초기화하고 UNIX 환경의 TERM 변수를 통하여 단말기의 종류를 결정. (VT100)

- printw() 함수: 표준 window인 stdscr에 출력 (buffer)

- refresh()함수: window인 stdscr의 내용을 실제 화면(physical screen)에 출력

- endwin() 함수: curses mode를 종료.

• p.106: 3-1-3.c

#include <curses.h>

int main(void)

{

int i;

initscr();

for(i=1;i<=9;i++){

move(5+i,15);

printw("%d * %d = %2d",3,i,3*i);

}

refresh();

sleep(3);

clear();

mvaddstr(5,15,"Screen is cleared...\n");

refresh();

sleep(3);

endwin();

return 0;

}

- erase()/clear() 함수: 표준 윈도우 stdscr 의 모든 위치에 공백(space)을 쓴다.

- mvaddstr(): move/add/string

• p.115: 3-2-3.c

#include <curses.h>

int main(void)

{

int ch, x=10, y=10;

WINDOW *win;

initscr();	// curses call to initialize window

cbreak();	// curses call to set no waiting for 'Enter' key

keypad(stdscr, TRUE);

mvaddstr(0,0,"Use KEY_LEFT/KEY_RIGHT/KEY_UP/KEY_DOWN...\n");

refresh();

win=newwin(1, 1, y, x);

waddch(win, '*');

while((ch = getch()) != 'q'){

switch(ch){

case KEY_LEFT:

mvwin(win, y, --x);

break;

case KEY_RIGHT:

mvwin(win, y, ++x);

break;

case KEY_UP:

mvwin(win, --y, x);

break;

case KEY_DOWN:

mvwin(win, ++y, x);

break;

default:

break;

}

wrefresh(win);

}

delwin(win);

endwin();

return 0;

}

- cbreak() 함수: Enable CBREAK mode - 입력시, 인터럽트(interrupt)와 흐름 제어 키(flow control key)를 제외하고는 입력자료에 어떠한 작용도 가하지 않는다.  e.g. cntl + c : interrupt

- keypad() 함수: TRUE - 기능(function) 키 입력 가능

- newwin() 함수: 새로운 윈도우 win 을 만든다.

win = newwin(lines, cols, startline, startcol);

세로 크기가 lines, 가로 크기가 cols 인 윈도우 생성

- wrefresh(win); 윈도우 win에 있는 내용들이 실제 화면(screen)에 나타난다.

• Example #1: ex1.c

// simple curses example; keeps drawing the inputted characters, in columns

// downward, shifting rightward when the last row is reached, and

// wrapping around when the rightmost column is reached

#include <curses.h> // required

int r,c,	// current row and column (upper-left is (0,0))

nrows,	// number of rows in window

ncols;	// number of columns in window

void draw(char dc)

{

move(r,c);	// curses call to move cursor to row r, column c

delch(); insch(dc); // curses call to replace character under cursor by dc

refresh();	// curses call to update screen

r++;	// go to next row

// check for need to shift right or wrap around

if (r == nrows) {

r = 0;

c++;	// go to next column

if (c == ncols) c = 0;

}

}

main()

{

int i; char d;

WINDOW *wnd;

wnd = initscr();	// curses call to initialize window

cbreak();	// curses call to set no waiting for Enter key

noecho();	// curses call to set no echoing

getmaxyx(wnd,nrows,ncols); // curses call to find size of window

clear();	// curses call to clear screen, send cursor to position (0,0)

refresh();	// curses call to implement all changes since last refresh

r = 0; c = 0;

while (1) {

d = getch();	// curses call to input from keyboard

if (d == ’q’) break;	// quit?

draw(d);	// draw the character

}

endwin();	// curses call to restore the original window and leave

}

• p.135: 3-4-2.c (Menu 만들기)

#include <curses.h>

#include <stdio.h>

#include <stdlib.h>

#define X    7

#define Y    2

int main()

{   char d;

initscr();

if(!has_colors())	// get the color info

fprintf(stderr, "Error - no color support on this terminal\r\n");

if(start_color() != OK)

fprintf(stderr, "Error - could not initialize\n");

clear();

// print color text

init_pair(1, COLOR_GREEN, COLOR_BLACK);

init_pair(2, COLOR_CYAN, COLOR_BLACK);

init_pair(3, COLOR_WHITE, COLOR_BLACK);

init_pair(4, COLOR_YELLOW, COLOR_BLACK);

init_pair(5, COLOR_RED, COLOR_BLACK);

attrset(COLOR_PAIR(3) | A_BOLD);

mvprintw(Y,X,"++ C Programming Report #1 ++");

attrset(COLOR_PAIR(1) | A_BOLD);

mvprintw(Y+1,X,"Coffee Machine v 1.00");

attrset(COLOR_PAIR(2) | A_BOLD);

printw("  Made by Group #1");

attrset(COLOR_PAIR(5) | A_BOLD);

mvprintw(Y+3,X,"[Caution]");

attrset(COLOR_PAIR(3) | A_BOLD);

mvprintw(Y+4,X,"    1. 동전을 넣으십시오.");

mvprintw(Y+5,X,"    2. 블랙/설탕/밀크가 있습니다.");

mvprintw(Y+6,X,"    3. 취소가 가능합니다.");

attrset(COLOR_PAIR(5) | A_BOLD);

mvprintw(Y+8,X,"Press 'q' to Quit");

while (1) {

d = getch();	// curses call to input from keyboard

if (d == ’q’) break;	// quit?

refresh();	// draw the character

}

endwin();

return 0;

}

• p.140: 3-5-2.c

#include <curses.h>

int main() {

int ch;

int coord_x = 10, coord_y = 10;

WINDOW *win;

initscr();

cbreak();

keypad(stdscr, TRUE);

mvaddstr(0,0,"Use KEY_LEFT/KEY_RIGHT/KEY_UP/KEY_DOWN...\n");

refresh();

win = newwin(5, 10, coord_y, coord_x);

waddch(win, '#');

while ((ch = getch()) != 'q') {

wborder(win, ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ');

wrefresh(win);

switch(ch) {

case KEY_LEFT:

mvwin(win, coord_y, --coord_x);

break;

case KEY_RIGHT:

mvwin(win, coord_y, ++coord_x);

break;

case KEY_UP:

mvwin(win, --coord_y, coord_x);

break;

case KEY_DOWN:

mvwin(win, ++coord_y, coord_x);

break;

}

box(win, 0, 0);

wrefresh(win);

}

delwin(win);

endwin();

return 0;

}

- wborder() 함수를 이용하여 기존 보더를 초기화

- box() 함수: 윈도우에 외곽선을 그림 (윈도우는 외각선을 1씩 차지하기 때문에, 5행 10열의 윈도우의 내부는 3행 8열이 됨)

Algorithm

• Algorithm: 데이터 처리(process)의 방법/순서 제시

- Algorithm: 연산들의 순서적인 집합

- 특징: 이산성, 정확성, 효율성, 끝나야함, 한계성

• 대표적인 Algorithm들

- Sorting and Searching

- Graph algorithms by Robert. E. Tarjan, Edsger W. Dijkstra 등

⇒ shortest-path, minimum spanning tree, bipartite graph, planar graph, etc...

- String match algorithms: Donald E. Knuth

• Techniques

- 순차(sequential)

- 순환(recursion): ex) the Tower of Hanoi(하노이의 탑)

- divide-and-conquer

- Turing machine: algorithm 수행 기계 by Alan Turing

- NP-completeness: Stephen Cook, Leonid Levin

- A. I.: heuristics, expert system, John McCarthy

- distributed algorithms: Leslie Lamport

- parallel algorithms

- genetic algorithms

• Project Euler: HW #1

http://projecteuler.net

• 순서도(flow chart):

http://comedudb6.knue.ac.kr/tykim/Myhome/Cnote/FlowChart.pdf

e.g., 피보나치 수열

yes

no

yes

no

시 작

i=0

n 입력

first=0; second=1

i<n

i<=1

next=first+second;

first=second;

second=next;

i=i+1;

next=i;

print i+1, next

끝

• 두 정수의 최대공약수 문제

▸problem #1: 최대공약수 (http://blog.daum.net/kim2yj/1585)

최대공약수의 활용

최대공약수는 비단 일상생활에서만 사용되는 것은 아니다. 다양한 과학적인 상황에서도 폭넓게 사용되고 있다. 예를 들어, 1923년 기본 전하와 광전효과에 대한 연구로 노벨 물리학상을 받은 로버트 밀리컨(Robert Millikan, 1868~1953)은 가장 작은 전하량인 기본 전하량 e의 크기를 구하기 위해 실시한 기름방울시험에서 최대공약수를 활용하였다.

밀리컨은 이 실험에서 중력에 의해 내려가는 기름방울의 힘과 두 금속 전극 사이에 정지되어 있는 작은 기름방울에 작용하는 힘 사이의 균형 상태를 측정하였다. 이러한 수백 번의 실험 끝에 기름방울에 있는 전하량의 크기들을 구하였다. 그런데, 모든 전하량의 크기는 전자가 가지는 기본 전하량(e)의 정수배가 되어야 한다는 사실로부터, 기본 전하량 e를 기름방울실험에서 얻은 전하량들의 최대공약수를 통해 얻는데 성공하였다.

▸problem #2:

http://www.ebsmath.co.kr/resource/rcsView?cate=10094&cate2=10101&cate3=10115&rscTpDscd=RTP10&grdCd=MGRD01&sortType=B&sno=20411&itemSize=12

(http://blog.daum.net/kim2yj/1585)

▸Algorithm: 이 문제를 컴퓨터로 풀 수 있을까? - 기계적 계산

두 정수의 최대공약수

http://en.wikipedia.org/wiki/Greatest_common_divisor

http://en.wikipedia.org/wiki/Euclidean_algorithm

1) Algorithm #1:

GCD(a, a)=a

GCD(a, b)=GCD(a-b, b)	, if a>b

GCD(a, b)=GCD(a, b-a)	, if b>a

(from 서울, 초등)

즉, 유클리드 호제법은 “두 정수 m,n(m>n)이 있을 때, m과 n의 최대공약수는 m-n과 n의 최대공약수와 같다”라는 명제를 기초로 한다.

이를 알고리즘으로 정리하면

가) m과 n이 같지 않으면 다음을 반복한다.

나) m>n이면 m=m-n, 그렇지 않으면 n=n-m

다) m과 n이 같다면 m(또는 n)이 구하고자 하는 최대공약수이다.

예) m=24, n=18

m         n

24         18

24-18=6         18

6       18-6=12

6        12-6=6

GCD = 6

The algorithm proceeds by successive subtractions in two loops:

IF the test B ≥ A yields "yes" (or true) (more accurately the number b in location B is greater than or equal to the number a in location A)

THEN the algorithm specifies B ← B − A (meaning the number b − a replaces the old b).

Similarly IF A > B THEN A ← A − B.

The process terminates when (the contents of) B is 0, yielding the g.c.d. in A.

2) Algorithm #2:

GCD(a, 0)=a

GCD(a, b)=GCD(b, a mod b)	, where a mod b=a를 b로 나눈 나머지값

e.g.,	GCD(34398, 2132)=GCD(2132, 286)

GCD(2132, 286)=GCD(286, 130)

GCD(286, 130)=GCD(130, 26)

GCD(130, 26)=GCD(26, 0)

GCD=26

(from 서울, 중등 기초)

유클리드 알고리즘은 최대공약수에 관한 아래 결과와 나눗셈 알고리즘을 바탕으로 한다.

[보조정리]

a, b, q, r이 정수일 때 a=bq+r이라 하자. 그러면 gcd(a,b) = gcd(b,r)

유클리드 알고리즘은 최대공약수(gcd)를 찾는데 아주 효율적인 방법이다. 유클리드 알고리즘을 설명하기 전에, gcd(91,287)을 찾는데 이 알고리즘이 어떻게 사용되는지를 보인다.

먼저, 두 정수 중 큰 수인 287을 작은 수 91로 나누어 287=91․ 3+14를 얻는다. 91과 287의 어떤 약수이든지 287-91․ 3=14의 약수임에 틀림없다. 또, 91과 14의 어떤 약수이든지 287=91․ 3+14의 약수임에 틀림없다. 그래서 91과 287의 최대공약수는 91과 14의 최대공약수다. 이것은 gcd(91,287)을 찾는 문제는 gcd(91,14)를 찾는 문제로 축소됨을 의미한다. 다음으로 91을 14로 나누어 91=14 ․ 6+7을 얻는다. 91과 14의 공약수는 역시 91-14 ․ 6=7을 나누고 14와 7의 공약수는 91을 나눈다. 그래서 gcd(91,14)= gcd(14,7)이다.

계속하여 14를 7로 나누어 14=7 ․ 2를 얻는다. 7이 14를 나누므로 gcd(14,7)=7이다. 더욱이, gcd(287,91)=gcd(91,14)=gcd(14,7)=7이므로 원래의 문제가 풀린다.

유클리드 알고리즘의 작동은 최대공약수를 구할 때, 두 양의 정수의 최대공약수를 찾는 문제를 보다 작은 정수들의 문제로 축소하기 위해 나눗셈을 어느 한쪽이 0이 될 때까지 연속적으로 행한다.

▸Program #1 (C program)

// file I/O 사용...

#include<stdio.h>

void main()

{

FILE *inf, *outf;

int m,n;

inf=fopen("d:/temp/input.txt","r");

outf=fopen("d:/temp/output.txt","w");

fscanf(inf,"%d%d",&m,&n);

while(m!=n)

{

if(m>n)

m=m-n;

else

n=n-m;

}

fprintf(outf,"%d",m);

fclose(inf);

fclose(outf);

}

▸Program #2 (Android App)

https://play.google.com/store/apps/details?id=com.scapelitte.lcmgcdfinder&hl=ko

▸Program #3 (HTML5 Web App)

http://comedudb6.knue.ac.kr/tykim/Myhome/CAInote/GCD/gcd.html