22년 11월 22일 TIL 알고리즘

알고리즘

어떤 문제의 해결을 위하여, 입력된 자료를 토대로 하여 원하는 출력을 유도하여 내는 규칙의 집합. 여러 단계의 유한 집합으로 구성되는데, 각 단계는 하나 또는 그 이상의 연산을 필요로 한다. [표준국어대사전]

 

어떤 문제가 있을때, 그것을 해결하기 위한 여러 동작들의 모임입니다.

그런데, 하나의 문제를 풀기 위해서는 다양한 방법이 있을 수 있습니다.

 

알고리즘을 공부하는 이유

• 개발자는 프로그램을 만드는 직업입니다. 즉, 좋은 개발자가 되려면? 좋은 프로그램을 구현할 줄 알아야 합니다.
• 좋은 프로그램이란? 적은 공간을 이용해서 빠른 속도로 수행되는 프로그램입니다!
• 그런 프로그램을 만들기 위해서는 경우에 따라 특정 자료구조나 접근방법을 사용해야 합니다. 즉, 프로그램을 잘하기 위해서는 여러 자료구조와 방법들을 배우고 익혀야 좋은 프로그램을 만들 수 있습니다.
• 막연히 개발만 하다보면 좋은 코드를 만들지 못합니다! 자료구조와 알고리즘에 대해서 배워 더 좋은 프로그램을 만들어 보자구요!

좋은 회사에 취직하고 싶어요!

• 수많은 회사들이 코딩테스트를 통해 개발자를 구인하고 있습니다. 카카오, 삼성, 구글 등 국내외 유망 IT 기업들 외에도 많은 스타트업까지 코딩테스트를 개발자의 필수 관문으로 만들고 있습니다.
• 그러나, 엄청나게 어려운 수준의 문제를 출제하진 않습니다.
• 기초적인 지식과 해결책으로 적절한 사고를 할 수 있는지에 대해 검증하기 위함이므로, 5주차 동안 잘 따라오신다면 충분히 해결하실 수 있으리라고 생각합니다.
• (그렇다고 이런 문제를 항상 풀어야 하는 것은 아닙니다. 취업하고부터는 이미 잘 만들어진거 쓰시면 됩니다 🙂)

---

1. 시간 복잡도

• 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계
• 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것
• 우리는 시간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘

 

2. 공간 복잡도

• 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계
• 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것
• 우리는 공간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘

 

3. 점근 표기법

알고리즘의 성능을 수학적으로 표기하는 방법입니다. 알고리즘의 “효율성”을 평가하는 방법입니다. 점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 저희가 지금까지 이 함수는 N 정도의 시간과 공간이 걸리겠구나 하면서 분석했던 게 점근 표기법의 일종이라고 말할 수 있습니다.

 

점근 표기법의 종류

1. 빅오(Big-O)표기법 : 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대한 표기입니다.

빅오 표기법으로 표시하면 O(N) 의 시간복잡도를 가진 알고리즘이다 라고 표현할 수 있습니다.

대부분의 알고리즘을 빅 오 표기법으로 분석합니다.

대부분의 입력값이 최선의 경우일 가능성은 굉장히 적을 뿐더러, 우리는 최악의 경우를 대비해야 하기 때문입니다.

 

2. 빅 오메가(Big-Ω) 표기법 : 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대한 표기입니다.

빅 오메가 표기법으로 표시하면 Ω(1) 의 시간복잡도를 가진 알고리즘이다 라고 표현할 수 있습니다.

---

문자열 뒤집기 - 모두 같은 숫자로 만들기 위해 뒤집는 횟수 세기

input = "011110"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
    count_turn_zero = 0		#0으로 뒤집는 횟수를 담을 변수 선언
    count_turn_one = 0		#1로 뒤집는 횟수를 담을 변수 선언

    if string[0] == '0':				#만약 string의 첫번째 요소가 0이라면
        count_turn_zero += 1			#count_turn_zero(0으로 뒤집는횟수) 1 추가
    elif string[0] == '1':				#만약 string의 첫번째 요소가 1이라면
        count_turn_one += 1				#count_turn_one(1로 뒤집는횟수) 1 추가

    for n in range(len(string) - 1):		#string의 길이 - 1 만큼 반복함
        if string[n] != string[n + 1]:		#만약 string의 n번째 요소 와 n+1번째 요소가 같지 않다면
            if string[n] == '0':			#string의 n번째 요소를 0으로 만들고
                count_turn_one += 1			#count_turn_one(1로 뒤집는횟수) 1 추가
            if string[n] == '1':			#string의 n번째 요소를 1으로 만들고
                count_turn_zero += 1		#count_turn_zero(0으로 뒤집는횟수) 1 추가
	
    return count_turn_zero, count_turn_one	#모두 0또는 1로 만들기 위해 뒤집는 횟수 반환


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

결과값 : (1,2)

시간 복잡도 : 비교 연산 2회(+2), range(len(string)-1)의 길이만큼 아래 연산 실행(N),

비교 연산 1번 실행, 비교 연산 2번 실행 = 3N + 2

 

공간 복잡도 : string의 길이 = 6, 변수 count_turn_zero, count_turn_one 2개 = 총8 만큼의 공간

 

빅 오 표기법 : O(N)