이전에 알고리즘을 학습 할때 공부했고 코딩테스트 문제에도 자주 나오는 DP 알고리즘이지만솔직히 크게 와닿지 않아서 기록을 하지 못했다. 'dp 대충 어떻게 쓰는지는 알겠는데 Memoization, Tabulation이 뭔데?' '뭐가 그렇게 차이가 있는건데?' 필자는 무언가 언어적으로 이해가 되지 않으면 잘 와닿지 않는 사람이라..대충 넘겨서 dp를 완벽히 정복하지 못했던 것 같다. 그리고 남들 다 예시로 쓰는 피보나치 수열로 대충 쓰고 싶지 않았다.ㅎ.. 복붙인 것 같은 글들 피로해~ 그러나 어느 분께서 정말 DP를 자세하게 써주셔서 이제 누군가 DP를 나에게 물어보면 대답할 수 있을 정도로 이해했기에 기록해본다. (ThanksTo > https://cdragon.tistory.com/entry/Alg..
힙의 구조와 특징 완전 이진 트리 형태 [중복 값 허용, 반 정렬 상태]로 최소값 또는 최대값을 빠르게 찾아내는데 유용한 자료구조입니다. 따라서 최소 힙, 최대 힙 두가지 종류가 존재합니다. + 우선순위 큐(Priority Queue)를 위한 자료구조라고도 합니다. 최소 힙(Min Heap) 부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태 -> 즉, root 노드가 가장 작습니다. 자식 노드에서는 따로 규칙이 없어서 왼쪽이 오른쪽보다 클수도, 오른쪽이 왼쪽보다 클 수도 있습니다.. 보장되어있지 않아 반 정렬 형태라고 합니다. 최대 힙(Max Heap) 부모 노드의 키가 자식노드의 키보다 크거나 같은 형태 -> 즉, root 노드가 가장 큽니다. 최소 힙과 마찬가지로 반 정렬 형태입니다. 힙의 시간..
연결리스트의 구조와 특징 연결리스트(LinkedList)란? Collection Framwork내에 있는 List 컬렉션 중 하나(List의 일부). List의 종류 > ArrayList(리스트로 생성되나 성격은 array와 더 비슷하다. 동적배열이라고 생각하면 쉬움), LinkedList List는 객체 자체를 저장하지 않고 객체의 번지(메모리 주소)를 저장한다. 그러나 이러한 객체의 번지는 array와 ArrayList와 달리 연속적이지 않다. 또한 맨 처음 부분인 head와 맨 끝부분 tail으로 구분 된다. 위의 그림은 정확하진 않겠지만 데이터들이 Array, ArrayList와 달리연속적으로 저장되지 않는다는 것을 알려주고 싶어 그림을 첨부했다. + LinkedList 컬렉션은 이중 연결 리스트..
해시맵의 구조와 특징 가볍게 생각하면 해시맵은 python에서 dictionary와 같이 key와 value 값을 매핑된 상태로 저장할 수 있는 자료구조라고 생각할 수 있습니다. 그러나 가볍게 대충 보면 안되겠죠? 우선 기본적으로 자바에서 해시맵(HashMap)은 인터페이스 Map을 상속받고, Map은 key와 value으로 구성된 객체를 저장하는 구조를 가지고 있습니다. 따라서 상속받은 해시맵도 Map의 성질을 그대로 가져 key와 value값으로 구성된 객체를 저장하기 편한 자료구조입니다. 이때 null key와 null value를 허용한다고 합니다. 아주 조금 더 깊게 생각해봅시다. 이름에 있는 hash는 보통 hash function(해쉬함수)와 연관이 있다고 생각하시면 되는데요! key값을 해..
배열의 구조와 특징 배열(Array)이란? 배열 크기가 고정적인 배열이다. 항상 크기를 정해줘야 인덱스 값으로 접근하여 할당 연산자로 데이터값을 저장할 수 있다. 정적인 배열의 장점으로는 사이즈가 늘 일정해서 사이즈 값은 상수고 인덱스로 접근하기가 편하다. 또한 데이터를 저장할때는 반드시 모두 같은 타입이어야 배열에 저장이 가능하다. -> 같은 타입의 여러 변수를 하나의 묶음으로 다루는 것, 같은 타입의 여러 변수를 하나하나 저장해서 쓰는 것보다 한곳에 모아두고 필요한 것들만 사용하기 용이하기 때문에 위의 그림은 int[] arr = new int[3]; 으로 생성된 배열의 구조와 인덱스를 보여주고 있는 그림이다. 개념은 쉽지만 매번 사용할때마다 헷갈리고 다시 구글링을 하게 되서 배열의 간단한 사용을 코..
큐의 구조와 특징 큐(Queue)란? 줄 서는 것처럼 순서대로 처리되는 자료구조 그림과 같이 앞(front)과 뒤(rear)가 있고 먼저 들어온 데이터가 먼저 나가는 First In First Out(FIFO)(선입선출)을 따르게됩니다. 큐에 데이터를 추가하는 것을 Enqueue, 데이터를 삭제하는 것을 Dequeue라고 표현합니다. 앞인 front에서는 삭제 연산만 수행하고 뒤인 rear에서는 삽입 연산만 수행하는 특징을 갖고 있습니다. 큐의 관련 메서드 메서드 메서드의 기능 시간복잡도 add(Object obj) queue에 데이터 obj값을 넣는다. queue가 가득 찼을 경우 에러 반환 () O(1) offer(Object obj) queue에 데이터 obj값을 넣는다. queue가 가득 찼을 경..
스택의 구조와 특징 스택(Stack)이란? 한 쪽 끝에서만 데이터를 삽입하고 삭제할 수 있는 제한적인 자료구조 그림과 같이 아래가 막혀있고 위에서 쌓는 구조이기 때문에 Last In First Out(LIFO)(후입선출)을 따르게 됩니다. 스택에 있는 가장 최근의 데이터의 위치를 top이라고 표현합니다. 즉 top의 위치가 데이터의 크기라도고 할 수 있습니다. 스택의 관련 메서드 메서드 메서드의 기능 시간복잡도 push(Object obj) stack에 데이터 obj값을 넣는다. O(1) pop() stack에 있는 최상단 데이터를 추출(조회) 후에 삭제한다. O(1) peek() stack에 있는 최상단 데이터를 조회만 한다. O(1) search(Object obj) stack에 obj값이 있는지 조..
