알고리즘17 [알고리즘-12] 스택(Stack), 큐(Queue) 안녕하세요 기린입니다 :) 이번 시간에는 스택과 큐를 배워보겠습니다. 스택(Stack)과 큐(Queue)는 컴퓨터 공학에서 가장 기본이 되는 자료구조입니다. 말 그대로 자료를 표현하고 처리하는 방법에 관한 것입니다. 예를 들자면 스택은 택배 상하차를 생각하시면 되고, 큐는 은행 창구를 생각하시면 됩니다. 먼저, 스택부터 확인해봅시다. 어렵지 않은 개념이니 천천히 생각해보시죠 :] 스택은 아래와 같이 출구가 하나밖에 없는 상태로 표현할 수 있습니다. 첫 번째 명령어 삽입(7)이 실행되면 7이 삽입됩니다. 다음 명령어 삽입(5)이 실행되면 위와 같습니다. 이후에 원소 4가 삽입됩니다. 이제 명령어 삭제()가 수행되는데, 삭제할 때는 항상 가장 최근에 들어간 원소가 나갑니다. 이후에 원소 6이 삽입됩니다. 결.. 2022. 4. 19. [알고리즘-11] 심화 정렬 문제 풀어보기 안녕하세요 기린입니다 :) 이번에는 지난 시간까지 배운 정렬들을 활용하여 백준 온라인 저지 https://www.acmicpc.net/ 에 있는 심화 정렬 문제들을 풀어보고자 합니다. 실제 프로그래밍 대회나 실무에서 요구하는 대부분의 정렬 문제는 단순한 형태의 정렬 문제가 아닙니다. 다양하게 연관된 데이터 상에서 정렬을 수행해야 하는 문제가 대부분입니다. 따라서 심화적인 정렬 문제들을 풀어보면서 연습하는 시간이 필요합니다. ① 단어 정렬 https://www.acmicpc.net/problem/1181 위 문제는 단어들을 정렬하는 문제입니다. 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 1. 길이가 짧은 것부터 2. 길이가 같으면 사전 순으로 .. 2022. 4. 12. [알고리즘-10] 계수 정렬(Counting Sort) 안녕하세요 기린입니다 :) 지금까지 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬 알고리즘에 대해 알아보았는데요 여기서 정렬 속도가 가장 빠른 알고리즘은 퀵 정렬, 병합 정렬, 힙 정렬 등이 시간복잡도 O(N * logN)으로 가장 빠르다고 할 수 있습니다. 하지만 이 보다 더 빠르게 정렬해야 한다면 어떻게 해야할까요? 다음의 5이하 자연수 데이터들을 오름차순 정렬하세요. 1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1 이번 예시의 데이터의 갯수는 30개입니다. 다만 모든 데이터가 1부터 5사이에 속한다는 특징이 있습니다. 이처럼 '범위 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘이 있습니다. 시간 복잡도가 무려 O(.. 2022. 4. 11. [알고리즘-9] 힙 정렬 (Heap Sort) 안녕하세요 기린입니다 :) 오늘은 힙 정렬(Heap Sort)에 대해 알아보겠습니다. 먼저 힙 정렬은 병합 정렬과 퀵 정렬만큼 정렬속도가 빠른 알고리즘입니다. 그리고 실제 고급 프로그래밍 기법으로 자주 사용하기 때문에 반드시 알고 넘어가야 할 정렬 알고리즘이지요. 힙 정렬은 힙 트리 구조(Heap Tree Structure)를 이용하는 정렬 방법입니다. 힙 트리 구조를 이해하기위해 먼저 힙과 트리 구조에 대해 알아야 합니다. 가장 먼저 트리 구조 중 이진 트리(Binary Tree)에 대해서 알고있을 필요가 있습니다. 이진 트리란 컴퓨터 안에서 데이터를 표현할 때 데이터를 각 노드(Node)에 담은 뒤에 노드를 두 개씩 이어 붙이는 구조를 말합니다. 이 때 트리구조에 맞게 부모 노드에서 자식 노드로 가지.. 2022. 4. 5. [알고리즘-7] C++ STL sort() 함수 다루기 - ① 안녕하세요 기린입니다 :) 지금까지 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬의 개념을 이해하고 간단한 예시를 통해 프로그램까지 작성하는 시간을 가졌습니다. 자 이번엔 C++ STL sort 함수에 대해 알아 보도록 하겠습니다. 정렬은 컴퓨터 공학의 오래된 연구 분야이므로 아주 훌륭한 정렬 라이브러리들이 존재하죠. 즉, 앞서 직접 코딩했던것 처럼 할 필요 없이 라이브러리를 가져다 쓰면 되는 것입니다. 그치만 기본적인 정렬 원리에 대해서는 잘 알고있어야 문제해결능력에 도움이 될거라 생각합니다. 이제 sort 함수의 사용법을 소스코드로 보시겠습니다 #include #include using namespace std; int main(void) { // 입력 int a[10] = {2, 3, .. 2022. 3. 29. [알고리즘-6] 병합 정렬 (Merge Sort) 안녕하세요 기린입니다 :) 지난 시간까지 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬 알고리즘을 공부했습니다. 이번에는 병합 정렬 (Merge Sort)에 대해 알아보겠습니다 ! 병합 정렬도 퀵 정렬 알고리즘과 같이 '분할 정복' 방법을 채택한 알고리즘 인데요 결론은 시간 복잡도가 O(N * logN)이라는 거죠 :] 다만 퀵 정렬 알고리즘은 피벗 값에 따라서 편향되게 분할할 가능성이 있다는 점에서 최악의 경우 O(N ^ 2)의 시간 복잡도를 가지지만 병학 정렬 알고리즘은 정확히 반절씩 나눈다는 점에서 최악의 경우에도 O(N * logN)의 시간 복잡도를 보장합니다. 퀵 정렬을 이해하셨다면 이 병합 정렬은 쉽게 이해하실 수 있을겁니다. 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 8 2.. 2022. 3. 25. 이전 1 2 3 다음
