자바 (73) 썸네일형 리스트형 [백준] 1149 RGB거리 (JAVA) 풀이 이 문제는 정석적인 DP라고 볼수있겠다. 심지어 색도 3개이고 집의 개수도 적어서 시간 걱정 역시 안해도 된다. 문제에서 조건을 까다롭게 주었는게 결국은 인접한 집들끼리는 색이 겹처서는 안된다는 말이다. 알고리즘의 개요는 입력 받아 저장하는 2차원 int형 배열인 street와 dp를 만들면된다. 그러고 나서 dp의 첫번째 줄은 초기화를 해주고 그 다음은 겹치지 않는 색들끼리(dp) 비교해서 그 중 작은 값과 현재집의 특정색상과 더해서 저장 DP를 끝까지 수행해주면 dp[N-1]중에서 가장작은값을 출력. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.ut.. [백준] 2667 단지번호붙이기 (JAVA) 풀이 이 문제는 단순히 DFS혹은 BFS로 전부 탐색하면서 각각의 cluster가 몇개가 있는지 있다면 그 cluster에 존재하는 원소들의 값을 바꿔나가면서 탐색이 끝나면 각 클러스터는 몇개이고 cluster의 원소수는 몇개가 있는지 출력하면 되는 문제이다. 범위도 작기때문에 시간 걱정없이 풀면 될듯하다. 코드 import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.util.List; class Main{ public static int [][]map; public static boolean [][] visited; public static int []dr_x = {-1, 0, 1, 0}; public.. [백준] 2352 반도체 설계 (JAVA) 풀이 LIS문제를 더풀어보고 DP문제를 더 풀어보자고 생각을해 문제들을 찾아보다가 이문제를 발견하였고 처음보았을때는 LIS를 그냥 적용하면 될것 같아 쉽네~ 이러고 했는데 시간초과까지는 아니지만 너무 오래 걸려서 풀렸다. 그래서 다른 방법이 있나 하고 찾아 보았고 해답은 바이너리 서치와 LIS 를 섞어서 푸는 것이였다. 기존의 LIS방식은 시간복잡도가 O(N*N)이였는데 이번에 풀은 방식의 시간복잡도는 O(NlogN)이다. 전체적인 큰틀은 다음과 같다. 1. 배열탐색하면서 가장큰수를 계속 뒤에 이어붙인다 2. 중간에 끼어들수 있는수는 이분탐색을 이용해, 적절한 위치에 있던 수와 교체한다. 3. 배열을 탐색하면서 맨앞요소보다 작은 요소가 새익면 맨앞요소를 교체한다. 처음에는 두번째와 세번째가 이해가 잘 되.. [백준] 2565 전깃줄 (JAVA) 풀이 이 문제는 가만히 생각하다 보니 복잡하지만 풀이가 보였다. 풀이 방법은 일단 문제에서 주어진 입력값을 전부 받고 그다음 가장 많이 겹치는 순으로 선을 제거해 겹쳐저있는 선들의 수를 계산 해나갔다. 그러나 이 방식으로 하면 시간도 오래걸리고 결론적으로 문제에서 틀렸다고 나오기도 하였다. (배열범위를 벗어났다고 나오지만...) 그래서 구글링을 하였고 역시 내가 생각한 풀이 방법보다 훨씬 깔끔했다. 나는 처음에는 문제에서 하라는대로 전선을 전부 이은후 하나씩 제거 해나갔는데 다른 사람들의 코드는 전부 연결한후 LIS방식으로 지우는 것이 아닌 최대 몇개까지 이을수있는것인가.를 구하고 전체에서 방금 구한수를 빼서 정답을 도출했다. 즉 전체집합에서 여집합을 빼서 구했다. 앞으로는 조금 유연하게 보도록 노력해야.. [백준]11055 가장 큰 증가 부분 수열 (java) 풀이 이 문제는 전형적인 LIS문제중 하나이다. 문제는 크게 어려울것이 없이 기준값이 정해지면 인덱스의 처음부터 마지막까지 돌아가면서 만약 증가하는 부분수열을 만족한다면 DP에 저장하면 된다. 그렇게 기준값을 끝까지 돌리고 난후 DP에 저장되어있는 수들중 가장큰수를 출력하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(ne.. [백준] 11279 최대 힙(JAVA) 풀이 이 문제는 어렵게 생각할것 없이 그냥 우선순위큐를 사용하면 된다. 특이점으로는 오름차순이 아니라 내림차순으로 우선순위를 정해야하는데 나는 그냥 넣을때는 전부 - 부호를 붙혀서 넣었고 뺄때는 -부호를 다시 붙혀서 빼내었다. import java.io.*; import java.util.PriorityQueue; import java.util.StringTokenizer; class Main { static int N; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new Bu.. [백준] 7562 나이트의 이동 (JAVA) 풀이 위의 문제는 BFS의 정석이라고도 할수있는 문제이다. 그렇다고 풀었는건 아니다... 문제에서 주어지는 나이트의 최단이동경로에 초점을 두어 최단경로를 구하는 알고리즘을 생각하다 보니 풀지 못하였던 것 같다. 그냥 다음으로 이동할때 이동하기전의 이동횟수에 하나씩 더해가다 어느 순간 goal의 좌표와 현재 좌표가 같게 되면 그때의 이동횟수를 출력하면 문제는 풀린다. 살짝 dp와도 비슷한 점이 있는것 같다. 느낀점은 구현만 확실히 해놓으면 부담없이 전부 탐색하면 될듯하다. package com.company; import java.io.*; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class .. [백준] 1182 부분수열의 합 (JAVA) 풀이 살짝 변칙적인 백트랙킹 인듯하다. 이문제에서는 for문이 필요하지 않다. 이해는 코드를 보면 갈것이다. 백트랙킹 문제를 더 풀어봐야 할것 같다. package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { static int N; static int S; static int count=0; static int Sum; static int[] Num; public static void main(String[] args) throws IOException { BufferedRea.. [백준] 9465 스티커 (JAVA) 풀이 이 문제는 쉬운 DP문제에 속하는 듯하다. 결국 못풀었지만... 일단 알고리즘의 기본 베이스는 DP를 통해 앞에 있던 수들중 가장큰 수를 구하는 것이다. 밑에 있는 코드에서 쉽게 알수있겠지만 DP의 점화식은 다음과 같다. DP[0][j] = MAX(DP[1][j-1] , DP[1][j-2]) + cost[0][j]이다. 나는 처음 이식을 보고 바로 뒤에(j-2)의 같은 행은 왜 비교를 안하는지 궁금했다. 그러나 잠깐 생각해보니 바로 풀렸다. 왜냐면 같은 행의 두번째 뒤까지 비교해서 구한다면(DP[0][j-2])이는 DP[0][j-2]에서 바로 현재 위치로 온다는 것인데 그렇다면 중간에 더하고 올수있는 대각선을 DP[1][j-1] 그냥 뛰어 넘어 버리기 때문에 이는 문제에서 요구하는 최대값이 될수없다.. [백준] 1541 잃어버린 괄호 (JAVA) 풀이 이문제는 어렵게 생각할 필요없이 현재 파싱한 문자열중에 -가 나온적이 있다면 그 뒤에 나오는 수들은 전부 빼버리면 된다. 왜냐면 문제에서 괄호를 적절히 처서 최소로 만들라고 했기때문에 -가 하나가 나오든 여러개가 나오는 한번 나온후라면 괄호를 나온만큼 치면 음수가 되기때문이다. 간단한 문제이기에 코드또한 짧고 이해하기 쉬울것이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { Bu.. 이전 1 ··· 4 5 6 7 8 다음
