본문 바로가기

전체 글120

[C++] 큐(Queue) 이번 시간에는 큐(Queue)에 대해 알아보도록 하겠다. 큐(Queue)는 스택과 달리 선입선출(FIFO, First In First Out) 구조이다. stl queue의 함수들을 살펴보도록 하겠다. 함수 이름 함수 기능 push(element) 큐의 맨 뒤에 원소를 추가 pop() 큐의 맨 앞의 원소를 삭제 front() 큐의 맨 앞의 원소를 반환 back() 큐의 맨 뒤의 원소를 반환 empty() 큐가 비어있으면 1, 큐가 비어있지 않으면 0 반환 size() 큐에 들어있는 원소의 개수를 반환 stl queue를 사용한 코드를 살펴보도록 하겠다. #include #include using namespace std; int main() { queue q; q.push(7); q.push(5); q... 2020. 5. 7.
[C++] 스택(Stack) 이번 시간에는 스택에 대해 알아보도록 하겠다. 스택(Stack)과 큐(Queue)는 컴퓨터 공학에서 가장 기본이 되는 자료구조이다. 스택은 택배 상하차, 큐는 은행 창구에 비유되기도 한다. 이번 시간에는 stl stack을 쓰는 방법을 알아보겠다. stack을 직접 구현하는 것은 다음에 추가하도록 하겠다. #include #include using namespace std; int main() { stack s; s.push(7); s.push(5); s.push(4); s.pop(); s.push(6); while (!s.empty()) { cout 2020. 5. 7.
[C++] 퀵 정렬 (Quick Sort) 이번 시간에는 퀵 정렬에 대해 알아보도록 하겠다. 저번 시간까지 배웠던 선택 정렬, 버블 정렬, 삽입 정렬 모두 시간 복잡도가 O(n ^ 2)였다. 이러한 복잡도를 가지는 알고리즘은 데이터의 갯수가 10만개만 넘어가도 일반적인 상황에서 사용하기가 매우 어려운 알고리즘이다. 그렇기 때문에 더욱 빠른 정렬 알고리즘이 필요하고, 대표적인 빠른 알고리즘이 퀵 정렬로, O(N * logN)의 시간 복잡도를 가진다. 퀵 정렬(Quick Sort)는 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬한다. 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다. 일반적으로 퀵 정렬에서는 기준값이 있고, 이를 피벗(pivot)이라고 하는데, 보통 첫 번째 원소를 피벗 값으로.. 2020. 5. 6.
[C++] 삽입 정렬(Insertion Sort) 이번 시간에는 삽입 정렬에 대해 알아보도록 하겠다. 삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결한다. 다른 정렬 방식들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 필요할 때만 위치를 바꾼다. 삽입 정렬은 비교적 느린 정렬 알고리즘에 속하지만 쉽게 생각할 수 없는, 조금은 복잡한 구조를 가지고 있다. 하지만 삽입 정렬은 앞서 소개했던 버블 정렬과 선택 정렬에 비해서는 더 효율적인데, 매 차례에 바로 앞 원소와 비교하면서 자신의 위치까지만 swap 연산을 하고, 자신의 위치를 찾으면 멈추기 때문이다. 코드로 구현해 보면, #include int main() { int i, j, temp; int array[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 }; .. 2020. 5. 6.

티스토리툴바