공부(2018~2019) - 스킨변경전

1. 1026번 보물간단한 정렬 문제, Arrays.sort를 이용해서 a는 0번부터 b는 끝부터 곱해서 더 해주면 된다.다른방법으로는 Collection을 이용한다. 주의할 점은 Arrays.sort는 오름차순 밖에 할 수 가 없다. 내림차순은 Collections.reverse를 이용123456789101112131415161718192021222324252627282930313233343536373839import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Collection..

1. 7569번 토마토7576번 토마토의 응용 문제, BFS를 사용하는 기본 문제로 3차원 배열을 사용하여 문제 풀이앞 뒤 왼쪽 오른쪽 위 아래 총 6가지의 변화량을 잘 잡아주기만 하면 된다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import ja..

1. 2178번 미로 탐색기본 BFS 문제, 주의할점은 처음에 DFS로 접근을 했는데 시간초과가 발생했다. 1이 많을 경우 경로가 무수히 많기 때문이었다. 영역이나 경우의 수를 묻는 문제가 아닌 최단경로 문제일 경우에는 BFS로 접근하는 것이 좋을 것 같다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;imp..

1. 7576번 토마토기본 BFS 문제, 영역이 하루에 한번씩만 늘어나기 때문에 BFS를 활용하여 level을 출력한다. 주의할 점은 DFS는 영역의 깊이를 탐색하기 때문에 BFS로 푸는 것이 더 쉽게 풀수 있다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import..

1. 1987번 알파벳백트래킹 문제, 단순 DFS는 영역을 구할 때 사용한다. 즉 한번의 경우가 아닌 갈 수 있는 모든 곳을 탐색 하는 것이다.이 경우는 하나의 경로에 하나의 답이 필요한 문제로 하나의 경로가 끝나면 다시 이전 경로로 돌아가 탐색해야한다.하나의 경로가 끝나는 경우 그 경로에 해당하는 값은 없애주어야 한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Str..

1. 1652번 누울 자리를 찾아라단순히 발아래에 짐이 있는지 벽이 있는지 확인하면 되는 문제, 문제를 이해하는 것이 문제2중 for문으로 가로 확인, 세로 확인 하여 풀이123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960import 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 N..

1. 1946번 신입사원그리디 알고리즘 -> 매번 비교를 통해 가장 최선이 되는 값을 구한다.처음에는 모든 경우의 수를 판단해서 한명씩 지워나가게 했으나 사원수가 최대 100000 명이므로 시간 초과 발생배열의 인덱스를 이용하여 쉽게 순위를 판단하여 풀 수 있는 문제 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112import java.io.Buffe..

1. 1012번 유기농 배추DFS를 이용해서 영역 구하는 간단한 문제Arrays.fill 함수를 이용하면 쉽게 초기화를 할 수 있다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.StringTokenizer; publ..

1. 11724번 연결요소의 개수DFS 문제, 영역의 개수 구하는 문제와 동일한 방식주의 할 점은 방향성이 없다는 것은 간선은 하나로 봐야하고 (1 3),(2 3) 이렇게 들어올떄 1-3-2 를 하나로 인식하는 지를 확인해야한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer; pub..

1. 10974번 모든순열다음 순열에서 출력을 계속해주는 재귀 형태로 풀이12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(S..

1. 4673번 셀프넘버버셀프넘버를 구하기 보다 셀프넘버가 아닌 수를 체크해서 풀이 인덱스를 저장하여 체크 되지 않은 index를 출력1234567891011121314151617181920212223int main(){ bool check[20001] = { false }; for (int i = 1; i

1. 1010번 다리놓기nCr로 풀 수 있다. 공식 n!/r!(n-r)!123456789101112131415161718192021222324252627282930313233343536373839import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.math.BigInteger;import java.util.ArrayList;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { Buffere..