11월, 12월, 1월 초중순까지 프로그래머스에서 코딩테스트 문제를 풀다가(Lv.0 ~ 1 수준) 팀프로젝트와
정보처리기사 공부를 하면서 나도 모르게 코테 문제를 풀고 알고리즘 공부하는 것에 매우 소홀해져 있었습니다.
알고리즘 유기해버리면 큰일나니 다시 정신을 부여잡고 시작하기로 했습니다.
JS로 하지말고 파이썬으로 하는게 더 유리하고 좋다는 팀원들의 말도 있었고,
실제로 파이썬으로 준비하는 사람들의 비중도 꽤 높던데 저는 JS로 준비해볼려고 합니다.
프론트엔드 개발자로 취업하고 계속 일을 할려면 JS로 문제 해결할 수 있는 능력과
기본적 토대가 되어있어야 할텐데 JS로 준비하는게 도움이 되지 않을까요.
그리고 따로 파이썬으로 할 만큼 시간도 마음도 여유가 없는 것도 큽니다.
원래는 그냥 프로그래머스에서 문제를 풀어보고, 안 풀리는 문제는 답을 찾아보고 어떻게 풀었고
왜 이렇게 풀었는지 다른 사람의 답안을 보고 이해하면서(이해가 안 되면 외우려고 했다) 풀었는데
기본적으로 알고리즘의 종류가 어떤 게 있는지 모르는 상태에서
그냥 배열 관련 함수와 Set과 관련된 함수 등을 이용하여 무작정 풀려고 하니 매우 비효율적이었습니다.
그래서 패스트캠퍼스에서 UPSKILL : Javascript 코딩테스트 131개 예제 & CS지식으로 끝내기라는 강의를 구매했는데 강의를 중간에 멈췄다가 다시 듣기 시작했습니다. 백준 문제를 예제로 사용하여 혼자 먼저
풀고 영상을 보면서 정답과 풀이 방식을 확인하는 식으로 진행되고 있으며 해당 강의는 유명한 강사인 나동빈님께서 진행합니다.
그럼 알고리즘을 공부하기 위해서 알아야 하는 기본 개념인 자료구조들의 종류와 개념에 대해서 정리해보도록 하겠습니다.
🌱 알고리즘의 기본인 자료구조
자료구조는 다수의 자료(데이터)를 담기 위한 구조입니다.
그렇기 때문에 자료의 수가 많아질 수록, 효율적으로 이를 저장할 수 있어야 합니다.
그래서 이런 자료의 양이 늘어날 때 제대로 관리하기 위해서는 자료구조의 필요성을 이해하고 있어야 합니다.
만약 자료구조를 제대로 이해하지 못하면, 불필요하게 메모리와 계산을 낭비할 여지가 있습니다.
선형 구조(Linear Data Structure)
- 배열 Array
- 연결 리스트 Linked List (단일, 이중)
- 스택 Stack
- 큐 Queue
비선형 구조(Non-Linear Data Structure)
- 트리 Tree
- 그래프 Graph
선형 자료구조는 하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조입니다.
데이터가 일렬로 연속적 연결이 되어있는 형태입니다.
반대로 비선형 자료구조는 하나의 데이터 뒤에 다른 데이터가 여러 개 올 수 있는 자료구조입니다.
데이터가 일직선상으로 연결되어 있지 않아도 되는 형태입니다.
알고리즘과 자료구조의 상호관계
자료구조를 이해하고 효율적으로 설계하기 위해서는 알고리즘 지식이 필요합니다.
문제 상황에 맞는 적절한 자료구조가 사용되어야만 효율적인 알고리즘을 작성할 수 있습니다.
그렇기에 자료구조와 알고리즘은 서로 필요로 하는 존재죠.
둘을 공부하고 익히는 것은 프로그래밍을 할 때에 메모리 낭비와 재사용성이 좋은 코드 생성과도 직결됩니다.
프로그램의 성능 측정 방법
- 시간 복잡도: 알고리즘에 사용되는 연산 횟수를 측정
- 공간 복잡도: 알고리즘에 사용되는 메모리의 양을 측정
코딩테스트를 위한 문제를 풀 때는 공간을 많이 사용하는 대신 시간 복잡도를 단축하는 방법을 주로 사용합니다.
보편적인 시간 복잡도 표기법으로는 Big-O 표기법을 사용합니다.
Big-O 표기법은 복잡도를 표현하는 방법으로 최악의 시간 복잡도를 표기합니다.
특정한 알고리즘이 얼마나 효율적인지 수치적으로 표현하는 방법입니다.
Big-O는 가장 빠르게 증가하는 항(가장 큰 항)만을 고려하는 표기법입니다(최악일 때의 시간).
일반적으로 연산 횟수가 10억을 넘기면 1초 이상의 시간이 소요된다고 합니다.
가장 큰 항에 붙어있는 계수는 제거합니다. N이 무한대로 증가하면 계수는 의미가 없어지기 때문이죠.
현실 세계에서는 동작 시간이 1초 이내인 알고리즘을 설계해야 합니다.
그래서 시간 복잡도를 고려하는 것이 매우 매우 중요합니다.
효율적인 알고리즘을 만들기 위해 각 자료구조의 종류별 개념과 사용 예시를 알아봅시다.
🌱 배열 Array
가장 기본적인 자료구조입니다. 여러 개의 변수를 담는 공간에 해당합니다.
배열은 인덱스가 존재하고 0부터 시작한다. 그래서 특정한 인덱스에 직접적으로 접근이 가능합니다.
인덱스 접근의 수행 시간 : O(1)
컴퓨터의 메인 메모리에서 배열의 공간은 연속적으로 할당됩니다.
그래서 장점은 캐시 히트 가능성이 높고, 조회가 빠릅니다.
캐시 히트
캐시에서 데이터를 성공적으로 찾는 것으로, 캐시 히트율은 전체 메모리 접근 중
캐시에서 데이터를 성공적으로 찾은 비율을 말합니다.
캐시 히트율이 높을수록 캐시에서 데이터를 더 자주 찾을 수 있다는 의미입니다.
단점은 배열의 크기를 미리 지정해야 하는 것 때문에 데이터 추가 및 삭제에 한계가 있습니다.
자바스크립트 배열의 특징
동적 배열의 기능을 제공하기 때문에 맨 뒤의 위치에 원소 추가가 자유롭게 가능합니다.
let arr = [1, 2, 3, 4];
arr.push(5);
// 결과
[1, 2, 3, 4, 5]let arr1 = [1, 2, 3, 4, 5];
let arr2 = [6, 7, 8, 9, 10];
let arr = arr1.concat(arr2, [11, 12], [13]);
// 결과
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]그래서 배열의 용량이 가득 차면, 자동으로 배열의 크기를 증가시킵니다.
임의의 크기를 가지는 배열을 만들 수 있어서 원하는 값을 직접 입력하여 초기화 할 수 있습니다.
let arr = Array.from({ length: 5 }, () => 7);
// 결과
[ 0, 1, 2, 3, 4 ]
[ 7, 7, 7, 7, 7 ]2차원 배열이 필요할 때는 원하는 값을 직접 넣어 초기화 할 수도 있습니다.
let arr = [
[0, 1, 2, 3],
[4, 5, 6, 7],
[8, 9, 10, 11]
];
// 결과
[
[ 0, 1, 2, 3 ],
[ 4, 5, 6, 7 ],
[ 8, 9, 10, 11 ]
]한 줄로 2차원 배열을 초기화 할 수도 있습니다.
let arr = Array.from(Array(4), () => new Array(5))
// 결과
[
[ <5 empty items> ],
[ <5 empty items> ],
[ <5 empty items> ],
[ <5 empty items> ]
]반복문을 사용해서 2차원 배열을 초기화시키는 방법도 있습니다.
let arr = new Array(3);
for (let i = 0; i < arr2.length; i++) {
arr2[i] = Array.from(
{ length: 4 },
(undefined, j) => i * 4 + j
);
}
console.log(arr2);내부적으로 포인터를 사용해서 연결 리스트의 장점도 가지고 있다.
배열 혹은 스택의 기능이 필요할 때 사용할 수 있다. 다만 큐의 기능은 제공하지 않는다.
배열의 원소로 객체를 담을 수도 있다.
그 외에 slice, indexOf와 같은 대표적인 배열 인덱싱 함수들을 사용하여 배열에서 원소값을 꺼낼 때
유용하게 사용하기도 합니다.
🌱 단일 연결 리스트 Single Linked List
연결 리스트는 각 노드가 한 줄로 연결되어 있는 자료 구조입니다.
배열과 달리 컴퓨터의 메인 메모리상에서 주소가 연속적이지 않습니다.
그리고 크기가 정해져 있지도 않기 때문에 크기가 동적으로 변경 가능합니다.
각 노드는 '데이터, 포인터'의 형태를 띱니다.
- 포인터: 다음 노드의 메모리 주소를 가리키는 목적으로 사용됩니다. 보통 .next로 사용합니다.
- 연결성: 각 노드의 포인터는 다음 혹은 이전 노드를 가리킵니다.
시간 복잡도
- 삽입: O(1)
- 삭제
shift(맨 앞): O(1)
pop(맨 뒤) - O(n) - 탐색: O(n)
- 접근: O(n)
pop의 시간 복잡도가 n인 이유는 마지막 노드를 찾기 위해서 리스트를 순회해야 하기 때문입니다.
이중 연결 리스트에서는 O(1)입니다.
특징
장점
포인터를 통해 다음 데이터의 위치를 가리키기 때문에, 삽입과 삭제가 간편합니다.
삽입 작업과 리스트 맨 앞 노드의 제거 작업 등이 빈번할 경우,단방향 연결 리스트가 배열의 훌륭한 대안이 됩니다.
단점
특정 n번째의 원소를 검색할 때는 앞에서부터 원소를 찾아야 하기 때문에 검색(searching) 속도가 느립니다.
연결 리스트를 이용하면 다양한 자료구조를 구현할 수 있습니다.
대부분의 알고리즘 문제에서는 연결 리스트를 직접 구현하지 않아도 문제 해결에 어려움이 없습니다.
🌱 배열 vs 연결 리스트
배열에 새로운 원소를 삽입 할 때는 최악의 경우 원하는 인덱스에 원소를 삽입하기 위해서
한 칸씩 값들을 다 밀어버리는 상황이 나옵니다.
그리고 한 원소를 삭제할 때, 최악의 경우 삭제된 인덱스를 메꾸기 위해서 뒤의 원소들을
한 칸씩 앞으로 당기는 상황이 나옵니다. 따라서 최악의 경우 시간 복잡도는 O(N)입니다.
하지만 연결 리스트를 이용하면 단순히 연결만 끊어주면 됩니다.
따라서 삭제할 위치를 정확히 알고 있는 경우 O(1)의 시간만 소요됩니다.
연결 리스트에서는 삽입할 위치를 알고 있다면 물리적인 위치를 한 칸씩 옮기지 않아도 삽입할 수 있습니다.
삭제의 경우에도 똑같다. 포인터만 바꿔주면 되기 때문입니다.
뒤에 붙이는 경우는 가장 쉽습니다. 마지막 노드의 다음 위치에 연결시켜주면 됩니다.
🌱 마무리
배열과 단일 연결 리스트에 대해서 정리했습니다.
배열은 실제 프로그래밍에서도 숨쉬듯이 사용되고, 코딩테스트 문제에서도
그냥 기본 중에 기본으로 사용되는 자료구조입니다.
배열을 조작하는 메소드를 잘 알고 있다면 문제를 풀 때 효율적인 접근법을 생각할 수 있습니다.
그래서 평소에 꾸준히 배열 관련 함수를 사용해보는 연습도 필요합니다.
