CS45 공간복잡도(Space Complexity) 란? 공간복잡도란? 프로그램 성능을 분석하는 방법 중 하나로, 프로그램이 얼마나 많은 메모리(공간)를 차지하는 가를 분석하는 방법이다. 최근에는 공간 복잡도의 중요성이 예전보다는 낮아졌다고한다. 그 이유는 반도체 기술향상이다. 메모리의 공간이 충분하기 때문에 그렇다. 공간복잡도는 총 공간요구 = 고정공간 요구 + 가변공간 요구 로 나타낼 수 있다. 수식은 S(P) = c + Sp(n)으로 표기한다. * 고정 공간(알고리즘과 무관한 공간) : 코드 저장 공간, 단순 변수 및 상수 (문제의 인스턴스에 무관, 일정한 양의 메모리공간) * 가변 공간(알고리즘 실행과 관련있는 공간) : 실행 중 동적으로 필요한 공간 (문제의 인스턴스에 따라 가변적인 메모리 공간) 공간복잡도를 줄이는 방법은? 고정공간 보다는 가변공간을.. 2022. 3. 11. 시간복잡도(Time Complexity) 란? 시간 복잡도란? 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다. 같은 결과를 가져오는 프로그램도 어떻게 작성하느냐에 따라 걸리는 시간이 달라집니다. 같은 결과를 나타내는 소스라면 최대한 시간이 적게 걸리는 소스가 좋은 소스입니다. 그렇기에 더 효율적인 알고리즘을 구성하기 위해서 시간 복잡도의 측면을 고려하고 중요하게 봅니다. 빅 - 오 표기법이란? 시간 복잡도에는 여러 개념이 있지만, 그 중 '아무리 많이 걸려도 이 시간 안에는 끝날 것'의 개념이 제일 중요하다. 최악의 경우를 발생을 예측하고, 이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라고 부른다. O(1) (constant time) : 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 말한다... 2022. 3. 8. 완전탐색이란? 완전탐색이란? 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 일컫는다. 그리고 컴퓨터의 빠른 계산 속도를 잘 이용하는 방법이다. 알고리즘이라고 부르기보단, 문제 푸는 방법이라고 이해하면 좋을 거다. Ex. 알고리즘을 모르는 상태에서, 문제를 풀 때, 가능한 모든 경우의 수를 확인해서 답을 찾아낸다. 이 과정이 완전 탐색이다. -> 이럴 경우, 수열의 수가 적을 경우에는 충분히 빠르게 해결하겠지만, 수열의 수가 억 단위일 경우에는 시간복잡도 문제가 생긴다. 따라서, 가능한 경우의 수가 많은 경우에는 이용하기 어려우므로 완전 탐색을 이용할 수 있는지 ? 잘 파악하는게 중요하다. 탐색해야 할 개수가 100만 개.. 2022. 3. 8. 큐(Queue) 란? 큐란 ? 먼저 넣은 데이터가 먼저나오는 FIFO 구조로 저장하는 형식을 말한다. 큐의 종류? 선형 큐는 막대모양으로 된 큐이다. 크기가 제한되어있고, 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한칸씩 옮겨야한다는 단점이있다. 환형 큐는 선형큐의 문제점(배열로 큐를 선언할 시, 큐의 삭제와 생성이 계속 일어났을 때, 마지막 배열에 도달한 후 실제로는 데이터 공간이 남아있지만 오버플로우가 발생)을 보완한 것이 환형큐이다. front가 큐 끝에 닳으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결하는 방식이다. 우선순위 큐는 우선순위를 이용하여 우선순위가 높은 순서대로 나게 된다. 실생활 예시를 들자면, 병원에서 기존 환자들을 진료보다가, 응급환자가 오게되면 먼저 진료하게 되는 경우로 이해하면 된다. 큐.. 2022. 3. 6. 스택(Stack) 이란? 스택이란? 자료구조 중, 선형구조에 해당하는 자료구조이다. 제한적으로 접근할 수 있는 나열구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록이라고 한다. (Pushdown list) 또한, 컴퓨터에는 참조지역성이라는 것이 있습니다. 간략히 설명하자면 참조지역성은 한 번 참조된 곳은 또 참조될 확률이 굉장히 높다는 것입니다. 그 참조지역성의 원리 중에서 시간지역성의 원리라는 것이 있는데 시간지역성은 '최근' 참조된 데이터가 다시 참조될 확률이 높다는 겁니다. 스택은 그 시간지역성을 최고로 활용할 수 있는 자료구조입니다. 스택의 특징? - 제일 위의 데이터만 알 수 있다. - 쌓여가는 와중에도 스택에 쌓인 데이터 갯수는 알 수 있다. - 중간의 데이터 절대 알 수 없다. 만약 알고 .. 2022. 3. 6. 이전 1 ··· 3 4 5 6 다음
