1. 알고리즘(algorithm)

명칭의 기원

알고리즘은 9세기 페르시아의 수학자인 ~~무하마드 알콰리즈미~~(Muhammad al-Kwarizmi)의 이름을 라틴어화한 algorismus에서 따온 말

정의

어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 말한다.

구현 과정
- 문제 정의 → 모델 고안 → 명세 작성 → 설계 → 검증 → 분석 (복잡도 등) → 구현 →
  
  테스트 → 문서화

추상 자료형(Abstract Data Type)

List(배열) 논리적 개념

Stack Queue Tree Graph

문제 풀때 라이브러리 사용하지 않는다. List 사용할 때 max(), min(), index(),sort()

슬라이싱 쓰지말기

쓰지 말고, 공부할 때

기본적인 모든 로직을 구현해 보는 것이 좋다.

코딩할 떄 쓰는 언어적 표현

for, while(반복), if-else(분기) 이거 말고 쓰이는 게 없다.
수식은 피연산자와 연산자
함수호출도 수식

일일이 구현해보고 장단점 파악, 잘 알고 씨는 것

for append

<알고리즘>

유한한 단계를 통해 문제를 해결하기 위한 절차나 방법이다.
주로 컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법을 말한다.
간단한게 다시 말하면 어떠한 문제를 해결하기 위한 절차라고 볼 수 있다.

같은 일을 하는 서로 다른 코드들 중에 어떤 것이 더 좋은 코드인가?? = 효율적인 알고리즘

ex) 1~100까지의 합을 구하는 문제

슈더코드와 순서도

def CalcSum(n):
    sum = 0
    for i in range(1, n+1):
        sum += sum + i
    return sum

알고리즘 성능은 무엇으로 측정하는가

aps과정의 목표 중의 하나는 보다 좋은 알고리즘을 이해하고 활용하는 것이다.
무엇이 좋은 알고리즘인가?
- 정확성 얼마나 정확하게 동작하는가
- 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가 : CPU할당량 ==> 시간과 관련
- 메모리 사용량 : 얼마나 적은 메모리를 사용하는가 (자료를 구동하는 데 있어서 필요한 메모리)
- 단순성 : 얼마나 단순한가
- 최적성 : 더 이상 개선할 여지없이 최적화 되었는가 (효율성 UP)
결론 : 알고리즘은 결국 컴퓨팅 작업인데 컴퓨팅 자원을 이용해서 구동.

cpu 메모리 => 적게 쓰면서 정확하게 구동되는 것을 효율적이다 라고 말함.

문제 크기와 관련이 있음

시간 복잡도 (Time Complexity)

<빅-오 표기법>

실행 횟수 구하기 다항식형태의 알고리즘 표현식으로 표현하기
가장 차수가 높은 것만 남기고 버리기

O(3n +2) = O(3n) = O(n)

  		 최고차항 	계수 제거
		 선택

ex)
for문이 2번 반복 ==> a*n^2 + b*n + c

for문이 3번 반복 ==> a*n^3 + b*n^2 + c*n + d

== n이 커지면 결국 반복횟수가 엄청 많아지는데, 차수가 가장 높은 항이 제일 중요.

빅오 : O() 최악의 경우
- 최악이란 : 제일 마지막에 있거나 아예 없거나 —> n번 가장 나쁜 케이스를 알기 떄문에 예측을 정확하게 할 수 있다. 제일 많이 씀. 최악이 중요
오메가 : Ω () 최선의 경우
- 최선이란 : 제일 처음에 있을떄 –> 1번
씨타 : θ() 최선 최악이 같을 때 씀. (교집합) O() 와 같다고 생각해도 무관

검색 List

순차탐색 : n이 많아지면 효율성이 떨어짐

n개

…

이진 탐색 정렬이 되어있다고 가정하고, 추측을 해서 찾아 갈 수 있음.

중간찍기 1번 확인 후 필요 없는 영역을 버리기

반씩 떨구기

log₂ n 번만 하면 됨 분할전공 알고리즘

TIP) <sup> 제곱쓰기 // <sub> 아래숫자 (로그)

직접 작성한 코드에 대해서 내가 해결하고자 하는 시간 복잡도를 가지는 알고리즘이다라고 하는 것을 알고 있어야합니다.

이런 방법은 대략 시간복잡도가 이정도 되는 것을 이해하는 것을 말합니다.

O(1) : 항상 시간이 일정 == 최상의 알고리즘 // 해싱이라는 알고리즘 

O(n) : 반복 1번 중첩

O(n<sup>2</sup>) : 반복 2번 중첩

O(n<sup>3</sup>) : 반복 3번 중첩

O(nlogn)알고리즘 : 정렬알고리즘 == 빠름빠름

컴퓨터 입장에서 실행시간이 매우 많이 필요한 문제 = NP

NP vs P

어렵 vs 쉬움

대량의 데이터를 처리하기 위해서는 O() 의 처리 속도가 중요하다.

배열 : 메모리 배열 포인터 어레이

1) 정렬 :

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

조건 : 크기 비교 == 자료형이 같아야 함.

:water_buffalo: 버블정렬

인접한 두개의 우너소를 비교하며 자리를 계속 교환하는 방식
과정

첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동한다.

한단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.

교환하며 이동하는 모습이 물 위에 올라오는 거품모양

시간복잡도 : O(n²)
코드

arr = [55, 7, 78, 12, 42]

for i in range(1, len(arr)):
    if arr[i - 1] > arr[i]:
        arr[i - 1], arr[i] = arr[i], arr[i - 1]

print(arr)


for i in range(1, len(arr) - 1):
    if arr[i - 1] > arr[i]:
        arr[i - 1], arr[i] = arr[i], arr[i - 1]

print(arr)


for i in range(1, len(arr) - 2):
    if arr[i - 1] > arr[i]:
        arr[i - 1], arr[i] = arr[i], arr[i - 1]


print(arr)

:water_buffalo: 선택정렬

첫 번째 데이터를 두 번째 데이터부터 마지막 데이터까지 차례대로 비교하여 가장 작은 값을 찾아 앞쪽부터 수정해 나아가는 과정.
시간 복잡도 : O(n^2)

:water_buffalo: 카운팅정렬

항목들의 순서를 결정하기 위하여 집합에 각 항목이 몇개씩 있는지 세는 작업을 하여, 선형시간( 일차 함수, linear)에 정렬하는 효율적인 알고리즘
실제의 값 자체를 인덱스로 활용한다. 최댓값을 알아야 함(범위)
제한 사항

카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 한다.

정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능(음수 불가능) : 정렬할 값들이 양의 정수 또는 변환할 값들이 양의 정수일 때 가능. 문자열인 경우 양의 정수로 매핑할 수 있는 경우 가능.

시간 복잡도 : O(n+k) (단, n은 리스트의 길이, k는 정수의 최댓값)

K = 4
A = [0, 4, 1, 3, 1, 2, 4, 1]
B = [0] * len(A)
cnt = [0] * (K + 1)

for val in A:
    cnt[val] += 1

for i in range(1, K + 1):
    cnt[i] += cnt[i - 1]

for i in range(len(A) - 1, -1, -1):
    cnt[A[i]] -= 1
    B[cnt[A[i]]] = A[i]

print(A)
print(B)

2) 완전 탐색(Brute-force)

최적화 문제 : 최대 혹은 최소가 되는 경우를 찾는 문제
모든 경우의 수를 테스트 한 후, 최종 값을 도출하는 방법
1억을 기준으로 작은 값은 문제해결 가능하지만, 보다 큰 값은 시간 관계상 해결 불가능.
순열, 조합

수업때 적은 자투리

자료형 C 언어적인 특징들이 파이썬에 많이 녹아져 있음.

연산자 값과 연산자 산술 연사자 비교 연산자 논리 연산자 컴퓨터가 하는 일

컴퓨터 자료형이 중요. 자료형 –>

자료의 표현
1. 자료의 계산
2. 실수의 표현 123.456
  
  자료를 저장한다는것은 자료형이 필요 ==> 이해가 필요

주 1장씩 진행

월요일에는 교재 내용을 공부 + 실습문제 1개

화요일에는 실습 + 실습문제 4개 + 추가 1개

전산전공 아니기 떄문에 자료구조 알고리즘 과목 프로그래밍 언어 배우고, 자료구조 배우고 알고리즘 배운다. 보통

저장하는 방법 어떻게 저장하면 좋을지

자료를 구축하고 메모리에 저장하는 효율적인 방법

1. 알고리즘(algorithm)

추상 자료형(Abstract Data Type)

<알고리즘>

알고리즘 성능은 무엇으로 측정하는가

시간 복잡도 (Time Complexity)

<빅-오 표기법>

검색 List

대량의 데이터를 처리하기 위해서는 O() 의 처리 속도가 중요하다.

1) 정렬 :

:water_buffalo: 버블정렬

:water_buffalo: ​선택정렬

:water_buffalo: 카운팅정렬

2) 완전 탐색(Brute-force)

수업때 적은 자투리

Related Posts

cloud computing 27 Feb 2020

Open Stack 이란? 27 Feb 2020

ServiceWorker 06 Feb 2020

:water_buffalo: 선택정렬