시간표생성프로그램 - 개발 후기

시간표생성프로그램을 약  5일간 개발하면서 느꼈던 점이나 배웠던 점, 어려웠던 점을 기술해보려고 한다.

 

문제점

 

1. 모든 조합이 생성되지 않는다.... (가장 큰 문제)

처음에 조합이 생성되어 시간표들이 생성되었을 때는, 소리를 질렀다.

나도 이제 수동으로 조합을 안해봐도 되는구나.... 

 

내가 이번 학기 수강신청을 할 시간표를 확인해보니... 이 시간표는 조합에 포함되어있지 않았다. ㅜㅜ

문제점을 찾기위해 구현한 코드를 모두 살펴보았을때 의심되는 부분을 발견했다.

 

내가 기존에 설계한 조합 알고리즘은 

그저 단순히 classes 에 저장된 수업들을 중첩반복문을 통해 combinedResult 에 넣는 방식이었다.

이 과정에서 같은 과목이 이미 추가되어있지 않고, 동일 시간이 아닌 경우만 조합이 된다.

하지만 동일 과목의 경우, 무조건 먼저 classes에 저장된 과목이 조합되는것을 확인하게 되었다...

 

- 어떻게 개선할까?

먼저 저장된 수업들을 과목별로 분리해서 배열에 저장하도록 한 다음

각 배열에서 과목별로 모든 수업을 꺼내서 조합할 수 있게 한다.

 

그런데 과목이 7개라고 한다면, 각 과목당 수업이 4개정도 개설되었다고 하자

그러면, 먼저 각 과목의 조합순서를 정하는데 7! 의 경우의 수가 생긴다 = 5040가지의 경우의 수...

여기서 각 과목에서 수업을 꺼내는 경우의 수를 하면 4! 즉 한 과목당 24가지의 경우의 수 ...

 

엄청난 경우의 수를 계산하게 되고 이러면 사이트의 무게가 무거워지고 느려질 수 밖에 없을 것 같다.

그래서 이 방법을 쓰게된다면 결국은 랜덤으로 과목 순서를 정하고 거기서 모든 조합을 계산하는 방법으로 개선하면 그나마 연산을 줄 일 수 있을 것이다.

 

GPT에게 또다른 의견을 물어보았다.

GPT는 백트래킹 알고리즘을 사용하라고 조언해주었다. 그러나 백트래킹 알고리즘에 대해 아직 자세하게 알지 못하므로

적용할 수 없었다. 좀 더 알고리즘을 공부하고 개선해보아야겠다.

 

- 이렇게 개선할 수 있었다 !

8월 21일 드디어 개선 방안을 고안해냈다.

1학기 자료구조 수업때 배운 재귀호출을 이용해보기로 하였다.

내가 실제로 조합을 하기 위해 추가한 수업들의 경우의 수를 계산해보니 약 9만건이 나왔다.

이를 실제로 프로그램을 통해 작동해보니 15분이라는 시간이 소요되었다.

이를 해결하기 위하여 필수로 포함된 과목이 있는 경우 계산에서 제외하고 다음 과목으로 넘어가도록 하였다.

 

또 계산된 결과가 엄청 많았는데 그 중 절반정도는 7개과목이 있다면 5개, 6개 정도의 과목으로만 조합된 경우도 많았다.

이런 것들을 제외하고 7개의 과목을 입력했다면 7개의 과목으로 조합된 시간표만 저장해서 출력하도록 하였다.

 

이렇게 하니 계산하는데 걸리는 소요시간은 약 15분에서 1분미만으로 줄었다.

다만, 이용자의 환경이나, 혹은 입력된 수업 수, 과목 수, 필수 여부에 따라 계산 소요시간이 달라진다.

 

 

 

느낀 점

아...

컴퓨터공학과정에서 자료구조와 알고리즘이 중요한 이유, 그리고 각 기업에서 코딩테스트를 보는지 더 이해하게 되었다.

 

지금이야 물론 이정도의 데이터 양이지만, 실무에서는 더 방대한 양의 데이터를 다루게 될 것이다.

DB에서 각 데이터를 꺼내서 연산을 하고 그런다면 알고리즘과 자료구조가 많이 중요할 것이다.

자료구조와 알고리즘 공부를 열심히 해야겠다.

 

그리고 내가 구현한 코드들은 많이 난잡한 것 같다.

다음 프로젝트에는 설계 기초를 견고하게 하고 구현을 해서 이를 개선해보아야겠다.