공룡호가 사는 세상 이야기

7 by 7 크기의 정사각형 모양의 지도가 있다.
지도에서 0은 집 없음, 1은 집 있음을 나타낸다.
단지란 왼쪽, 오른쪽, 위쪽, 아래쪽으로 연결되어 있는 집들의 집합이다.
예를 들어, 다음 지도에서는 세 개의 단지가 있다.


각 단지의 크기는 7, 8, 9이다. 입력 데이터가 주어지면,
단지의 개수와 각 단지의 크기를 출력하는 프로그램을 작성하시오.

<입력 예>
0 1 1 0 1 0 0
0 1 1 0 1 0 1
1 1 1 0 1 0 1
0 0 0 0 1 1 1
0 1 0 0 0 0 0
0 1 1 1 1 1 0
0 1 1 1 0 0 0

<출력 예>
3
7 8 9

Explanation :
#include <stdio.h>
#define n 7 //가로세로 크기
int apt[n][n] = {{0, 1, 1, 0, 1, 0, 0}, {0, 1, 1, 0, 1, 0, 1}, {1, 1, 1, 0, 1, 0, 1},//단지입력
{0, 0, 0, 0, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1, 0}, {0, 1, 1, 1, 0, 0, 0}};

int danji_num = 10; //단지번호(1단지는 11, 2단지는 12)
int cnt; //단지당 세대수

void cell_del(int x, int y) //찾은 세대는 지움(중복계산 방지)
{
apt[x][y] = danji_num;//단지 번호를 붙여 버린다. 1단지면 11, 2단지면 12...
}

int get(int x, int y) //해당 좌표값을 가져옴
{
if(x<0 || y<0 || x>=n || y>=n)
return 99; //0과 1이 아닌 아무숫자나 리턴(에러처리)
return apt[x][y]; //배열값을 다시 리턴(해당 좌표값을 가져온다)
}

void cell_cnt(int x, int y) //단지당 세대수 카운트
{
cell_del(x, y); //단지 삭제함수 호출

if(get(x, y-1) == 1) //상하좌우 검색(재귀)
{//좌
cnt++;
cell_cnt(x, y-1);
}

if(get(x, y+1) == 1)
{//우
cnt++;
cell_cnt(x, y+1);
}

if(get(x+1, y) == 1)
{//하
cnt++;
cell_cnt(x+1, y);
}

if(get(x-1, y) == 1)
{//상
cnt++;
cell_cnt(x-1, y);
}
}

void print(int *danji_cnt)
{//출력
printf("%d\n", danji_num-10);

for(int i=0; i<(danji_num-10); i++)
printf("\n%d ",danji_cnt[i]);
}

void main(void)
{
int danji_cnt[100]={0};

for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(apt[i][j] == 1) //세대가 있으면
{
danji_num++; //1단지는 11, 2단지는 12
cnt = 1; //이미 세대를 하나 찾았으므로 세대수 초기값은 1
cell_cnt(i,j); //단지내의 세대수를 카운트
danji_cnt[danji_num-11]=cnt;
}
}
}

print(danji_cnt); //결과출력
}

원래 문제는 file에서 읽어, file로 출력해야 하는데, 귀찮아서 빼버렸다.
이 프로그램의 핵심은 배열을 순서대로 카운트 하면서,
1과 0을 판별해 내고 1일때 또다시 현재 위치에서 상,하,좌,우에 단지가 있는지 검색하고, 있다면 이동하고, 이동한 위치에서 또다시 검색하는 것이 핵심이다.

예를들어 1을 찾아서 우측으로 이동 했다면, 이동한 자리를 기준으로 또다시 상,하,좌,우를 검색해야 하므로, 문제의 핵심은 재귀에 있다.

루프가 돌아가는 동안 읽었던 값에 표시를 해 둠으로써 다시 읽어버리는 오류를 미리 제거해 주며,
또한 루프를 빠져나왔다가 다시 들어갈때는 표시값을 변경함으로써,
표시값을 배열첨자로 사용하는 배열의 값이 달라지므로,

각 아파트 단지의 수는 그 배열의 전체크기가 되며,
각 단지의 세대수는 그 배열의 값이 되는 것이다.

진태형에게 재귀가 약하다고, 알고리즘 문제를 하나 부탁했더니 '하노이 탑'을 해보란다. 그 문제는 재귀 중에도 어려운 재귀에 속하고, 소스를 이미 봐 버려서 안된다고 했더니, 이 문제를 하나 내준다.

ACM에 출제된 문제를 변형한 거라며, 풀어보란다.
문제를 다 풀고, 원래 문제를 찾아 봤더니 별로 바뀐게 없다.
그냥 내도 될 것을... 대체... 이걸 변형이라고 내 준건지. ㅋㅋㅋ
형 성의를 봐서, 문제와 소스를 첨부한다. 흐흐.-.-a

대 부분의 사람들은 비교적 작은 수의 로마 숫자와 친숙하다.
i, v, x, l, c는 각각 10진수 1, 5, 10, 50, 100을 나타낸다.


그외의 다른 값들을 앞의 기호들을 합한 숫자로 나타낸다고 하자.
예를 들면, 숫자 3은 i가 3개 모여서 만들어진 것이다. 73은 l이 1개, x가 2개, i가 3개로 이루어져 있다. 즉 가장 적은 로마숫자의 합으로 숫자를 표기할 수 있다고 한다.

입력
입력은 1에서 100사이의 정수들로 결정되며, 0을 제외한 각각의 정수는 각각의 다른 기호들이 몇 개씩 필요한지를 결정한다.

출력
입력으로 받은 각각의 정수에 대해 입력 받은 정수와 그에 따른 각각의 필요한 기호의 수를 한 줄에 출력한다.

입력 예제
1
2
22
87

출력예제
1 : i 1, v 0, x 0, l 0, c 0
2 : i 2, v 0, x 0, l 0, c 0
22 : i 2, v 0, x 2, l 0, c 0
87 : i 2, v 1, x 3, l 1, c 0

Explanation :
#include <stdio.h>
#include <stdlib.h>

int roma[5]={0};
int n;

int input(void)
{//입력
printf("A Number of Page : ");
scanf("%d",&n);
return n;
}

bool check(void)
{//입력에러 처리
if(n < 0 || n > 100)
return false;
else
return true;
}

void print(int *sn)
{//출력
printf("\n%d : i %d, v %d, x %d, l %d, c %d\n\n",
*sn, *(roma + 0), *(roma + 1), *(roma + 2), *(roma + 3), *(roma + 4));
}


void cal(int n)
{//계산 (개노가다 한다. 입력제한이 있으므로 상관없다)
if(n >= 100)
{
roma[4] = (n / 100);
n = n % 100;
cal(n);
}

if(n >= 50)
{
roma[3] = (n / 50);
n = n % 50;
cal(n);
}

if(n >= 10)
{
roma[2] = (n / 10);
n = n % 10;
cal(n);
}

if(n >= 5)
{
roma[1] = (n / 5);
n = n % 5;
cal(n);
}

if(n > 0 && n < 5)
{
roma[0] = (n / 1);
n = n % 1;
cal(n);
}
if(n == 0)
{
return;
}
}

void main(void)
{
int sn = input();

if(check()==false)
exit(1);

cal(n);

print(&sn);
}

한 여름의 뜨거운 태양빛 아래에 종이를 하루 종일 놓아 두어도 종이는 불타오르지 않는다.
반면에 볼록렌즈를 이용해서 태양빛을 모으면 단 1분이 못 되어서 종이에 불이 붙고, 이내 종이 전체를 태워 버린다.

이 때 처음에 종이에 불을 붙이는 행위가 중요하다. 그런데 종이에 불을 붙이려면 태양빛을 볼록렌즈로 집중해야 한다.
이와 마찬가지로 실력을 증진시키기 위한 원리도 집중에 있다.

종이의 일부분이 일단 타면 나머지는 자연스럽게 타 버리듯이, 학습 또한 초점의 원리에 기초를 두고 있다.

초기에 무리하지 말라.
자신의 힘으로 깨뜨릴 수 있는 만큼의 분량만으로 시작하라.
이것이 핵짐적인 원칙이다.

촛불을 켤 수 있는 사람은 횃불을 켤 수 있고, 횟불을 켤 수 있는 사람은 봉화불을 켤 수 있다.

촛불을 켜는 것부터 시작하라.

한가지 덧붙이자면,
'진정한 고수는 말을 하지 않는다. 코드로 모든 것을 말한다.'

박진수 '프로그래밍 마인드'

프로그램을 작성하다 보면, 문자를 입력한 뒤에 개행문자를 입력하지 않고 자동으로 입력스트림에 있는 문자를 해당 변수로 가져갈 수 있는 방법이 궁금해진다.
getch() 를 사용하면 해결할 수 있는데, getch()는 리턴형이 int형이므로, 정수형을 리턴한다. getch는 문자를 받는 함수이므로 숫자를 입력하여도 문자로 인식한다.
그래서 '1'을 입력하면 정수형 '1'이 아닌 문자로 인식하고 정수로 변환, '49'를 리턴한다.

결국 리턴값이 중요한 것이 아니다.
예를 들어, int a = getch();를 하여 '1'을 입력했다면
a=49가 되는데, 메모리에 있는 값이 변하는 것이 아니다.
모든 것은 맞닿아 있으므로 형변환 등을 통해 입맛대로 간쳐서 드시면 될 터이다.

응용-> getch()를 사용하여 콘솔에서 암호를 입력받는 함수

int getpass(char * buffer, int buf_size)
{
int count = 0;
int c = 0;
while(1)
{
c = getch();
buffer[count] = (char)c;
count++;
if(c==13) //enter
break;
printf("*"); //password
if(count == buf_size-1)
break;
}
buffer[count]='\0';
printf("\n");
}

getch()라는 함수를 이용하면 키보드로 입력하는 것은 화면에 나오지 않는다는 점에 착안.
13이라는 숫자는 엔터키를 의미한다.
암호를 입력하고 나서 엔터를 치거나, 입력한 문자의 개수가 (버퍼크기-1)개일 경우는
입력을 종료한다.

cf) getch() function Declared in 'conio.h' or 'curses.h'

'프로그래밍' 카테고리의 다른 글

아파트 단지 번호 붙이기  (0) 2006.01.07
ACM 로마숫자 문제 변형판  (0) 2006.01.07
초점의 원리  (0) 2006.01.06
Simple Linked List, head와 tail의 연결과 메모리 누수  (0) 2005.12.30
객체지향의 철학  (0) 2004.11.21

<오류 소스코드>
#include
using namespace std;

class node
{
public:
int data;
node *next;
};

node head;
node tail;


void init_list(void)
{
*head = new node;
*tail = new node;

head->next = tail;
}

node* find_node(int key)
{
node *s;
s = head->next;
.
.
.
}

key값과 포인터를 갖는 구조체나 클래스를 정의한 다음,
node head, tail; 로 객체를 생성한다.

객체를 생성한 다음 초기화 하는 함수에서
접근이 가능하도록 포인터를 설정하고, new연산자로 공간을 할당한다.

하지만 저렇게 하였을 경우에는 심각한 에러를 발생시킨다.
다시 소스를 차근차근히 살펴보면, find_node 함수나 기타 함수 또는 어디서든 head나 tail에 접근할 수 없다.

이를테면 head에 접근하기 위해서는 *head로 접근을 시도해야 하는데, 해당 포인터를 init_list()함수 내에서 선언 해 버렸기 때문에, 함수가 종료되는 동시에 사라진다.(포인터변수 또한 변수임은 마찬가지)

그리하여, 다른 곳에서 head와 tail에 접근할 수 없을 뿐더러, 더욱 심각한 문제는 init_list()함수에서 선언했던 포인터변수는 사라지지만 new연산자로 할당한 2개의 공간(node)은 그대로 메모리를 차지한채 접근할 수 없는 상태로 허공을 떠돌게 된다.(메모리 누수)

그러므로 메모리할당은 함수 안에서 하되, head와 tail의 포인터 변수는 전역으로 설정해 주어야 한다.

node *head, *tail; // 전역

void init_list(void)
{
head = new node; // 함수가 종료되어도 사라지지 않는다.
tail = new node;
}

그리고 또한가지 그냥 지나칠 수 없는 점은
head와 tail의 연결 상태이다.원소가 아무것도 없는 리스트를 초기화 하고자 하여,
head->next = tail; 만 설정해 주게 되면 언뜻 아무 문제가 없어보인다.
하지만, while문 같은 루프의 내부에서 t=t->next;와 같은 문장이 있어서 계속 다음 노드로 이동하는 경우에 프로그래머의 실수로 루프를 끝내지 못할 경우 tail에 까지 이르게 되는데, 이 tail이 가르키는 곳을 정해주지 않아서 NULL이나 기타 엉뚱한 곳을 가르키고 있다면 t는 숨어버린다. 즉 다시 찾을 수 없다는 말이 된다.

이러한 결과는 결국 시스템이 다운을 가져온다. 대신에,
tail->next = tail; 이라는 한줄을 삽입하여, 꼬리 다음은 꼬리라고 순환적인 구조를 해 둘 경우 다운은 되지 않고 무한루프에 빠지게 된다.

무한루프는 Ctrl-Break로 멈출 수 있으며 디버그의 기능을 이용하여 현재의 상태를 점검해 볼 수 있다.
첨부파일 #1
첨부파일 #2

'프로그래밍' 카테고리의 다른 글

아파트 단지 번호 붙이기  (0) 2006.01.07
ACM 로마숫자 문제 변형판  (0) 2006.01.07
초점의 원리  (0) 2006.01.06
입력과 동시에 스트림에서 문자 가져오기 - getch();  (0) 2006.01.01
객체지향의 철학  (0) 2004.11.21

본제: 객체지향의 철학

[객체지향이란 무엇인가?]

객체지향 프로그래밍이란 말 그대로 '객체를 지향한다', 즉, 객체를 지향하는 스타일(Style)로 프로그램을 작성하는 것을 말한다.
여기서 '지향' 이란 것에 주목할 필요가 있다. '지향' 이란 말의 의미는 무엇인가? 지향은 '방향을 가리킨다' 라는 뜻인데, 이 글의 제목에서 '철학' 이란 말을 쓴 것도 지금 자세히 이야기 하려는 것과 깊은 관련이 있다. '철학' 이란 '생각하는 길' 을 의미하는데, 생각하는 길이라고 하는것은 어떤 실체적인 것을 의미하는것이 아닌, 그 사람의 논리적이고 합리적인 사고방식을 말하는 것이다.
그렇다면 다시 '객체지향의 철학' 은 무엇인가에 대해서 생각해 보면, 그것은 '객체를 방향으로 하여 생각하는 길' 이 되며, 단순하게 요약한다면 '객체중심으로 생각하기' 를 의미한다.
자, 이제 일차적인 결론이 나왔다. '객체지향' 이라고 하는것은 하나의 생각일 뿐이며 이것은 비관념적인 어떤것에도 종속되지 않는다. 생각은 완전한 관념의 세계인데, 이것을 외부로 표현하는 것이 흔히 말하는 '객체지향 프로그래밍' 이라고 하는것이다.

일반적으로 'OOP(Object Oriented Programming) 언어를 사용하는 것=OOP 를 하는것' 이라는 통념이 있는데, 이는 잘못된 생각이다. 그렇지만 대부분의 사람들은 'OOP 언어를 사용하는것=OOP 를 하는것(OOP 언어를 사용하는것->OOP 를 하는것, OOP 언어를 사용하는것<-OOP 를 하는것)' 이 옳지 않음을 알고 있는 경우가 많다. 그렇지만, 약간 다른 말로 'OOP 언어를 사용하지 않는것=OOP 를 하지 않는 것(OOP 언어를 사용하지 않는것->OOP 를 하지 않는 것, OOP 언어를 사용하지 않는것<-OOP 를 하지 않는 것)' 이라고 하였을 때, 이것이 틀리다는 것을 알고있는 사람은 그리 많지 않다. 잘 살펴보면 두개의 명제들은 각각 명제의 대우로 쌍을 이루고 있음을 알 수 있다. 즉, 그 명제는 자동적으로 옳지않은 명제가 되는것이다.
C 언어를 하더라도 객체지향을 한다고 할 수 있다. 'OOP 를 하지 않는것<-OOP 언어를 사용하지 않는것' 이 아니기 때문이다.

물론 여기서 언어가 사람에게 주는 영향을 완전히 무시한다는 것은 아니다. 두개의 것에 대해 '언어->사람' 인지 '사람->언어' 인지, 영향의 선후관계는 명확하지 않지만, 두 가지가 밀접한 관계를 가지고 있음은 누구도 부인할 수 없는 사실이다. 그러한 것에 입각하여 OOP 언어는 사용자의 사고방식을 객체지향이 아닌 언어보다 더 객체지향적으로 사고하게끔 해 준다.
C 를 할때 객체지향적인 생각을 하지 않는것은 아니지만, 그것을 표현하기 위해서 그것을 '표현하는 구조적 방법' 에 대해서 생각해야 하고, 그것이 그리 쉬운일이 아니라는 것은 누구나 알고있는 사실이다.
그러한 것에 대해서 C++ 는 C 보다 더 적합한 솔루션이 될 수 있다. 긍극적으로 C++ 는 C 에서 Object Oriented 적인 표현을 생각하지 않아도 된다는 표면적인 효과가 존재하고, 그것을 사용하는 사람의 사고를 더욱 '객체지향화' 해 준다는 내면적인 효과가 존재한다. (언어를 사용하는 사람은 그 언어와 직,간접적 영향을 주고 받는다는 것을 전제로 함)