자료구조와 알고리즘 (12) 썸네일형 리스트형 알고리즘 어떻게 준비할까? 알고리즘이란 어떤 문제를 해결하기 위한 절차나 방법을 말합니다. 꼭 컴퓨터 세계에서만 쓰이는 단어는 아닙니다. 수학을 포기한 학생이 수학 시험 답안을 적을 때 12345라는 일정한 패턴을 쓴다면 이것도 알고리즘이라고 할 수 있습니다. 컴퓨터는 사람들의 반복적인 일을 빠르고 정확하게 처리해줍니다. 이렇게 블로그에 글자를 입력하는 것도 사람이 어떤 자판을 눌렀을 때 바로 화면에 그려준다는 점에서, 이 입력과 출력 사이에 컴퓨터 내부적으로 동일한 패턴이 이뤄진다는 점에서 알고리즘이라고 할 수 있습니다. 이 단순한 입출력 말고도 컴퓨터의 모든 부분이 알고리즘으로 되어 있습니다. 때문에 컴퓨터를 다루는 개발자가 되기로 마음먹었다면 알고리즘은 반드시 공부해야 합니다. 그러면 이 알고리즘은 어떻게 해야 잘할 수 있을.. 시간 복잡도 (Time Complexity) 알고리즘마다 시간 복잡도를 측정하는 이유는 성능 때문이다. 데이터의 수가 늘어남에 따라서 알고리즘의 처리수가 어떻게 증가하는지를 알면 같은 문제를 해결할 때 어떤 알고리즘이 대량의 데이터를 다루기 적절한지를 파악할 수 있다. 컴퓨터의 연산 속도는 엄청 빨라서 작은 처리수의 증가는 의미 없고 처리수를 구하는 식에 가장 큰 영향을 주는 부분만 떼서 보는 식으로 시간 복잡도를 계산한다. 시간 복잡도는 Big O를 써서 다음과 같이 표현한다. O(1), O(log n), O(n), O(n²), O(c의 n제곱) O(1)은 데이터량과 관계없이 동일한 처리수를 가질 때를 말한다. O(log n)은 데이터량이 늘어날 때 처리수가 증가하지만 갈수록 늘어나는 폭이 줄어드는 때를 말한다. O(n)는 데이터량이 늘어나는만큼.. 리스트, 해시 테이블, 그래프, 트리 (Linked List, Hash Table, Graph, Tree) 1. Linked List 리스트는 데이터가 저장되는 노드에 데이터 필드와 링크를 마련해놓고 데이터 필드에 데이터를, 링크에 다음 노드가 무엇인지를 가리키는 정보를 저장한다. 때문에 정적 배열과 달리 중간의 노드를 삭제하더라도 삭제한 노드의 앞 노드의 링크를 뒤 노드에 연결시켜 단순한 작업으로 데이터를 수정할 수 있다. 노드를 추가하는 것도 마찬가지다. 다만 노드에 두 정보가 들어가니 정적 배열보다 용량이 클 수밖에 없다. 노드에 링크 하나가 있으면 Singly Linked List라고 하고 링크가 둘 있으면 Doubly Linked List라고 한다. 링크가 하나 더 있으면 양쪽 방향으로 움직일 수 있어 성능이 더 좋을 것으로 생각되지만 용량은 더 커진다. 끝 노드의 링크를 첫 노드에 연결시켜 Circ.. 스택과 큐 (Stack & Queue) 1. Stack LIFO (Last in First out) 스택이 데이터를 처리하는 방식을 일컫는 말이다. 나중에 들어온 데이터가 먼저 나간다. 데이터를 넣기 위해 push라는 함수를 쓰면 아무 데이터도 없을 때 null을 가리키고 있던 top이 새로 들어온 데이터를 가리키게 되고 이렇게 push를 할 때마다 top이 새로운 데이터를 가리킨다. 데이터를 빼기 위해 pop이라는 함수를 쓰면 top이 바로 아래의 데이터를 가리키게 되고 위의 데이터를 빼서 반환한다. 2. Queue FIFO (First in First out) 큐가 데이터를 처리하는 방식을 일컫는 말이다. 먼저 들어온 데이터가 먼저 나온다. 데이터를 넣기 위해 enqueue라는 함수를 쓰면 첫 데이터가 들어왔을 때 front와 end가 첫.. 이전 1 2 다음
