프로그래머스 인공지능 데브코스 3기 수업내용 정리 #1(자료구조와 알고리즘)

Clay Ryu's sound lab·2021년 12월 7일

Note for 2021

목록 보기

1/33

오늘의 공부 요약 : 함수를 좀더 잘 이해하기 위한 좋은 방법은 다양한 사용의 예를 봐두고 정리해두는 것이라 느껴진다.

기초 자료형, 기본 데이터 타입에 대해서

문자열(str)
리스트(list)
사전(dict)
순서쌍(tuple), 집합(set)...

자료구조(data structure)는 왜 필요할까?

문제해결에 적합한 자료구조가 있기 때문이다.
가령 리스트 자료형 안에서 최대값을 가지는 값을 찾기 위해서는 리스트의 모든 값들을 따져봐야한다. 그렇게 되면 값들이 커질수록 연산의 시간은 오래걸리게 된다. 따라서 좀더 효율적인 문제해결을 위해서는 그에 적합한 자료구조를 찾는 것이 중요하다고 생각할 수 있다.

알고리즘(Algorithms)이란?

[사전적 정의] 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합
[프로그래밍] 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택

결론은 최적의 해법을 찾는 것!

자료구조1. 선형배열(Linear Array)

파이썬에서는 배열이 따로 존재하지 않고 리스트(list)라는 이미 존재하는 데이터 타입을 사용한다.
리스트는 서로 다른 종류의 데이터 타입을 원소로 가질 수 있다.

메소드1.원소 덧붙이기와 끝에서 꺼내기
L = list()
L.append()
L.pop()
상수의 시간이 걸리는 연산 O(1)

메소드2.원소 삽입하기와 원소 삭제하기
L.insert(3, 65) -> 3번째 위치에 65원소를 넣어라.
del(L[2]) -> 2번째 위치의 원소를 삭제하라.
pop 함수와 다른점은 값을 리턴하지 않는다는 것 같다.
리스트의 길이에 비례하는 연산 O(n)

메소드3.원소 탐색하기
L.index('a') -> 'a'원소의 인덱스 값을 리턴

<연습문제>
리스트L과 원소x가 주어질때 원소x가 L에 위치한 인덱스 값을 리턴하는 함수를 만들어라.
while pop구문을 활용해서 L.index(x) 값에 count 값에 더해서 answer리스트에 넣어주는 루프문을 만들어 해결했다.

알고리즘1. 배열의 정렬(sort)과 탐색(search)

정렬이란?
정해진 규칙에 따라 원소를 다시 나열하는 것
파이썬에서는 sorted()(내장함수)와 sort()(리스트의 메서드)로서 활용가능 하다.

sorted(iterable, key, reverse)순서로 입력 가능하다.

lambda는 함수를 한줄로 표현하는 방식이다. key값을 지정할때 매우 유용하다.

선형탐색(Linear Search)
리스트에서 탐색은 앞에서부터 모든 원소를 체크하므로 리스트의 길이에 비례하는 시간이 소요된다.O(n)

이진탐색(Binary Search)
탐색하려는 리스트가 크기 순으로 정렬이 되어 있는 경우에만 사용이 가능하다.
lower와 upper index를 정하고 middle을 그 중간 인덱스로 정한뒤에 middle의 값과 찾으려는 값을 비교한다.
만약 찾으려는 값이 middle의 값보다 크다면 lower값을 middle의 +1로 다시 정해주고 함수를 반복한다.
만약 찾으려는 값이 middle의 값보다 작다면 upper값을 middle의 -1로 다시 정해주고 함수를 반복한다.
실행할수록 탐색하는 요소들의 수가 반으로 줄어들기 때문에 소요시간은 O(logn)이다.

<연습문제> 이진탐색 구현하기
while문을 만들어 놓고 break나 return을 안만드는 실수를 했다.

 def solution(L, x):
     lower  = 0
     upper = len(L) - 1
     idx = -1
     target = x
     while lower <= upper:
          middle = (lower + upper) // 2
          if L[middle] == target:
              idx = middle
          elif L[middle] < target:
              lower = middle + 1 
          else:
              upper = middle - 1
      answer = idx
      return answer

알고리즘2.재귀 알고리즘(Recursive Algotithms)

재귀함수(recursive functions)란
하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것
이진트리에서의 탐색과 같이 계속해서 같은 작업을 반복하는 경우에 사용이 가능하다.
재귀 알고리즘은 recursive version을 iterative version으로 바꾸어 생각해볼 수 있다. 다만 재귀 알고리즘은 효율적인 측면에서 상대적으로 약한 모습을 보인다. 극단적으로는 모든 값을 더하는 함수를 구하는 것은 고등학교에서 배웠던 등차수열의 합으로서 계산하면O(n)을 O(1)으로까지 시간을 낮추어서 해결할 수 있다.

2-1.재귀 알고리즘의 응용

조합의 수 계산
mCn의 경우는 m-1Cn-1 + m-1Cn으로 이루어지므로 재귀 알고리즘을 이용해서 계산을 해볼수 있다.

재귀 알고리즘의 효율
재귀 함수를 호출하는 경우에 동적 계획법을 염두에 두어야 함수를 중복으로 호출하는 경우를 방직할 수 있다.

<연습문제> 이진탐색 구현
재귀함수의 종결문을 x not in L로 처리했다가 처리시간을 오버했다. 많은 양의 함수가 호출될 경우를 생각하지 못했다.
def binsearch(L, x, lower, upper):
	if : lower > upper
		return -1
	mid = (lower + upper) // 2
	if x == L[mid]:
		return mid
	elif x < L[mid]:
		return binsearch(L, x, lower, mid + 1)
	else:
		return binsearch(L, x, mid -1, upper)