어제는 백준 푸는게 넘 오래걸리고 안풀려서 개념 정리를 못했드앙
헤헤 어제 넘 힘들엇다 ㅋㅎ
사실 알고리즘 기초 관련한거라 복잡한 내용은 아직 없지만 무튼 ~~ 이렇게라도 기록 남겨놓기 ㅎㅎ
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
플러드 필 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 4방향 재귀적 플러드 필 플러드 필(영어: flood fill) 혹은 시드 필(영어: seed fill)은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 이 알고리즘은 그
ko.wikipedia.org
활용?
: 최단경로 찾기 (다익스트라 알고리즘), 위상정렬 등
알고리즘?
: 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번: 달리기
첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는
www.acmicpc.net
거듭제곱.. 빠르게 연산할라면?
압축압축 ㅎㅎ 이거는 나중에 다시할듯.. 글고 사실 글쿤하고 넘어가면 될듯
로그형 시간복잡도 중 .. 행렬을 사용하는 방법이 있긴한데
ㅎㅎ 걍 그러려니 하려
드뎌 끝 ! 고생했다 얼렁 백준 풀자 !!