알고리즘 성능평가 & 백준1969 DNA 문제 풀이

FOSCAR 알고리즘 스터디 1주차 2조 블로깅

 

알고리즘의 복잡도

 

1. 시간 복잡도 : 소스코드가 실행되는데 소요되는 시간

2. 공간 복잡도 : 소스코드가 실행되었을 때 사용되는 메모리 공간

 

프로그래밍에서는 위의 두 가지 복잡도가 낮을수록 좋다. 

 

그런데 위에서 설명한 정성적인 설명으로는 복잡도에 대한 수치적 비교우위를 정할 수 없다. 

 

우리는 이를 Big O(빅 오)라고 하는 함수적 표현을 통해 복잡도에 대한 개념을 수치적으로 표현할 것이다.

 

Big O 표기법 : 소스코드의 수행시간을 소스코드만을 통해 계산하고자 할 때 연산 횟수에 대한 함수로 표시하게 되는데 이 대 이 함수식의 최고차 항만을 고려하여 복잡도를 계산한 것이다. 

 

ex)

시간복잡도 = 3n^2 + 2n^2 + 9

라고 할 때 

이를 Big O포기법으로 나타내면 O(N^3)이라고 할 수 있다. 

 

 이때 최고차항 만을 고려하는 이유 : CPU의 연산 속도는 비교적 큰 수에 해당하므로 극한값에 대한 유횻값을 고려하는 것이 합리적이기 때문이다. 

 

그렇다면 알고리즘의 성능을 나타낼 수 있는 시간복잡도 함수에서의 최고차항으로 표현될 수 있는 함수들은 어떤 것들이 있을까?

 

좋음<-------------------------------------------------------------------------------------------------------------->나쁨

상수 O(1) , 로그(logN) , 선형 O(N) , 로그선형 O(NlogN) , 이차 O(N^2) , 삼차 O(N^3) , 지수 O(2^N)

 

프로그램에 입력되는 자료 N의 범위에 따라 연산 횟수가 많아질수록 좋지 못한 코드이고(입력 자료 대비 수행시간이 오래 걸림) 반대로 자료 N의 범위가 무엇이든 간에 연산 횟수가 일정한 연산 횟수에 수렴하거나 더 이상 증가하지 않는 경우 좋은 코드(수행시간이 적게 걸림)라고 할 수 있다. 

 

알고리즘 시간 복잡도 계산 예제

예제 1) 리스트에 있는 모든 항들의 값을 더하는 프로그램

 

#########################

array= [1,2,3,4,5,6]

summary = 0

#########################

for x in array:

    summary += x

#########################

print(summary)

 

이의 소스코드에서 가운데 for문이 있는 구간에서는 자료의 갯수 N에 따라 그에 비례하여 덧셈 연산이 반복될 것이다.

 

이외의 부분에서는 프로그램이 한번 실행될 때 자료의 갯수에 상관없이 한번만 실행되는 상수시간의 연산시간이 소요될 것이다. 

 

우리는 앞서 배웠듯이 극학의 개념을 적용하여 최고차항에 대한 연산 횟수르 고려하기 때문에 단지 for문에 의한 연산 횟수 의 시간복잡도 O(N)이라고 할 수 있다. 

 

 

예제2) 2중 반복문

 

array =[1,2,3,4,5]

###########################

for x in array:

    for y in array:

        k = x*y

        print(k)

 

해당 예제 역시 이중  for문에 의한 연산시간 만 고려하면 되기 때문에 O(N^2)의 시간복잡도를 갖는다. 

 

 

만약 for문안의 연산이 상수시간정도 걸리는 연산들이 있다고 해도 결과적으로 N*N(1+2+...)이기때문에 이 역시 O(N^2)의 시간복잡도를 갖는다고 할 수 있다.

 

 

 

수행시간 실측 Tip

 

CPU는 대략 1초에 5000만번의 연산을 수행한다. 

 

5억 번의 연산 횟수 기준, python의 경우 5~15초(코딩테스트에서 pypy를 지원한다면 수행시간이 단축될 수도 있지만 항상그런것은 아니다.) , C언어의 경우 1~3초 가량의 시간이 소요된다.

 

코딩테스트에서는 주어진 시간제한이 없다면 약 1~5초 정도라고 생각해야 한다. 

시간 복잡도를 고려한 설계 매뉴얼은 대략 다음과 같다.

 

만약 문제에서 시간제한이 1초라고 했을 때

 

N의 범위가 500인 경우 O(N^3)으로 설계해야 한다. 

N의 범위가 2,000인 경우 O(N^2)으로 설계해야 한다. 

N의 범위가 100,000인 경우 O(NlogN)으로 설계해야 한다. 

N의 범위가 10,000,000인 경우 O(N)으로 설계해야한다. 

 

즉, N의 범위가 많을수록 일반적인 연산시간이 증가할 수 있기 때문에 알고리즘 성능시간을 줄일 수 있는 방향으로 설계해야 한다.  

 

알고리즘 문제 해결 과정

 

1. 지문 읽기 및 컴퓨터적 사고

2. 요구사항(복잡도) 분석 

3. 문제 해결을 위한 아이디어 찾기

4. 소스코드 설계 및 코딩

 

Python에서 수행시간 측정 방법

 

import time

#time.time()은 현재 시간값을 가져와 준다.

start_time = time.time() # 현재시간(알고리즘이 시작되기 직전)을 start_time변수에 저장한다.

###########################

#알고리즘 구현부

###########################

end_time = time.time() # 현재시간(알고리즘이 끝난 직후)을 end_time변수에 저장한다.

print("time: ", end_time - start_time)

 

DNA 문제 1969번

 

 

• 문제링크 : https://www.acmicpc.net/problem/1969 

1969번: DNA

 

• 문제 풀이

그림을 봐야 이해하기 편해서 인용해왔습니다.!

 

 

문제를 절차상으로 이해하면 까다롭지만 정성적으로 이해해보았을 때에는 다음과 같다. 

 

여러개의 DNA 묶음이 중첩되었을 때 이들을 합성하여 대표 DNA하나를 추출한다고 생각하면 된다. 

 

그런데 DNA하나를 추출해내는 규칙이 다수결의 원칙을 활용한다는 것이다.(같은 자리라고 하면 많은 수를 가진 염가 우위를 점하게 되는 것이다. 

 

두번째 규칙은 가장 빈도수가 많은 염기를 제외한 다른 염기들의 (여기선 불순불이라고 칭하겠다.) 숫자가 최소여야 한다. 

불순물의 총갯수를 이 문제에서는 해밍거리라고 한다.

 

이러한 규칙들을 바탕으로 다음의 소스코드를 구성할 수 있다.  

 

추가적으로 간단하지만 시간복잡도도 설계 및 계산해보았다.  

 

# 문제의 목적은 여러가지 염기서열들 중에 각자리별로 최다 빈도를 갖는 문자를 선정하여

# 하나의 대표 염기서열을 선정하는데에 있다.

# 그 방법으로 최다 빈도 문자를 제외한 문자들의 갯수의 최솟값(HD변수에 추가)을 찾는 것을 선택했다.

#시간복잡도를 계산하였을 떄 N의 범위를 최대 1000으로 잡을 수 있기 떄문에

# O(N^2)의 시간 복잡도로 설계하였을 때 1초이내에 실행된다고 할 수 있다.

n,m = map(int, input().split()) #m개의 문자로 이뤄진 묶음을 n묶음 만들겠다.

arr=[]

result = ''

for i in range(n):

    arr.append(list(map(str,input()))) #m개의 문자들을 문자형으로 리스트로 n묶음 추가한다. 2차원 리스트

HD = 0 #최빈 문자를 제외한 다른 문자의 빈도수 합

for i in range(m):

    a,c,g,t =0,0,0,0

    #같은 m값에 대해 다른 DNA들을 검사하는 것이므로, 이차원 리스트 상의 첫번째 열을 검사한다.

    for j in range(n): #만약 j가 1이고 m도 1일 때

        if arr[j][i] =='T': # 1행 1열의 문자검사 //다음 for문에서는 2행 1열의 문자 검사//다음 for문에서는 3행 1열의 문자 검사

            t +=1 #맞으면 1추가

        elif arr[j][i] == 'A':

            a += 1

        elif arr[j][i] == 'C':

            c += 1

        elif arr[j][i] == 'G':

            g += 1

   

    #위의 for문이 끝나면 행렬(2차원 리스트)의 한열에 대해서 문자의 갯수파악이 완료된다. (소문자 변수 a,c,g,t에 저장됨)

    #일단 만약 1열에 대한 문자파악이 완료되었다 치면

    if max(a,g,t,c) ==a: # 1열에 대해서 어떤 문자가 가장 많이 나왔는지 파악하고

        result += 'A' #가장 많이 나온 문자에 대해 최종 DNA 서열에 추가시킨다.(최종 염기서열의 1열(첫번째 문자 획득))

        HD += g+t+c # 최빈 문자를 제외한 나머지 문자들의 빈도수를 HD이라는 변수에 저장한다.

    elif max(a,g,t,c) ==c:

        result += 'C'

        HD += a+g+t

    elif max(a,g,t,c) ==g:

        result += 'G'

        HD += a+t+c

    elif max(a,g,t,c) ==t:

        result += 'T'

        HD += a+g+c

# 안쪽 for문은 통해 1개의 세로줄씩 검사가 끝나고,

#가장 바깥 for문이 실행되었을 때 비로소 모든 열에 대한 검사가 끝나게 된다.

print(result)# 최종적으로 각 열마다의 최빈 문자열의 결과를 하나의 염기서열로 보여준다.

print(HD)# 최솟값을 연산한다.