[데브코스] TIL 1일차

 

자료형과 자료구조

1. 자료형(data type)
   - 문자열(str)
   - 리스트(list)
   - 사전(dict)
   - 순서쌍(tuple)
   - 집합(set)
   - …
2. 기본 자료형으로 웬만한 것들은 다 해결 가능한데, 왜 자료구조를 왜 알아야할까?
   - 더 효율적인,
   
   
3. 알고리즘
   - (사전적 정의) 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합
   - (프로그래밍) 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택

 

 

배열

1. 선형 배열(Linear Array)
   - 원소들을 순서대로 늘어놓은 것
   
   O(1)
   기능 1) 원소를 끝에 붙이기
   기능 2) 끝에서 원소 꺼내기
   
   O(n)
   기능 3) 원소를 중간에 삽입
   기능 4) 중간에 있는 원소 삭제
   기능 5) 원하는 원소의 인덱스 찾기
   *del vs. pop 차이

 

 

배열 - 정렬(sort)과 탐색(search)

1. 정렬(sort)
   1) A.sort(), sorted(A)
   
   A.sort() : A 배열 자체를 변환 → 파이썬 내장 함수
   sorted(A) : A 배열 변환한 결과를 리턴 → 리스트에 쓸 수 있는 메서드
   * 함수와 메서드의 차이
   2) reverse = True 내림차순
   
   3) key를 지정해 정렬 가능
   A.sort(key=lambda x:x[1])
   *lambda 정리
2. 탐색(search) 알고리즘
   1) 선형 탐색(Linear search) O(n)
   - 처음부터 원소를 비교해보는 것. 최악의 경우 모든 원소 비교 필요
   
   
   2) 이진 탐색(Binary search) O(logn)
   - 정렬되어 있는 리스트에서 원하는 수를 찾으려고 비교를 할 때마다 리스트를 반씩 줄임

def linear_search(L,x):
    i = 0
    
    while i < len(L) and L[i] != x:
        i += 1
        
    if i < len(L):
    	return i
    else:
    	return -1

 

 

 

재귀 알고리즘(recursive algoritms) - 기초

1. 재귀함수
   - 하나의 함수에서 자신을 다시 호출해 작업을 수행하는 것
   
   왜 재귀함수를 사용할까?
   - 생각보다 많은 종류의 문제가 재귀적으로 해결 가능해서…
   
   *그렇다면 효율성보다는 유용성때문에 채택하는가?
2. 예제
   1) 이진 트리
   2) 자연수의 합 구하기(1~n까지의 모든 자연수의 합?)
3. 재귀함수 필수 조건 : 종결 조건(이게 없으면 무한대로... 끝나지 않게됨)
   
   
4. 재귀 알고리즘은 효율적인가?(vs 반복문과 비교)

# 1. 재귀 버전(recursive version) O(n)
def sum(n):
    if n <= 1:
        return n
    else:
        return n + sum(n-1)



# 2. 반복 버전(iterative version) O(n)
def sum(n):
    s = 0
    
    while n >= 0:
    	s += n
        n -= 1
    
    return s

 

5. 추가 예제 - factorial

def what(n):
    if n <= 1:
    	return 1
    else:
    	return n*what(n-1)

 

 

 

재귀 알고리즘(recursive algoritms) - 응용

def combi(n,m):
    if n == m:
    	return 1
    elif m == 0:
    	return 1
    else:
    	return combi(n-1,m) + combi(n-1,m-1)

1. 조합의 수 (n개의 서로 다른 원소에서 m개를 택하는 경우의 수)
   문제 : n개의 서로 다른 원소에서 m개를 택하는 경우의 수
   재귀적 해결 : n-1개에서 m-1개를 택하는 경우의 수(특정한 하나의 원소 입장에서, 자신을 포함하는 경우) + n-1개에서 m개를 택하는 경우의 수(자신을 포함하지 않는 경우)
   
   *효율성 측면에선 비효율적…
   
   
2. 재귀 알고리즘의 유용성
   예제 1) 하노이의 탑 - 반복문으로는 어떻게 구현할지 감이 안옴

 

 

결국, 재귀는 효율성보단 유용성때문에 쓰인다는 점을 기억해야 할듯!

 

 

알고리즘의 복잡도(시간/공간적 자원을 얼마나 요구하는가?)

1. 시간 복잡도(Time complexity) - 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계
2. 공간 복잡도(Space complexity) - 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계
3. Big-O notation