01.알고리즘의 개요

1. 알고리즘의 개념

🤍알고리즘 : 문제를 해결하기 위한 일련의 절차, 어떤 작업을 수행하기 위한 명령어를 입력받아 결과를 출력해 내는 과정을 기술한 것

알고리즘 사이트

알고리즘 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 풀어맺기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 위한 단계적 절차

9세기 페르시아 수학자인 무함마드 알콰리즈의 이름을 라틴어화한 알고리스무스에서 유래
-위키디피아

---

2. 알고리즘의 표현 방법

🤍자연어 : 사람이 사용하는 자연 언어.

• 자연어로 표현된 알고리즘은 사람에게 친숙한 언어로 구성되어 있어 쉽게 작성할 수 있지만, 명확하지 않은 표현 때문에 오해가 발생할 수 있음.

🤍순서도 : 기호와 선을 이용해 문제 해결에 필요한 처리 과정을 표현한 방법.

• 순서도는 전체적인 구조 흐름을 파악하는 데 적합하지만, 복잡한 알고리즘을 표현할 떄는 그림도 복잡해져 효과가 떨어짐.

🤍 의사코드(수도 코드) : 프로그래밍 언어로 작성된 코드와 비슷한 형태로 알고리즘을 표현하는 방법으로, 구조는 프로그래밍 언어와 비슷하지만 특정 프로그래밍 언어의 문법을 따르지는 않음.

• 실제 프로그래밍 언어는 아니다. 자유로운 수단일 뿐

🤍프로그래밍 언어: 프로그래밍을 할 때 사용하는 언어로 , 컴퓨터가 이해할 수 있는 언어.

---

3. 알고리즘의 설계

🤍알고리즘의 설계: 가장 효율적인 문제 해결 방법을 찾아내는 과정

<알고리즘 제어 구조의 종류>

• 순차구조 : 명령을 순서대로 하나씩 수행하는 구조

• 선택구조 : 조건의 결과에 따라 명령을 선택해서 실행하는 구조

• 반복구조 : 같은 동작을 여러번 반복해 수행해야할 때 실행하는 구조

➕ 알고리즘의 조건

• 입력 : 알고리즘에 입력되는 자료가 0개 이상 존재해야 함.
• 출력 : 알고리즘이 실행되면 결과 값이 1개 이상 나와야 함.
• 유한성 : 알고리즘은 반드시 종료되어야 함.
• 명확성 : 알고리즘의 명령은 모호하지 않고 명확해야 함.
• 실행 가능성 : 알고리즘의 모든 명령은 실행 가능해야 함.

02.알고리즘의 분석

1. 알고리즘의 복잡도

🤍알고리즘의 복잡도: 해당 알고리즘이 특정 기준에 따라 얼마나 빠르고 느리게 실행되는지를 보는 것

• 'cpu 실행 시간'은 알고리즘의 효율성을 판단하는 가장 중요한 평가 기준인데, 이 기준으로 알고리즘 효율성을 측정하는 가장 좋은 방법은 시간 복잡도를 분석하는 것이다.

2. 시간 복잡도(Time complexity)

🤍 시간 복잡도(Time complexity) : 알고리즘이 실행되고 종료될 때까지 어느 정도의 시간이 필요한지를 측정하는 방법.

3. 빅 오 표기법(Big O Notaion)

🤍 빅 오 표기법(Big O Notaion) : 알고리즘의 시간 복잡도를 표현하는 방법.

• 컴퓨터에서 입력된 값의 크기에 따라 알고리즘 처리 횟수가 얼마나 증가하는지 나타낼 때 사용.
• 입력된 데이터의 개수에 따른 알고리즘의 효율성을 분석할 때, 빅 오 표기법을 이용하면 알고리즘의 복잡도를 근삿값으로 나타낼 수 있음.
• O(n) 알고리즘의 시간 복잡도가 O(n^2)알고리즘보다 낮다는 것을 알 수 있음.
  • O(n): 알고리즘의 수행 횟수가 n만큼 커진다.
  • O(n^2): 알고리즘의 수행횟수가 n2만큼 커진다.

➕ 빅오 표기법 깊게 알기

• 어떤 알고리즘의 수행 속도가 입력된 데이터 개수 x에 따라 f(x)

➕ 대표적인 빅오 표기법 종류

3. 정렬 알고리즘

🤍정렬: 데이터를 일정 규칙에 따라 재배열 하는 것.

🤍선택정렬: 아무렇게나 놓인 데이터 중 가장 작은 데이터의 위치를 가장 앞에 있는 데이터 위치와 바꾸는 알고리즘

🤍버블정렬(bubble sort): 나란히 놓인 데이터 두 개 중 숫자가 큰 데이터를 뒤로 보내며 정렬하는 방식.

• 버블 정렬은 왼쪽에 놓인 데이터에서부터 시작, 크기순으로 자리를 서로
  바꿈.

🤍삽입정렬 :

- 올리고 비교하고 밀고 넣고

➕병합 정렬

• 병합 정렬(merge sort): 고급 정렬 알고리즘 중 하나로 , 정렬된 여러 개의 자료 집합을 병합하여 하나의 정렬된 집합으로 만드는 정렬 방법.
• 병합정렬 수행과정
• 분할:
• 정복
• 병합 정렬 예시
  1.분할 단계 -> 2.정복 및 결합 단계
  

🔻정렬 알고리즘 추가 설명

삽입정렬, 버블정렬, 선택정렬: O(n^2)
병합정렬, 힙 정렬, 퀵 정렬 :

삽입정렬 시간복잡도 계산
병합정렬 시간복잡도 계산

1 2 3 4
13141516

1234
1113456 : stabel.

데이터가 들어온 순서대로 보존이 되어야하는데
원본 내용에 있는 같은 데이터가 섞이게 되면
안정적이지 않다.

• 같은 내용물이어도 순서가 중요하다.
  3214
  11113456 : unstable

4. 검색 알고리즘

🤍순차검색

• 정렬되어 있지 않은 데이터의 순차 검색
  (방법1)
• 정렬된 데이터의 순차 검색 ( 시간이 반 정도 줄어든다)
  (방법2)

🤍이진검색 : 데이터 가운데에 위치한 항목을 검색 값과 비교하여 검색 값이 더 크면 오른쪽 부분을 검새하고 검색 값이 더 작으면 왼쪽부분을 검색

• 숫자 맞추기 처럼 찾는게 이진 검색

🤍해싱 : 산술적인 연산을 이용해 키가 있는 위치를 계산하고 , 그 위치를 바로 찾아가는 방법.

• 해쉬 함수 : 키 값을 데이터 위치로 구현하는 함수
• 해쉬 테이블

🔻해싱 추가 설명

a b c d...
1 2 3 4 ...

f('ace') = 1+3+5 =8
f('dd') = 4+ 4 =8
각 값에 따른 배열에 영어를 지정해주는 것
array[8] =ace

근데 단점이 발생하게 된다. dd 도 합이 8인데 얜 배열 8번에 들어가는게 아닌 것인가..?

해쉬 값 충돌

이미 세팅된 배열에 ace가 들어 있기 때문에 dd가 들어갈 자리가 없다. 이걸 해쉬값 충돌이라고 부른다. 같은 값이 들어간 데이터가 2개 이상 들어가려 할 때.

• 해결방법 1 : 배열 9번에 넣자.(일단 합은 8이긴한데) ->근데 이러면 또 대 혼란 발생 (추후에 9값이 또 들어오려하면 출돌)
• 해결방법 2 : 링크를 해서 연결리스트 생성 후 가르키게 만들어준다. 그래서 포인터를 통해 연결해서 만들어 줄 수 있다.