본문 바로가기

자료구조15

동적 프로그래밍 기초 - 피보나치 수열(메모제이션) 코딩 인터뷰 완전 분석이라는 책에서 동적 프로그래밍 공부의 기초로 피보나치 수열 문제를 다뤘었다. 그 때 메모제이션이라는 기법으로 중복 호출되는 부분을 캐시처럼 저장하여 사용하는 방법이 있어서 한 번 훑고 넘어간 적이 있다. 그런데 딱 그 문제가 릿코드 https://leetcode.com/problems/climbing-stairs/ 에서 나왔다!! 리마인드 할 겸 정리하려한다. 기존의 피보나치의 경우 보통 이런 방식이다. public int climbStairs(int n) { if(n==0){ return 0; } if(n==1){ return 1; } if(n==2){ return 2; } return climbStairs(n-2) + climbStairs(n-1); } 하지만 이 피보나치의 재귀.. 2020. 3. 17.
[자료구조] ConcurrentHashmap, HashMap, HashTable 회사 선임님이 ConcurrentHashMap를 사용하셔서 궁금해서 찾아본김에 바로 정리쓰 ConcurrentHashMap HashMap을 thread-safe 하도록 만들어진 클래스 key, value에 null을 허용하지 않음 putIfAbsent 메소드 존재 putIfAbsent() key 값이 존재하면 기존 값 반환, 아니면 해당 값을 저장한 뒤 반환 다른 비슷한 자료구조들은 어떨까? Hashtable get(), put() 메소드 public synchronized V get(Object key) { ... } public synchronized V put(K key, V value) { ... } 메소드 레벨에서 synchronized를 사용한다. 위처럼 메소드 레벨에서 synchronized.. 2019. 12. 29.
[자료구조] 우선순위 큐(PriorityQueue) + 힙(Heap) - 2 프로그래머스 프린터라는 문제를 풀다가 의아한 점이 생겼다. PriorityQueue priority = new PriorityQueue(Collections.reverseOrder()); 우선순위 큐를 사용하기 위해 우선순위 큐를 생성하고, 문제에서 숫자가 클 수록 우선순위가 높다고 요구하여 내림차순으로 설정을 했다. 그런데 우선순위 큐에 {2,5,4,1,3}을 넣었을 때 내가 단순히 생각하기에는 {5,4,3,2,1}이 나올 것이라고 생각했지만, 실제로는 {5,3,4,1,2}가 나왔다. ??? 자바 공식 문서에서도 reverseOrder() Returns a comparator that imposes the reverse of the natural ordering. 라고 했다. 내림차순이라는 소리다. 알.. 2019. 5. 13.
[자료구조] 우선순위 큐(PriorityQueue) -1 우선순위큐도 Queue라는 자료구조의 선입선출 규칙을 따른다.먼저 들어온 놈이 먼저 나간다.하지만 JAVA에서 제공하는 우선순위큐는 우선순위를 결정하여 들어온 순서에 상관없이 우선순위가 높은 엘리먼트가 나가게 된다.예제class Prisoner { ​ String name; int weight; // 형량 ​ public Prisoner(String name, int weight) { super(); this.name = name; this.weight = weight; } }이 클래스는 'name'과 'weight(형량)' 의 2가지 필드가 있다. 이 Prisoner 클래스를 PriorityQueue에 넣고, 형량에 따라 큐에서 나오게 하려한다.이제 이 Prisoner 클래스에 Comparable 인터.. 2018. 11. 2.
[자료구조] 자바 Map 총정리 Map이 잘 기억이 나지 않아 정리를 하려한다. map은 key와 value로 쌍을 이룬다.key 값은 중복 될 수 없지만 value는 중복이 가능하다.주민등록번호는 중복되는 사람이 없지만 이름은 같은 사람을 떠올리면 쉽게 이해 할 수 있다. Map 메소드 중 가장 많이 쓰이는 메소드는 put(), get(), remove()이다. 가장 많이 쓰이는 클래스는 HashMap, TreeMap, LinkedHashMap이다.HashMap과 HashTable의 차이점은 아래와 같다. 기능HashMapHashTable키, 값에 null 저장 가능 여부OX여러 쓰레드 안전 여부XO그래서 HashMap을 Thread safe하게 이용하려면Map m = Collections.synchronizedMap(new Hash.. 2018. 9. 28.
큐 - 큐 큐의 구조는 스택과 다르게 '선입선출'의 구조를 가진다. 즉, 먼저 들어온 것이 먼저 나가는 구조이다.큐의 예로는 은행에서 쉽게 볼 수 있는 번호표가 있다. 먼저 온 손님이 먼저 은행업무를 볼 수 있다. 큐에서는 맨 처음 위치와 맨 마지막 위치만 기억하면 쉽게 해결이 된다.이 위치를 큐에서는 front, rear라고 한다.위 그림에 Deletion, Insertion이라는 용어가 있다. 보통 큐에서 Dequeue, Enqueue라는 용어를 많이 쓰는데, Enqueue = Insertion Dequeue = Deletion 은행에서 보면 먼저 온 사람들은 이미 번호표를 받았기 때문에 마지막에 온 사람에게 번호표를 주기 때문에 rear부분에 Enqueue가 들어가게 된다. (1) Enqueue(삽입).. 2018. 7. 17.

티스토리툴바