1969: DNA
DNA는 모든 유전 물질을 구성하는 분자입니다. 이 DNA는 4개의 다른 뉴클레오티드(아데닌, 티민, 구아닌, 시토신)로 구성됩니다. 특정 DNA의 물질을 표현할 때 해당 DNA를 구성하는 뉴클레오솜을 말합니다.
www.acmicpc.net
DNA는 모든 유전 물질을 구성하는 분자입니다. 이 DNA는 4개의 다른 뉴클레오티드(아데닌, 티민, 구아닌, 시토신)로 구성됩니다. 특정 DNA의 물질을 표현할 때 그 DNA를 구성하는 뉴클레오티드의 첫 글자를 취하여 표현합니다. 티민-아데닌-아데닌-시토신-티민-구아닌-시토신-시토신-구아닌-아데닌-티민으로 이루어진 DNA가 있으면 “TAACTGCCGAT”로 표현될 수 있다. 그리고 Hamming distance는 같은 길이의 DNA가 2개일 때 각 위치에 있는 서로 다른 nucleotide character의 수입니다. “AGCAT”와 “GGAAT”의 첫 번째와 세 번째 문자가 다른 경우 해밍 거리는 2입니다.
여기 우리가 할 일이 있습니다. N 길이 M DNA s1, s2, …, sn이 주어지면 해밍 거리의 합이 가장 작은 DNA s를 찾습니다. 이는 s와 s1의 해밍 거리 + s와 s2의 해밍 거리 + s와 s3의 해밍 거리…의 합이 최소가 된다는 것을 의미한다.
DNA의 숫자 N과 문자열의 길이 M은 첫 번째 줄에 표시됩니다. 그리고 두 번째 줄부터 N+1 줄까지 N 조각의 DNA가 주어진다. N은 1,000 이하의 자연수이고, M은 50 이하의 자연수이다.
누르다
첫 번째 줄에는 해밍 거리의 합이 가장 작은 DNA를 인쇄하고 두 번째 줄에는 해밍 거리의 합을 인쇄하십시오. 이러한 DNA가 여러 개인 경우 알파벳순으로 첫 번째 DNA가 출력됩니다.
샘플 입력 1 복사
5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
예제 출력 1 복사
TAAGATAC
7
샘플 입력 2 복사
4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA
샘플 출력 2 복사
ACGTACGTAA
6
샘플 입력 3 복사
6 10
ATGTTACCAT
AAGTTACGAT
AACAAAGCAA
AAGTTACCTT
AAGTTACCAA
TACTTACCAA
샘플 출력 3 복사
AAGTTACCAA
12
예전에 풀었던 문제인데 거의 1년이 지나서 문제가 거의 새것처럼 느껴집니다. 언뜻 보기에는 문제가 이해하기 어려울 수 있지만 N과 M 뉴클레오티드로 구성된 DNA 구조가 들어가 있습니다. 여기서 매트릭스의 느낌이나 2차원 배열의 느낌이 있음을 알 수 있다. 또한 컬럼별로 비교 빈도가 가장 높은 문자가 기본 문자가 됩니다. 이렇게 하면 가장 많은 참조 문자로 구성된 DNA 구조가 Hamming 거리가 가장 작은 DNA임을 알 수 있습니다. 여기에서 전체 검색을 수행하면서 최대 주파수 DNA를 찾아야 함을 알 수 있습니다. 마지막으로 모든 DNA의 해밍 거리의 합을 얻을 수 있습니다.
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT예제 1의 예제를 살펴보겠습니다.
열을 비교할 때 열 1은 T, 열 2 A, 열 3 A, 열 4 G, 열 5 A, 열 6 T, 열 7 A 및 열 8 C입니다. 그 문자들을 계산하지 않은 값은 1,1,1,0,1,0,2,1이 되고 이 값들을 모두 더하면 정답이 7이라는 것을 알 수 있는데, 이는 해밍 거리이다.
이 원칙을 그대로 코딩해 봅시다.
N, M = map(int, input().split())
min_ham_d = ''
ham_count = 0
DNA = (input() for i in range(N))
for i in range(M): # M: 열
DNA_idx = (0, 0, 0, 0) # DNA_idx : DNA 빈도수
for j in range(N): # N: 행
if DNA(j)(i) == 'A':
DNA_idx(0) += 1
elif DNA(j)(i) == 'C':
DNA_idx(1) += 1
elif DNA(j)(i) == 'G':
DNA_idx(2) += 1
elif DNA(j)(i) == 'T':
DNA_idx(3) += 1
max_idx = DNA_idx.index(max(DNA_idx))
if max_idx == 0:
min_ham_d += 'A'
elif max_idx == 1:
min_ham_d += 'C'
elif max_idx == 2:
min_ham_d += 'G'
elif max_idx == 3:
min_ham_d += 'T'
ham_count += N - max(DNA_idx)
print(min_ham_d)
print(ham_count)이렇게 해결할 수 있었습니다. 먼저 행과 열 문자 N과 M을 취하고 새로운 반복 목록 DNA를 선언합니다. 이후 DNA_idx에 DNA 빈도를 입력하고 이때 N행이 반복되는 동안 A, C, G, T의 모든 경우를 고려하여 빈도를 DNA_idx 목록에 입력한다.
그런 다음 max_idx에 DNA_idx 리스트의 인덱스 중 가장 큰 값을 넣고 이 값을 0, 1, 2, 3으로 조사하여 A, C, G, T를 변수에 넣어 가장 작은 Hamming distance를 찾습니다. 변수의 총 개수는 N 값과 개수에서 루프 내 DNA_idx의 최대 빈도를 빼면 가장 작은 Hamming 거리에 대한 정답을 찾을 수 있습니다.
완전 탐색감이 강했지만, 그리디 알고리즘을 사용할 때 아이디어가 더 빨리 떠오를 것 같은 문제였다.