알고리즘6 No7662 이중 우선순위 큐 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 두개의 PriorityQueue를 활용해서 하나는 최대값을 앞에 하나는 최소값을 앞에 두는 queue를 활용하면 될 것 같았다. 그래서 입력 값을 받으면 두 queue에 넣고 최대값을 빼라는 명령이 있으면 최대값queue는 poll을 최소값queue는 remove 메소드를 쓰면 될 것 같았다. 코드는 아래와 같다. package com.yuk; import java.io.BufferedRead.. 2022. 11. 23. No7576 토마토 (너비 우선 탐색) 너비 우선 탐색을 이용한 문제풀이다. 전에 사용해봤던 방식은 토마토 박스의 모든 공간를 좌표를 key, 토마토 객체를, value 값으로 하여 HashMap에 넣었다. 하루가 지날 때마다 박스의 모든 공간을 검색하여 그날 익어야 할 토마토를 찾아놓은 후 익게 하는 방식으로 풀어보았다. 하지만 매일마다 모든 토마토를 검색해야 하기에 시간 초과를 피할 수 없었다. https://6cessfuldev.tistory.com/17 No7576 토마토 (HashMap의 Custom key 만들어 풀어보기) 너비우선탐색 문제이다. 그런데 문제는 지금까지 풀었던 너비우선탐색 문제에서 탐색을 시작해야 하는 시작점이 하나였다면 이 문제는 시작점이 여러 개 일 수 있다는 문제이다. 문제를 읽고 6cessfuldev.tist.. 2022. 11. 21. No2630 색종이 만들기 (분할 정복) 종이를 4분할 하여 1분면, 2분면, 3분면, 4분면 각각의 결과에 따라 멈추거나 다시 4분할하여 재귀 함수를 실행하는 알고리즘이다. 구현하는 방식은 어렵지 않다. package com.yuk; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class No2630 { static int n; static int[][] arr; static int one; static int zero; static void dq(int x, int y, int num) { boolean flag = true; int first = arr[x][y]; loop : for (int i = x; .. 2022. 11. 15. No1931 회의실 배정 (그리디 알고리즘) 본 문제는 그리디 알고리즘을 사용하여 매 선택마다 최적의 답을 구하는 문제이다. 아래 블로그의 글을 참고하였다. https://hongjw1938.tistory.com/172 알고리즘 - 그리디 알고리즘(Greedy Algorithm) 1. 그리디 알고리즘(Greedy Algorithm)이란? 간단히 설명해, 그리디 알고리즘은 "매 선택에서 현재 당장 최적인 답"을 선택해 전체 적합한 결과를 도출하자는 알고리즘 기법이다. 즉, 백트래킹을 통해 hongjw1938.tistory.com 시작 시간과 종료 시간을 가지고 있는 여러 회의들을 시간이 겹치기 않고 가장 많이 담을 때 총 개수를 구하는 문제이다. 핵심은 1. 다음 단계의 회의를 선택할 때 .조건은 전 회의 종료 시간보다 다음 단계의 회의 시작 시간이.. 2022. 11. 8. No1389 케빈 베이컨의 6단계 법칙(플로이드 와샬 알고리즘) 2차원 배열로 두 점 사이의 간선의 유무를 입력. 플로이드 와샬 알고리즘을 통해 몇 번을 건너 도달할 수 있는지를 배열에 입력하여 답을 구하는 문제 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); int[][] map = new int[N][N]; boolean[] visit = new boolean[N]; //map 초기화 //자기 자신을 가리키는 경우 0, 초기값 최대로.. 2022. 11. 2. 이진 검색 (10816번, 1920번) 배열의 중간 위치의 값과 key값을 비교하여 찾아가는 방식 public static int binarySearch (int[] arr, int key) { int lo = 0; int hi = arr.length-1; while(lo key) { //다음 검색 배열의 끝 인덱스 값을 배열 중앙의 값보다 1작은 값으로 hi = mid-1; //찾고 싶은 key 값이 검색 배열 중앙의 값보다 클 경우 } else if(arr[mid] < key){ //다음 검색 배열의 첫 인덱스 값을 배열 중앙의 값보다 1 큰 값으로 lo=mid+1; } else { //같으면 key 값과 검색 배열 중앙값이 같으면 1 리턴 return 1; } } return 0; } 자료 구조와 알고리즘 공부는 이전에 책을 했었지만 직.. 2022. 9. 29. 이전 1 다음