자바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. No1260 DFS와 BFS(그래프 이론: 너비우선탐색, 깊이우선탐색) 백준 7576 번(토마토)를 풀기 전에 먼저 전에 풀었던 깊이 우선 탐색(Depth First Search)과 너비 우선 탐색(Breadth First Search) 기본 문제인 이 문제의 문제풀이를 기록하면서 두 가지 알고리즘을 정리해보고자 한다. 1. 깊이 우선 탐색(DFS) 간선들로 연결된 점들을 이차원 배열(int[][])로 표현한 후 i와 j 사이를 연결하는 간선이 있을 경우 arr[i][j], arr[j][i]의 값을 1로, 없을 경우 0으로 표현한다. 이후 탐색할 때 i와 연결된 점들을 찾을 때 arr[i]의 값들을 검색하면 된다. 한번 검색한 곳을 다시 지나치지 않기 위해 visit(boolean[]) 배열 하나를 만들어 i번째 점을 검색한 후 visit[i]는 true값으로 변경한다. 검.. 2022. 11. 18. 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. No9012 괄호 (Stack) 스택을 이용해서 푸는 문제다. 자바 Array를 사용하여 Stack을 직접 구현해보았다. class ArrayStack { int top; int stackSize = 50; int[] stackArr; public ArrayStack() { top = -1; stackArr = new int[this.stackSize]; } public boolean isEmpty() { if(top == -1) return true; return false; } public boolean isFull() { if(top == stackSize-1) return true; return false; } public void push(int value) { if(isFull()) { return; } stackArr[++.. 2022. 10. 25. 이진 검색 (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 다음
