프로그래밍 숙제4를 진행하는 데 필요한 내용과 수강생들의 메일 질문에 대한 답변을 이 게시판에 업데이트 할 것 입니다.

 

자주 확인하셔야 불이익을 받지 않을 수 있습니다.

 

  • 채점 환경

Visual Studio 2017

 

  • 제출 양식

이름이 HW4_S201*****(학번 8자리)인 프로젝트 폴더를 압축하여 제출한다. (보고서는 없음)

- 소스코드 파일명 (총 1개): 201*****.cpp 

- 프로젝트 파일명: HW4_S201***** 

- 최종 제출 파일: HW4_S201*****.zip 

- 메일 제목: HW4_S201*****

- 제출 메일: 2017algorithm@gmail.com

 

  • 프로그램 데이터 파일의 위치

프로그램은 HW4_201*****.vcxproj가 있는 경로에, 

이름이 INPUT인 폴더 안에 input-3-1.txt, input-3-2.txt, input-3-3.txt 인풋 파일을 읽을 수 있어야 하고,

이름이 201*****_OUT인 폴더 안에 output-3-1.txt, output-3-2.txt, output-3-3.txt 아웃풋 파일을 생성할 수 있어야 한다.

 

201*****_OUT 폴더는 프로그램 시작전에 없다고 가정하고, 프로그램을 수행하면서 새롭게 생성한다.

디렉토리 생성 방법은 다음과 같다.

 

#include <stdio.h>
#include <direct.h>

int main() {
    FILE *fp;
    
    mkdir("20161234_OUTPUT");
    fp = fopen("20161234_OUTPUT/output-3-1.txt", "w");

    fprintf(fp, "This is a test.");

    fclose(fp);

    return 0;
}

 

  • 제출 기한

2017년 12월 24일 일요일 오후 1시 정각 (LATE 없음)

 

 

프로젝트 관련 질문은 wxiz49@sogang.ac.kr로 메일 보내주시길 바랍니다.

 

------------------------------------------------------------------------------------------------------------------------------------------------

 

다음은 Problem 3-1, 3-2, 3-3에 대한 부가설명입니다.

  • [Problem 3-1]

복수 정답이 존재할 경우, 펠린드롬에 포함된 원소의 인덱스가 더 작은 것을 선택해주세요.

예를 들어, 인풋이 BCDACDB인 경우 LPS는 BCACB, BCDCB, BDCDB, BDADB 네 가지가 생깁니다.

BCACB의 CAC, BCDCB의 CDC, BDCDB의 DCD, BDADB의 DAD 중, CDC가 가장 앞선 인덱스에서 생성되므로, 답은 BCDCB입니다.

  • [Problem 3-2]

이 문제에서 답으로 생성된 펠린드롬들은 서로 겹치지 않습니다.

복수 정답이 존재할 경우, 다음의 방법으로 답을 선택해주세요.

(0, N) 범위의 최소 펠린드롬 개수를 구하기 위해, 0번째 문자와 N-1번 째 문자가 같지 않을 경우,

[0, N-1] 범위의 상수 k에 대해, (0, k)범위와 (k+1, N) 범위의 합이 가장 큰 것을 선택해야 하는 과정이 필요합니다.

이 때, k가 작은 쪽의 답을 선택해주세요.

 

예를 들어, 인풋이 2323132일 때, 최소 개수의 펠린드롬으로 나누면 232 + 313 + 2 와 2 + 3 + 23132 두 경우가 생깁니다.  

232 + 313 + 2는 (0, 2) + (3, 6) 이므로 k가 2이고,  2 + 3 + 23132는 (0, 0) + (1, 6) 이므로 k가 0입니다. 

 

  • [Problem 3-3]

명세서 예제 출력의 답은 2 3 2 => 2 2 3 입니다.

댓글 0

번호 제목 글쓴이 날짜 조회 수
» 알고리즘 설계와 분석 - 프로그래밍 숙제 4 (수정) grmanet 2017.12.16 588
공지 알고리즘 설계와 분석 - 프로그래밍 숙제 3 (수정) grmanet 2017.11.10 630
공지 알고리즘 설계와 분석 - 프로그래밍 숙제 1 인풋 데이터 생성 (수정) grmanet 2017.10.10 467
공지 알고리즘 설계와 분석 - 프로그래밍 숙제 1 (수정) grmanet 2017.09.29 1240
공지 2017년 2학기 알고리즘설계와분석 게시판입니다. grmanet 2017.08.28 933