IT 공부정리

코딩테스트 문제를 풀 때 시간 복잡도를 계산하여 수행 시간을 짐작하여 문제를 해결한다. 대학교 때 자료구조 시간 때 배운 시간복잡도와 공간 복잡도를 복습하여 정리하였다. 1. 시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity) 정의 복잡도는 알고즘의 성능을 나타내는 척도이다. 시간 복잡도 : 알고리즘의 수행시간을 평가한다. 즉, 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다. 공간 복잡도 : 알고리즘 수행에 필요한 메모리 양을 평가한다. 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다. 복잡도를 측정함으로써 시간 복잡도에서는 알고리즘을 의해 필요한 연산의 횟수를, 공간 복잡도에서는 메모리의 양을 계산할 수 ..

자료구조 2023. 1. 31. 11:19

1. 정렬이란? 정렬(sorting)은 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것을 의미한다. 정렬은 컴퓨터 공학에서 가장 기본적이고 중요한 알고리즘 중의 하나로 일상생활에서 많이 사용된다. 정렬은 자료 탐색에 있어서 필수적이다. 예를 들어 사전에서 우리가 단어를 쉽게 찾을 수 있는 것은 사전안의 단어들이 알파벳 순으로 정렬되어 있기 때문이다. 만약 사전이 알파벳 순으로 정렬되어 있지 않다면 특정 단어를 찾는 것은 거의 불가능할 것이다. 이는 컴퓨터도 마찬가지이며, 정렬되어 있지 않은 자료가 주어지면 탐색의 효율성이 크게 떨어진다. 지금까지 개발된 정렬 알고리즘은 매우 많지만 모든 경우에 있어서 최상의 성능을 보여주는 최적의 알고..

자료구조 2021. 10. 17. 20:47