🧑🏻‍🏫 자료구조와 알고리즘

그동안 몰랐었던 자료구조와 알고리즘에 대한 기본기를 알아보자

🍿 개요

프로그램은 자료구조와 알고리즘으로 이루어져있다.
자료구조는 데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타낸다.
우리는 자료구조를 배우지 않았어도 프로그래밍을 하면서 사용했다.

가장 단순한 자료구조는 변수다. 또 다른 자료구조는 배열이다.
자료구조를 제대로 이용하면 코드를 좀 더 단순하게 짤 수 있다.

🍿 알고리즘

알고리즘은 어떤 문제를 해결하기 위한 구체적이고 확실한 방법을 말한다.

좋은 알고리즘이란 ?

사용자에 따라 다르다.
메모리를 적게 사용하고자 한다면 메모리를 적게 사용되는 알고리즘이 더 좋은 알고리즘이라고 할 수 있고, 어떤 사용자는 속도가 더 빠른 것을 원하는 사람도 있다.
하지만 일반적으로는 알고리즘의 속도를 성능의 척도로 사용한다.
이를 ⭐️시간 복잡도⭐️ 라고 부른다.

🍿 시간 복잡도란 ?

특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 말한다. 하지만 시간을 측정해서 알고리즘을 평가하기에는 현실적으로는 어렵다. 왜냐면 사용자 컴퓨터의 성능이 다 다르기 때문이다. 그래서 실행 시간이 다 다르다. 누구는 5초가 걸릴 수가있고 누구는 1초 걸릴 수가 있다.

그러므로 코드 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측한다.
코드에서 성능에 많은 영향을 주는 것은? 바로 ⭐️반복문⭐️이다.
반복문이 여러 번 반복될수록 실행시간이 길어진다. 그래서 알고리즘의 성능을 평가할 때는 알고리즘의 반복문을 보고 평가한다.

원하는 데이터를 찾는 알고리즘은 경우를 나누어서 평가한다.

• 최선의 경우 한 번에 찾을 때 -> Big-오메가
• 최악의 경우 배열의 길이만큼 걸릴 때 -> Big-O
• 평균의 경우 배열의 길이 중간만큼 걸릴 때 -> Big-세타

이중에서 우리가 가장 많이 사용하는 것은 Big-O 이다.
빅오표기법은 O(n)으로 표기한다. 데이터가 많아지면 그에 비례해서 계산량이 많아지는 것이다.
O(n)의 알고리즘은 선형시간 알고리즘이라고 한다.
빅 오 표기법은 입력이 늘어날 때, 계산량이 늘어나는 척도를 나타내기 위한 것이다.

선형시간 알고리즘 외에도 상수시간 알고리즘이라는 것도 있다.
이것은 O(1)으로 표현한다. 입력의 크기와 상관없이 상수의 시간이 걸린다는 의미이다.
이 외에도 성능은 O(logn), O(nlogn), O(n^2), O(2n), O(n!)-> 팩토리얼 등등이 있다. (아.. 진심 머리 아파옴..🤦🏻‍♀️)

빅오 표기법의 특징

만약 n^2(제곱) + 2n + 100의 성능을 보이는 알고리즘이 있다면 이를 표현할 때는?
계산에 가장 많은 영향을 미치는 항만 표기하는 것이다.
n^2이 가장 많은 영향을 미치므로 이거 외에 나머지 항들은 버려진다.

3n^2 +100n 은 가장 큰 항을 포기하는 것이다. 그리고 상수는 필요없기 때문에 상수도 버려준다. 그럼 답은 O(n^2)이 된다.

JS 실행 환경 구축

확장자 mjs 파일은 자바스크립트 모듈 파일이다. (테스트코드 작성할 때 쓴다)

🍿 배열

배열은 프로그래밍에서 기본적으로 제공해주는 자료구조이다.
배열을 선언했다면 운영체제는 메모리에서 숫자가 들어갈 수 있는 빈 공간을 찾아서 순서대로 값들을 할당해줍니다. 할당하지 않은 부분은 의미없는 쓰레기 값이 저장된다.

그리고 운영체제는 배열의 시작 주소만 기억합니다. 프로그래머가 배열의 세번째 원소에 접근하고 싶다면 arr[2] 이런식으로 접근한다. 운영체제는 이런 메모리 공간들을 다 기억하기 때문에 길이 상관없이 한 번에 가져온다. 배열은 읽기/쓰기 등 참조에서 좋은 성능을 보여준다.

배열의 성능은 좋지만 데이터의 삽입, 삭제 성능은 그리 좋지 않다.
자바스크립트 배열은 상황에 따라서 연속적, 불연속적으로 메모리를 할당하지만 대부분은 불연속적으로 할당한다.

배열의 장점

• 읽기, 쓰기와 같은 참조에는 O(1)의 성능을 가진다.

배열의 단점

• 크기 예측이 힘들기 때문에 메모리 낭비가 발생할 수 있다.
• 데이터 삽입, 삭제가 비효율적이다.

🍿 연결리스트

배열의 단점을 해결하기 위해서, 저장하려는 데이터들을 메모리 공간에 분산 할당하고 이 데이터들을 서로 연결해준다. 이것은 노드라는 것을 만들어서 수행한다. 노드의 구조는 데이터를 담는 변수 하나와 다음 노드를 가리키는 변수 하나를 말한다.

필요한 노드를 만들어 연결하는데 이런 구조로 연결 리스트라고 부른다.

연결리스트의 장점

빈 메모리공간 아무 곳에 데이터를 생성하고 연결만 해주면 되기 때문에 배열에서 초기 크기를 알아야 하는 단점이 연결리스트에는 없다.
배열은 1과 3사이에 2를 삽입하려면 3뒤로의 데이터들은 모두 뒤로 밀려나기 때문에 오버헤드가 많이 드는 반면, 연결리스트는 중간에 데이터를 삽입하면 다음 가리키는 노드만 바꿔주면 되기 때문에 아주 간단하게 작업할 수 있다. 데이터 삭제도 마찬가지다.

연결리스트의 단점

• 연결리스트는 데이터들이 전부 떨어져 있기 때문에 바로 접근할 수 없습니다.
• 연결리스트에서의 데이터 참조는 O(n)의 성능을 가진다. 배열은 O(1)의 성능을 가져서 더 좋음.

결론

성능을 생각하면 배열이고, 메모리 절약을 위해서는 연결리스트를 선택해서 코딩하면 된다.