용기러기's Coding World

알고리즘 시간 복잡도에 대해서 알고는 있었지만, 이 키워드를 가지고 깊게 고민해본 적이 없는데 한번 짚고 넘어가야할 것 같아 정리를 해두고자 한다:D ​ 먼저, 알고리즘 시간 복잡도에 대해서 나만의 정의를 해보면, 자료의 크기를 n이라고 했을 때, 이 n을 그래프의 가로축에 두고, 그 n이 점점 커진다고 했을 때 세로축에는 해당 자료를 가지고 수행하는 알고리즘의 걸리는 시간(time)이 오고, 이 때, 가로축과 세로축의 관계, 즉, 그래프의 선이 어떤 방향으로 가게 될지 반비례, 비례 관계 그리고 그 관계의 정도(기울기)를 시간 복잡도라고 생각해볼 수 있다. ​ 마지막으로 간단 정리하면, 시간 복잡도는 자료크기가 커질 때, 그 자료를 바탕으로 수행하는 알고리즘의 수행 시간이 자료의 크기와 어떤 상관관계를..

오늘은 지난 배열편에 이어 linked list(연결 리스트)라고 불리는 자료구조에 대해서 시간 복잡도와 연관해서 분석해보고, 현실에서 어떤 것과 닮아있는지를 통해서 심화학습 해보도록 하겠습니다 :D 먼저, linked list(연결 리스트)에 대해서 간략하게 정의해보면, 우리가 아는 배열의 특징(메모리가 이미 정해져있음, 인덱스를 통해 자료를 저장 및 관리함)과는 달리! 인덱스가 없고, 본래 정해져있는 크기가 없습니다. 즉, 배열과 달리 자료의 크기에 유동성이 있고, 자료는 인덱스를 통해서 관리되지 않고 단일 연결 리스트(singly linked list) 의 경우 이전의 자료에 의해서 다음 자료가 유지가 되는 형태로 자료가 저장 및 관리됩니다. 좀 더 구체적으로 이해해보면, linked list는 먼..

오늘은 '알고리즘', 즉, 문제를 해결하는 방법 혹은 절차가 얼마나 효율적인지 (상대적인 개념)를 체크하는 기준이 되는 '시간 복잡도' 그리고 '공간 복잡도' 중에서 '시간 복잡도'를 위주로 특정 '자료구조(자료를 저장하거나 사용하는 방법을 정의해 놓은 것)'를 사용했을 때, 자료의 '추가', '삭제', '조회', '탐색'에 있어서 시간 복잡도가 얼마나 되는지를 통해 어떤 상황에는 어떤 자료구조를 쓰는 것이 좋은 것인지를 고민해보는 시간을 가져보고자 한다 :D 그럼 가장 먼저 볼 자료구조는! 배열(Array)! :D 입니다. 먼저, 우리가 흔히 아는 Array(C언어와 Java의 배열과 같이 길이가 정해져있는 배열을 말함)! 참고로, 자바스크립트, 파이썬 등의 언어에서의 배열은 길이 제한이 없는 배열이기..