2010학년도 2학기 자료구조(Data Structure) 첫 과제!
ESPA를 이용한 채점방식을 처음 사용하였는데, 일단은 만점이 나왔었던 과제
ESPA 의 채점방식이 코드를 넣으면 스스로 컴파일을 하여 여러개의 샘플 데이터를 비교해 보고 주어진 입력에 대해 출력이 일치하면 점수를 주는 식인데, 이게 샘플데이터가 뭔지 모르니 어떤것이 틀렸는지를 스스로 여러 샘플을 통해 알아내야 한다는 것이 힘들면서도 흥미로운 프로그램이다.
따라서 가급적 처음부터 조건과 형식을 잘 맞추어 구현하는것이 중요하다!는 것이 느낀점
[소개]
일반적인 portal site 에서 인기검색어를 알려주는 것의 기본이 되는 프로그램이다.
입력된 여러 단어들 중에서 특정 시점에 가장 빈도가 높은 단어를 골라서 출력하여 준다.
일반적인 portal site 에서 인기검색어를 알려주는 것의 기본이 되는 프로그램이다.
입력된 여러 단어들 중에서 특정 시점에 가장 빈도가 높은 단어를 골라서 출력하여 준다.
[입출력]
입력파일 이름은 portal.inp 이며, 출력파일 이름은 portal.out 이다.
입력파일에는 5~15자의 영문소문자가 알파벳 순서로 나열 되어 있고, 중간에 인기검색어의 출력을 원하는 시점에 ASK 라는 단어가 입력되어 있으며, 이 때는 처음부터 이 시점 까지의 인기검색어가 출력된다.
만일 최고빈도수가 같은 키워드가 있을 경우 제일 최근에 임력된 단어가 출력된다.
[예제]
portal.inp
portal.out
coupon facsimile books kimtakgu
coffee ASK yoger presso careful charyum
absinthe cashbag galaxy iphone
server microsoft masterpiece ASK
coffee
masterpiece
[언어]
C++
C++
[설계]
- 자료구조
키워드와 키워드의 빈도수를 저장하는 string, int 두 타입으로 class Keyword{...}를 선언 한 뒤
이 class 를 vector자료형으로 사용
키워드와 키워드의 빈도수를 저장하는 string, int 두 타입으로 class Keyword{...}를 선언 한 뒤
이 class 를 vector자료형으로 사용
- 알고리즘
파일 입력으로 임시의 변수에 저장 한 후 새로운 단어일 경우 vector 에 push_back 으로 Keyword를 추가하고,이미 있을 경우 이름이 같은 Keyword 에 빈도만 1을 늘려준다.
ASK 가 출력될 경우 최빈도의 단어를 찾아 출력한다.
[구현과정]
내가 생각한 알고리즘으로 프로그램을 짜면, 변수에 단어를 모두 저장 하는 것보다는 메모리 사용 측면에서 효율적이다.
단어가 들어올때마다 검색을 하는 과정이 다소 무거운 과정일 수도 있는데, 이것은 빈도수를 count 하기 위해서도 필수적인 작업이므로 더이상 속도나 차지하는 메모리를 줄일 수는 없어 보였다.
그런데 또 최빈도수가 같을 경우 최근 단어를 출력하여야 하는 조건 때문에, 제일 늦게 등록된 단어를 출력 하였는데,
즉 Keyword vector에 iterator 를 사용하여 iterator 값이 큰 단어를 출력하였는데, 그리하면 제일 처음에 등록되었지만 마지막에 입력된 단어인 경우 가령,
hello
hello
hi
라는 입력이 들어왔을 경우에는 vector 에 등록된 순서는 hi - hello 이지만 hi 가 제일 최근에 나왔으므로 hi를 출력하여야 하는데 이 방법으로는 출력이 옳게 나오지 않았다.
그래서, 나는 최고빈도단어의 순서를 저장하는 변수 num_hot을 만들어 단어를 입력받을 때마다 그때의 최고빈도의 단어와 비교하여 빈도가 같아지면 바로바로 num_hot 을 변경하여 주는 방법을 택하였다.
이리하면 굳이 Keyword 클래스에 입력된 순서를 하나의 멤버로 정의하지 않아도 되어 메모리를 절약할 수 있기 때문에 더 효율적이라고 생각했다.
그러나, 이렇게 입력이 들어올때마다 검사를 하는것과 클래스에 하나의 멤버를 저장하는 것과 어느쪽이 빠른지는 정확히 알 필요가 있는 것 같다.
[분석]
입력된 임시 단어가 기존에 존재하는지 검색하는 과정에서 string 을 사용하여 검색하지 않고, char 를 이용하여 제일 첫글자부터 검사하고 넘어가는 방식으로 하면 더 빠를 수 있지 않을까 싶기도 하다.
그런데 그러면, Keyword 의 string 항목을 char* 바꾸어주고 C 함수를 써야 할 것 같은데, 그렇게 되면, 들어오는 키워드에 따라 char* 의 크기를 선언 하는 것에서 동적 할당을 해 주는데 효율적일 듯 한데
string이라는 형식은 정확히 어떻게 정의되는 형식인지를 정확히 알아 보는 작업이 필요할 것 같다.
! 해야 할 일
string 형식의 정의와 저장되는 형태, 자주쓰는 함수들이 돌아가는 메카니즘 알기
어떤 변수에 멤버를 하나 더 추가하는 것과 조건 연산을 하나 더 넣는 것의 속도 비교