하나의 문제를 푸는 알고리즘은 다양할 수 있다.

정수의 절대값 구하기

1, -1 -->> 1

방법1: 정수값을 제곱한 값에 다시 루트를 씌우기

방법2: 정수가 음수인지 확인 해서, 음수일 때만 -1을 곱하기

알고리즘 시간 복잡도의 주요 요소

반복문이 지배한다.

생각해보기: 자동차로 서울에서 부산을 가기 위해, 다음과 같이 항목을 나누었을 때, 가장 총 시간에 영향을 많이 미칠 것 같은 요소는?

예:

자동차로 서울에서 부산가기

1. 자동차 문열기
2. 자동차 문닫기
3. 자동차 운전석 등받이 조정하기
4. 자동차 시동걸기
5. 자동차로 서울에서 부산가기
6. 자동차 시동끄기
7. 자동차 문열기
8. 자동차 문닫기

다른 것은 시간이 얼마 안 걸리나, 5번은 시간 소요에 가장 많이 미친다.

마찬가지로 프로그래밍 알고리즘에서도 시간복잡도에서 if문을 몇개 썼을 때, 변수를 몇개 선언 그런 것이 문제가 아니라, 반복문을 어떻게 구성했는지에 따라 알고리즘의 성능,시간이 달라질 수 있다.

반복문으로 만든 알고리즘 안 반복의 횟수가 굉장히 차이가 나기 때문에 시간복잡도가 차이가 많이 난다.

알고리즘 성능 표기법

Big O(빅-오)표기법: O(N)

• 알고리즘 최악의 실행 시간을 표기
• 가장 많이/일반적으로 사용한다.
• 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이다.

오메가 표기법

최상의 실행 시간을 표기

세타 표기법

평균 실행 시간을 표기

대문자 O 표기법

빅 오 표기법, Big-O 표기법 이라고도 부른다.

O(입력)

• 입력 n 에 따라 결정되는 시간 복잡도 함수
• O(1), O(logn), O(nlogn), O(n2),O(2n),(O(n!)등으로 표기한다.
• 입력 n의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있다.
• O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!)

실제 실행시간은 다 다를 수가 있다.

그런데 다른 알고리즘과 비교를 하면, 어떤 알고리즘은 O(n), 내가 알고리즘은 O(1)

이라고 했을 때, O(n)보다 성능이 좋다라고 할 수 있다.

단순하게 입력 "n"에 따라, 몇번 실행 되는지를 계산하면 된다.

표현식에 가장 큰 영향을 미치는 n의 단위로 표기한다.

n이 1이든 100이든, 1000이든, 10000이든 실행을

무조건 2회(상수회) 실행한다: O(1)

예) n이 100인데,

코드는 if를 쓴다고 가정하자.

if n > 10:

   print(n)

이런 코드라고 했을 때, 만약에 n에 1,100,1000 숫자던 간에 코드 두 줄만 실행하면 끝이다.

n에 따라서 변경되는 것이 없다.

n에 따라, n번, n + 10 번, 또는 3n + 10 번등을 실행한다 : O(n)

for index in range(n):

print(index)

n이 1번이면 반복문이 1번 밖에 안된다.

근데 n이 10번이면 10번 실행한다.

n이 10000번이면 10000번 실행한다. 이럴 때는 O(n)이라고 표기한다.

n에 따라, n²번, n² + 1000 번, 100n² - 100번,또는 300n² + 1번등 실행한다: O(n²)

variable = 1

for i in range(300):

	for num in range(n):

 		for index in range(n):

                      	print(index)

빅오 입력값 표기 방법

예 :

만약 시간 복잡도 함수가 2n² + 3n 이라면

1.가장 높은 차수는 2n²

2.상수는 실제 큰 영향이 없다.

3.결국 빅 오 표기법으로는 O(n²)

연습1: 1부터 n까지의 합을 구하는 알고리즘 작성해보기

//방법 1
def sum_all(n):
	total = 0
	for num in range(1, n + 1):
  		total += num
return total
sum_all(100)

//방법 2
n(n+1)
------
   2   
  
def sum_all(n):
  return int(n * (n + 1)/2)

sum_all(100)

5050

방법 1을 시간복잡도로 생각해보면, 반복문은 실제로 n번 돌기에 시간복잡도는 n이 된다.

시간 복잡도는 n이고 빅오 표기법으로는 O(n)이다.

이에 반해, 방법2는 1이고, 빅 오 표기법은 O(1)이다.

방법1과 방법2 중에 어떤 것이 더 좋냐면,

O(1)이 성능이 더 좋다고 볼 수 있다.

참고: https://fastcampus.co.kr/courses/210773/clips/

Node 구현

• 보통 파이썬에서 링크드 리스트 구현시, 파이썬 클래스를 활용

링크드 리스트의 장단점(전통적인 C언어에서의 배열과 링크드 리스트)

1. 장점

• 데이터 공간을 미리 할당하지 않아도 된다.
• (배열은 미리 데이터 공간을 할당해야 한다)

1. 단점

• 연결을 위한 별도 데이터 공간이 필요하므로,저장공간 효율이 높지 않다.
• 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다.
• 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요하다.

5.파이썬 객체지향 프로그래밍으로 링크드 리스트 구현하기

class Node:   //Node Class는 Linked List의 각 요소를 나타낸다.
//Node Class에서는 Data를 저장하는 data속성과 다음 Node를 참조하는 next 속성을 가지고 있다.
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def print_list(self):
        current_node = self.head
        while current_node:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("None")

# 사용 예제
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.print_list()

• 데이터를 제한적으로 접근할 수 있는 구조
• 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
• 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조

1.스택 구조

• 스택은 LIFO(Last In,First Out)또는 FILO(First In,Last Out)데이터 관리 방식을 따른다.

LIFO : 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책

FILO : 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책

책을 쌓는다고 생각했을 때, 마지막에 꺼내는 것이 첫번째로 쌓은 책과 같다고 생각하면 된다.

• 대표적인 스택의 활용

컴퓨터 내부의 프로세스 구조의 함수 동작 방식

주요 기능

• push(): 데이터를 스택에 넣기
• pop(): 데이터를 스택에서 꺼내기

#재귀 함수 //자기 함수에서 함수를 호출 하는 것
def recursive(data):
   if data < 0:
      print ("ended")
    else:
      print (data) //0이상 이면 해당 인자 출력
      recursive(data -1) //인자에서 -1 후, 함수 호출
      print("returned",data)
      
     recursive(4)
    
    //Process stack구조에서 recursive에서 함수가 저장이 된다.
    
      
     

자료 구조 스택의 장단점

• 장점

1.구조가 단순해서, 구현이 쉽다.

2.데이터 저장/읽기 속도가 빠르다.

• 단점(일반적인 스택 구현시)

1.데이터 최대 갯수를 미리 정해야 한다.

파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능하다.

2.저장 공간의 낭비가 발생할 수 있다.

미리 최대 갯수만큼 저장 공간을 확보해야 한다.

스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적이다.이 경우 위에서 열거한 단점이 있을 수 있다.

<파이썬 리스트 기능에서 제공하는 메서드로 스택 사용해보기>

append(push),pop 메서드 제공

data_stack = list()
data_stack.append(1)
data_stack.append(2)
data_stack //[1,2]
data_stack.pop() //2  

<프로그래밍 연습>

연습1. 리스트 변수로 스택을 다루는 pop,push 기능 구현해보기(pop,push 함수 사용하지 않고 직접 구현해보기)

stack_list = list()

def push(data):
  stack_list.append(data)
  

def pop():
  data = stack_list[-1]
  del stack_list[-1]
  return data

for index in range(10):
  push(index)
  
pop() //9

참고:https://fastcampus.co.kr/

줄을 서는 행위와 유사 하다.

가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조

음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일

큐는 FIFO(Fist-In,First-Out)또는 LILO(Last-In,Last-Out)방식으로써 스택을 꺼내는 순서가 반대다.

여기서 처음들어온 순부터 4,5,8 이 된다. 여기서 4를 꺼내면 5가 노란색으로 온다.

용어

Enqueue: 데이터를 넣는 기능

Dequeue:데이터를 꺼내는 기능

import queue

data_queue = queue.Queue()

data_queue.put("funcoding")
data_queue.put(1)

data_queue.qsize() //2   (데이터의 갯수 확인)

data_queue.get() //queue에서는 데이터를 꺼낼 수만 있지, 어떤 데이터를 꺼내달라는 요청을 못함.
//data_queue.get() 하면 먼저 넣은 'funcoding' 꺼내기

data_queue.qsize() //1

data_queue.get()  //두번째 값을 꺼낸다 즉, 1을 꺼낸다.

data_queue.qsize() //0이 된다.

LifoQueue()로 큐 만들기(LIFO)

import queue

data_queue = queue.LifoQueue()

data_queue.put("funcoding")
data_queue.put(1)

data_queue.qsize() //2

data_queue.get() //Lifoqueue는 Lifo이므로,마지막(1)부터 빠져나간다.

PriorityQueue()로 큐 만들기

각각의 데이터 마다, 우선순위 번호를 지정 가능하다. 데이터를 추출할 때는 가장 우선순위가 높은 데이터가 추출 하게끔 할 수 있다.

import queue

data_queue = queue.PriorityQueue()

data_queue.put((10,"korea")) //튜플로 해서 쌍으로 데이터를 넣게 되어 있다. 첫번째 값은 우선순위 두번째가 우선 순위다.
data_queue.put((5, 1)) //이렇게 삽입하면, 우선순위 5에 값은 1이다.
data_queue.put((15, "china"))

data_queue.qsize() //3

data_queue.get() //(5,1) //우선 순위가 낮은 것부터 나온다.
data_queue.get() //(10,'korea')

참고: 어디에 큐가 많이 쓰일까?

운영체제에서 멀티 테스킹을 구현하기 위해서 프로세스 스케쥴링 방식 구현하기 위해 많이 사용된다.

연습문제 1. 리스트 변수로 큐를 다루는 enqueue,dequeue 기능 구현해보기.

queue_list = list()



def enqueue(data) 데이터를 넣는 함수
queue_list.append(data)

def dequeue()
data = queue_list[0]
del queue_list[0]
return data


for index in range(10):
  enqueue(index)
  
  len(queue_list) // 10
  
  dequeue() 1부터 순차적으로 10까지 

참고:https://fastcampus.co.kr/

-데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조

-파이썬에서는 리스트 타입이 배열 기능을 제공하고 있다.

배열이 필요한 이유

• 같은 종류의 데이터를 효율적으로 관리하기 위해 사용
• 같은 종류의 데이터를 순차적으로 저장

배열의 장점

-빠른 접근 가능

배열의 단점

-추가,삭제가 쉽지 않다.

-미리 최대 길이를 지정 한다.

<파이썬과 C 언어의 배열 예제>

C언어

3개의 공간을 가진 것 처럼 선언 되어 있다.

3개 이상 데이터를 넣을려면, 변수 재 지정 해야한다.

include 

int main(int argc, char * argv[])
{
  char country[3] = "US";
  printf ("%c%c\n", country[0], country[1]);
  printf ("%s\n", country);
  return 0;
}

파이썬

즉시, 데이터 추가 가능.

country = 'US' 
print(country) US

country = country + 'A'
print(country) USA

파이썬의 배열

• 파이썬 리스트 활용

//1차원 배열: 리스트로 구현시
data = [1,2,3,4,5]
print(data) //[1,2,3,4,5]

//2차원 배열: 리스트로 구현시
data = [[1,2,3],[4,5,6],[7,8,9]]
data //[[1,2,3],[4,5,6],[7,8,9]]

print (data[0]) //[1,2,3]
print (data[0][0])//1
print (data[0][1]) //2
print (data[1][0]) //4

<연습문제>

연습 1. 위의 2차원 배열에서 9,8,7 순서로 출력해보기

print(data[2][2],data[2][1],data[2][0])

연습 2. 다음에서 'M'이 몇 번 나왔는지 빈도수 출력하라.

m_count = 0
for data in dataset:
   for index in range(len(data)):
      if data[index] == 'M':
        m_count += 1
        
print(m_count)//38

참고: https://fastcampus.co.kr/