서강대학교공과대학컴퓨터공학과 (/5) CSE08 ( 반 ): 알고리즘설계와분석 < 프로그래밍숙제 > (v_.0) 담당교수 : 임인성 05 년 0 월 일 마감 : 0 월 일토요일오후 8 시정각 제출물, 제출방법, LATE 처리방법등 : 조교가과목게시판에공고할예정임. 목표 : 주어진문제에대한분석을통하여 optimal substructure 를유추하고, 이를 bottom-up 방식으로계 산하는과정에대한연습을통하여, 알고리즘설계기법중의하나인 dynamic programming 에대한이해도 및응용능력을높이도록한다. [ 문제 ] 다음의문제를 dynamic programming 기법을사용하여해결하자. Given two sequences X = x x x n and Y = y y y m (n, m 0), find a longest common subsequence (LCS) of X and Y. 이제주어진두문자열 (character sequence) X 와 Y 에대하여 (i) 그것들의 LCS의길이와 (ii) LCS에해당하는문자열을찾는프로그램을작성하라.. 여러분의프로그램은자신의프로그램원시파일과동일한디렉토리에저장되어있는 P_input.bin 파일에서테스트데이터를읽어들여, 동일한디렉토리에이름이 P_output.bin인파일에프로그램수행결과를저장해야한다.. 입력파일에는모든값들이 binary format으로저장이되어있다. 먼저첫 바이트에는테스트케이스의개수가 int 타입으로저장되어있으며, 이후이개수만큼의각케이스에대한입력데이터가순차적으로저장되어있다. 한테스트케이스에대해서먼저첫 바이트에는첫번째문자열 X 의길이 n, 그리고다음 바이트에는두번째문자열 Y 의길이 m이각각 int 타입으로저장되어있고, 연달아다음 n 바이트에는 X 에대한문자들이, 그리고그다음 m 바이트에는 Y 에대한문자들이 char 타입으로저장되어있다 ( 문자열의길이는최대 095까지처리가능하여야함 ).. 출력파일역시모든값들을 binary format으로저장해야한다. 먼저첫 바이트에는테스트케이스의개수를저장해야하며 ( 입력데이터의첫 바이트와동일 ), 다음각테스트케이스에대한답이순서
서강대학교공과대학컴퓨터공학과 (/5) 대로저장되어야한다. 각테스트케이스에대해먼저첫 바이트에는해당 LCS의길이 l 을 int 타입으로저장하며, 연달아다음 l 바이트에는해당 LCS의문자들을 char 타입으로저장해야한다. 동일한길이를가지는 LCS가두개이상일경우어떠한결과를출력해도문제를올바로푼것으로간주한다. [ 문제 ] 다음의문제를 dynamic programming 기법을사용하여해결하자. Given two strings A = a a a n and B = b b b m (n, m 0), consider the problem of transforming A into B by either inserting a character into A, deleting a character from A, or replacing a character in A by another. Suppose that the costs per insertion, deletion, and replacement are c ins, c del, and c repl, respectively. Then, find the minimum cost of transforming A into B, and show how A can be converted into B at the cost. 위의문제에서 c ins = c del = c repl = 인경우에대하여, (i) 문자열 A를 B 로변환하는데필요한최소비용과 (ii) 그러한최소비용에해당하는변환과정을구하는프로그램을작성하라.. 여러분의프로그램은자신의프로그램원시파일과동일한디렉토리에저장되어있는 P_input.txt 파일에서테스트데이터를읽어들여, 동일한디렉토리에이름이 P_output.txt인파일에프로그램수행결과를저장하여아한다. 첫번째문제와는달리입출력데이터모두 ASCII format으로저장을한다.. 입력파일의첫줄에는테스트케이스의개수가정수타입으로주어져있고, 이후각케이스에대하여두줄씩입력문자열이저장되어있다 ( 첫번째줄에 A, 그리고두번째줄에 B 가저장되어있으며, 각문자열은해당줄의첫문자부터 newline 문자 ( 또는 EOF 문자 ) 바로직전까지의모든문자 (space 문자포함 ) 로구성되어있으며, 문자열의길이는최대 095개까지처리가능하여야함 ). 다음은세개의테스트케이스로구성된입력파일의예를보여주고있다. kitten sitting exponential polynomial Another fine day in the park Anybody can see him pick the ball. 출력파일의첫줄에는테스트케이스의개수를저장해야하며 ( 입력데이터의첫줄과동일 ), 다음각테스트케이스에대한답이순서대로저장되어야한다. 각테스트케이스의경우먼저첫줄에최소비용을정수타입으로저장한후, 다음최소비용에해당하는개수의줄각각에는문자열 A를 B 로변환을하는과정을순차적으로저장해야한다. 이때반드시 A의문자들을앞에서뒤로가면서스캔하면서변환해야한다. 이때변환을위한세가지연산에대한각명령의문법은다음과같다. I i x Insert a character x in A right after a i.
서강대학교공과대학컴퓨터공학과 (/5) D i Delete a i from A. R i x Replace a i in A by a character x. 다음은앞의입력데이터에대한문제풀이결과를보여주고있다. R s R 5 i I g D D R 5 l R y R 8 o I 8 m 9 R y R b R 5 o. R 8 l. 주의 : 변환과정에서한순간에서로다른연산을적용하는것이가능하다면 ( 즉최소비용의변환으로가는길이여러가지가존재한다면 ), 항상 DELETION > INSERTION > REPLACEMENT의순서로연산을선택을해야한다. [ 문제 ] 다음의문제를 dynamic programming 기법을사용하여해결하자. Given a set of n positive integers A = { a, a,, a n }, patition A into two subsets A and A (i.e. A = A A, A A = ) such that S S is minimized, where S i is the sum of elements in A i (i =, ). 이제주어진집합 A에대하여 (i) 위문제에서찾고자하는최소차이와 (ii) 그러한최소차이에해당하는두집합 A 과 A 를구하는프로그램을작성하라.. 여러분의프로그램은자신의프로그램원시파일과동일한디렉토리에저장되어있는 P_input.txt 파일에서테스트데이터를읽어들여, 동일한디렉토리에이름이 P_output.txt인파일에프로그램
서강대학교공과대학컴퓨터공학과 (/5) 수행결과를저장하여아한다. 두번째문제와같이입출력데이터모두 ASCII format으로저장을한다.. 입력파일의첫줄에는테스트케이스의개수가정수타입으로주어져있고, 이후각케이스에대한입력데이터가주어진다. 각케이스에대해서는먼저첫줄에 A의원소의개수 n 이정수타입으로저장되어있고 ( 원소의개수는최대 0개까지처리가능하여야함 ), 이후그개수에해당하는줄각각에 A의원소가정수타입으로저장되어있다. 7 8 7. 출력파일의첫줄에는테스트케이스의개수를저장해야하며 ( 입력데이터의첫줄과동일 ), 다음각테스트케이스에대한답이순서대로저장되어야한다. 각테스트케이스의경우먼저첫줄에최소차이, A의원소의개수 n, 그리고첫번째부분집합 A 의원소의개수 n 등세개의정수를저장한후, 이후두부분집합의원소를한줄에한개씩순차적으로저장해야한다. 이때첫 n 개의원소는 A 의원소로, 그리고나머지 n n 개의원소는 A 의원소로간주한다. 만약동일한최소비용을가지는집합분할이두개이상존재할경우, 어떠한결과를출력해도문제를올바로푼것으로간주한다. 다음은앞의입력데이터에대한문제풀이결과를보여주고있다. 0 7 8
서강대학교공과대학컴퓨터공학과 (5/5) 7 [ 참고사항 ]. 숙제제출기간동안조교가숙제와관련하여중요한공지사항을게시판에올릴수있으니항상수업게시판을확인하기바람. 제출내용및방법에변경이있을수있음.. 채점은우선여러분의원시코드를확인한후, 본과목에서준비한테스트데이터를사용하여기계적으로여러분의프로그램을검증할예정이므로, 위에서기술한정확한입출력형식을따르도록코딩을할것. 이를위하여샘플로제공하는테스트데이터를잘활용할것.. 숙제를하면서서로아이디어를교환하는것은허용하나 ( 게시판활용권장 ), 자신의코드는자신이직접작성해야함.. 제출파일에서바이러스발견시본인점수 X (-) 이고, 다른사람의숙제를복사할경우관련된사람모두에대하여만점 X (-0) 임.