🤍[알고리즘] SW Expert 파이썬 SW문제해결 기본 - LIST1 강의

알고리즘

알고리즘
: 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법

알고리즘 표현법

• 슈도코드
• 순서도

알고리즘 성능 분석

1. 정확성
   얼마나 정확하게 동작하는가
2. 작업량
   얼마나 적은 연산으로 원하는 결과를 얻어내는가
3. 메모리 사용량
   얼마나 적은 메모리를 사용하는가
4. 단순성
   얼마나 단순한가
5. 최적성
   더이상 개선할 여지 없이 최적화되었는가

각 알고리즘의 성능을 분석할 필요가 있다.
-> 알고리즘 성능 분석의 기준으로 알고리즘의 작업량을 비교
ex) 1~100까지 합 구하는 문제
1. (1+2+....+100) = 99번 연산
2. 100*(1+100)/2 = 3번 연산
더하려는 범위가 클수록 연산 횟수의 차이가 커짐

알고리즘의 작업량 분석 방법

1. 실제 걸리는 시간을 측정
2. 실행되는 명령문의 개수를 계산

1번은 프로그램이 실행되는 환경에 따라 달라질 수 있으므로 2번을 기준으로 하여 시간복잡도를 측정하는 방법이 자주 사용된다.

알고리즘 1 시간복잡도 = 2n+1
알고리즘 2 시간복잡도 = 3

시간복잡도 표현 방법 - 빅-오(O) 표기법

: 시간복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시
계수는 생략하여 표시

O(2n+1) 
= O(2n) : 최고차항 2n만 선택
= O(n) : 계수 제거

O(2n^2 +10n+100) = O(n^2)
O(4)=O(1)

요소 수의 제곱수로 표현되는 시간복잡도를 가지는 알고리즘의 경우 연산수가 기하급수적으로 증가하기 때문에 유의해서 사용해야 한다.

따라서 시간복잡도가 N^2인 알고리즘 대신 logN인 알고리즘을 선택해야 한다.
시간복잡도가 필요한 이유!

List

python 소개

1. 미리 기계어로 컴파일해두는 것이 아니라 실행시마다 소스를 기계어로 번역해서 실행하는 인터프리터 방식이므로 느리지만 플랫폼에 상관없이 실행이 가능하다.
2. 객체지향 언어
3. IoT분야의 라즈베리파이, 빅데이터의 자료분석등에서 파이썬 관심 높아짐

예전에는 하드웨어 성능이 좋지 못해서 프로그램의 실행 속도가 크게 차이가 났음. 따라서 실행속도가 느린 파이썬 주목 못받다가
하드웨어 성능 개선으로 실행속도의 차이가 크지 않게되면서 개발시간단축에 관심이 집중되면서 파이썬 주목받기 시작

변수

1. 파이썬에서 모든 자료는 객체로 참조형 변수로 처리.
   Java나 C에서 사용되는 기본형 타입 변수도 파이썬에는 객체
2. 변수의 선언은 따로 없음
   변수값을 초기화 시 변수가 메모리에 생성
   하나의 변수에 다른 타입의 값을 변수에 저장할 수 있음.

a=3
a="hello"

모든 변수는 참조형 타입의 변수로 실제 데이터가 저장되어 있는 메모리의 주소를 저장한다.
변수의 타입이 고정되어있는것이 아니고 저장되어 있는 데이터 타입에 따라 변수 타입이 결정됨.

자료형

파이썬의 변수에는 함수, 클래스 등 모든것을 저장할 수 있다.

• int
  사용할 수 있는 정수크기에 제한이 없다. 메모리가 허용가능한 무한대의 정수까지도 사용할 수 있다.

여러가지 자료구조 지원

1. 다수의 데이터를 저장할 수 있는 컨테이너
   

• tuple
  순서가 있는 데이터의 묶음. 순서가 있으므로 중복 데이터 허용
  데이터 추가, 수정, 삭제할 수 없음.
  파이썬에서 데이터를 ,로 나열하면 기본적으로 튜플로 인식. 이 과정을 packing이라고 한다.
  튜플로 묶여있는 데이터를 낱개로 꺼내는 작업을 unpacking
• list
  순서가 있는 데이터의 묶음. 중복 데이터 허용
  데이터 추가, 수정, 삭제 가능
  튜플과 리스트는 흡사하지만 차이는 데이터 변경 여부
  리스트보다 튜플이 처리속도가 빠르기 때문에 값을 변경할 필요가 없다면 튜플 사용
• dictionary
  키와 값의 쌍으로 하나의 데이터를 구성.
  순서가 없고 키를 기준으로 데이터를 구분하기 때문에 키의 중복은 허용안됨, 값의 중복은 중복 허용
  데이터 변경 가능.
• set
  순서 없음. 데이터 중복 허용하지 않음
  순서가 없으므로 인덱싱, 슬라이싱은 할 수 없지만 데이터 추가, 수정, 삭제가능.

dictionary의 키와 set은 중복을 허용하지 않는다.
내부적으로 중복을 처리하는 과정에서 패싱 기법이 사용되는데, 키와 set은 값이 변경될 수 없는 불변 객체만 사용될 수 있다.

List 소개

• 배열(List)
  : 같은 타입 변수들을 하나의 이름으로 열거하여 사용하는 자료구조
  • 파이썬의 list는 C나 자바의 배열과 비슷한 자료구조
  • 하나의 변수를 통해서 대량의 데이터를 효율적으로 처리할 수 있다.

List 사용방법

파이썬의 변수

• 별도의 선언방법이 없으며 변수에 처음 값을 할당할 때 생성
• 값을 초기화하기 전에, 변수를 미리 만들어 두어야 할 경우를 대비해 공백 리스트를 생성하는 2가지 방법 제공

# 방법 1
num=[]
#방법 2
arr=list()

배열과 리스트의 차이점

배열보다 리스트가 사용하기 편리

2차원 리스트: 리스트 안에 원소로 리스트가 들어감

arr=[[1,2],[3,4],[5,6]]

리스트는 순서를 가진 집합으로 시퀀스(Sequence)자료형 중 하나.

시퀀스 자료형

• 순서가 존재하므로, 인덱싱과 슬라이싱의 연산 모두 적용가능
  • 인덱싱
    : 시퀀스 자료형에서 하나의 요소를 인덱스 연산자를 통하여 참조하는것

  arr=[4,5,6,7,8,9]
  arr[0] #4
  arr[-1] #9

  리스트 범위를 벗어난 인덱스 사용시 인덱스 에러가 발생
  • 슬라이싱
    : 시퀀스 자료형의 원하는 범위를 선택하는 연산

  arr=[4,5,6,7,8,9]
  arr[1:3] #[5,6]
  arr[:3] #[4,5,6]
  arr[1:] #[5,6,7,8,9]
  arr[:] #[4,5,6,7,8,9]

• 시퀀스 자료형에 사용할 수 있는 함수와 연산 사용가능
  
  

리스트 함축(List Comprehension)

수학에서 집합을 정의하는 표현식과 유사
ex) 10보다 작은 짝수들의 집합을 원소로 하는 리스트

mylist=[2,3,4,5,6]
newlist=[i for i in mylist if i%2==0]

리스트 함축에서 if문을 생략할 수 있고 for문과 if문쌍은 추가적으로 더 작성할 수도 있다.

Exhaustive Search

완전 검색 소개

완전검색(Exhaustive Search)
: 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법

• Brute-force 혹은 Generate-and-Test 기법이라고도 불린다.
• 모든 경우의 수를 테스트 한 후, 최종 해법을 도출함
• 일반적으로 경우의 수가 상대적으로 작을 때 유용함
• 모든 경우의 수를 생성하고 테스트하기 때문에 수행속도는 느리지만, 해답을 찾아내지 못할 확률이 적음
• 주어진 문제를 풀때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는것이 바람직하다.

순열

순열(Permutation)
: 서로 다른 것들 중 몇개를 뽑아서 한줄로 나열하는것

• 서로다른 n개 중 r개를 택하는 순열 : nPr
• nPr= n*(n-1)*(n-2)*....*(n-r+1)
• nPn=n!
• n!=n*(n-1)*(n-2)*....*2*1

Greedy Algorithm

탐욕 알고리즘이란?

탐욕 알고리즘(Greedy Algorithm)
: 최적해를 구하는데 사용되는 근시안적인 방법

• 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해나가는 방식으로 진행하여 최종적인 해답에 도달
• 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그것들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없음
• 일반적으로, 머리속에 떠오르는 생각을 검증없이 바로 구현하면 Greedy 접근이 됨

탐욕 알고리즘의 수행과정

1. 해 선택
   현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분 해 집합(Solution Set)에 추가함
2. 실행가능성 검사
   새로운 부분 해 집합이 실행가능한지를 확인.
   곧, 문제의 제약조건을 위반하지 않는지를 검사함
3. 해 검사
   새로운 부분해 집합이 문제의 해가 되는지를 확인.
   아직 전체 문제의 해가 완성되지 않았다면, 해 선택부터 다시 시작함.

탐욕 알고리즘적인 접근은 해답을 찾아내지 못하는 경우도 있다.

Sort

정렬 개요

정렬(Sort)이란
: 2개 이상의 자료를 특정 기준에 의해 작은값부터 큰 값(오름차순 : ascending), 혹은 그 반대의 순서대로(내림차순 : descending) 재배열하는것

키 : 자료를 정렬하는 기준이 되는 특정 값
ex) 서류를 번호대로 정렬하는 경우 : 서류번호가 키

대표적인 정렬 방식의 종류

• 버블 정렬 (Bubble sort)
• 카운팅 정렬 (Counting sort)
• 선택 정렬 (Selection sort)
• 퀵 정렬 (Quick sort)
• 삽입 정렬 (Insertion sort)
• 병합 정렬 (Merge sort)

버블 정렬

Bubble Sort
: 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식

정렬과정

1. 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동
2. 한 단계가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로 정렬됨
3. 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품모양 같아서 버블정렬

버블정렬의 시간복잡도 = O(n^2)
안쪽 반복문의 범위가 바깥쪽 반복문의 범위에 의해 제어되는것 유의

카운팅 정렬

Counting Sort
: 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘

정렬과정

• 정수나, 정수로 표현할 수 있는 자료에 대해서만 적용가능.
  각 항목의 발생 회수를 기록하기 위해, 정수 항목으로 인덱스되는 카운트들의 리스트를 사용하기 때문.
• 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야함.

시간복잡도 = O(n+k)
n: 리스트의 개수, k: 정수의 최대값

정렬 비교