Thread Safe Multi-Thread 상황에서 함수, 변수, 객체에 동시 접근이 발생해도 프로그램 실행에 문제가 되지 않는것을 의미한다. Java에서 Thread Safe를 유지하는 방법을 알아보았다. 1. Confinement(제한) 지역 변수는 각 스레드의 자체 스택에 저장되고, 스택은 고유한 영역으로 동시 접근이 발생하지 않는다. 사용 예시 public class Factorial { private static void computeFact(final int n) { BigInteger result = new BigInteger("1"); for (int i = 1; i
MST(Minimum Spanning Tree 최소 신장 트리) 신장 트리 : 모든 정점이 연결된 그래프, 사이클이 존재하지 않아야 한다. n개의 점을 (n-1) 개의 간선으로 연결한다. 최소 신장 트리 : 신장 트리 중 간선 가중치의 합이 가장 작은 신장 트리를 의미한다. Prim(프림) 알고리즘 시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장해 나가는 방법이다. 수행 과정 임의의 정점을 시작 지점으로 선택 연결된 모든 간선의 가중치를 비교 가장 작은 무게의 간선 선택(사이클이 만들어지지 않도록) 모든 정점이 연결될 때까지 2~3번 과정 반복 시간복잡도 V : 정점의 개수 E : 간선의 개수 우선순위 큐로 구현 우선순위 큐 생성 작업 : O(logV) * O(E) = O(ElogV) 각 노드에서..
Heap(힙) 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 💡 완전 이진 트리 : 이진 트리의 일종으로, 자식은 왼쪽부터 연결한다. (왼쪽 자식이 없으면서 오른쪽 자식이 존재할 수 없다) 일종의 반정렬 상태를 유지한다. 부모와 자식간에 정렬된 상태지만, 형제 노드간의 정렬은 이루어지지 않은 상태다. 중복된 값을 허용한다. (이진 탐색트리는 중복허용 X) 힙 종류 최대 힙(Max Heap) 부모 노드가 자식 노드보다 크거나 같은 완전 이진 트리 최소 힙(Min Heap) 부모 노드가 자식 노드보다 작거나 같은 완전 이진 트리 힙 구현 일반적으로 배열을 사용한다.(연결 리스트로 구현할 수도 있긴 하다.) 구현의 편의성을 위해 0번 인덱스는 사용하지 않는다. 일정한 규칙을 유지한다...
트리(Tree) 계층적인 자료를 표현하는 자료구조다. 나무를 거꾸로 한 모습이다. 사이클이 존재하지 않고, 모든 노드가 연결되어 있다. 방향 그래프이다 트리 관련 용어 이진 트리(Binary Tree) 자식의 노드의 수가 최대 2개인 트리를 의미한다. 트리 순회(Tree Traversal) 전위 순회(Pre-order Traversal) : 노드, 왼쪽 자식, 오른쪽 자식 순서로 방문하는 순회 방법 A-B-D-E-C-F-G 의 순서 중위 순회(In-order Traversal) : 왼쪽 자식, 노드, 오른쪽 자식 순서로 방문하는 순회 방법 D-B-E-A-F-C-G 의 순서 후위 순회(Post-order Traversal) : 왼쪽 자식, 오른쪽 자식, 노드 순서로 방문하는 순회 방법 D-E-B-F-G-C..
Stack(스택) 삽입(push)과 삭제(pop)이 한쪽 끝(top)에서만 일어나는 자료구조다. top : 가장 상단에 위치한 원소를 가리키는 용어 push() : top 위치에 데이터를 삽입하는 기능 시간복잡도 : O(1) 용량이 꽉 찬 스택에 push()를 시도하면 Stack Overflow 에러가 발생한다. pop() : top 위치의 데이터를 삭제/반환 하는 기능 시간복잡도 : O(1) 데이터가 없는 스택에 pop()을 시도하면 Stack Underflow 에러가 발생한다. 특징 후입선출 LIFO(Last In First Out) 특정 데이터를 찾기 위해서는 해당 값을 찾을 때 까지 pop()을 반복해야 한다 - O(N) JAVA 에서는 Stack 라이브러리를 제공한다. Queue(큐) 삽입(en..
Linked List(연결 리스트) 특징 노드가 연결되어 있는 형태의 자료구조다. 노드 : 데이터 + 다음 노드를 가리키는 포인터 연속되지 않은 메모리 공간에 저장(+동적 할당) 시간복잡도 접근 / 탐색 : O(N) 첫 번째 노드부터 (N-1)번을 거쳐 가야 한다. 삽입 / 삭제 : 단순 삭입/삭제 : O(1), but 현실적으로 O(N) 단순하게 연결된 구조만 변경하면 된다. 그러나, 원하는 위치에 삽입/삭제 하기위해서는 접근, 탐색의 과정이 필요하다. 따라서, O(1 + N - 1) ⇒ O(N)이 된다. 배열(Array)과의 차이 배열과 달리 크기에 제한이 없어 삭제/추가 작업이 자유롭다. 배열에 비해 접근, 탐색에 시간이 오래걸린다. 배열의 접근,탐색 시간복잡도 : O(1) 참고 간략 설명! 배열(..
등장 배경 코드의 성능, 효율성을 판단할 기준이 필요했다. 실제 실행시간과 메모리 사용량을 측정한다면? 하드웨어의 성능, 소프트웨어(운영체제)의 성능, 호환성 등 외부 요인이 작용하여 동일한 기준으로 비교할 수 없다. 미완성 코드는 실행이 불가능하므로 측정이 불가능하다. → 다른 요인과 무관하게 입력 크기에만 영향을 받는 이론적 시간 측정 방법을 만들었다. 시간복잡도 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다. 점근 표기법을 이용하여 나타낸다. 💡 점근 표기법이란, 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법을 말한다. 단위 연산의 횟수를 기준으로 계산한다. 💡 단위 연산(primitive operation)이란, 정의, 단순 계산, 비교, 출력 등의 가장 간..
