개발자로 살아남기

우선순위 큐(Priority Queue)와 힙(Heap) 우선순위 큐 (Priority Queue) 기존의 큐와 다르게 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나옴 데이터간에 순서가 보장되지 않음 ex) 2, 3, 4, 1, 5 추가 후 iterator를 이용해 출력 시 1, 2, 4, 3, 5로 출력 구현방법 및 특징 - 배열 기반으로 구현 1) 인덱스로 데이터에 바로 접근할 수 있음 2) 데이터의 삽입/삭제에서 데이터들을 한칸씩 뒤로 밀거나 당기는 연산이 있어야 함 3) 삽입의 위치를 찾아내기 위해 최악의 경우 배열의 모든 데이터들과 우선순위를 비교해야 함 4) 저장 시 시간복잡도 O(n), 삭제 시 시간복잡도 O(1) - 연결리스트 기반으로 구현 1) 삽입의 위치를 찾기위해 최악의 경..

트리 (Tree) 트리 (Tree) 비선형 자료구조 계층적 관계를 표현하는 자료구조 (일상생활에서 사용하는 회사의 조직도 등) 여러 노드가 하나의 노드를 가리킬 수 없는 구조 (아래 그림은 트리가 아님) 용어 정리 노드 (node) - 트리의 구성요소로, 위 그림에서 A, B, C, D, E, F가 이에 해당됨 간선 (edge) - 노드와 노드를 연결하는 선 루트 노드 (root node) - 위 그림의 트리구조에서 최상위에 존재하는 A를 의미 단말노드 (terminal node) 또는 잎사귀 노드 (leaf node) - 다른 노드가 연결되어있지 않은 노드로서 위 그림에서 E, F, C, D가 이에 해당됨 내부노드 (internal node) 또는 비단말 노드 (nonterminal node) - 단말..

큐 (Queue) 큐 (Queue) 먼저 들어간 데이터가 먼저 나오는 구조 (선입선출) (FIFO, First-In, First-Out) 마트에서 계산 대기할 때, 영화관 입장 시 등등 데이터 삽입 시 위치를 알기 위한 Rear 변수 필요 데이터 반환 시 위치를 알기 위한 Front 변수 필요 데이터 삽입과 반환이 이루어지는 위치가 다름 (스택은 동일한 위치에서 pop과 push가 이루어지지만, 큐는 Rear, Front를 통해 위치를 알아내야 함) 추상자료형 (ADT) 자료형 반환값 설명 initialize() void 큐(Queue) 초기화 isEmpty() boolean 큐가 비어있는지 확인 enqueue(Data) void 큐에 데이터 삽입 dequeue() Data 맨 앞에 있는 데이터 반환 및..

스택을 이용한 후위 표기법 (postfix) 후위 표기법 연산 순서의 정보가 담겨있음 예) 중위 표기법 : 5+2/7 전위 표기법 : +5/27 후위 표기법 : 527/+ 위 예시에서 후위 표기법에서 나누기(/) 연산자가 더하기(+) 연산자보다 앞에 있으므로 나누기 연산부터 진행 후 더하기 연산을 한다는 것을 알 수 있음 연산자의 우선순위에 대해 알 필요가 없음 - 연산자의 배치 순서에 따라 연산 순서가 결정됨 - 위 같은 특성 때문에 소괄호에 대한 처리도 불필요함 소괄호가 없는 중위표기법에서 후위 표기법으로 변경하는 방법 예시) 중위표현식 : 5+2/7 숫자는 그대로 표현한다. 연산자는 스택에 저장한다. 스택에 연산자가 있을 경우 우선순위를 비교한다. 3-1. 새로 추가할 연산자의 우선순위가 더 높을 ..

스택 (Stack) 스택 (Stack) 선형 자료구조 프링글스처럼 한 쪽은 막혀있고 다른 한 쪽으로 과자를 꺼내거나 넣는 것 후입선출 (Last-In, First-Out, LIFO) 구조 마지막에 삽입한 것이 먼저 나오는 구조 배열 또는 리스트로 구현 가능 추상 자료형 (ADT) 자료형 반환값 내용 initialize() void 스택 초기화 push(Data) void 스택에 데이터 삽입 pop() Data 데이터 반환 후 삭제 peek() Data 데이터 반환 후 삭제하지 않음 isEmpty() boolean 스택이 비어있는지 확인 배열로 스택 구현 배열의 크기를 고정해야 함 스택에서 가장 마지막에 삽입된 위치를 저장하는 변수가 필요 (topIndex) 구현 디렉토리 구조 ArrayStack.java..

양방향 연결 리스트 (이중 연결 리스트) 양방향 연결 리스트 이중 연결 리스트라고도 함 노드가 양쪽 방향으로 연결된 구조 구조 기본 연결 리스트에서 이전 노드를 가리키는 prev 변수 필요 - 기존에 구현한 연결 리스트에서는 삭제할 노드의 이전 노드와 삭제할 노드의 다음 노드를 사로 연결해주기 위해 앞에서부터 탐색하여 이전 노드를 찾음 (첫번째부터 탐색을 진행하기 때문에 데이터가 많아질수록 부하가 발생) - 양방향 연결 리스트의 경우 이전 노드를 바로 알 수 있기 때문에 성능상 이점이 있음 추상 자료형 자료형 반환값 내용 initialize() void 리스트 초기화 insert(Data) boolean 리스트에 데이터 삽입 first() Data 첫번째 데이터를 가리키도록 함 (Dummy 노드를 추가한..

단순 연결 리스트 단순 연결 리스트 크기가 변경 불가능한 배열의 단점을 극복 (배열은 정적인 메모리 구성) 크기가 정해져있지 않음 (동적인 메모리 구성) 데이터들을 Node로 관리 (Node : data, 다음 노드의 주소값으로 이루어져 있음) 리스트는 데이터의 저장 순서를 유지해야하는 자료구조가 아님 Node 리스트의 구성 필요한 Node들 head : 리스트의 머리를 가리킴 tail : 리스트의 꼬리를 가리킴 cur : 데이터의 조회에 사용됨 head에 데이터 추가 시 장점 : tail 노드가 불필요 단점 : 저장 순서가 유지되지 않음 tail에 데이터 추가 시 장점 : 저장 순서가 유지됨 단점 : tail 노드가 필요 데이터 추가 tail 또는 head쪽에 데이터 추가 후 tail 또는 head가 ..

순차 리스트 순차 리스트 데이터가 메모리에 연속적으로 저장됨 (ex. 배열 등) 장점 1) 인덱스로 데이터에 접근할 수 있으므로 속도가 빠름 단점 1) 배열의 길이가 사전에 정의되어야 함 2) 중간 데이터 삭제 시 해당 인덱스 이후의 값들은 한 칸씩 이동이 발생 설명 삽입 - 보통 배열의 마지막에 데이터가 삽입되며, 삽입 시 배열의 크기도 고려해야 함 - 배열의 중간에 데이터를 삽입하기 위해서는 배열의 길이가 충분한지 확인해야 하며, 삽입된 위치 뒤에 존재하는 모든 데이터들이 한 칸씩 뒤로 이동해야 하므로 중간에 데이터 삽입 시 비효율적 - 시간 복잡도 : O(n) 삭제 - 배열의 중간에 위치한 데이터를 삭제할 경우 해당 위치의 뒤 데이터들은 한 칸씩 앞으로 이동해야 하므로 배열의 크기가 크고 삭제가 빈..