본문 바로가기

전체 글103

백준 18405번 경쟁적감염 JAVA 처음에 바이러스의 위치를 받을때 바이러스 숫자가 작은 순으로 퍼져야 하기때문에 Priority Queue를 이용해서 큐를 받아야 한다..만 난 처음에 아무생각 없이 그냥 큐로 짜놓고 우선순위 큐로 바꾸기 싫어서 그냥 배열로 바꾸고 그걸 정렬하고 그걸 큐에 집어넣는 식으로 처리했다. package com.company; import java.io.*; import java.util.*; class Point{ int X; int Y; int number; Point(int x, int y,int number){ this.X=x; this.Y=y; this.number=number; } } public class Main { public static void printMap(int[][] map){ for(.. 2020. 11. 5.
동빈북 3장 그리디 내용 정리 Greedy라는 단어는 한국어로 번역하면 욕심쟁이 기법이다. 단어에서 느껴지는 뉘양스 그대로 그 상황에서만 최선이 되는 경우를 고르는 알고리즘인데 아무생각없이 보면 그 자리에서 가장 유리한 선택을 하는것이 최적의 답일 것 같다고 생각 할 수 있지만.. 인생을 보더라도 항상 그 순간에 최적의 선택을 한다고 그것이 모두 모아놓고 봤을땐 최선이 아니다. 알고리즘도 어찌보면 인생과 비슷하기 때문에 문제마다 전체적으로 보는 것이 중요하다.(물론 인생이 더 복잡하지만..) 아무튼 현재의 선택이 나중에 끼칠 영향을 고려하지 않는다. 그 예제로는 예를들어 배열이 6 10 5 30 6 이렇게 있다고 했을때 연속된 숫자를 고르지 못해 만약 그냥 당장 배열 요소중 하나만 본다고 가정하면 답은 17이 될 것이다. 하지만, 알.. 2020. 11. 3.
백준 11479번 통나무건너뛰기 JAVA 해결 방식은 새로운 덱을 하나 만들어서 정렬시킨 배열에서 숫자가 큰 순으로 덱에다가 번갈아 가며 앞뒤로 집어넣으면 결론적으로 가장 작은 차이가 생기는 덱이 하나가 생성된다. 그 후, 덱에 들어있는 값을 배열로 옮겨 인접한 배열 요소의 차이가 가장 큰 값을 구한다. 단, 이때 그 차이는 절대값으로 해야한다. 한번에 맞춰서 기분이 좋다.. import java.io.*; import java.lang.reflect.Array; import java.util.*; import java.util.logging.FileHandler; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = n.. 2020. 11. 3.
백준 3273번 두수의합 JAVA 풀어보진 않았지만 전체 탐색으로 합을 구하려고 하면 아마도 복잡도가 N^2이 되어서 시간복잡도가 터질 가능성이 높은 문제이다. 문제의 핵심은 두수의 합이기 때문에 더한 값이 목표하는 값보다 크다면 그 뒷부분의 값은 더할필요가 없다는 것이 핵심이다. 가장 큰값과 작은 값을 시작과 끝점으로 삼아서 합이 작다면 시작부분을 더 큰수로 교체해주고 만약 더 크다면 끝부분을 더 작은수로 줄여주며 비교해주면서 일치하는 값이 나온다면 start를 증가시키거나 end를 줄여주어서 필요없는 부분은 탐색하지 않도록 한다. import java.io.*; import java.util.*; public class Main { static int[] numbers; public static void main(String[] ar.. 2020. 10. 11.

티스토리툴바