문제 : 사전순으로 단어를 생성하여 N 번째 올 단어를 찾아라  

 


● 특정 문자열이 주어지고 이 문자열 안에 포함된 단어들을 사전순으로 정렬하라. 그리고 주어진 N 번째 오는 단어가 무엇인지 구하라.

단, 문자열의 최대 길이는 1,000 이고, 모두 소문자 알파벳으로만 되어 있다.

중복되는 단어는 한 단어로 생각한다. 

시간제한이 있다. (빠를 수록 점수가 높다, 1초가 넘으면 실패)


● 사전순이란 것은 알파벳 a ~ z 까지 단어를 정렬하는 것을 의미한다. 


● 예를 들어, melon 이란 문자열이 주어졌을 때, 7번째 오는 단어를 구하라. 

melon 안에 포함된 단어를 사전순으로 정렬하면 다음과 같다. 

1 : e

2 : el

3 : elo

4 : elon

5 : l

6 : lo

7 : lon

8 : m

9 : me

10 : mel

11 : melo

12 : melon

13 : n

14 : o

15 : on


즉, 답은 lon 이 된다. 



 

 일반적인 풀이  

 

● 풀이방법 1 : 위 문제와 같이 알파벳 a부터 문자열 안에 단어를 찾고, 그 뒤로 한글자씩 붙여서 단어를 만들어 나간다.

    

○ 문제점 :  주어진 문자열이 최대 1,000으로 길기 때문에 a가 몇번이고 반복될 수 있다. 예를 들어, a 부터 시작할 경우, 문자열 내의 모든 a 의 위치들을 기록하고, 그 뒤에 오는 단어들을 비교해서 순서를 만들어 나가야 한다. a가 세 번 반복된 경우, 각각의 단어의 뒷글자를 확인해서 순서를 정해야 한다. 위 문제의 예제와 같은 경우는 e가 한 번만 나오지만, e가 계속 반복되는 경우, 또 비슷한 알파벳이 많아지는 경우 문제가 복잡해진다. 


● 풀이방법 2 : 문자열의 첫글자부터 문자열을 만들어 나가면서 이 문자열을 이진 트리 형태로 저장하여 빠르게 정렬한다. 이를 통해 n 번째 아이템을 빨리 찾을 수 있다. 풀이방법 1의 반복적인 검색을 생략할 수 있다.

○ 문제점 : 모든 문자열을 다 만들어보아야 해서 메모리 문제가 있을 수 있다. C++이나 Java로 문제를 푸는 경우는 메모리 이슈를 피할 수 있지만 <STDIO.H> 만 허용된 C언어에서는 어려움이 있다. 트릭을 통해 malloc과 유사하게 푼다 하여도 속도 이슈가 발생할 수 있다. 실제로 C++로 이 문제를 푼 경우 제한 시간에 걸렸다. 



   답이 되는 풀이  
 

● 생각의 전환이 필요하다. 문자열로부터 시작하는 것이 아니라 사전 으로 부터 시작한다. 즉, a가 있는지 검색하고 있으면 다시 aa가 있는지 검색한다. 이 때, 문자열 전체를 보는 것이 아니라 a를 찾은 위치에서 그 바로 뒤에 문자와만 비교하면 된다. a를 찾은 위치의 인덱스를 활용한다. 


● 예를 들어, 주어진 문자열이 kdaabdgga 일 때, 

1) 우선 a 를 찾는다. 인덱스가 2에 a가 있음을 발견한다. 

2) 인덱스 2부터 aa가 있는지 확인한다. 인덱스 2에 aa가 있다.

3) 인덱스 2부터 aaa가 있는지 확인한다. 인덱스 2에는  aaa는 없다

3-1) 문자열 전체에서 aaa가 있는지 확인한다. aaa는 없다. 

4) 인덱스 2부터 aab가 있는지 확인한다. aab는 있다. 

5) 인덱스 2부터 aaba가 있는지 확인한다. 인덱스 2에는 aaba가 없다. 

5-1) 문자열 전체에서 aaba가 있는지 확인한다. aaba가 없다. 

6) aabc, aabd 등을 동일하게 확인한다. 


● 이 방식은 풀이방법 1과 비교할 때, 검색 횟수가 현저하게 줄어든다. 문자열이 랜덤하게 만들어진다는 가정하에 a는 여러번 나오겠지만, aa는 그 숫자가 적어질 것이고, aaa는 훨씬 적을 것이기 때문이다. 



   최상의 풀이  
 

● 답이 되는 풀이도 속도 문제는 있다. aaa가 있는지 확인을 첫번째 a의 인덱스 뒤로는 다 해야 하기 때문이다. 즉, 예를 들어, 주어진 문자열이 aac로 시가된다면, aab 가 있는지 aad가 있는지 문자열 전체를 검사하는 작업을 계속 반복하게 된다. 


● 이 검색 시간을 줄이기 위해서 각 알파벳에 대한 해시를 만들어 놓으면 검색 시간을 대폭 단축시킬 수 있다. 헤시 인덱스를 한단어로 만들어도 되고 두 단어로 만들어도 된다. 두 단어 이상으로 만들면 오히려 효율이 떨어질 것으로 예상된다. 주어진 문자열이 일정길이 이상일 때만 헤시 테이블을 만드는 작업을 수행하는 식으로 프로그램을 완성하면 효율적인 검색이 가능하다. 


● 헤시테이블은 간단한 이중배열로 만들 수 있다. int hash[26][10] 정도로 만들어서, 각각의 알파벳의 10번째 나오는데까지 위치만 미리 기억해놔도 문제가 쉬워진다. 워스트케이시를 대응하기 위해서는 int hash[26][1000] 이 되어야 하는데 이는 메모리 낭비가 심하다.  또는 int hash2[26*26][10] 으로 만들수도 있는데 - (aa ~ zz) 이 경우 해시를 만드는데는 시간이 더 걸리겠지만, 검색 속도는 월등히 빨라질 수 있다. 



   예제 코드  
 

● 추후 업데이트할 예정이다.








'Exercise & Quizz > C' 카테고리의 다른 글

사전 순으로 단어 정렬하기  (0) 2014.07.19
빙고 게임 - 연속되는 숫자 찾기  (0) 2012.06.11
Posted by 지그프리드 지그프리드

댓글을 달아주세요:: 네티켓은 기본, 스팸은 사절



※ 아 이건 문제가 좀 거지 같네요. Virtual 함수 쓰는 법 연습인 건 알겠지만, 문제 정의도 별로고... 실제 테스트 시나리오도 너무 부실하게 기술되어 있고... 좀더 문제가 이해하기 쉬웠으면 좋겠습니다. 

결국, 제 맘대로 해버렸다는... <iostream> 에서 cout으로 출력할 대, float 계산 결과의 소수점 맞추는 것도 마음에 안드네요. 이건 c의 stdio의 fprinf 같은 것 이용해야 깔끔합니다. 

● BankAcct.h
#ifndef __BACKACCT_H__
#define __BACKACCT_H__

#include <iostream>
#include <string>

class BankAcct
{
	protected:
		int money;

	public:
		BankAcct();
		~BankAcct();

		void deposit(int v_money);
		int withdraw(void);

		virtual float getInterest(void) = 0;
};
#endif




●BankAcct.cpp
#include "BankAcct.h"

BankAcct::BankAcct()
{
	/* do nothing */
}

BankAcct::~BankAcct()
{
	/* do nothing */
}

void BankAcct::deposit(int v_money)
{
	money += v_money;

	return;
}

int BankAcct::withdraw(void)
{
	float temp = money;

	money = 0;

	return temp;
}



●Accounts.h
#ifndef __ACCOUNTS_H__
#define __ACCOUNTS_H__

#include "BankAcct.h"

class SavingAcct:public BankAcct
{
	private:

	public:
		SavingAcct();
		~SavingAcct();
		virtual float getInterest(void);
};

class CheckingAcct:public BankAcct
{
	private:

	public:
		CheckingAcct();
		~CheckingAcct();
		float getInterest(void);
};
#endif



●Acounts.cpp
#include "Accounts.h"

SavingAcct::SavingAcct()
{
	money = 0;
}

SavingAcct::~SavingAcct()
{
	/* do nothing */
}

float SavingAcct::getInterest(void)
{
	return 0.09;
}

CheckingAcct::CheckingAcct()
{
	money = 0;
}

CheckingAcct::~CheckingAcct()
{
	/* do nothing */
}

float CheckingAcct::getInterest(void)
{
	/* do nothing */
	return 0.05;
}




●main.h
#include <iostream>
#include <iomanip>
#include <string>
#include "Accounts.h"

using namespace std;



●main.cpp
#include "main.h"

int main()
{
	float s_temp=0, c_temp = 0;

	/* Create acconts */
	SavingAcct S = SavingAcct();
	CheckingAcct C = CheckingAcct();

	/* Save some money */
	S.deposit(20000);
	C.deposit(15000);

	/* Calculate interest incomes */
	s_temp = S.withdraw() * S.getInterest();
	c_temp = C.withdraw() * C.getInterest();

	cout << "Saving Account Interest Incomes : expecting : " << setw(8) << setprecision(6) << s_temp << "\n";
	cout << "Checking Account Interest Incomes : expecting : " << setw(8) << setprecision(6) << c_temp << "\n";

	/* Save more money */
	S.deposit(s_temp + 20000);
	C.deposit(c_temp + 17000);

	/* Widthraw and Calculate total incomes */
	s_temp = S.withdraw() * (1 + S.getInterest());
	c_temp = C.withdraw() * (1 + C.getInterest());

	cout << "Saving Account Total Incomes : " << setw(8) << setprecision(6) << s_temp << "\n";
	cout << "Checking Account Total Incomes : " << setw(8) << setprecision(6) << c_temp << "\n";

	return 0;
}


 


Posted by 지그프리드 지그프리드

댓글을 달아주세요:: 네티켓은 기본, 스팸은 사절


객체지향적으로 생각하라!
국내도서>컴퓨터/인터넷
저자 : 맷 와이스펠드(Matt Weisfeld) / 배선종역
출판 : 정보문화사 2009.05.07
상세보기

   Object Oriented Programing 을 공부하기 전에 필독할 만한 책  

  오늘날 프로그래밍의 주류언어로 자바(Java)가 각광을 받으면서, 대부분의 학교에서도 Java를 가르치고 있다. 자바와 C++을 공부하는데 있어서 C의 포인터 만큼이나 넘기 어려운 부분이 있다면, 객체지향(Object Oriented)의 개념을 이해하고, 설계에 적용하는 부분일 것이다. 어떠한 문제를 해결하기 위한 프로그래밍 방법은 수십가지가 있겠지만, 객체지향의 이념을 잘 살려서 우수한 설계와 구현을 하는 것은 결코 쉬운일이 아니다. 특히나 학부 레벨에서 관련된 내용을 배우기도 쉽지 않다. 대부분 과제에서도 죽지않고 돌아가는 프로그램을 짜기 급급한 수준이다. 

  이 책은 객체지향언어를 공부하기에 앞서 한번 완독할 만한 책이다. 내용이 어렵지 않으면서, 예제 코드도 적절하게, 충분히 있고, 개념 설명과 설계의 의도를 충실히 설명해 주고 있다. 최신 기술과 트렌드들을 다양하게 다루고 있고, 여러 언어의 차이와 특성에 대해서도 비교하여 설명해 주고 있다. 이만한 개념서를 찾아보기가 어렵다. 

  물론, 학부 수준 - 프로그래밍을 공부한지 1 ~ 2 학기 정도 - 된 학생의 입장에서는 모든 내용을 100% 소화하기는 어려울 것이다. 하지만, 이 책은 학기 시작 전에 읽고, 학기를 마친 뒤에 다시 한번 읽어봐도 좋을 만한 책이다. 수학 정석을 한 번 보고 버지리 않듯이, 이 책은 여러번 읽어도 좋을 만큼 내용이 다양하고, 새내기 프로그래머에게 주는 교훈들이 많이 들어있다. 

  충분히 읽어 내용을 이해한다면, 아니 이해하지 못해도 충분히 숙지해 둔다면, 후에 고급 개발자로 나아가는데 큰 도움이 될 만한 책이다. 강추한다. 

Posted by 지그프리드 지그프리드

댓글을 달아주세요:: 네티켓은 기본, 스팸은 사절

  지금 진행하는 작업은 세 개의 테이블이 서로 얽히고 섥혀서 돌아가는 어플리케이션이다. 좀더 상세하게는, 특별한 복사본을 갖고있는 두 개의 테이블과, 테이블 간의 관계를 관리하는 테이블 한개를 포함해서 여섯개의 테이블이 맞물려 있다. 특히 어려운 점은, 이 테이블들이 동시에 설계된 것이 아니고 전혀 별개의 기능들을 구현하면서 설계된 테이블인데다 이 기능을 위한 특화된 테이블 들도 아니라는 점이다.

 이런 상황에서 문제를 해결하기 위해, 복잡한 알고리즘을 고안하기 보다는, 끊임없이 테이블간의 싱크를 맞추는 방법을 선택했다. 어떤 동작을 할 때 마다, 화면의 갱신이 있을 때 마다 가장 최신의 정보를 모든 테이블이 동일하게 갖을 수 있도록 쿼리를 짰다. DB를 사용하면 편한점이, 일일이 루프를 돌려서 경신할 필요가 없이 쿼리를 DB에 던져주는 것 만으로도 모든 열들의 갱신이 이루어진다는 점이다.

  내 설계는 DB의 갱신이 일어날 때 마다 모든 테이블의 상태를 일치시켜주는 방식으로 진행이 되었다. 이 방식의 장점은 명확한 동작과 기능간의 인터랙션 설계가 없는 상태에서 안정된 구현이 가능하다는 점이다. 각각의 기능 중 한쪽에만 수정 사항이 보이는 일은 일어나지 않고, 혹시나 놓질 수 몇몇 예외상황에 대해서도 곧 회복이 되어 정상동작으로 돌아간다는 점이다. 구현도 어렵지 않았고, 무엇보다 핵심 기능을 쿼리들이 수행해 주기 때문에, 나중에 컨셉이 바뀌거나 세부 요구사항이 변경될 때도 수정이 쉽다는 장점이 있다.

  문제는 이런 방식은 임베디드 디비에서 동작하기에는 부하가 크다는 점이다. 더구나 각각의 기능들의 엔트리가 Max 1000개 까지 지원되는 상황에서 이 기능들이 Full Sync가 일어나는 상황에서는 약 30초 정도 화면이 멈춘 듯이 보이기도 한다. (모래시계를 돌려야 한다.) 이를 방지하기 위해서 쿼리 최적화에 굉장히 공을 많이 들였지만, 한계가 있었다. 특히 날짜 계산에서 여러가지 예외상황과 추가 요구사항에 대응하기 위하여 더 복잡한 쿼리를 사용하게 되었다. (이 쿼리에 관한 내용은 다음에 글을 쓸 기회가 있을 것이다.)

  결론을 이야기 하면, 결국 대부분의 코드를 최근에 추가되거나 수정된 엔트리만 다른 테이블에도 업데이트하도록 수정을 할 수 밖에 없었다. 가장 큰 이유는 Full Sync 동작에서 메모리 부족으로 리셋이 나는 것이 발견되었고, 그 오류가 서드 파티 라이브러리 내부의 문제라서 내가 손을 댈 수 있는 영역 밖이었다. 둘째는 속도 문제였는데, 이 또한 라이브러리 내부에서 가비지 콜렉션이 부족해서 발생하는 것으로 실험 결과 증명되었다. 서드 파티 라이브러리를 쓰는 것이 이런 문제를 안고 가기 때문에 항상 쉽지 않다.

  결국, 내가 구현한 기능이 아닌 다른 기능의 흐름을 철저하게 분석할 수 밖에 없었고, 그 상황에서 필요한 동작에서 최소한의 업데이트만 수정하도록 쿼리와 함수를 고쳤다. 참고로, 난 다른 기능의 구현 상황을 전혀 알지 못했고, 더군다나 이번에 처음 분석을 한 기능은 두 가지였다.

  처음에는 Full Sync 방식이 쉽게 쉽게 가면서 동작에서의 오류를 최소할 수 있는 종은 방법이라고 생각했지만, 결과적으로 기능 분석을 통해 최소한의 부하를 갖는 방식으로 갈 수 밖에 없었다. 지금길로 간다고 생각했지만, 거대한 삽질을 했던 것에 불과하다. 3월 한달이 이 엄청난 튜닝작업에 소모되었다. 특히 막판 수정으로 이틀을 날렸다. 토요일에 풀타임 근무를 할 수밖에 없었다.

  교훈 : 쉬운 길이 문제가 아니다. 결국은 최고 효율을 낼 수 있는 제대로된 설계와 구현이 필요하다.

  더 큰 교훈 : 이 프로젝트의 시작에 요구사항 분석과 설계가 결여되어 있었을 뿐 아니라, 함께 연동되는 기능들 간에 의사소통이 너무 적었다. 젠장.
Posted by 지그프리드 지그프리드

댓글을 달아주세요:: 네티켓은 기본, 스팸은 사절


  네이버에 이런 질문이 올라왔다.

안녕하세요 컴퓨터프로그래머가 되고싶은 중3 학생입니다

 

저는 초등학교 6학년때부터 컴퓨터프로그래머에 푹빠졌습니다

 

그리고 그생각만 가지고 보니 중3 이였습니다

 

저는 워드프로세서 1,2,3 ITQ 한글, 파워포인트 정보처리기능사 자격증을따냈습니다

 

하지만 자격증만으론 안되고 C언어 C++ JAVA 등 여러가지를 공부해야합니다

 

하지만 저는 중학교입학할때부터 컴퓨터공부를 전혀하지 않았습니다

 

자격증만 있고 확고한 자신감만있으면 된다고 생각한저였으니까요

 

지금은 공부할 마음이 생깁니다

 

어떻게하면 컴퓨터프로그래머가 될수있을지

 

또 어떻게공부해야지 나의 진로를 갈수있을지

 

도와주세요..


 뭐 도와주고 싶은 생각이야 든다만, 과연 프로그래머가 뭐하는 사람인지 잘 모르고 있는 것 같다는 생각이 먼저 들었다. 그래서 이렇게 답변을 달았다.

열심히 공부해서 좋은 대학에 가세요

컴퓨터프로그래머가 되고 싶다면, 가장 기본적인 조건은 대학교에서 컴퓨터를 전공하는 것입니다. 대부분이 회사들이 컴퓨터공학 전공이나 컴퓨터과학 전공의 학위를 요구하기 때문입니다. 좋은 프로그래머가 되고 싶으시다면, 중학생인 지금은 컴퓨터관련 자격증이나 C언어를 공부하는 것은 아무 의미가 없습니다. 그런 공부는 대학에 가서 하셔도 충분합니다.

  컴퓨터 프로그래머는 "어떤 문제를 해결하기 위한 알고리즘을 만들어서, 그 알고리즘을 컴퓨터 언어를 이용해 컴퓨터가 이해할 수 있는 프로그램을 만드는 사람"을 뜻합니다. 지금 질문자님께서 생각하시는 부분은 컴퓨터 언어를 이용해서 프로그램을 만드는 부분만 생각하고 계신 것 입니다. 하지만 실제로 좋은 프로그래머는 문제를 해결하기 위한 좋은 알고리즘을 만드는 사람입니다. 그리고 좋은 알고리즘을 만들기 위해서는 생각이 깊고 현명한 사람이 되어야 합니다. 생각이 깊고 현명한 사람이 되기 위해서는 좋은 대학에서 체계적인 교과과정에서 따라서 열심히 공부하는 것이 가장 필요한 일입니다.

 다시 말씀드립니다만, 지금 중3이라면 학교 공부 열심히 하시는 것을 권해드립니다. 수학과 영어를 열심히 하시는 것이 특히 중요합니다. 그래서 좋은 학교를 가세요. 특히 우리나라는 좋은 학교와 그렇지 않은 학교 사이에 수준차이가 많이 납니다.

  너무 현실적인 답변이었을까? 사실 지금 내가 하는 일도 프로그래머는 이런 일을 한다고 소개하는 수많은 에세이들과 비교하면 노가다에 더 가깝다는 생각도 든다. 좀더 정신노동, 창조적인 일을 하길 원하는데 실상은 그렇지 못한 면이 많다. 내 실력도 그런 일을 할 만큼 뛰어나진 않다고 느끼고 있고. 무엇보다 대학 때 배운 것들이 국제적인 기준에서 너무 수준이 낮았다. 만약 내가 아르바이트로라도 프로그래밍을 하지 았았다면 난 지금보다도 실력이 한참 모자라는 얼치기 개발자에 불과했을 것이다.

  요즘의 대침체 이전에 미국의 최고 장래성있는 직업은 S/W Engineer 였고, 석사 출신 신입의 초봉이 평균 10만 달러에 육박했었다. 대한민국의 프로그래머는 여전히 3D와 화이트칼라의 경계를 걷고 있고, 대우는 많이 부족하다. 거기에다 동종업게 이직금지라는 노예제도까지 존재하고 있다. 공생전 같은 글이 괜히 나오는 것이 아니라는 뜻이다.

 개인적으로, 프로그래밍을 정말 좋아한다. 이 일은 The Mythical Man Month에서 나오는 것과 같이, 새로운 것을 만드는 창조적인 일이고 아름다운 코드를 만든 예술적인 일이다. 목수가 책상 다리에 못을 박고서 예술적으로 박았다고 느끼는 지는 모르겠다. 하지만 프로그래머들은 코드를 몇줄 적어놓고 "아름답다" 고 말한다. 프로그래머는 사람의 언어 대신 컴퓨터의 언어로 글을 쓰는 작가들이기도 하다. 그래서 난 이 일을 사랑하는 것 같다.

 프로그래머가 되고 싶다면, 이 일을 얼마나 사랑할 수 있을지 고민을 좀 해보는 것이 필요하다. 정말 해주고 싶은 말은 이것이다.
Posted by 지그프리드 지그프리드

댓글을 달아주세요:: 네티켓은 기본, 스팸은 사절


BLOG main image
일상, 프로그래밍, IT 그리고 직장생활, Dive, 여행 by 지그프리드

카테고리

Class List (402)
Studies (30)
Exercise & Quizz (10)
Term Project (0)
ECIM list (Help!) (10)
Issues & News (0)
Gossip about IT & Job (22)
Tools (2)
Think about the Justice (23)
Book Review (170)
조엘 온 소프트웨어(번역) (28)
Diary (87)
Vacations (9)
Clash of clans 클래시 오브.. (11)

글 보관함

달력

«   2020/09   »
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30      
Total : 322,847
Today : 66 Yesterday : 29