똑똑한망치의 성장일기

1. 우선순위 큐란 무엇인가 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 FIFO (First In First Out) 구조를 가진다. 여기서 FIFO 구조란 먼저 들어온 데이터가 먼저 나가는 구조이다. 우선순위 큐(Priority Queue)는 먼저 들어온 순서대로 데이터가 나가는 것이 아니라 우선순위를 먼저 결정하고 우선순위가 높은 element가 먼저 나가는 자료구조이다. 우선순위 큐는 힙(Heap)을 이용하여 구현하는 것이 일반적이다. (1) 우선순위 큐의 특징 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조 ( 우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야 한다.) 내부구조가 힙으로 구성되어 있으므로 시간 복잡도는 O(NLogN) 이고, 이진트리 구조로 이루어져 있다. 힙 동..

1. 해시맵 (HashMap) 이란 무엇일까? map 인터페이스를 구현한 대표적인 클래스 HashMap은 키(Key)와 값(Value) 이 1:1구조로 구성된 객체를 저장하는데, 이 객체를 Entry 객체라고 한다. HashMap의 개별 요소가 되는 Entry 객체는 Map 인터페이스의 내부 인터페이스인 Entry 인터페이스를 구현한다. HashMap은 해시 함수를 통해 키와 값이 저장되는 위치를 결정한다. 사용자는 그 위치를 알 수 없고, 삽입되는 순서와 위치도 관계가 없다. 해시 함수를 통해 데이터를 관리하는 자료 구조로 많은 양의 데이터를 검핵하는 데 있어서 뛰어난 성능을 보인다. 키는 맵에서 유일한 값을 가져야 하고, 값은 중복된 값이어도 상관 없다. 키는 대소문자를 구별한다. ※ 맵 (Map) ..

1. 연결 리스트 (Linked List) 란 무엇인가 노드(객체) 끼리의 주소 포인터를 서로 가리키며 링크(참조) 함으로써 이어지는 구조 즉, 데이터를 링크로 연결해서 관리하는 자료구조 노드는 데이터 저장 단위로, 값과 포인터로 구성되어 있다. 포인터는 다음 노드나 이전 노드의 연결 정보를 담고 있다. 2. 연결 리스트 (Linked List) 장점, 단점 (1) 장점 데이터 공간을 미리 할당할 필요가 없음 즉, 리스트의 길이가 가변적이라 데이터 추가 / 삭제 용이 (메모리 관리 측면) (2) 단점 연결구조를 위한 별도 데이터 공간 필요 연결 정보를 찾는 시간이 필요 (접근 속도가 상대적으로 느림) 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성 하는 작업 필요 3. 연결 리스트 (Linked Li..

1. 배열이란 무엇인가 많은 수의 데이터를 다룰 때 사용하는 자료구조 각 데이터를 인덱스와 1:1 대응하도록 구성 같은 타입의 데이터가 메모리 상에 연속적으로 저장됨 (1) 배열의 장점 인덱스를 이용하여 데이터에 빠르게 접근 가능 자료의 물리적 위치와 논리적 위치가 같다. (2) 배열의 단점 데이터의 추가 / 삭제가 번거롭다 미리 최대 길이를 정해서 생성해야 한다. 가변 길이 배열은 배열의 크기를 변경할 때마다 새로운 배열을 생성 데이터 삭제 시, 인덱스를 유지하기 위해 빈 공간을 유지한다. (3) 배열 선언 int[] Number = new int[30]; // 배열 선언과 초기화를 동시에 실행 int[] Number = new int[10] {1,2,3, ... ,9,10}; // 배열에 저장할 값 ..

1. 자료구조란 무엇인가? 자료를 효율적으로 관리하기 위한 구조 관리란 데이터 저장, 데이터 탐색, 데이터 삭제 등 이 있다. 목적에 맞게 사용한 좋은 자료구조는 실행시간을 단축하거나 메모리 용량 절감 효과가 있다. (1) 자료구조의 분류 선형 자료구조 데이터간의 관계가 1:1인 자료구조 데이터를 저장하기 위한 기본적인 형태로 데이터가 일렬로 나열 되어 있을 뿐만 아니라 데이터 간에 순서가 있고 논리적으로 이어져 있는 구조 배열, 연결리스트, 스택, 큐, 데크, 해시 테이블 비선형 자료구조 데이터간의 관계가 1:N 또는 M:N 인 자료구조 데이터가 일렬로 나열되지 않은 자료구조 즉, 데이터가 계층적으로 구성된 경우 트리, 그래프, 힙 / 우선순위 큐, 트라이

1. 경우의 수 어떤 사건에서 일어날 수 있는 경우의 가짓수 사건 A가 일어날 경우의 수 : n(A) 2. 합의 법칙 사건 A 또는 사건 B가 일어날 경우의 수 사건 A와 사건 B의 합의 법칙 : n(A ∪ B) n(A ∪ B) = n(A) + n(B) - n(A ∩ B) //두 개의 주사위를 던졌을 때 합이 3 또는 4의 배수일 경우 int[] dice1 = {1, 2, 3, 4, 5, 6}; int[] dice2 = {1, 2, 3, 4, 5, 6}; int nA = 0; int nB = 0; int nAandB = 0; for (int item1: dice1) { for (int item2: dice2) { if ((item1 + item2) % 3 == 0) { nA +=1; } if ((item..

1. 집합 (Set) 특정 조건에 맞는 원소들의 모임 집합 표현 방법 : 원소나열법, 조건제시법, 벤 다이어그램 - 특징 중복되지 않은 수들의 모임이므로, 자바에서는 Set을 사용하여 중복데이터를 거를 수 있다. (1) 교집합 두 집합이 공통으로 포함하는 원소로 이루어진 집합 HashSet 메소드 : a.retainAll(b); HashSet a = new HashSet(Arrays.asList(1,2,3,4,5)); HashSet b = new HashSet(Arrays.asList(2,4,6,8,10)); a.retainAll(b); // 교집합 메소드 호출 //2,4 (2) 합집합 어느 하나에라도 속하는 원소들을 모두 모은 집합 HashSet 메소드 : a.addAll(b); HashSet a = ..

1. Queue 컬렉션 Queue(큐)는 Stack(스택)과 반대로 먼저 추가된 데이터가 먼저 나오는 FIFO (First In First Out) 동작을 갖는다. 이것은 선입선출 방식이라고도 한다. FIFO 방식은 운영체제의 프로세스 관리, 프린트 출력 대기열, 너비 우선 탐색(BFS, Breath-First Search) 알고리즘 등에서 사용된다. 큐는 한쪽에서만 입력이 이루어지고, 다른 쪽 끝에서는 출력만 이루어지는 구조이다. 큐에 자료를 넣는 것을 인큐(Enqueue) 라고 하고 반대로 자료를 꺼내는 것을 디큐(Dequeue) 라고 한다. 이때 자료는 가장 먼저 입력된 자료부터 나오게 된다. (1) 자바의 Queue 클래스 분류 설명 Queue 인터페이스 데이터를 일시적으로 쌓아두기 위한 자료구조..

1. Stack 컬렉션 스택(Stack)의 사전적 정의는 '쌓다', '더미'로서 접시 스택처럼 접시를 쌓아놓은 것을 말한다. 즉, 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있다. 스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 구조 특징이 있는데, 이러한 자료 구조를 LIFO (Last In First Out) 구조라고 한다. 많이 사용되는 Queue(큐)의 경우 먼저 추가된 데이터가 먼저 나오는 FIFO (First In First Out) 동작을 갖는 것과 비교된다. 스택은 배열이 수직으로 쌓여있는 것과 비슷하다. 따라서 요소의 추가 및 삭제는 맨 위에서만 차례대로 가능하다. 예를 들면 웹 뒤로가기, Ctrl+z 실행취소 등이 있다. 데이터가 입력된 순서의 역순으로 처리..