백준 (88) 썸네일형 리스트형 [백준] 2178 미로탐색(JAVA) 풀이 학교 알고리즘 시간에 배웠던 미로탐색 문제인줄 알고 단순히DFS로 접근해서 모든경로의 이동수를 리스트에 저장하여 그중 가장 작은 수를 출력할려고 했다. 그러나 시간초과로 인해. 어떡게 풀어야 좋을지 몰랐다. 그래서 찾아보고 그러니 정답은 DFS가 아닌 "BFS"였다. 그러면서 다른 블로그에서는 최단, 최소를 찾을때는 BFS를 통해 구한다고 하여서 왜 그런지 몰랐다. 그러다 어느 블로그를 찾게 되었고 그 곳에 자세한 설명이 있었다. 간략하게 설명을 하면 BFS에선 간선(u,v)를 통해서, 정점 v를 처음발견해 큐를 넣었다고 가정한다. 이때, 시작점에서 v까지의 최단거리는 distanc[v]는 , 시작점에서 u까지의 최단거리 distance[u]에다가 1을 더한것이다. 조금더 풀어쓰자면 1. dista.. [백준] 2352 반도체 설계 (JAVA) 풀이 LIS문제를 더풀어보고 DP문제를 더 풀어보자고 생각을해 문제들을 찾아보다가 이문제를 발견하였고 처음보았을때는 LIS를 그냥 적용하면 될것 같아 쉽네~ 이러고 했는데 시간초과까지는 아니지만 너무 오래 걸려서 풀렸다. 그래서 다른 방법이 있나 하고 찾아 보았고 해답은 바이너리 서치와 LIS 를 섞어서 푸는 것이였다. 기존의 LIS방식은 시간복잡도가 O(N*N)이였는데 이번에 풀은 방식의 시간복잡도는 O(NlogN)이다. 전체적인 큰틀은 다음과 같다. 1. 배열탐색하면서 가장큰수를 계속 뒤에 이어붙인다 2. 중간에 끼어들수 있는수는 이분탐색을 이용해, 적절한 위치에 있던 수와 교체한다. 3. 배열을 탐색하면서 맨앞요소보다 작은 요소가 새익면 맨앞요소를 교체한다. 처음에는 두번째와 세번째가 이해가 잘 되.. [백준] 2565 전깃줄 (JAVA) 풀이 이 문제는 가만히 생각하다 보니 복잡하지만 풀이가 보였다. 풀이 방법은 일단 문제에서 주어진 입력값을 전부 받고 그다음 가장 많이 겹치는 순으로 선을 제거해 겹쳐저있는 선들의 수를 계산 해나갔다. 그러나 이 방식으로 하면 시간도 오래걸리고 결론적으로 문제에서 틀렸다고 나오기도 하였다. (배열범위를 벗어났다고 나오지만...) 그래서 구글링을 하였고 역시 내가 생각한 풀이 방법보다 훨씬 깔끔했다. 나는 처음에는 문제에서 하라는대로 전선을 전부 이은후 하나씩 제거 해나갔는데 다른 사람들의 코드는 전부 연결한후 LIS방식으로 지우는 것이 아닌 최대 몇개까지 이을수있는것인가.를 구하고 전체에서 방금 구한수를 빼서 정답을 도출했다. 즉 전체집합에서 여집합을 빼서 구했다. 앞으로는 조금 유연하게 보도록 노력해야.. [백준]1937 욕심쟁이 판다 (JAVA) 풀이 이 문제를 처음보고는 할수있을듯 싶어 고민하였다. 조금 생각하다 내린 나의 결론은 이 문제는 DFS와 Dp를 이용해서 푸는 문제일 것이다. 그도 그럴것이 그래프 탐색과 유사하며 동일한 루트를 여러번 갈수도 있기에 시간을 줄이면 좋으므로 Dp또한 같이 적용시켜야 할것 같았다. 알고리즘의 전체적인 개요는 우선 대나무의 양이 저장되어있는 2차원 배열을 만든다. 그러고 나서 DFS를 적용할것이므로 visite2차원 배열을 만들어준다. 그리고 나서 마지막으로 DP를 2차원배열로 선언하는데 이때 나느 선언할때 값들을 1로 전부 초기화했다. 왜냐면 만약 상하좌우의 좌표의 대나무의 양이(막혀있지 않다고 가정하였을때) 현재 위치에 존재하는 대나무의 양보다 적으면 아무데도 이동할수는 없지만 그래도 적어도 현재 위치한.. [백준]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 ··· 5 6 7 8 9 다음
