본문 바로가기
공부기록/알고리즘

[알고리즘] 3일차

쇼파죠하 2024. 2. 15. 17:39

인덱스 트리 자체는 엄청 개념의 양도 많고 복잡해서 나중에 따로 게시글로 설명 부분 올려야겠다

 

 

 

인덱스 트리 설명...???? (TD, BU)

package day03.indextree;
// 인덱스 트리 (BU. TD)
public class Main {
	static int N;
	static long[] nums;
	static long[] tree;
	
	static int S;
	public static void main(String[] args) {
	
		N = 8;
		
		nums = new long[8];
		nums[0] = 1;
		nums[1] = 2;
		nums[2] = 3;
		nums[3] = 4;
		nums[4] = 5;
		nums[5] = 6;
		nums[6] = 7;
		nums[7] = 8;
		
		S = 1;
		while(S < N) {
			S *= 2;
		}
		tree = new long[S*2]; // 트리 크기는 S의 2배
		
	}
	
	static void init() {
		//bottom-up
		for(int i = 0; i < N; i++) {
			tree[S+i] = nums[i];
			
		}
		//내부 노드 마지막부터 시작해서 계속 돌아
		for(int i = S-1; i>0;i--) {
			tree[i] = tree[i*2] + tree[i*2 + 1];
		}
		
	}
	
	static long query_TD(int left, int right, int node, int queryLeft, int queryRight) {
		//1. 쿼리 범위 밖
		if (queryRight < left || right < queryLeft) {
			return 0; // 구간 합이기 때문에 return 0을 한거임
		} else if (queryLeft <= left && right <= queryRight) { // 2. 쿼리 안에 들어옴 2번상황
			return tree[node];
			
		} else { // 3. 걸쳐 있는 상황 애매하게
			int mid = (left + right) / 2;
			return query_TD(left, mid, node * 2, queryLeft, queryRight) + query_TD(mid + 1, right, node * 2 + 1, queryLeft, queryRight);
		}
		
		
	}
	
	
	static void update_TD(int left, int right, int node, int target, long diff) {
	// 1. 타겟과 무관
		if (target < left || right < target) {
			return;
		}else { //2. 타겟에 연관
			tree[node] += diff;
			if (left != right) {
				int mid = (left + right) / 2;
				update_TD(left, mid, node * 2, target, diff);
				update_TD(mid + 1, right, node * 2 + 1 , target, diff);
			}
		}
	}
	
	//bottom-up query
	static long query_BU(int queryLeft, int queryRight) {
		int leftNode = S + queryLeft - 1;
		int rightNode = S + queryRight -1;
		long sum = 0;
		
		while(leftNode <= rightNode) { // 얘네가 뒤집히지 않을 때까지 
			if(leftNode % 2 == 1 ) { // 홀수니까 내꺼써야지
				sum += tree[leftNode++];
			}
			if(rightNode % 2 == 1 ) { // 홀수니까 내꺼써야지
				sum += tree[rightNode--];
			}
			leftNode /= 2;
			rightNode /= 2;
			
			
		}
		return sum;
		
		
	}
	
	//bottom-up update
	static void update_BU(int target, long value) {
		int node = S + target - 1; //우리가 찾는 타겟 노드
		tree[node] = value;
		node /= 2;
		while(node > 0) {
			tree[node] = tree[node * 2] + tree[node * 2 + 1];
			node /= 2;
		}
		
	}
	
	

}

 

 

 

P1202. 보석도둑

//package day03.P1202;
//
//import java.util.ArrayList;
//import java.util.Collections;
//import java.util.Comparator;
//import java.util.List;
//import java.util.PriorityQueue;
//import java.util.Scanner;
//
////보석 도둑
//public class Main {
//	static int N,K;
//	static int[] m, v;
//	public static void main(String[] args) {
//		Scanner sc = new Scanner(System.in);
//		N = sc.nextInt();
//		K = sc.nextInt();
//		m = new int[N];
//		v = new int[N];
//		
//		for(int i = 0; i < N; i++) {
//			m[i] = sc.nextInt();
//			v[i] = sc.nextInt();
//		}
//		
//		List<Jewel> list = new ArrayList<>();
//		list.add(new Jewel(10,10));
//		list.add(new Jewel(1,5));
//		list.add(new Jewel(3,7));
//		list.add(new Jewel(8,5));
//		System.out.println(list);
//		Collections.sort(list,Comparator.comparingInt(Jewel::getWeight));
//		System.out.println(list);
//		
//		PriorityQueue<Jewel> pq = new PriorityQueue<>(Comparator.comparingInt(Jewel::getValue).reversed()); // 여기에서 원래는 내림차순이어서 reverse 붙여서 오름차순으로 바꿔줌
//		
//	}
//
//}
//
//class Jewel{
//	int weight;
//	int value;
//	
//	@Override
//	public String toString() {
//		return "[weight=" + weight + ", value=" + value + "]";
//	}
//	public Jewel(int weight, int value) {
//		super();
//		this.weight = weight;
//		this.value = value;
//	}
//	
//	public int getWeight() {
//		return weight;
//	}
//	public int getValue() {
//		return value;
//	}
//	
//}

 

이게 MAIN 코드

package day03.P1202;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;

//보석 도둑
public class Main {
	static int N,K;
	static Jewel[] jewels;
	static int[] bags;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		jewels = new Jewel[N];
		bags = new int[K];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			jewels[i] = new Jewel(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));

		}
		
		for(int i = 0; i<K; i++) {
			bags[i] = Integer.parseInt(br.readLine());
		}
		
		// 1. 가방 오름 차순 정렬
		Arrays.sort(bags);
		// 2. 보석 무게 오름차순 정렬
		Arrays.sort(jewels, Comparator.comparingInt(Jewel::getWeight));
		// 3. 보석 값 최대 힙
		PriorityQueue<Jewel> pq = new PriorityQueue<>(Comparator.comparingInt(Jewel::getValue).reversed()); 
		
		int jIndex = 0;
		long result = 0;
		//1. 가방 작은 순서대로 선택
		for(int i = 0; i<bags.length;i++) {
			// 2. 선택된 가방에 넣을 수 있는 모든 보석을 힙에 넣음
			while(jIndex < N && jewels[jIndex].weight <= bags[i]) {
				pq.add(jewels[jIndex++]);
			}
			// 3. 가방에 넣을 수 있는 가방 비싼 보석을 선택
			if(!pq.isEmpty()) {
			result += pq.poll().value;
			}
		}
		
		System.out.println(result);
		
	}

}

class Jewel{
	int weight;
	int value;
	
	@Override
	public String toString() {
		return "[weight=" + weight + ", value=" + value + "]";
	}
	public Jewel(int weight, int value) {
		super();
		this.weight = weight;
		this.value = value;
	}
	
	public int getWeight() {
		return weight;
	}
	public int getValue() {
		return value;
	}
	
}

 

내가 풀려고 시도해썼으

//package day03.P1202;
//
//import java.util.ArrayList;
//import java.util.Collections;
//import java.util.Comparator;
//import java.util.List;
//import java.util.PriorityQueue;
//import java.util.Scanner;
//
////보석 도둑
//public class Main {
//	static int N,K;
//	static int[] weight, value, bag;
//	public static void main(String[] args) {
//		Scanner sc = new Scanner(System.in);
//		N = sc.nextInt();
//		K = sc.nextInt();
//		
//		weight = new int[N];
//		value = new int[N];
//		bag = new int[K];
//		
//		List<Jewel> jewellist = new ArrayList<>();
//		List<Bag> baglist = new ArrayList<>();
//		for(int i = 0; i < N; i++) {
//			weight[i] = sc.nextInt();
//			value[i] = sc.nextInt();
//			jewellist.add(new Jewel(weight[i], value[i]));
//		}
//		for(int i = 0;i<K; i++) {
//			bag[i] = sc.nextInt();
//			baglist.add(new Bag(bag[i],0));
//		}
//		
//		
//		
//		Collections.sort(jewellist,Comparator.comparingInt(Jewel::getWeight));
//		Collections.sort(baglist,Comparator.comparingInt(Bag::getWeight));
//		System.out.println(jewellist);
//		System.out.println(baglist);
//		
//		PriorityQueue<Jewel> pq = new PriorityQueue<>(Comparator.comparingInt(Jewel::getValue).reversed()); 
//		pq.offer(jewellist[1]);
//		int ans += pq.poll().value;
//		System.out.println(pq);
//		int j,b = 0;
//		
//		for(int i = 0; i < N;i++) {
//			while(true) {
//				
//				
//			}
//			
//		}
//		
//		
//		
//		
//	}
//
//}
//
//class Jewel{
//	int weight;
//	int value;
//	
//	@Override
//	public String toString() {
//		return "[weight=" + weight + ", value=" + value + "]";
//	}
//	public Jewel(int weight, int value) {
//		super();
//		this.weight = weight;
//		this.value = value;
//	}
//	
//	public int getWeight() {
//		return weight;
//	}
//	public int getValue() {
//		return value;
//	}
//	
//}
//
//class Bag{
//	int weight;
//	int value;
//	
//	@Override
//	public String toString() {
//		return "[weight=" + weight + ", value=" + value + "]";
//	}
//	public Bag(int weight, int value) {
//		super();
//		this.weight = weight;
//		this.value = value;
//	}
//	
//	public int getWeight() {
//		return weight;
//	}
//	public int getValue() {
//		return value;
//	}
//	
//	
//}

 

 

 

p1927 최소힙

 

package day03.P1927;

import java.io.BufferedReader;

import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//최소힙
public class Main {
	static int N;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		MinHeap mh = new MinHeap();
		
		for (int i = 0; i < N; i++) {
			int input = Integer.parseInt(br.readLine());
			if(input == 0) {
				mh.delete();
			}else {
				mh.insert(input);
			}
			
		}

	}

}


class MinHeap{
	List<Integer> list;
	
	public MinHeap() {
		list = new ArrayList<>();
		list.add(0);
		
	}
	public void insert(int val) {
		list.add(val);
		int current = list.size() -1;
		int parent = current / 2;
		while(true) {
			if(parent == 0 || list.get(parent) <= list.get(current)) { 
				// 힙의 조건 만족
				//탈출조건 parent가 0이라는것은 루트노드라는 거니까 이것도 또한 바꿀 필요 없음
				//최대 힙이면 이 if문 부호만 바꾸면 돼
				break;
			}
			
			// swap 해주는부분
			int temp = list.get(parent);
			list.set(parent, list.get(current));
			list.set(current, temp);
			
			current = parent;
			parent = current / 2;
		}
		
	}
	
	public int delete() {
		// 최초의 상태에서 delete해버리면 안되니까 
		
		if (list.size() == 1) {
			return 0;
		}
		
		// delete는 top만 delete할 수 있음
		int top = list.get(1);
		list.set(1, list.get(list.size()-1)); // 제일 끝에꺼 top으로 가져옴
		list.remove(list.size() - 1);
		
		int currentPos = 1; //index? position currentPosition
		
		while(true) {
			int leftPos = currentPos * 2;
			int rightPos = currentPos * 2 + 1;
			
			//이게 루트인지 아닌지 확인
			//굳이 오른쪽까지 확인할 필요 없겠지
			if(leftPos >= list.size()) {
				break;
			}
			
			int minValue = list.get(leftPos);
			int minPos = leftPos;
			
			//우측자식이 존재하고, 우측자식값이 minvalue보다 작으면
			if(rightPos < list.size() && minValue > list.get(rightPos)) {
				minValue = list.get(rightPos);
				minPos = rightPos;
				
			}
			
			if(list.get(currentPos) > minValue) {
				int temp = list.get(currentPos);
				list.set(currentPos, list.get(minPos));
				list.set(minPos, temp);
				currentPos = minPos;
				
			}else {
				break;
			}
		}
		

	}
	
}

 

 

최소힙설명

 

//package day03.P1927;
//
//import java.util.Scanner;
//public class Main22 {
//	static int N;
//	static int H;
//	static int[] heap;
//	static int[] array;
//	int count;
//	
//	static int count;
//	public static void main(String[] args) {
//		Scanner sc = new Scanner(System.in);
//		sc = new Scanner(System.in);
//		N = sc.nextInt();
//		count= 0;
//		for (int i = 0; i < N; i++) {
//			array[i]= sc.nextInt();
//		}
//		
//		for(int i = 0; i< N; i++) {
//			if (array[i] != 0) {
//				heap[count++] = array[i];
//			}
//			else {
//				
//			}
//		}
//		
//		// 힙에서 최소힙으로 정렬하는 부분 적기
//		
//		
//		for(int i =0; i < N; i++) {
//			if (array[i] == 0) {
//				System.out.println(heap[0]);
//			}
//			
//		}
//				
//	
//	}
//}
//
//

 

2042 구간 합 구하기

package day03.P2042;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;


// 구간 합 구하기
public class Main {
	static int N,K,M;
	static long[] nums;
	static long[] tree;
	static int a,b,c;
	
	static int S;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();
		M = sc.nextInt();
		
		nums = new long[N];
		for(int i = 0;i<N;i++) {
			nums[i] = Integer.parseInt(br.readLine());
		}
		
		
		S = 1;
		while(S < N) {
			S *= 2;
		}
		tree = new long[S*2]; // 트리 크기는 S의 2배
		
		
//		for(int i = 0; i<K+M; i++){
//			a = sc.nextInt();
//			b = sc.nextInt();
//			c = sc.nextInt();
//			if (a==1) {
//				
//			}else {
//				
//			}
//		}
		
	}
	
	static void init() {
		//bottom-up
		for(int i = 0; i < N; i++) {
			tree[S+i] = nums[i];
			
		}
		//내부 노드 마지막부터 시작해서 계속 돌아
		for(int i = S-1; i>0;i--) {
			tree[i] = tree[i*2] + tree[i*2 + 1];
		}
		
	}
	
	static long query_TD(int left, int right, int node, int queryLeft, int queryRight) {
		//1. 쿼리 범위 밖
		if (queryRight < left || right < queryLeft) {
			return 0; // 구간 합이기 때문에 return 0을 한거임
		} else if (queryLeft <= left && right <= queryRight) { // 2. 쿼리 안에 들어옴 2번상황
			return tree[node];
			
		} else { // 3. 걸쳐 있는 상황 애매하게
			int mid = (left + right) / 2;
			return query_TD(left, mid, node * 2, queryLeft, queryRight) + query_TD(mid + 1, right, node * 2 + 1, queryLeft, queryRight);
		}
		
		
	}
	
	
	static void update_TD(int left, int right, int node, int target, long diff) {
	// 1. 타겟과 무관
		if (target < left || right < target) {
			return;
		}else { //2. 타겟에 연관
			tree[node] += diff;
			if (left != right) {
				int mid = (left + right) / 2;
				update_TD(left, mid, node * 2, target, diff);
				update_TD(mid + 1, right, node * 2 + 1 , target, diff);
			}
		}
	}
	
	//bottom-up query
	static long query_BU(int queryLeft, int queryRight) {
		int leftNode = S + queryLeft - 1;
		int rightNode = S + queryRight -1;
		long sum = 0;
		
		while(leftNode <= rightNode) { // 얘네가 뒤집히지 않을 때까지 
			if(leftNode % 2 == 1 ) { // 홀수니까 내꺼써야지
				sum += tree[leftNode++];
			}
			if(rightNode % 2 == 1 ) { // 홀수니까 내꺼써야지
				sum += tree[rightNode--];
			}
			leftNode /= 2;
			rightNode /= 2;
			
			
		}
		return sum;
		
		
	}
	
	//bottom-up update
	static void update_BU(int target, long value) {
		int node = S + target - 1; //우리가 찾는 타겟 노드
		tree[node] = value;
		node /= 2;
		while(node > 0) {
			tree[node] = tree[node * 2] + tree[node * 2 + 1];
			node /= 2;
		}
		
	}
	
	

}

 

 

2243. 사탕상자 main

package day03.P2243;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

//사탕상자(TOP-DOWN)
public class Main {
	static int N,n;
	static long[] nums;
	static int[] tree;
	static int a,b,c;
	static int MAX = 8; //적당한 MAX를 줘보자 나중에 1000000으로 바꿔서 제출
	
	static int S;
	public static void main(String[] args) throws Exception {
		//이 MAIN부분도 작성해야함.
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Scanner sc = new Scanner(System.in);
		N = 1000000;
		n = sc.nextInt();
		
		nums = new long[N];
		
		S = 1;
		while(S < N) {
			S *= 2;
		}
		
		tree = new int[S*2]; 
	}
	
	// QUERY
	
	static long query(int left, int right, int node, int target) { //여기서 target이 query (query - left 까지)
		if(left == right) { // 리프노드이면
			return left;
		}
		
		int mid = (left + right) / 2;
		if (tree[node * 2] >= target) { // 왼쪽 자식이 타겟보다 크거나 같으면 
			return query(left, mid, node * 2, target);
		}else {
			return query(mid + 1, right, node * 2 + 1, target - tree[node * 2]);
		}
		
		
		
	}
	// UPDATE
	
	static void update(int left, int right, int node, int target, long diff) {
	// 1. 타겟과 무관
		if (target < left || right < target) {
			return;
		}else { //2. 타겟에 연관
			tree[node] += diff;
			if (left != right) {
				int mid = (left + right) / 2;
				update(left, mid, node * 2, target, diff);
				update(mid + 1, right, node * 2 + 1 , target, diff);
			}
		}
	}
	
	
	
	
	
	

}

 

package day03.plus2243;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
	static int N;
	static long[] nums;
	static long[] tree;
	
	static int S;
	public static void main(String[] args) {
		N = 8000000; // 백만까지는 가능한데 천만하면 안됨 팔백만까지는되는듯 
		S = 1;
		while(S < N) {
			S *= 2;
		}
		System.out.println(S*2);
		tree = new long[S*2]; // 트리 크기는 S의 2배
		
		Runtime.getRuntime().gc();
		long useMemory = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
		System.out.println(useMemory / 1000000 + "MB");
	}
}

 

 

 

 

9202 Boggle

 

package day03.P9202;

public class Main {
	static TriNode root = new TriNode();
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	static void insert(String word) {
		TriNode current = root;
		for(int i = 0; i < word.length(); i++) {
			if(current.hasChild(word.charAt(i)) == false) {
				current.child[word.charAt(i) - 'A'] = new TriNode();
			}
			current = current.getChild(word.charAt(i));
		} // for문이 끝난거면 word의 끝까지 간것임 (마지막 노드라는 뜻이지)
		current.isWord = true;
	}
}

class TriNode{
	TriNode[] child = new TriNode[26];
	boolean isWord = false;
	boolean isHit = false;
	
	//사전은 하나인데 맵은 여러개라 맵 하나 돌면 그 다음에 isheat 초기화해줘야해
	void clearHit() { // 재귀호출을 이용해서 맵 끝났을 때 clear 구현
		isHit = false;
		for (int i = 0; i < child.length; i++) {
			if(child[i] != null) {
				child[i].clearHit();
			}
		}
	}
	
	//자식을 가지고 있는지?
	boolean hasChild(char c) {
		return child[c-'A'] != null;
	}
	
	TriNode getChild(char c) {
		return child[c-'A'];
	}
}

 

 

'공부기록 > 알고리즘' 카테고리의 다른 글

[알고리즘] 5일차_그래프  (0) 2024.02.19
[알고리즘] 4일차  (0) 2024.02.16
[알고리즘]P1713. 후보 추천하기  (0) 2024.02.14
[알고리즘] P2143. 두 배열의 합  (0) 2024.02.14
영리한 프로그래밍을 위한 알고리즘 강좌 - Ch3.레드블랙트리  (0) 2023.08.12

'공부기록/알고리즘' Related Articles

티스토리툴바