들어가며
전날 해야할 일을 정했었는데 컨디션이 좋지 않아 하기로 했던 일을 다 하지 못했다. 그래서 오늘 급하게 어제 정리하지 못했던 강의 내용을 정리하고 오늘 강의까지 들었다. 하루만 밀렸을 뿐인데 시간이 굉장히 촉박한 느낌이었다. 앞으로는 컨디션 조절도 잘해서 공부 밀리는 일 없이 차근차근 하고 싶다.
오늘은 전반적인 자료구조와 알고리즘에 대해 공부했다. 자료구조는 4학년 1학기에 관심이 있어 소프트웨어학부에 개설된 강의를 수강하면서 공부했다. 알고리즘은 따로 공부를 해본 적은 없고 코딩테스트 연습하다가 필요한 알고리즘이 있으면 그때마다 찾아보면서 공부했다. 자료구조와 알고리즘을 배우면 문제 해결 능력을 기르는 데 도움이 될 것 같다.
중요한 점!
특정한 상황에 맞는 자료구조가 있기 때문에 상황에 맞는 자료구조를 잘 선택하는 것이 중요하다. 항상 완벽한 자료구조는 절대 없음.
자료구조의 종류
자료구조의 종류는 크게 단순 구조, 선형 구조, 비선형 구조, 파일 구조로 나뉜다.
- 단순 구조는 정수, 실수, 문자열 등의 자료형을 의미한다.
- 선형 구조는 한 원소 뒤에 하나의 원소만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조를 의미한다. 배열, 연결 리스트, 스택, 큐 등이 선형 구조에 속한다.
- 비선형 구조는 원소 간 다대다 관계를 가지는 구조로 계층적 구조를 표현하기에 적합하다. 트리, 그래프 등이 여기에 속한다.
- 파일 구조는 서로 관련 있는 필드로 구성된 레코드에 대한 자료구조이다. (무슨 소린지 잘 모르겠다.)
시간 복잡도
프로그램의 성능을 정확히 측정할 수 있는 방법은 없다. 왜냐하면 고려해야 할 것이 너무 많기 때문에. 따라서 대략적인 성능을 측정할 수 있는 방법으로 빅오 표기법을 사용한다.
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)
빅오 표기법의 특징
- 데이터 입력값 n이 매우 크다고 가정하기 때문에 상수항은 무시하고 표현한다.
- 데이터 입력값 n의 크기에 영향을 받기 때문에 가장 큰 항 이외의 항은 무시하고 표현한다.
배열/순차리스트 (Array)
배열은 연관된 데이터를 연속적인 형태로 구성한 자료구조이다. 배열에 포함된 원소는 순서대로 번호(index)가 붙는다. 배열의 특징으로
- 고정된 크기를 가진다. 그러나 스크립트 언어(자바스크립트, 파이썬, 루비 등)에서의 배열은 자동으로 크기가 변하도록 설계되었다.
- 번호(index)를 알고 있으면 O(1)로 원하는 원소를 찾을 수 있다.
- 원소를 삭제하면 해당 번호(index)에 빈 자리가 생긴다. 그렇기 때문에 배열에 요소를 추가하거나 삭제할 경우 O(n)의 시간이 소요된다. 따라서 탐색이 많을 경우 유리하다.
가 있다.
연결 리스트 (Linked List)
추가와 삭제에 용이한 자료구조이다. 각 요소(또는 노드)를 포인터로 연결하여 관리한다. 맨 처음 시작 노드를 Head라고 하고 마지막 노드를 Tail이라고 한다. 제한 없이 요소를 동적으로 추가할 수 있다는 장점을 가지고 있다. 배열과는 다르게 탐색에 O(n)이 소요되고, 요소를 추가하거나 삭제할 때는 O(1)이 소요된다.
연결리스트는 크게 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linked List) 가 있다.
- 단일 연결 리스트: Head에서 Tail까지 단방향으로 이어지는 연결 리스트이다.
- 요소 찾기: Head 포인터부터 시작해서 순서대로 노드를 순회한다.
- 요소 추가: 추가할 위치의 이전 요소가 추가할 요소를 가리키게 하고 추가할 요소는 추가할 위치의 이전 요소가 가리키던 다음 위치의 요소를 가리키게 하면 된다.
- 요소 삭제: 삭제할 요소의 이전 요소가 삭제할 노드의 다음 요소를 가리키게 수정하면 된다. 이때 삭제할 요소는 가비지 콜렉터(Garbage Collector)에 의해 자동으로 메모리에서 삭제된다.
- 이중 연결 리스트: 단일 연결 리스트에서 각 노드가 다음 노드와 이전 노드를 모두 가리키게 만든 연결 리스트이다.
- 요소 찾기: 단일 연결 리스트와 같다. 다만, 단일 연결 리스트의 반대방향으로의 순회를 통해 요소를 찾을 수도 있다.
- 요소 추가: 추가할 요소의 포인터를 이전 요소와 다음 요소를 가리키게 하고, 이전 요소의 다음 요소 포인터는 추가할 요소를, 다음 요소의 이전 요소 포인터는 추가할 요소를 가리키게 수정한다.
- 요소 삭제: 삭제할 요소의 이전 요소의 다음 요소 포인터를 삭제할 요소의 다음 요소를 가리키게 하고, 삭제할 요소의 다음 요소의 이전 요소 포인터를 삭제할 요소의 이전 요소를 가리키게 한다.
- 원형 연결 리스트: 단일 연결 리스트나 이중 연결 리스트와 기본적인 구조는 같지만 Tail 노드의 포인터가 null 을 가리키는 것이 아니라 Head 노드를 가리키는 연결 리스트를 의미한다. 중간 요소부터 탐색을 시작했을 때 끝 노드에서 시작 노드로 가기 때문에 중간부터 탐색을 시작해도 연결 리스트를 한 바퀴 돌 수 있다.
단일 연결 리스트를 자바스크립트 코드로 구현해보았다.
1 class Node {2 constructor(value) {3 this.value = value;4 this.next = null;5 }6 }78 class SinglyLinkedList {9 constructor() {10 this.head = null;11 this.tail = null;12 }1314 find(value) {15 let curNode = this.head;16 while (curNode.value !== value) {17 curNode = curNode.next;18 if (curNode === this.tail) {19 curNode = null;20 break;21 }22 }23 return curNode;24 }2526 append(newValue) {27 const node = new Node(newValue);28 if (this.tail === null) {29 this.head = node;30 this.tail = node;31 } else {32 this.tail.next = node;33 this.tail = node;34 }35 }3637 insert(node, newValue) {38 if (node === null) {39 console.log("존재하지 않는 노드입니다. insert를 진행할 수 없습니다.");40 } else {41 const newNode = new Node(newValue);42 newNode.next = node.next;43 node.next = newNode;44 }45 }4647 remove(value) {48 let prevNode = this.head;49 while (prevNode !== this.tail && prevNode.next.value !== value) {50 prevNode = prevNode.next;51 }52 if (prevNode.next !== null) {53 prevNode.next = prevNode.next.next;54 }55 }5657 size() {58 let count = 0;59 let curNode = this.head;60 while (curNode !== null) {61 count++;62 curNode = curNode.next;63 }64 console.log(count);65 }6667 display() {68 let curNode = this.head;69 let string = "[";70 while (curNode !== null) {71 string += `${curNode.value}`;72 curNode = curNode.next;73 }74 string += "]";75 console.log(string);76 }77 }7879 const LinkedList = new SinglyLinkedList();80 LinkedList.append("1");81 LinkedList.append("2");82 LinkedList.append("3");83 LinkedList.append("4");84 LinkedList.append("5");85 LinkedList.display(); // [12345]86 LinkedList.insert(LinkedList.find("8"), "7"); // 존재하지 않는 노드입니다. insert를 진행할 수 없습니다.87 LinkedList.display(); // [12345]88 LinkedList.remove("2"); // 값이 2인 노드 제거89 LinkedList.display(); // [1345]90 LinkedList.size(); // 4
(코드가 너무 길어서 이중 연결 리스트와 원형 연결 리스트는 따로 코드 추가 예정)
배열과 연결리스트의 차이?
배열은 메모리를 연속적으로 사용하고, 연결리스트는 각 데이터가 저장된 메모리가 퍼져있다.
스택
나중에 들어간 값이 먼저 나오는 LIFO(Last In First Out) 자료구조이다. 스택 자료구조를 사용하는 예로 자바스크립트 엔진의 콜스택이 있다. 함수의 호출을 담는 역할을 한다.
자바스크립트에서는 배열을 사용하거나 연결 리스트로 구현해 사용할 수 있다. 자바스크립트 배열의 기본 메서드로 push 와 pop 이 있는데 이를 사용해 쉽게 스택 자료구조를 사용할 수 있다.
스택을 사용하는 코딩테스트 문제로 프로그래머스의 올바른 괄호 문제가 있다. 아래는 내가 작성한 코드이다. 같은 코드라도 가끔 효율성 테스트에 통과하지 못할 때가 있는데 그건 왜 그런지 모르겠다.
1 function solution(s) {2 const stack = [];3 for (let i = 0; i < s.length; i++) {4 const e = s[i];5 if (e === "(") {6 stack.push(e);7 } else {8 if (stack.length === 0) {9 return false;10 }11 stack.pop();12 }13 }14 return stack.length === 0;15 }
정리
자료구조와 알고리즘을 공부하기에 가장 좋은 방법은 코딩테스트 문제를 푸는 것이라고 생각한다. 오늘 배운 것처럼 적절한 자료구조와 알고리즘을 사용하려면 많은 문제를 경험해보고 그에 따라 효율적인 방법을 더 빠르고 정확하게 선택할 수 있을 것이라고 생각한다. 코딩테스트를 풀 때 정확도 보다 효율성이 어렵다고 느끼는 건 나뿐만이 아닐 것이다. 효율성을 통과해야하는 문제를 만났을 때 덜 당황하기 위해 시간 복잡도 개념을 좀 더 정확하게 이해해야겠다.
TMI
블로그에 글을 정리할 때
- 마크다운 웹 에디터로 글을 쓰고 결과물을 미리 확인
- 에디터에 쓴 글을 그대로 .mdx 파일로 생성 후
- 블로그 github repository에 푸시
하는 과정을 거친다.
웹 에디터에서 결과물을 확인할 때에는 디자인이 깔끔해서 그런지 좀 더 글을 잘 쓴 것 같은 느낌을 받아 뿌듯한데, 그대로 블로그에 올리게 되면 디자인이 별로라 그런지 글이 훨씬 못 쓴 것 같고 못생겨보인다. 정리가 안 된 느낌도 받는데 다른 사람이 읽었을 때 그런 느낌이 있을까봐 걱정이다. 또, 지금은 이미지를 첨부하는 과정이 번거로워서 이미지를 넣지 않았다. 빠른 시일 내에 블로그를 수정해야겠다.
아 그리고 얼마 전부터 집에 있는 데스크탑을 서버 컴퓨터로 쓰고 싶다는 생각을 해서 우분투를 설치하고 LG U+와 IPTIME 공유기의 포트 포워딩을 통해 외부에서도 컴퓨터에 접속할 수 있게 만들었다. 원래는 개인 블로그 서버로 사용할 목적으로 만들었는데 개발하기까지 시간이 좀 걸릴 것 같아 보류해두고 있었다. 당장 어디에 쓸 수 있을까 고민하고 있었는데 요즘 노트북에 저장공간이 부족해 ssh로 우분투에 접속하고 거기서 작업을 하기 시작했다! 별거 없지만 뭔가 나만의 클라우드가 생긴 것 같아 기분이 좋았다. 끝.
참고자료
자료구조란? https://0verc10ck.tistory.com/1
빅오 표기법 https://noahlogs.tistory.com/27
스크립트 언어란? https://m.blog.naver.com/rlarbtjq7913/221711007833
콜스택 https://alstn2468.github.io/Javascript/2020-02-28-callstack/