해밍 거리와 쿼드 트리

어디에도 묶이지 않은 Python 문제 세 개다. 해밍 거리는 DNA 서열 14줄에서 길이 7 의 패턴과 가장 가까운 자리를 찾는 것이고, 쿼드 트리 둘은 흑백 이미지를 p, w, b 문자열로 압축하는 문제다. 쿼드 트리 두 개를 합치는 2-1 은 재귀 안에서 인덱스를 전역으로 움직이다가 꼬여서 끝내지 못했고, 2-2 는 N×N 행렬을 받아 괄호 표기로 압축하는 쪽이라 완성했다.

해밍 거리

seq1 = [
"CTTGGTACACGGAACGTTCTGAAAAGAGCTATGAATTGCAGACACCTTTTGAAATTAAATTGGCAAAGAA",
"ATTTGACACCTTCAATGGGGAATGTCCAAATTTTGTATTTCCCTTAAATTCCATAATCAAGACTATTCAA",
"CCAAGGGTTGAAAAGAAAAAGCTTGATGGCTTTATGGGTAGAATTCGATCTGTCTATCCAGTTGCGTCAC",
"CAAATGAATGCAACCAAATGTGCCTTTCAACTCTCATGAAGTGTGATCATTGTGGTGAAACTTCATGGCA",
"GACGGGCGATTTTGTTAAAGCCACTTGCGAATTTTGTGGCACTGAGAATTTGACTAAAGAAGGTGCCACT",
"ACTTGTGGTTACTTACCCCAAAATGCTGTTGTTAAAATTTATTGTCCAGCATGTCACAATTCAGAAGTAG",
"GACCTGAGCATAGTCTTGCCGAATACCATAATGAATCTGGCTTGAAAACCATTCTTCGTAAGGGTGGTCG",
"CACTATTGCCTTTGGAGGCTGTGTGTTCTCTTATGTTGGTTGCCATAACAAGTGTGCCTATTGGGTTCCA",
"CGTGCTAGCGCTAACATAGGTTGTAACCATACAGGTGTTGTTGGAGAAGGTTCCGAAGGTCTTAATGACA",
"ACCTTCTTGAAATACTCCAAAAAGAGAAAGTCAACATCAATATTGTTGGTGACTTTAAACTTAATGAAGA",
"GATCGCCATTATTTTGGCATCTTTTTCTGCTTCCACAAGTGCTTTTGTGGAAACTGTGAAAGGTTTGGAT",
"TATAAAGCATTCAAACAAATTGTTGAATCCTGTGGTAATTTTAAAGTTACAAAAGGAAAAGCTAAAAAAG",
"GTGCCTGGAATATTGGTGAACAGAAATCAATACTGAGTCCTCTTTATGCATTTGCATCAGAGGCTGCTCG",
"TGTTGTACGATCAATTTTCTCCCGCACTCTTGAAACTGCTCAAAATTCTGTGCGTGTTTTACAGAAGGCC"
]

seq2 = "AGATGCG"

def hamming_distance(x,y):
  count = 0
  for i in range(len(y)):
    if x[i] != y[i]:
      count += 1
  return count

answers =[]
min_hamming_distance = len(seq2)

for i, seq1_part in enumerate(seq1):
  for j in range(len(seq1_part)-len(seq2)+1):
    if hamming_distance(seq1_part[j:j+7],seq2) <= min_hamming_distance:
      min_hamming_distance = hamming_distance(seq1_part[j:j+7],seq2)
      answers.append([i,j,min_hamming_distance])

answers.sort(key = lambda x :(x[2]))

for answer in answers:
  if answer[2] == min_hamming_distance:
    print(f"가장 낮은 hamming distance는 {min_hamming_distance}이며, seq1의 {answer[0]+1}행 {answer[1]+1}열에 존재합니다.")

쿼드 트리 두 개 합치기 (미완)

S3 = ""
S1_idx = 0
S2_idx = 0
# def calc_quad_tree():
#   # 2. 더하기

def sum_quad_tree(S1_part, S2_part):
  global S3, S1_idx, S2_idx
  S3 += "p"

  for i in range(4):

    if S1_part[i+S1_idx] == "b" or S2_part[i+S2_idx] =="b":
      if S1_part[i+S1_idx] == "p":
        S1_idx += 4
      if S2_part[i+S2_idx] == "p":
        S2_idx += 4
      S3 += "b"
    elif S1_part[i+S1_idx] == "p" and S2_part[i+S2_idx] =="p":
      sum_quad_tree(S1_part[1:], S2_part[1:])
      S1_idx += 4
      S2_idx += 4
    elif S1_part[i+S1_idx] == "p":
      sum_quad_tree(S1_part[1:], "wwww" + S2_part)
      # 중간에 w가 붙어야대는데
      S1_idx += 4
    elif S2_part[i+S2_idx] =="p":
      sum_quad_tree("wwww" + S1_part, S2_part[1:])
      S2_idx += 4
    elif S1_part[i+S1_idx] == "w" and S2_part[i+S2_idx] == "w":
      S3 += "w"


def Solution(S1, S2):
  global S3

  if S1[0] == "b" or  S2[0] =="b":
    return 1024
  elif S1[0] == "w" and S2[0] =="w":
    return 0
  elif S1[0] =="p" and S2[0] =="p":
    sum_quad_tree(S1[1:], S2[1:])
  elif S1[0] =="p":
    sum_quad_tree(S1[1:], S2)
  elif S2[0] =="p":
    sum_quad_tree(S1, S2[1:])

Solution("ppwwwbpbbwwbw", "pwbwpwwbw")
print(S3)

쿼드 트리 압축

#쿼드 트리 함수 정의
def quad_tree(x, y, n):
    global matrix, answer #배열 정보와 답이 될 변수를 끌어옴
    color = matrix[y][x] #첫 색깔(흑백)과 나머지 색이 같아야함
    double_break = False #for문 탈출용 double_break

    for i in range(x, x+n):
        if double_break:
            break

        for j in range(y, y+n):
            if matrix[j][i] != color: #하나라도 틀릴시에 재귀문 생성

                answer += '(' #문 열고
                quad_tree(x, y, n//2) #2사분면
                quad_tree(x + n//2, y, n//2) #1사분면
                quad_tree(x, y + n//2, n//2) #3사분면
                quad_tree(x + n//2, y + n//2, n//2) #4사분면
                answer += ')' #문 닫고

                double_break = True #탈출!
                break

    if not double_break:
        if matrix[y][x] == 1: #검정색이라면
            answer += '1'
        else:
            answer += '0' #흰색이라면


N = int(input())
matrix = []
answer = ''

for _ in range(N):
    matrix.append(list(map(int, str(input()))))

quad_tree(0,0,N)
print(answer)