공부의 기록 (21) 썸네일형 리스트형 [SWEA] 1289. 원재의 메모리 복구하기 - java ⬛ 1289. 원재의 메모리 복구하기 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV19AcoKI9sCFAZN& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com ⬛ 풀이 방법 0으로 초기화되어 있는 int orgBit 배열을 만들어 입력받은 String과 비교 해당 인덱스의 값이 다르다면 인덱스 이후의 배열값을 해당값으로 바꿈 값을 바꿀 때마다 count++ ⬛ 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStr.. [자료 구조] Heap의 개념 설명과 구현 ⬛ 사전 지식 1. 완전 이진 트리 각 노드가 최대 2개의 자식 노드를 갖는 이진 트리 중 왼쪽부터 차례대로 채워져 있는 트리 최하단 레벨의 노드는 좌측부터 채워져 있어야 한다. 2. 우선순위 큐 우선순위가 높은 데이터가 먼저 나가는 형태의 큐 모든 항목은 우선순위를 가지며 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 큐에서 삭제 우선순위 큐의 구현 방법 배열로 구현할 경우 우선순위를 비교하는 연산이 필요하기 때문에 최대 O(N)의 시간 복잡도를 가진다. 연결리스트로 구현할 경우에도 노드간의 연결을 거쳐 우선순위를 비교하는 연산이 필요하기 때문에 최대 O(N)의 시간 복잡도를 가진다. 완전 이진트리인 힙으로 구현할 경우 최대 O(logN)의 시간 복잡도를 가진다. ⬛ Heap의 개념 우선순위 큐.. [자료 구조] Queue 개념 설명과 구현 ⬛ Queue 개념 한쪽 방향(Rear)에서는 자료의 삽입이, 다른 한 쪽 방향(Front)에서는 자료의 삭제가 이루어지는 FIFO(First In First Out) 형식의 자료 구조 Queue의 가장 먼저 들어온 요소를 Front, 가장 늦게 들어온 요소를 Rear라고 부르며 이 두가지 요소에 의해서만 접근이 가능 Rear에서 이루어지는 삽입 연산을 ‘enQueue’, Front에서 이루어지는 삭제 연산을 ‘deQueue’라고 한다. ⬛ Queue 연산 1. enQueue(int data) : Rear에 데이터를 추가 2. deQueue() : Front에 있는 데이터를 반환 후 삭제 3. peek() : Front에 있는 데이터를 반환 (삭제 x) ⬛ Queue 활용 프로세스 스케줄링 프린터 출력 .. [자료 구조] Stack 개념 설명과 구현(배열, 연결리스트) ⬛ Stack 개념 한 방향에서만 자료를 추가, 삭제할 수 있는 LIFO(Last In First Out) 형식의 자료 구조 가장 최근에 추가된 항목이 가장 먼저 삭제된다. 가장 최근에 추가된 데이터를 top이라고 부르고 추가와 삭제는 이 top에서만 이루어진다. 삽입하는 연산을 'push’라고 하며 삭제하는 연산을 ‘pop’이라고 한다. 만약 스택이 비어있을 때 자료를 꺼내려고 하면(pop) ‘Stack Underflow’가 발생 만약 스택이 꽉 차있을 때 자료를 넣으려고 하면(push) ‘Stack Overflow’가 발생 ⬛ Stack 연산 1. pop() : 스택에서 가장 위에 있는 항목(top)을 제거하며 반환 2. push(item) : item을 스택의 가장 윗 부분에 추가 3. peek().. [자료 구조] LinkedList 개념 설명과 구현 ⬛ LinkedList 개념 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조로 다음 노드에 대한 참조를 통해 연결된다. 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성된다. 동적으로 메모리를 사용할 수 있기 때문에 메모리를 효율적으로 사용할 수 있다. 삭제와 삽입의 과정만은 O(1)으로 해결되지만 해당 위치를 찾기 위해 첫 번째 노드부터 순차적으로 요소에 접근하는 과정에서 O(n)의 시간이 추가적으로 발생한다. 결국 O(n)의 시간복잡도를 가지게 된다. ⬛ LinkedList 연산 1. add(E e) : list의 끝에 지정된 요소를 추가 2. add(int index, E element) : list의 지정된 위치에 지정된 요소 삽입 3. addFirst(E e) : l.. 이전 1 2 3 다음
