<알고리즘, 자료구조 1주차> 알고리즘, 개발환경, 시공간복잡도, 점근표기법

학습 내용 요약

1. 알고리즘
2. 개발 환경 디렉토리
3. 시공간복잡도
4. 점근표기법

1. 알고리즘

1) 정의
알고리즘이란 문제를 해결하는 여러 동작의 모임이다.

2) 배우는 이유
우리가 알고리즘을 배워야 하는 이유는 프로그램을 구현할 때, 최소한의 메모리를 소모하면서 가장 빠른 연산을 할 수 있도록 만들어야 하기 때문이다. 즉, 매순간 최적의 경로를 탐색하기 위해 알고리즘을 연구하는 것이다.

2. 개발 환경 디렉토리

1) 디렉토리 생성 및 설정 규칙

• 파일 및 폴더명은 파악하기 쉽게 작성
• 파일 및 폴더명에 특수문자를 넣을 경우 '_'만 사용
• 협업 시, 공동 규칙에 따라 파일 및 폴더 관리

3. 시공간복잡도

1) 시간복잡도
(1) 정의
시간복잡도란 입력값의 양에 따라 문제 해결 시간이 얼마나 걸리는지 알아보는 것으로 입력값과 문제 해결 시간의 상관관계를 말한다. 여기서 입력값이란 함수에서 인자로 들어오는 값인데 크기가 변할 수 있는 값을 지칭한다.

(2) 관련 사항

• 입력값의 길이: N
• 1 연산 = 각 줄 1번 실행
• 시간복잡도 비교 시, 상수는 제외하고 N의 지수 비율로 비교!

list = [1,2,4,5] 	 -> 배열의 길이 = 입력값의 길이 = N
for num in list: 	 -> N만큼 연산 실행
	if num %2 ==0:	 -> 비교 연산 1번 실행
    sum = num	 	 -> 대입 연산 1번 실행
    			 => N x (비교 연산 1 + 대입 연산 1) = 2N의 시간

2) 공간복잡도
(1) 정의
공간복잡도란 입력값의 양에 따라 문제 해결에 쓰이는 공간이 얼마나 늘어나는지 보는 것으로 입력값과 문제 해결에 쓰이는 공간의 상관관계를 말한다.

(2) 관련 사항

• 1 공간 = 변수에 저장하는 데이터의 양
• 공간 복잡도가 더 작다고 해서 더 좋은 것 No!
• 대부분의 알고리즘 성능은 공간에 의해 결정되지 않음. 따라서, 시간 복잡도를 더 신경써야 함.
  

alphabet = ['a','b','c','d']	-> 4공간
index = 0			-> 1공간

4. 점근표기법

1) 정의
알고리즘의 성능을 수학적으로 표기한 것으로 알고리즘의 효율성을 평가하는 방법이다. 이는 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현한다.

2) 종류
(1) 빅오 표기법
입력값에 따라 최악의 성능이 나올 때 어느 정도의 연산량이 걸리는지 표기하는 방식이다. 표시 기호는 O(N)이다.

(2) 빅오메가 표기법
빅오 표기법과 반대로 최선의 성능이 나올 때 어느 정도의 연산량이 걸리는지 표기하는 방식이다. 표시 기호는 Ω(1)이다.

※ 입력값이 단일 변수인지 배열인지 등에 따라 연산량이 달라지고, 그로 인해 알고리즘 복잡도도 달라짐

기억할 점

• 입력값에 비례해서 복잡도가 얼마나 늘어날지 파악하자. (1? N? NxN?)
• 공간복잡도보다 시간복잡도를 더 줄이기 위해 고민하자.
• 최악의 경우 얼마의 시간이 소요될지(빅오 표기법)에 대해 고민하자.

알고리즘의 경우 거의 모든 알고리즘을 빅오 표기법으로 분석한다. 왜냐하면, 대부분의 입력값이 최선의 경우일 가능성은 굉장히 적기 때문에 최악의 경우를 대비해야 하는 것이다.

어렵거나 완전히 이해 못한 내용
알고리즘이 중요하다는 것은 알겠지만, 예비 주니어 개발자여서 실행되는 코드를 만드는 데만 집중하고 있다. 좀 더 정교하고 깔끔한 코드를 만들기 위한 고민은 그래도 항상 하는 습관을 들이도록 하자.

시공간복잡도의 정의는 이해했지만, 아직 입력값이 변할 수 있는 값이라는 말이 무슨 뜻인지 명확하게 알지 못한 느낌이다. 그리고 1연산의 의미를 좀 더 명확하게 이해할 필요가 있다.