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
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)이란, 정의, 단순 계산, 비교, 출력 등의 가장 간..
