최종 수정일: 2026-11-16
알고리즘 6주차 가정 과제(Week 06 Assignment)이다. 주제는 동적 프로그래밍이며, 두 문서를 비교하여 LCS(최장 공통 부분 수열) 알고리즘으로 유사도를 계산하는 표절 검사 웹 앱을 만든다. 6주차 이론의 내용과 이어진다.
- 배점: 전체 성적의 1%
- 제출 기한: 다음 이론 수업 전의 월요일 23:59
- 제출 방법: LMS에 소스 코드(
.zip)와 보고서(.pdf)를 제출한다
주의: 마감 직전에는 LMS에 문제가 생길 수 있으므로 늦어도 일요일까지 제출한다. 시스템 오류로 늦게 제출한 경우는 인정하지 않으며, 기한을 지킬 책임은 학생에게 있다.
두 문서를 비교하고 최장 공통 부분 수열(Longest Common Subsequence, LCS) 알고리즘(동적 프로그래밍)으로 유사도를 계산하는 표절 검사기 웹 앱을 만든다.
- 백엔드: Python (FastAPI 또는 Flask)
- 프런트엔드: HTML, CSS, JavaScript
동적 프로그래밍으로 LCS 알고리즘을 구현한다.
- 입력된 두 텍스트에 대해 DP 표를 만든다.
- 역추적(backtrack)으로 LCS를 찾는다.
- 유사도 점수를
LCS length / max(len(A), len(B)) * 100%로 계산한다. - diff 보기를 만든다. 각 부분을 일치(matched), 추가(added), 삭제(removed)로 표시한다.
- 문서 A와 문서 B를 입력하는 두 개의 텍스트 영역을 둔다.
- 표절 분석을 실행하는 "Check" 버튼을 둔다.
- 다음을 표시한다.
- 유사도 점수(백분율)
- LCS 길이와 실제 LCS 문자열
- 색으로 구분한 diff 보기: 일치(회색), 삭제(빨간색), 추가(초록색)
| 메서드 | 엔드포인트 | 설명 |
|---|---|---|
POST |
/check |
두 텍스트를 비교하고 유사도 점수와 diff를 반환 |
GET |
/ |
프런트엔드 페이지 제공 |
표 1. 구현할 API 엔드포인트
week06_assignment/
├── app.py # 백엔드
├── static/
│ ├── index.html
│ ├── style.css
│ └── app.js
└── requirements.txt
그림 1. 제출할 소스 코드의 디렉토리 구성
- 두 예시 텍스트를 비교하는 표절 검사기의 화면 캡처
- 짧은 예시(예: "ALGORITHM"과 "ALTRUISTIC")의 DP 표
- 분석: LCS의 시간 복잡도와 공간 복잡도를 설명한다. 이것은
git diff나 Turnitin 같은 도구와 어떤 관계가 있는가?
| 항목 | 비율 |
|---|---|
| 웹 앱이 실행되고 올바르게 동작한다 | 20% |
| 알고리즘 요구사항을 모두 구현한다 | 40% |
| 보고서 (최대 2쪽, 글자 크기 11 이상) | 40% |
표 2. 평가 항목과 비율
주의: 과제 내용은 필기시험에 출제될 수 있다. 과제 결과와 시험 성적 사이에 큰 차이가 있으면 감점될 수 있다.
기한 전에 LMS에 제출한다.