사전캠프 10일차

 

SQL 강의 4주차 

서브 쿼리와 조인에 대해 배웠으며 여러 실습들을 따라하며 감을 잡았다

아래는 숙제 문제를 풀어본것이다.

 

SELECT a.restaurant_name , case when avg_price between 5000 and 9999 then 'price_group1'
								when avg_price between 10000 and 19999 then 'price_group2'
								when avg_price between 20000 and 30000 then 'price_group3'
								when avg_price > 30000 then 'price_group4' end as price_group,
							case when avg_age between 0 and 29 then 'age_group1'
								when avg_age between 30 and 39 then 'age_group2'
								when avg_age between 40 and 49 then 'age_group3'
								else 'age_group4' end as age_group
from (
select f.restaurant_name , avg(f.price) as avg_price, avg(c.age) as avg_age
from food_orders as f join customers c on f.customer_id = c.customer_id  group by 1 order by 1
) a;

 

되게 난잡한거 같지만 case when then 문과 join 서브쿼리 이 3개는 확실히 배워가는 강의 였던거 같다! 

또한 항상 쿼리문 작성할 때 group by나 order by 할 때 항상  다 써줫는데 저렇게 숫자로 출력하는 첫번째 열을 가져온다 라는 것을 명시해주는 것이 정말 편한거 같다!

 

백준 알고리즘 문제 풀기

 

10026 적록색약

이전 문제들에 비해 상당히 쉬웠다. 그냥 DFS를 이용해서 count 수를 구하고 색약인 경우 R을 G로 바꾸고 다시 DFS로 count를 구하면 되었다. 

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static char arr[][];
	public static boolean visited[][];
	public static int n;
	public static int m;
	public static int count;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		n = Integer.parseInt(bf.readLine());
		arr = new char[n][n];
		visited = new boolean[n][n];
		for(int i=0;i<n;i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine(),"RGB",true);
			for(int j=0;j<n;j++) {
				arr[i][j] = st.nextToken().charAt(0);
			}
		}
		count = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(!visited[i][j]) {
					count++;
					dfs(i,j, arr[i][j]);
				}
			}
		}
		System.out.print(count+" ");
		visited = new boolean[n][n];
		count = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(arr[i][j]=='R') {
					arr[i][j] = 'G';
				}
			}
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(!visited[i][j]) {
					count++;
					dfs(i,j, arr[i][j]);
				}
			}
		}
		System.out.println(count);
		
	}
	public static void dfs(int y, int x, char c) {
		int [] xflag = {-1,0,0,1};
		int [] yflag = {0,-1,1,0};
		visited[y][x] = true;
		for(int i=0;i<4;i++) {
			int newX = x - xflag[i];
			int newY = y - yflag[i];
			if(newX >= 0 && newY >=0 && newX <n && newY <n) {
				if(!visited[newY][newX] && c == arr[newY][newX]) {
					dfs(newY, newX, c);
				}
			}
		}
	}

 

7569번 토마토

저번에 풀었던 토마토의 3차원 배열 버전 문제! 문제 푸는 방식은 그대로였기 때문에 쉽게 풀었다!

class tomato{
	int x;
	int y;
	int z;
	public tomato(int z, int y, int x) {
		this.x = x;
		this.y = y;
		this.z = z;
	}
}

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int arr[][][];;
	public static int n;
	public static int m;
	public static int h;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());
		arr = new int[h][m][n];
		for(int i=0;i<h;i++) {
			for(int j=0;j<m;j++) {
				st = new StringTokenizer(bf.readLine());
				for(int k=0;k<n;k++) {
					arr[i][j][k] = Integer.parseInt(st.nextToken());
				}
			}
		}
		if(zeroCount()==0) {
			System.out.println(0);
		}
		else {
			bfs();
		}
		
	}
	public static void bfs() {
		int [] xflag = {-1,0,0,1,0,0};
		int [] yflag = {0,-1,1,0,0,0};
		int [] zflag = {0,0,0,0,-1,1};
		int day =0;
		Queue <tomato> q= new LinkedList<>();
		for(int i=0;i<h;i++) {
			for(int j=0;j<m;j++) {
				for(int k=0;k<n;k++) {
					if(arr[i][j][k] == 1) {
						q.add(new tomato(i,j,k));
					}
				}
			}
		}
		while(!q.isEmpty()) {
			tomato t = q.poll();
			int x = t.x;
			int y = t.y;
			int z = t.z;
			for(int i=0;i<6;i++) {
				int newX = x + xflag[i];
				int newY = y + yflag[i];
				int newZ = z + zflag[i];
				if(newX >= 0 && newY >=0 && newZ >=0 && newX <n && newY <m && newZ < h) {
					if(arr[newZ][newY][newX] == 0) {
						arr[newZ][newY][newX] = arr[z][y][x] + 1;
						if(arr[newZ][newY][newX] > day) {
							day = arr[newZ][newY][newX];
						}
						q.add(new tomato(newZ,newY,newX));
					}
				}
			}
		}
		if(zeroCount()==0) {
			System.out.println(day-1);
		}
		else {
			System.out.println(-1);
		}
		
	}
	public static int zeroCount() {
		int count = 0;
		for(int i=0;i<h;i++) {
			for(int j=0;j<m;j++) {
				for(int k=0;k<n;k++) {
					if(arr[i][j][k] == 0) {
						count++;
					}
				}
			}
		}
		return count;
	}
}

 

11725번 트리의 부모 찾기

생각보다 까다로웠다 DFS로 푸는 것 보단 단계별로 하나씩 내려가는 BFS가 이 문제를 푸는데에는 맞는 방식이며 인접행렬로 구할 시 메모리가 어마어마 한 양이 필요하므로 이 문제에서는 인접 리스트를 이용해서 풀어야했다! 

또한 검색으로 알아본 결과 8000 * 8000 정도가 한계이며 다른 메모리를 사용하는 것까지 포함해서 한 범위가 7000이 넘어가면 2차원 배열을 사용하면 안된다는 것을 배웠다!

인접 행렬의 메모리 사용량 O(N^2) 의 공간 복잡도를 사용

인접 리스트의 메모리 사용량 O(V+E) 의 공간 복잡도 사용 v는 정점의 개수 e는 간선의 개수

또한 간선의 수가 n의 제곱에 가까워 질수록 둘의 공간 복잡도는 비슷해진다!

 

• 시간이 중요한 작업(예: 간선 존재 확인, 추가/제거)이 많다면, 인접 행렬이 적합.
• 메모리와 전체 그래프 탐색 효율이 중요한 경우, 특히 희소 그래프에서는 인접 리스트가 적합.

 

 

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static ArrayList<Integer>[] arr;
	public static boolean visited[];
	public static int parent[];
	public static int n;
	public static int m;
	public static int h;
	public static int count;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		n = Integer.parseInt(bf.readLine());
		arr = new ArrayList[n+1];
		for(int i=1;i<=n;i++) {
			arr[i] = new ArrayList<>();
		}
		parent = new int[n+1];
		visited = new boolean[n+1];
		for(int i=0;i<n-1;i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a].add(b);
			arr[b].add(a);
		}
		dfs(1);
		for(int i=2;i<=n;i++) {
			sb.append(parent[i]).append("\n");
		}
		System.out.println(sb);
	}
	public static void dfs(int start) {
		Queue <Integer> q = new LinkedList<>();
		q.add(start);
		while(!q.isEmpty()) {
			start = q.poll();
			visited[start] = true;
			for(int i : arr[start]) {
				if(!visited[i]) {
					visited[i] = true;
					parent[i] = start;
					q.add(i);
				}
			}
		}
		
	}
}