출저 : https://www.acmicpc.net/problem/2026 "DFS 문제를 잘 읽어야함..." 문제를 잘 안 읽어서 계속 틀렸음. 문제를 잘 읽어 보면 선택된 K명의 모든 애들이 다 친구여야 함. 최초에 1-3-2-4 의 관계가 되면 나는 1,2,3,4 모두 답으로 출력했음. 이거 빼고는 그냥 DFS 문제. 따라서 아래 68~ 73 라인을 추가했음. 팁으로 경로를 찍을 때는 list 보다는 아래와 같이 result 배열 하나만을 생성해 이를 이용해 경로를 찍는 것이 더 좋다고 생각됨. 또 하나, 전부 친구인지 아닌지 판별하는 부분에서 boolean 변수를 사용할 수도 있지만 이미 생성된 j를 가지고 끝까지 돌았는지 j == index 인지 판별하면 변수 생성을 하나 줄일수 있으미.. 12..
출저 : https://www.acmicpc.net/problem/1389 "다익스트라,BFS,DFS 다~~" 다익스트라를 연습할 수 있는 좋은 문제 인 듯, 일단 다익스트라는 BFS를 활용해 시작지점으로부터 연결된 모든 노드로 가는 최소값을 찾는 알고리즘이다. ( 단, 다익스트라는 가중치가 각각 다른 경우에 유용하며, 이 문제에서는 가중치가 1이므로 그냥 BFS 혹은 DFS 탐색하면됨...) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869import java.io.BufferedReader;import java.io.IO..
출저 : https://www.acmicpc.net/problem/2583 "BFS" 영역을 나 누 자 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Collections;import java.util.LinkedList..
출저 : https://www.acmicpc.net/problem/2234 "BFS 그리고 비트마스킹(필수는아님..)" 비트마스킹을 사용하지 않고도 0 ~ 15 까지의 숫자별로 가능한 방향을 이차원 배열로 정의해줘서 풀면됨... 하지만 아래 풀이는 비트마스킹 써씅ㅁ. solve1()을 통해 아래 두개의 답을 구할 수 있다. 1. BFS를 돈다.2. 1번 BFS를 돌면서 각 방의 size가 구해지므로 최대값을 비교해 구한다. 마지막 문제에 대한 답을 구하는게 관건인듯 하다. 나는 1,2 번을 구하면서 새로운 int[][] arr 을 정의해서 이곳에 0~ 방의 개수 까지 카운터를 마킹했다.(영역 나누기 처럼) 동시에 각 index마다 방의 크기를 ArrayList에 저장해두었다. 그 후에 새로 정의한 맵 a..
출저 : https://www.acmicpc.net/problem/1463 "DP DP 딥" 1을 가지고 N을 만든다고 역으로 생각하자. dp[3] 까지 최소값을 구한다. 1이 되겠다. 그 이후에 4를 만드려면 어떤 방법이 있을까? 2 에서 2를 곱하거나 3에서 더하기 1을 하거나. dp[n/2] + 1 ( n % 2 == 0 )dp[n] = dp[n/3] + 1 ( n % 3 == 0 ) dp[n-1] 이중에 최소값을 dp[n]으로 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344import java.util.Scanner; public class Main { static int n; static int..
출저 : https://www.acmicpc.net/problem/2579 "DP 쓸 때, dp값과 map에 값을 활용해보자.." 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class Main { static int N; static int[] dp; static int[] map; public static void main(String[] args) throws IOException{ BufferedReader br = n..
출저 : https://www.acmicpc.net/problem/1149 "DP" 어려웠다. 기초적인 dp문제라고 했는데 왜 이리 어려웠지...ㅎㅎ dp[x] = dp[x-1] + min(x) ; 까지는 생각을 하고, 해답을 봤다. 그리고 최초 dp[0] 가 R,G,B 일 때를 모두 체크하기위해 dp[x][3] 배열을 만들어 해당 dp 값을 이용한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringToken..
출저 : https://www.acmicpc.net/problem/1003 "DP" 12345678910111213141516171819202122232425262728293031323334353637import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class Main { static int T,N; static int z, o; static int dp[][]; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader b..
출저 : https://www.acmicpc.net/problem/15685 "아이디어가 필요한 구현문제" 삼성 기출 문제. 각 세대를 더해 갈 수록 기존에 찍었던 선들을 모두 왼쪽으로 돌려서 다시 그려준다. 초기에 생각만 잘하면 쉽게 풀릴 문제 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Lis..
출저 : https://www.acmicpc.net/problem/1932 "DP, bottom-up / DP라고 무조건 재귀 생각하지말자." 알고리즘은 삼각형의 맨 밑부분부터 시작해서 dp 갱신을 시작한다. 처음에 재귀로 구현했는데 시간초과가 났다. dp 값을 비교해서 기존 dp 값보다 작으면 탐색하지 못하게 하였는데??? 라고 생각했다. dp 값이 나중에 큰 값으로 갱신된다면, 이전 까지 탐색 경로들은 그냥 지나칠 거임.. 따라서 해당 지점에 가능한 가장 큰 값이 맨 나중에 갱신되는 데이터가 주어졌다면 아마 dp 값 비교를 통한 가지치기는 적용 안될듯. 1234567891011121314151617181920212223242526272829303132333435363738394041424344impo..
- Total
- Today
- Yesterday