악깡버👩🏻‍🌾

Algorithm/자료구조 & 알고리즘 검색 결과

해당 글 6건

[알고리즘] 비트마스킹 - 순열, 조합, 부분집합

1. 부분집합 - 비트마스킹 int[] arr = {1, 2, 3, 4, 5}; int length = arr.length; //2의 5승 System.out.println(1

Algorithm/자료구조 & 알고리즘 2023. 9. 16. 17:24

우선순위 큐(Priority Queue)와 힙(Heap)

우선순위 큐(Priority Queue)는 완전이진트리인 힙(Heap)으로 구현되어 있다. 우선순위 큐(Priority Queue) 큐(Queue)는 FIFO(First in - First out)구조로 먼저 들어온 데이터가 먼저 나가는 구조이다. 우선순위 큐(Priority Queue)는 들어온 순서와는 무관하게 우선순위가 높은 데이터가 먼저 나가는 구조이다. 데이터가 들어오면 우선순위에 따라 자동으로 정렬한다. 때문에 우선순위 큐는 우선순위에 따라 정렬하는데 효율적인 힙(Heap)을 이용하여 구현한다. - 힙이 아닌 배열로 구현했다고 가정하자. 데이터를 삽입하면 우선순위에 따라 정렬하기 위해 모든 인덱스를 탐색해야 한다. 여기서 시간복잡도는 데이터가 n개 일 때 O(n)이 된다. 연결리스트도 마찬가지..

Algorithm/자료구조 & 알고리즘 2023. 8. 17. 23:48

[자료구조] HashSet

HashSet Set인터페이스에서 지원하는 구현 클래스 1. 중복을 허용하지 않는다. 2. 입력한 순서가 보장되지 않는다. 3. null을 허용한다. 중복을 걸러내는 과정 HashSet은 객체를 저장하기 전에 1. 먼저 객체의 hashCode() 메소드를 호출해서 해시 코드를 얻어낸다. 2. 같은 해시 코드가 존재한다면 equals() 메소드로 비교해서 true가 나오면 동일한 객체로 판단하여 중복 저장을 하지 않는다. 문자열을 HashSet에 저장할 경우 문자열이 같은 두 String 객체는 서로 같은 객체로 간주되는데, 그 이유는 String 클래스는 hashCode()와 equals() 메소드를 재정의한다. 그래서 같은 문자열이면 true를, 다르면 false를 리턴하게끔 했다. 특이한게 HashS..

Algorithm/자료구조 & 알고리즘 2023. 1. 9. 21:14

[자료구조] HashMap

1. 해시맵 선언 Map map = new HashMap (); 2. 해시맵 값 넣기 map.put(1, 2); // put : 기존에 있는 map의 value를 덮어씀 / 추가 map.put(1, 3); map.put(1, map.get(1)+1); // map.get(key값) => key에 대한 value를 가져옴 map.put(1, map.getOrDefault(1, 0)); // key가 1인 value가 있으면 걔를 가져오고, 없으면 0 넣어줌 map.get(2); // =>null이 출력됨 3. 정렬 (ArrayList 이용) List list = new ArrayList (map.values()); //=> value를 list에 넣어줌 List list = new ArrayList (ma..

Algorithm/자료구조 & 알고리즘 2023. 1. 4. 22:14

[알고리즘] BFS와 DFS 시간복잡도

BFS는 도착지점까지 최단거리를 구할 때 유리하다. (너비 우선 탐색) DFS는 도착지점까지 갈 수 있는 모든 경로를 봐야할 때 유리하다. (깊이 우선 탐색) 각각의 경로의 특징을 저장할 수 있다. 모든 지점을 방문해야 한다면 BFS, DFS의 시간복잡도는 동일하다. 인접리스트: O(N+E) 인접행렬: O(N*N) 하지만 DFS를 재귀함수로 구현 한다는 점에서 실제 수행시간은 DFS보다 BFS가 조금 더 빠르게 동작한다.

Algorithm/자료구조 & 알고리즘 2022. 11. 20. 10:49

[알고리즘] 순열, 조합, 부분집합 Java

public class 순조부연습 { static int N, M; //순열 static boolean[] isSelected; //static int[] tgt; //비트마스킹(순열), 조합 static int[] tgt, src; static int[][] dp; // 조합- dp //부분집합 //static boolean[] isSelected; public static void main(String[] args) { //1. 순열 기본 perm1(0); //2. 중복 순열 perm2(0); //3. 비트마스킹 순열 perm_bit(0, 0); //4. np 활용 순열 np(); //1. 조합 기본 comb1(0, 0); //2. 조합 기분2 comb3(0, 0); //3. 중복 조합 comb2(0..

Algorithm/자료구조 & 알고리즘 2022. 8. 22. 02:54