알로리즘 문젠데 ... 도저히 ㅠㅠ
글쓴이: 익명 사용자 / 작성시간: 수, 2002/07/10 - 11:02오후
안녕하세요
제가 프로그래밍중 다음과 같은 문제에 봉착했는데, 제가 기초가 부족
해서 인지 하루종일 생각해 봐도 통 감이 안옵니다.
배열, 혹은 파일에 다음과 같은 데이타가 있을때,
aaa
aaa
bbb
bbb
bbb
ccc
ccc
ccc
ccc
이것을 다음과 같이 정렬합니다.
ccc
ccc
ccc
ccc
bbb
bbb
bbb
aaa
aaa
즉 c 가 가장 많으니까, 제일 위로 올라가고 그다음 b a 이런 식으로
정렬이 되게 하는 겁니다.
생각날듯 말듯, 생각이 않나는 군요 ㅠㅠ
Forums:
Re: 알로리즘 문젠데 ... 도저히 ㅠㅠ
안녕하세요...
Step 1)
일단은 aaa, bbb, ccc 이 세가지 패턴이 있다면은 이것들이 전부 몇 번이
오는지를 먼저 판별을 하세요...
Step 2)
위 Step 1) 에서 나온 값을 근거로 제일 큰 값을 가진 것들을 우선 처음
에 정렬을 하고...
다시 그 다음 값을 가진 패턴을 이에 붙혀 주는 식으로 하면은 될 것 같네
요...
_ 信
Re: 알로리즘 문젠데 ... 도저히 ㅠㅠ
패턴의 종류와 수만 기억한 다음...
이 수에 따라 패턴 종류를 정렬하고 차례대로
수만큼 각 패턴을 출력해 주면 되겠네요.
그럼 고운 하루...
STL로 구현한 코드입니다.
이런 경우는 트리나 해쉬테이블과 같은 연관 컨테이너(associative container)를 사용하는 방법이
가장 간단하고, 빠르며, 메모리 사용량도 적습니다.
다음은, STL의 연관 컨테이너인 map과 multimap을 사용하는 방법입니다.
//---------------------------------------------------------------------------
#include
#include
#include
#include
#include
#include
//-------------------------------------------------------------------
using namespace std;
int main()
{
typedef vector vec_str;
vec_str input_words, output_words;
input_words.push_back("aaa");
input_words.push_back("aaa");
input_words.push_back("bbb");
input_words.push_back("bbb");
input_words.push_back("bbb");
input_words.push_back("ccc");
input_words.push_back("ccc");
input_words.push_back("ccc");
input_words.push_back("ccc");
typedef map freq_map; // map 대신 hash_map을 써도 좋습니다.
freq_map freq;
for (size_t i = 0; i < input_words.size(); ++i)
// freq에 words[i]가 있으면 1만큼 증가,
// 없으면 새로 추가하고 빈도를 1로 세팅.
freq[input_words[i]]++;
typedef multimap invert_freq_map;
invert_freq_map invert_freq;
for (freq_mapiterator i = freq.begin(); i != freq.end(); ++i)
invert_freq.insert(invert_freq_mapvalue_type(i->second, i->first));
// 단어와 빈도를 거꾸로 해서 multimap에 저장
for (invert_freq_mapiterator i = invert_freq.begin();
i != invert_freq.end(); ++i)
for (int j = 0; j < i->first; ++j) // 빈도만큼 output_words에 삽입
output_words.push_back(i->second);
copy(output_words.rbegin(), output_words.rend(),
ostream_iterator(cout, "\n")); // output_words를 cout에 출력
return 0;
}
Re: 알로리즘 문젠데 ... 도저히 ㅠㅠ
#!/usr/bin/perl
# 정말 많은 분들이 답변 해 주셨습니다.
# 그런데 저는 perl 로 해봤습니다.
# 이걸아마 C/C++ 로 했다면, .... 아마 저는 휴~
@array = qw( 3 2 3 1 3 2 1 1 1 1 3 ); # 배열에 임의의 숫자 저장
# 일단 숫자 별로 sorting ex) 1 1 1 1 1 2 2 3 3 3 ...
# 그러나 이건 우리가 원하는 답이 아니죠? ^^;
@sortarr = sort { $a <=> $b } @array;
# 배열을 돌면서....
for($i = 0; $i < @sortarr; $i++ )
{
$value = $sortarr[$i];
# 빈도수를 변수에 저장..
$ret = grep(/$value/, @sortarr);
# 빈도수+데이타 <- 요런 식으로 배열에 푸쉬....
push(@part, "$ret" . "+" . "$sortarr[$i]");
}
# 앞에 빈도수 를 기준으로 거꾸로 정렬
# 그럼 가장 빈도수가 높은 데이타가 위로 가지요 ^^;
@sortarr = reverse sort { $a <=> $b } @part;
# 그 다음에 빈도수를 제외하고 데이타만 출력하면
for($i = 0; $i < @sortarr ; $i++ )
{
my ($q, $p) = split(/\+/, $sortarr[$i]);
print "$p\n";
}
댓글 달기