전체 글137 2021.2.21 TIL : [자료구조] 퀵 정렬(Quick Sort) 퀵 정렬은 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법이다. 값을 서로 교체하는 데에 N번, 엇갈린 경우에 교체 이후에 원소가 반으로 나누어지므로 전체 원소를 나누는 데에 평균적으로 log N번이 소요 되므로 평균적으로 Θ(N log N)의 시간 복잡도를 가진다. *'피벗'은 뭔가요? 피벗은 특정 계산을 수행하기 위한 임의의 알고리즘에 의해 먼저 선택된 행렬의 성분(항, 원소)이다. 퀵 정렬은 편향된 분할(정렬할 데이터가 이미 정렬이 되어 있거나 역으로 정렬되어 있는 경우 - 피벗이 한 쪽으로 치우쳐 N개의 원소를 피봇 기준으로 나누는 작업을 N번 실행)이 발생할 때 연산의 양이 O(N^2)이다. 따라서 실제로 정렬을 함에 있어서는 퀵 정렬을 직접 구현하지 않는다. 따라서 C++의 Alg.. 2021. 2. 21. 2021.2.20 TIL : [자료구조] 선택 정렬과 삽입정렬 선택 정렬이란 데이터 중에 가장 작은 것을 선택해서 앞으로 보내는 정렬 기법이다. 가장 작은 것을 선택하는 데에 N번, 앞으로 보내는 데에 N번의 연산으로 O(N^2)의 시간 복잡도를 가진다. 즉, 의사코드를 적어보면 다음과 같다. C언어로 구현한 선택 정렬 코드는 여기에서 확인할 수 있다. for(int i = 0; i < N; i++) i 번째 숫자부터 N번째 숫자까지 모두 확인하여 가장 작은 수를 찾아낸다. 가장 작은 숫자를 i번째 숫자와 바꾼다. 삽입 정렬이란 각 숫자를 적절한 위치에 삽입하는 정렬 기법으로, 들어갈 위치를 선택하는 데에 N번, 선택하는 횟수가 N번이니까 O(n^2)의 시간 복잡도를 가진다. 즉, i가 0에서 N까지 1씩 증가하는 수라고 할 때, i번째 자리의 값이 i-1번째 값보.. 2021. 2. 20. 2021.2.9 TIL : [자료구조] 스택(Stack) 오늘은 스택에 대해서 배웠는데, 지난 CS50 강의에서 메모리 구조를 배우면서 알게 된 힙과 스택에서의 스택과는 조금 다른 뜻인 것 같았다. 스택은 한 쪽으로 들어가서 한 쪽으로 나오는 자료구조를 의미한다. 이는 들어가는 곳과 나오는 곳이 같다는 특징이 있는데, LIFO(Last-In-First-Out) 방식을 떠올리면 쉽게 이해할 수 있다. 이러한 특성 때문에 스택은 수식 계산 등의 다양한 알고리즘에서 다방면으로 활용된다. 스택에서 Push는 스택에 새 데이터를 추가하는 것, Pop은 가장 최근에 추가한 데이터를 빼내는 것을 의미한다. 예를 들어 push(7) - push(3) - push (5) - pop() - push (11) - pop() - push (12)이 스택의 자료구조로 이루어져 있다면.. 2021. 2. 9. 2021.2.6 TIL : [자료구조] 양방향 연결리스트 오늘은 양방향 연결 리스트의 동작 원리와 구현 방법을 공부하고, 이를 통해 포인터 사용 능력을 업해보는 시간을 가졌다. 양방향 연결 리스트란 지난 2월 5일에 작성한 TIL에서 배운 단일 연결리스트와 달리, 포인터를 2개 사용하여 원소의 앞과 뒤를 모두 연결한 리스트를 의미한다. 따라서 이 리스트의 각 노드는 앞 순서의 노드에 대한 포인터, 뒤 순서의 노드에 대한 포인터를 데이터 값과 함께 가지고 있다. 이를 위해 노드의 자료형 자체에서 포인터 2개와 데이터 값까지 표현해 줄 필요가 있다. 특히, 수업에서는 오름차순으로 정리된 연결리스트를 만들었다. 이전까지는 for loop를 주로 사용했는데, 이 수업에서는 while loop를 더 많이 사용했다. for에 적응이 되고 나면 while을 쉽게 할 수 있.. 2021. 2. 7. 2021.2.5 TIL : [자료구조] 연결리스트 연결 리스트는 말 그대로 앞, 뒤의 순서가 있는 리스트를 말한다. 이는 배열과도 비슷한데, 배열 기반 리스트는 배열로 만들어서 그 순서를 알기 쉬운 반면(ex. arr[0], arr[1]), 연결 리스트는 1 ---> 2 이런 식으로 진행되기 때문에 다른 점이 있다. 배열 같은 경우는 기초 C 언어 강의(나의 경우는 CS50)에서 다루고 있기 때문에 별도로 주의깊게 살피지는 않았다. 다만 배열 기반 리스트는 다음과 같은 특징이 있었다. 1) 배열로 만들어 특정 위치에 뭐가 있는지 알 수 있다. 2) 데이터가 들어갈 공간에 맞게 미리 메모리를 할당해야 한다. (배열의 길이를 미리 알아야 함) 3) 원하는 위치로 삽입이 번거롭다. (하나의 데이터를 삽입할 시, arr[i+1] = arr[i] / 하나의 데이.. 2021. 2. 6. 이전 1 ··· 20 21 22 23 다음
