💻자료구조와 알고리즘
자료구조
- 메모리를 효율적으로 사용해 빠르고 안정적으로 데이터를 처리하는 것이 목표로 상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있습니다.
알고리즘
- 특정 문제를 효율적이고 빠르게 해결하는 것이 목표로 정해진 일련의 절차나 방법을 공식화한 상태를 말합니다.(수학적 표현)
Dijkstra Algorithm
최단 경로 탐색 알고리즘으로 1956년에 만들어졌습니다.
빅오 표기법
- 알고리즘의 시간 및 공간 복잡도를 분석하여 측정합니다.
빅오 표기법 규칙
-
계수 법칙
상수 k가 0보다 크다고 가정(k>0), f(n)이 O(g(n))이면 kf(n) 은 O(g(n))이다. n이 무한에 가까워질때 다른 계수는 무시해도 되기 때문에 n과 관련되지 않은 계수를 제거합니다.
-
합의 법칙
결괏값인 시간 복잡도가 두 개의 다른 시간 복잡도의 합이라면 빅오 표기법 역시 두 개의 다른 빅오 표기법의 합이라는 것을 의미합니다.
-
곱의 법칙
마찬가지로 두 개의 다른 시간 복잡도를 곱할 때 빅오 표기법 역시 곱해진다는 것을 의미합니다.
-
전이 법칙
교환 법칙은 동일한 시간 복잡도가 동일한 빅오 표기법을 지님을 나타내기 위한 간단한 방법입니다.
-
다항 법칙
직관적으로 다항 법칙은 다항 시간 복잡도가 동일한 다항 차수의 빅오 표기법을 지님을 나타냅니다.
배열, 연결리스트
자료구조를 사용할 때 4가지 기본 연산과 관련하여 시간 복잡도와 공간 복잡도를 고민하게 됩니다.
-
삽입
삽입은 새로운 항목을 자료 구조 내에 추가하는 것을 의미합니다.
-
삭제
자바스크립트는 .pop() 메소드를 사용하여 배열 삭제를 구현합니다. 마지막으로 추가된 항목을 제거하고 제거된 항목을 반환합니다.
-
접근
특정 인덱스의 배열에 접근하는 연산의 시간 복잡도는 O(1)입니다. 접근 연산은 인덱스를 사용해 메모리의 주소로부터 직접 값을 얻기 때문입니다.
-
반복
반복은 자료 구조 내에 담긴 항목들에 하나씩 접근하는 과정입니다. 여러 방법이 있지만 해당 방법들 모두 O(n)이라는 시간 복잡도가 있습니다.
여기서 배열은 추가와 삭제가 반복되는 로직에는 사용하는 것이 부적합합니다.
😰 이유는 선형시간(시간 복잡도)가 추가되기 때문입니다.
만약 추가와 삭제가 반복되는 로직이라면 연결리스트 (Linked List) 가 적합 합니다.
- 요소를 추가하거나 제거할때는 O(1)이 소요됩니다.
- 메모리가 허용하는 내에서 요소를 계속 추가할 수 있습니다.
Singly Linked List, Doubly Linked List, Circular Linked List
알고리즘 문제(올바른 괄호)
괄호를 바르게 짝지어서 올바른 괄호와 올바르지 않은 괄호를 true와 false로 return값을
주는 솔루션 함수를 요구 하였는데
스택을 사용하여 push(), pop()을 사용하여 구현 해보았지만 테스트 케이스는 4개 중 2개 통과
테스트는 통과하지 못 하였습니다.
회고🥲
사실 아직 알고리즘보다 제대로 쌓아놓지 못했던 문법적인 것들에 대해 며칠간 더 하고 싶었으나 진도를 따라가려면 어쩔수 없이 알고리즘도 같이 병행해야 했다ㅠㅠ(당연히 필수지만...) 급하게 풀기도 했지만 벼락치기 형식으로 준비했던 알고리즘이다 보니 다시 기억도 안나고 부족한 기초와 맞물려 더욱 더 오래 걸리는 상황이 생겼다...(변명할 여지없이 실력 부족이다..ㅎ) 한 달간은 오래 걸리더라도 확실히 알아가고 내가 목표로 했던 항상 '왜'라는 질문을 던지며 동작을 이해하고 구현하는 개발자가 되기 위하여 안일하게 공부해왔던 업보를 견뎌야 할 듯하다.😔 깃허브도 계속 써 나아갈 예정이고 모던 자바스크립트에서 시작부터 말했던 '의도적인 연습' 그리고 내 성격상 rabbit hole에 빠지기도 쉽다고 생각하여 항상 경계하고 앞으로도 시간 분배를 더욱 신경쓰고 다른 사람보다 느리더라도 하나를 할 때 제대로 하자는 마인드는 항상 가지고 할 예정이다.
