튜터님한테 이메일 할 땐 [스파르타코딩클럽]을 제목에 붙이자. 안그러면 스팸처리됨
스택
후입 선출 LIFO
스택 활용
-
데이터를 임시 저장하고 싶을 때
-
최근에 임시 저장한 데이터 가장 먼저 활용, 쌍 맞추어 저장, 뒤로가기 기능
ex) e.g.foo(int x, int y)
큐bar(z){
}
foo(x,y) {
int a = 3
bar(4)
}
foo(1,2)
->
1/ 2/3/4 순서대로 들어온거고, 4가 가장 먼저 pop됨
(최근 저장된 데이터 삭제)stack ex2) 쌍이 맞는지 검사하고 싶을 때
- 문자열을 쭉 순회 2. (를 만나면 push 3. )를 만나면 pop 4. 문자열 순회가 끝나고 스택이 비어 있다면 올바른 괄호
(((( ->push
)))) ->pop
쌍이 안맞으면 ((((( ))) -> pop을 못함
선입선출 FIFO 큐의 활용
데이터를 임시 저장하고 싶을 때
큐를 버퍼로 활용, 차례대로 줄세울 때
ex) 영화관 예약 인원
큐는 양쪽 끝이 뚫려있는 구조
큐의 변형: 원형큐, 덱(Deque=Double-Ended Queue)-양쪽에서 데이터 삽입 및 삭제가 가능, 우선순위 큐(저장된 순서와 무관하게 우선순위가 높은 데이터가 먼저나감-이진트리)
정렬의 개념
데이터를 정해진 기준에 따라 재배치 하는 것
BDCA -> ABCD
다양한 정렬 알고리즘이 존재 (버블정렬, 선택 정렬, 삽입 정렬, 퀵 정렬)
성능 ->버블,선택, 삽입 O (n^2) 퀵정렬 O(nlogn)
퀵이 성능 가장 좋음
다양한 정렬 알고리즘 (정렬하다 패스한 건 횟수에 포함이 안됨)
#삽입정렬
#버블 정렬
:요소를 쭉 순회하며, 인접한 요소와 비교하며 정렬이 제대로 되었는지 확인, 정렬이 제대로 될 때까지 인접한 요소와 비교하여 바꿔치기 해서 정렬
-시간복잡도: O(n^2)
ex) [2,5,1,5,6,9] 다시 처음부터 시작, 9라는 요소는 마치 거품이 위로 올라가듯 정렬됨
#선택정렬
: 요소들 중 최소값을 찾아, 그 값을 요소의 맨 처음 값으로 대체하고, 맨 처음 값을 뺀 나머지 요소들이 정렬될때까지 반복, 시간복잡도 O(n^2)
#퀵정렬
: 분할 정복(divide-and-conquer) 알고리즘의 일종, 큰 문제를 작은 분리하여 작은 문제들을 해결함으로써 큰 문제를 해결, 이름 처럼 빠른 정렬, 내장 정렬 함수의 대부분의 원리가 되는 알고리즘
-시간 복잡도 O(nlogn)
1. 임의의 하나의 요소를 고른다. 이를 피벗(pivot=기준점)이라고 한다. 피벗보다 작은 부분집합, 피벗보다 큰 부분집합을 선정한다.
2. 피벗의 좌, 우를 기준으로 정렬한다. 정렬 뒤 피벗은 더 이상 움직이지 않는다. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 둘로 나눈다.
3. 분할된 두개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다.
ex) [5,2,9,1,5,6] -> [2,1,5,9,5,6] ([2,1], [9,5,6]
->[1,2,5,5,6,9]
