BOJ
-
[백준 5427] - [BFS 최단거리] - 불 (JAVA)알고리즘/BFS_DFS 2018. 12. 20. 13:57
문제링크 : https://www.acmicpc.net/problem/5427 이 문제는 BFS를 가지고 풀면 되는데 좌표정보를 갖는 queue를 2개를 사용해야 한다. queue1은 불의 좌표를 저장하는 queue로 사용하고queue2는 사람의 좌표를 저장하는 queue로 사용한다. 입력 값이 숫자가 아닌 # * . @ 형식의 char 타입 데이터 이기 떄문에 나는 이 char를 custom 해서 int 형의 값으로 변경했다. # --> -1* --> -2. --> 0@ --> 1 방문 정보를 저장할 visited 배열을 사용하기 싫어서 빈 공간은 0으로 두고 사람이 움직일때 좌표의 값이 0인 위치만 이동하게 소스를 작성했다. 복잡하다면 char형의 이차원 배열과 visited 배열을 두개 생성하고 문..
-
[백준 1780]-[분할정복]-종이의 개수 (JAVA)알고리즘/분할정복(Divide and conquer) 2018. 11. 28. 13:18
문제 링크 : https://www.acmicpc.net/problem/1780 이 문제는 분할정복으로 풀어야 한다. 입력받은 사이즈가 9 라면 총 9*9 개의 모든 좌표가 같아야 하나의 정사각형 종이가 완성된다. 그럼 9*9개의 수가 같지 않다면? 9등분을 한뒤에 다시 정사각형 종이가 나오는지 확인해야 된다.사이즈 9를 3으로 나눠 다시 확인하고 여기서도 정사각형 종이가 나오지 않는다면 3으로 다시 나눠서 확인해야한다. 이문제의 조건은 사이즈는 무조건 3의 배수로 입력 된다고 한다. 첫째 줄에 N(1≤N≤3^7, N은 3^k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다. 3으로 나눠지지 않을 걱정은 안해도 되고 그럼 이 문제를 어떻게 푸는지 간단하게 정리하면 1) 사이즈만큼 하나..
-
[백준 2581] - [수학] - 소수알고리즘/수학 2018. 11. 27. 12:51
문제 링크 : https://www.acmicpc.net/problem/2581 이 문제는 소수이 먼저 확인하고 소수인 수를 합하고 최소값만 구하면 되는 문제이다. 입력받는 수의 최대값은 10000 이기 때문에 int 타입으로 처리가 가능하고 int 타입의 최대 수를 MIN 값으로 초기화 한 뒤에 풀면 소수일경우 최소값을 판단하는데 쉽게 판단 할 수 있다. 그리고 마지막에 결과를 반환할때 최소값의 값이 아직 int의 최대값이면 소수가 발견되지 않은거기 때문데 -1을 출력하면 된다. 소스123456789101112131415161718192021222324252627282930313233343536373839import java.io.BufferedReader;import java.io.IOExceptio..
-
[백준-4307]-[그리디알고리즘]-개미알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 11. 15. 19:08
문제링크 : https://www.acmicpc.net/problem/4307 이문제는 그림으로 보면서 풀면 이해가 제일 쉬울거 같다. 길이 10의 막대기가 있고 개미 3마리가 있다.개미들의 위치는 2, 6, 7에 있다. 개미1 개미2 개미3 1(지나면 끝) 2 3 4 5 6 7 8 9 10 (닿으면 끝) 여기서 무시해야될 조건이 있다. 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다. 위의 조건은 무시하고 각 개미가 떨어지는 시간의 최소와 최대를 구해보면 최소 최대 개미12 8 개미24 6 개미33 7 각 개미의 최소 시간중 제일 큰 값은 4, 최대 시간의 제일 큰 값은 8 주어진 예제의 원하는 값과 같다.각 개미들이 만나는 상황은 신경 쓸 이유가 없다는 뜻이다. 즉 이문제를 푸는 방법은..
-
[백준-2217]-[그리디알고리즘]-로프알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 11. 15. 18:54
문제링크 : https://www.acmicpc.net/problem/2217 이문제는 병렬로 연결된 로프가 버틸 수 있는 최대 중량이 얼마나 되는지 물어보는 문제이다. 로프가 한개일 때는 로프가 버틸 수 있는 한계가 최대 중량이다. 그럼 로프가 두개일 때는? 로프의 최대중량이 작은 로프의 힘 * 2 가 로프가 두개일때 최대 중량이다. 왜그럴까?? 문제에 다음 조건이 존재하기 때문이다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 중량이 20 일때 로프 두개를 사용하면 한 로프당 걸리는 중량은 10 이다. 최대중량이 10, 12 의 로프 두개가 있을때 최대 중량이 12인 로프가 아무리 10보다 더 들 수 있어도 그 이상의 무게를..