[TIL] 알고리즘 아자아자

어제는 백준 푸는게 넘 오래걸리고 안풀려서 개념 정리를 못했드앙

헤헤 어제 넘 힘들엇다 ㅋㅎ

 

사실 알고리즘 기초 관련한거라 복잡한 내용은 아직 없지만 무튼 ~~ 이렇게라도 기록 남겨놓기 ㅎㅎ

 

Chap 1. 알고리즘 기초

1 ) 알고리즘 ? 기초 탐색 ?

알고리즘의 시작 .. 그것은 바로 완전탐색 ..

 

- 깊이 우선 탐색 DFS (Depth First Search)

대표적인 그래프 탐색 방법이죵~~

일반적으로, 재귀함수를 통해 구현하곤 합니당

Stack을 이용하기도 (BFS와 대조되는 부분!)

스택을 이용한다 ? 본디 함수란 .. 스택 구조로 호출되고 작동하기 때문에 .. STACK OVERFLOW 조심!

 

활용 ?

: 백트래킹, 단절선 찾기, 단절점 찾기, 위상정렬, 사이클 찾기 등

 

코드 구현할때 ?

void dfs (int n) {

    1) 우선적으로, 탈출조건부터 코드짜자! 까먹으니까 ㅎㅎ

    2) 그 다음은 가능한 경우를 따지는것~
        vist[index] = true; //방문
        dfs(n+1);
        visit[index] = false; //끝
}

 

- 너비 우선 탐색 BFS (Breadth First Search)

이 또한 대표적인 그래프 탐색 방법 ~

가로로 인접 노드를 와다다 탐색하는 느낌이랄까 ~~~~

일반적으로 Queue를 이용하여 구현합니당. 선입선출! 스택을 활용하는 DFS랑 비교대조 하핫

플러드필을 떠올리시라 ! 홍수가 뻗어나가는 짤을 떠올려라 !

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84

플러드 필 - 위키백과, 우리 모두의 백과사전

 

활용?

: 최단경로 찾기 (다익스트라 알고리즘), 위상정렬 등

 

알고리즘?

: ENQUEUE, DEQUEUE 활용하기

 

근데 완전탐색의 단점이 몬디 ?? 바로 시간복잡도가 클수 있다는거야~~

따라서~~ 훗날 배울 DP를 잘 구현할 줄 알아야함니다 !!

 

2 ) 정렬 ? 정렬의 특성?

- 정렬함수 Sort ( )

CPP에서는 ! 정렬함수는 <algorithm> 헤더로 가져올수있지요

 

sort (시작지점 주소, 끝지점 주소 +1 )

혹은

sort( v.begin(), v.end() )

요런 느낌으로 !

 

- Compare ?

근데 sort함수에는 세번째 인자로 compare 함수를 넣을수 있다요

기존의 compare함수도 있긴해서 걍 갖다써도 되지용

근데 알고리즘 실력 향상을 위해 compare 직접 구현하는거 연습해보라요

 

- 정렬의 응용

정렬하면 무ㅓ가 좋을까유 ?

• 유일성 검사
• 중복제거
• 빈도 구하기

위와 같은 상황에서 편하다는 장점이 있지요

 

딴소리 ) 근데 사실 중복제저, 빈도 구하기 같은거는 STL이나 이중반복문으로 할 수 있긴함! 당욘 STL이 효율적이여

 

- 정렬의 응용 두번째

• 합집합/교집합 구하기

정렬된 두개이상의 데이터 집합에서, 정렬된 데이터의 특징을 이용해 합집합이나 교집합을 구할수 잇지요

그런데 잠깐 !

2 pointer 알고리즘을 사용하길 바라요

sliding window라고 하기도 하지요

얘네들 아주 조아요

 

예를들어, 연속된 이웃위치에 있는 숫자들의 합을 구할때 ?

sol 1. 이중 for문을 쓴다

sol 2. 2 포인터를 활용한다

 

1번은요 시간복잡도가 N^2이여라 ... 넘 말도 안대유

그러나 2번은 ? 시간복잡도가 N입니다 우핫핫

 

• 이분탐색, 이진탐색

이거슨 흔히 숫자맞추기 게임을 떠오르게 하지요

근데 이진탐색할때는 역시 마찬가지로 정렬이 되어 있어야하쥬

compare 함수에 대한 이해도 같이 !

 

- 표준라이브러리를 활용한 정렬?

마 우리 씨쁠쁠에서는 표준 라이브러리로 정렬할 수 있다 마

말했듯이, compare함수도 제대로 알고있어야한다. 그래야 swap등에 활용할때도 편하다 마

정렬 기준을 우리가 막막 이용해먹을라면 compare을 알아야한다마

 

CPP 의 compare함수는

true를 리턴하면 데이터 위치 바꿔줘라 마

이거 헷갈리면 디버깅해서 확인해라

compare 함수의 첫번째 인자가 더 앞쪽에 위치한 데이터인거시다

 

생각보다 글이 길어지고있구만

 

3 ) 시간복잡도 ? 공간복잡도 ?

 맨날 듣던 그 친구들 맞다 마

- 시간복잡도 (Time Complexity)

작동하는 알고리즘의 수행시간을 정량화 한것이다 마

얘네 계산할때 나는 초보라 맨날 헷갈린다

알고리즘 시간복잡도는 결국 연산의 횟수를 구하는 방법인셈이다

대략, 1억번의 연산당 1초의 시간이 걸린다고 간주하곤 한다

1억번이란, 10의 8제곱이다! 10^8 !

N=10000일때, N^2은 대략 1억이다

위와같은 상황을 종종 많이 마주칠것이닷

n (인풋, 배열 크기, 변수 크기 등등)의 범위가 10000까지인데, 중첩문 등으로 N^2를 유도하는 문제들!

하지만 그들의 유도에 넘어간다면 에러가 날것이지 ! 하핫 난 고대로 항상 낚이지 !

 

무튼 ..

 

시간복잡도의 표기법에는 여러가지가 있는데

결국 빅오가 중요하다

Big - Oh !

O(N)라고 나타내는게 그것!

Worse Case를 따지는 것이다.

 

사실 생각해보면 당연함.

빅오메가 best case는 신경안써도 알아서 잘 돌아갈거임

빅세타 average case는 알빠아님

 

무튼 .. 결론 ?

반복문, 재귀함수 등등에서 구조를 잘 살펴보고 시간복잡도를 예측하여 구현해라!

하핫 머리로는 아는데 내 결과물을 보면 항상 모르는듯 ㅎ

 

- 시간복잡도의 종류

• 로그형
• 선형 로그형
• 선형
• 2차형
• 3차형
• 지수형, 팩토리얼 등등 나쁜넘들 ..

로그형이 와방 굿임 = 이진탐색, 우선순위 큐, 힙의 원소삽입삭제

선형로그형도 굿 = 힙 정렬, 병합 정렬(머지소트)

선형도 굿이긴한데 문제로는 그닥 안나올걸

 

병합정렬.. 궁금해도 지금은 스탑

DP (분할정복) 할때 할거임 (미친듯이할거임 ..)

아 근데 백준의 달리기문제가 이걸로하는거임! (플레ㅎ.. 썸데이 구현해보겟슴 ㅋ 나 아직 골드도 업법버 이러다 끝남 하하)

https://www.acmicpc.net/problem/2517

2517번: 달리기

 

거듭제곱.. 빠르게 연산할라면?

압축압축 ㅎㅎ 이거는 나중에 다시할듯.. 글고 사실 글쿤하고 넘어가면 될듯

 

로그형 시간복잡도 중 .. 행렬을 사용하는 방법이 있긴한데

ㅎㅎ 걍 그러려니 하려

 

드뎌 끝 ! 고생했다 얼렁 백준 풀자 !!