DNA 서열은 'A', 'G', 'T', 혹은 'C' 4글자로 이뤄진 서열을 말한다.

임의의 DNA 서열 A, B에 대해 B를 뒤집은 다음, B의 뒤집힌 보수의 형태 (reverse complementary form)를 취했을 때, A와 같을 경우 2개의 DNA서열을 서로 동치한다고 한다.

'뒤집힌 보수의 형태' 란 DNA 서열 s를 뒤에서 앞으로 읽는 형태로 바꾼 다음, 각 문자에 대해 보수를 취해준 형태를 뜻한다. 여기서 보수란 문자 'A'는 'T'로, 'T'는 'A'로, 'G'는 'C'로, 'C'는 'G'로 치환된 서열을 뜻한다.

예를 들어 DNA 서열 ACGTA를 뒤집었을 경우 ATGCA가 되며, 이를 보수로 치환하면 TACGT가 된다. 따라서 ACGTA 뒤집힌 보수의 형태는 TACGT이며, ACGTA와 TACGT는 동치 관계에 있다.

서로 다른 DNA 서열이 주어졌을 때, 동치 관계에 있는 DNA 서열이 존재하지 않는 부분 집합 중 원소의 개수가 가장 큰 부분 집합을 찾는 프로그램을 작성하라.

DNA 서열 timer 1s memory - MB

DNA 서열 1s - MB