초코chip의 코딩 생활

정리배낭 문제목표값(v)를 만족시키는 부분집합 찾기 문제 평범한 배낭 - 골드5 배낭 문제: 목표값을 만족시키는 최적의 부분집합 찾기풀이법:원소의 개수(1~i), 목표값(k)목표값 1~k까지, i번째 원소를 선택한 경우, 선택하지 않은 경우 2가지 경우를 비교하면서 dp 테이블을 채우기if( 채울 수 있는 경우 ) ==>  w[i] dp[i][k] = max( dp[i-1][k](i번쨰 원소를 선택하지 않을 경우), dp[i-1][k - w[i]] + v[i](i번쨰 원소를 선택할 경우) ) if (채울 수 없는 경우) ==> w[i] > kdp[i][k] = dp[i-1][k] (이 경우 i번째 원소를 선택하지 않을 경우만 보면 됨)why?: 왜 i번째 원소를 선택하지 않을 경우가 i-1, k인가?  ..

정리  자료구조 주의사항!!우선순위큐는 삽입, 삭제 시에만 재정렬이 되는거지, 내부의 값을 수정했을때는 정렬이 적용되지 않음이럴땐 건실하게 그냥 리스트 쓰고, 변경했을때 정렬 알고리즘 써라큐, 스택, 우선순위큐 자료구조들은 get을 통한 접근이 불가능하다!이러고 싶으면 링크리스트 써라! 링크리스트는 offer(), poll() 연산 다 지원함remove() 연산을 사용하면 삭제되는 값을 반환해줌 n만큼 이동을 해야하는데, 계속 변동성이 생기는 경우// diff 만큼 이동해야하는데 중간에 빠지는값 떄문에 diff - 빠지는값 만큼 이동해야하는 경우// adjusts란 배열에 빠진 값들을 저장해서 빠진 값들 중에 중간 값이 몇개 있는지 체크 -> 그 값을 적용int diff = t - dq.peekFirst..

정리그래프 탐색바이러스 - 실버3https://www.acmicpc.net/problem/2606 문제 유형:노드 형태의 그래프 형태시작점에 연결된 노드의 개수를 세는 문제노드 관점의 그래프 자료구조를 사용했을떄 dfs/bfs 아무거나 상관x그냥 연결된 모든 노드를 탐방을 하고 연결된 노드 개수를 세는 문제 -> 스택 or 큐에 넣을때마다 count 증가 단지번호붙이기 - 실버1https://www.acmicpc.net/problem/2667 문제 유형: 2차원 배열 형태의 그래프 형태연결된 모든 노드의 개수를 세는 문제즉, 모든 노드를 시작점으로 다 탐색을 해야함 해결책:graph[1][1] ~ graph[n][n]까지 모든 노드를 시작 지점으로 하고 탐색을 진행단, 이미 방문한 노드이거나 탐색 불가 ..

일반 배열 (int[])java.util.Arrays 사용기능설명생성int[] arr = new int[n];접근XX삽입, 삭제XX길이arr.length최대, 최소Arrays.stream(arr).max().orElse(-1)초기화Arrays.fill(arr, 1);정렬Arrays.sort(arr);전체 출력Arrays.toString(arr);일반 객체 배열 (Class[])Comparator 전달기능설명생성Class[] arr = new Class[n];접근arr[i]삽입, 삭제XX길이arr.length최대, 최소Arrays.stream(arr).max((c1, c2) -> c1.x - c2.x).orElse(null);초기화XX정렬1. 오름차순 Arrays.sort(arr, (c1, c2) -> c..

노드 관점 해당 노드에 연결된 다른 노드가 뭔지 알고싶을때 0: [] 1: [3,2] 2: [1] 3: [4] 정수 노드 가중치가 없는 그래프 ArryList graph = new ArrayList(); // 노드 개수만큼 추가 for (int i = 1; i

개념 정의: 우선순위가 높은 대상이 먼저 나오는(pop) 자료구조 언제 사용?: 계속해서 선택지가 업데이트(추가)되는 상황에서 가장 최선의 값을 골라야하는 상황에 사용 구현 방법 리스트와 힙 방식이 있는데, 보통 heap을 이용해서 구현 우선 순위 큐 구현 방식 삽입(push) 시간 삭제(pop) 시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 최소 힙 vs 최대 힙 최소 힙(오름차순): 가장 작은 값이 먼저 나오는 것 최대 힙(내림차순): 가장 큰 값이 먼저 나오는 것 사용법 java.util의 PriorityQueue 라이브러리 사용 기본형 초기화 //기본 타입 변수는 사용 불가 PriorityQueue pq = new PriorityQueue(); 삽입(offer)/추출(p..

개념 정의: 양쪽 끝에서 데이터의 삽입과 삭제가 가능한 선형 자료구조 연산: 앞쪽 삽입: d.offerFirst(v); 뒤쪽 삽입: d.offerLast(v); 앞쪽 조회: v = d.peekFirst(); 뒤쪽 조회: v = d.peekLast(); 앞쪽 삭제: d.pollFirst(); 뒤쪽 삭제: d.pollLast(); 비어있는지 확인: d.isEmpty(); 사용방법 java.util의 Deque 인터페이스와 LinkedList 클래스 사용 선언 Deque deque = new LinkedList(); 앞쪽 삽입 덱의 맨 앞에 값 삽입 deque.offerFirst(1); // 또는 deque.addFirst(1); 뒤쪽 삽입 덱의 맨 뒤에 값 삽입 deque.offerLast(2); // 또는..

개념 정의: 데이터를 선입선출(FIFO) 방식으로 관리하는 자료구조 연산: 삽입: q.offer(v); 조회: v = q.peek(); 삭제: v = q.poll(); 비어있는지 확인: q.isEmpty(); 사용방법 java.util의 Queue 인터페이스와 LinkedList 클래스 사용 선언 Queue queue = new LinkedList(); 삽입 큐의 맨 뒤에 값 삽입 queue.offer(1); 조회 큐의 맨 앞(front) 값을 조회 int a = queue.peek(); 삭제 큐의 맨 앞(front) 값을 삭제하고 그 값을 반환 queue.poll(); 큐 비어있는지 확인 // 큐가 비어있다면 true 반환 queue.isEmpty();

개념 정의: 데이터를 후입선출(FILO)로 구현하는 방법 연산: 삽입(push) 조회(peek) 삭제(pop) 비어있는지 확인(isEmpty) 언제 사용? 조건에 맞는 값들 중에서 가장 마지막(최신)의 것이 최적의 해인 경우 사용 탑: https://www.acmicpc.net/problem/2493 사용방법 java.util의 Stack라이브러리 사용 선언 Stack stack = new Stack(); 삽입 스택의 맨위(top)에 값 삽입 stack.push(1); 조회 스택의 맨위(top) 값을 조회 int a = stack.peek(); 삭제 스택의 맨위(top) 값을 삭제 리턴값 없음 stack.pop() 스택 비어있는지 확인 //빈 스택이라면 true 발생 stack.isEmpty()

사용법 요약 삽입: map.put(key값, value값) 조회: map.get(key값) 키 조회: Set keys = map.keySet(); 삭제: map.remove(key값) 전체 출력: map.toString(); 개념 정의 Map 정의: 키(key)와 값(value)을 저장하는 데이터 구조의 인터페이스 HashMap 정의: Map 인터페이스의 구현체, 해시 테이블을 사용하여 키와 값을 저장 즉, 해시 함수를 통해 키와 값을 저장 -> 값 접근 성능이 좋음 HashMap 특징 키와 값은 모두 객체여야 한다. 기존에 저장된 키와 동일한 키로 값이 저장되면, 기존의 값이 새로운 값으로 대치된다. 저장 공간보다 값이 추가로 들어오면, 저장공간을 약 2배로 늘림 따라서, 초기에 값 개수가 정해져 있다..