알고리즘
-
[백준 11404] - [플로이드 와샬] - 플로이드 (JAVA)알고리즘/플로이드 와샬 (Floyd Warshall) 2018. 12. 28. 16:19
문제 링크 : https://www.acmicpc.net/problem/11404이 문제는 새로 접하는 알고리즘인 플로이드 와샬(Floyd Warshall) 알고리즘이다. 최단 경로를 구하는 알고리즘이다. 2차원 배열로 존재하면서 기준점 K를 두고 I에서 J 까지 가는 거리와 I에서 K 까지 갔다가 K에서 J 까지 가는 거리 두가지를 비교하여 최소 값을 최단 거리로 구하면 된다. 문제에서 주어진 예제 입력으로 플로이드 와샬 알고리즘을 공부해보자. 이 문제에서 요구하는 답은 N 개의 도시가 존재하고 1 부터 N까지의 도시각 각각의 도시에 갈 수 있는 최소 비용이다. N x N 의 2차원 배열로 존재하고 각 도시의 도달할 수 있는 최소비용이 저장되면 된다. 비용을 저장하는 배열에는 무한대의 값으로 초기화 해..
-
[백준 4963] - [그래프] - 섬의 개수 (JAVA)알고리즘/그래프(Graph) 2018. 12. 28. 14:43
문제 링크 : https://www.acmicpc.net/problem/4963 이 문제는 그래프 기본 문제이다. DFS 혹은 BFS로 풀면 되고 정답률이 48%로 어렵지 않은 문제이고 그렇기에 간단하게 접근 할 수 있다. 좌표 기준 가로, 세로, 대각선으로 움직일수 있는 땅을 하나의 섬이라 간주한다고 한다. 한번 탐색할때 가로 세로 뿐만 아니라 대각선으로도 탐색을 진행하면 임의의 좌표 [Y,X] 와 하나의 섬인 경우를 확인할 수 있다. 속도를 줄이기 위해 땅의 좌표들은 입력을 받을때 큐에 저장하였고 큐에서 하나씩 추출해가면서 탐색을 진행했다. 소스1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484..
-
[백준 2468] - [DFS BFS] - 안전영역 (JAVA)알고리즘/BFS_DFS 2018. 12. 27. 18:17
문제 링크 : https://www.acmicpc.net/problem/2468 이 문제는 정말 분노를 유발하는 문제였다. 일단 문제를 풀기에 앞서 이문제를 풀기전에 꼭 명심해야할 사항을 먼저 적고 시작하겠다. 각 영역의 높이를 기준으로 문제를 풀면 틀린다. 비가 안왔을 경우에 대해서도 처리를 해야한다. 위의 말이 무엇인지는 문제를 풀다보면 이해가 저절로 갈것이라 생각한다. 계속 문제가 틀렸다 나오길래 멘탈이 무너진 상태에서 질문 검색을 통해 확인해보니 비가 온 높이로 잠기는 안전영역을 확인하는것이었다. 안전 영역 자체의 높이로만 DFS 혹은 BFS 탐색을 돌리면 비가 안왔을 경우인 비의 높이 0 에대해서 대응을 하지 못하기 때문에 계속 틀리다는 결과를 받았다. 문제가 매우 모호한 문제이기에 이 문제를 ..
-
[백준 10610] - [그리디알고리즘] - 30 (JAVA)알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 12. 27. 16:24
문제 링크 : https://www.acmicpc.net/problem/10610 이 문제는 그리디 알고리즘 문제 중에서 어려운 편에 속하는 문제이다. 문제 자체에 오해 할 수 있는 요소가 존재해서 다들 잘못 이해 하고 접근하다가 계속 틀리다는 결과를 받는거 같다. N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 입력값 은 최대 10^5 의 숫자라고 하는게 100000 까지 입력을 받는게 아니라 자리수가 10^5개라는 말이었다. 대부분의 사람들도 100000 까지만 입력 받는걸로 이해하고 문제를 접근해서 고생을 한 거 같다. 정수형 타입인 int 나 실수형 타입인 long 이나 10^5개의 자리수를 입력 받을 수 있는 자료형은 없다. 그럼 어떻게 문제를 풀어야 할..
-
[백준 5585] - [그리디알고리즘] - 거스름돈 (JAVA)알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 12. 27. 14:46
문제 링크 : https://www.acmicpc.net/problem/5585 이문제는 어렵지 않은 그리디 알고리즘 문제이다. 그리디 알고리즘 이란 탐욕적 알고리즘으로 모든 경우의 수를 다 구하면 된다. 거스름돈을 구하는 경우는 아주 쉬운 예제 인데 접근 법은 남은 잔액에서 금액이 큰 동전부터 지급 가능한 개수를 구해나가면 된다. 예제로 380원이 물건 값이 나왔고 1000엔을 받았을때 620원을 거스름돈으로 지불해야 한다. 지불 할 수 있는 동전은 500, 100, 50, 10, 5, 1 엔 총 6가지의 동전이 존재한다. 최소의 개수로 거스름돈을 지불 하고자 한다면 금액이 큰 동전 위주로 지불해주면 되기 때문에 금액이 큰 500엔 부터 줄 수 있는 경우의 수를 구한다. 1) 500엔 으로 지불 가능한..
-
[백준 2156] - [다이나믹프로그래밍] - 포도주 시식 (JAVA)알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 12. 27. 13:33
문제 링크 : https://www.acmicpc.net/problem/2156 이 문제는 다이나믹 프로그래밍 (DP) 으로 접근 하면 된다. 다이나믹 프로그래밍에서 제일 중요한건 점화식이다. 같은 규칙으로 계산이 되고 그 규칙을 찾고 찾은 규칙에서 점화식을 구하면 문제는 아주 쉽게 풀린다. 모든 DP 문제는 점화식 구하는게 일이다. 이 문제에서 제공하는 조건은 두가지가 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 일단 첫번째 조건은 한 잔에 들어 있는 포도주를 찔끔찔끔 마실수 없다는걸 말하는 거고 두번째 조건은 연속으로 3잔을 마실수 없다는걸 말한다. 이 두번째 조건이 점화식을 구..
-
[백준 1799] - [백트래킹] - 비숍 (JAVA)알고리즘/백트래킹 2018. 12. 26. 17:13
문제 링크 : https://www.acmicpc.net/problem/1799이 문제는 이전에 풀었던 N-Queen 문제의 확장판 문제이다. 2018/11/21 - [알고리즘/백트래킹] - [백준-9663]-[백트래킹] - N-Queen 그리고 백트래킹 문제의 최고존엄 문제 급이지 않을까 생각한다. 이 문제를 잘못 접근하게 되면 문제는 풀겠지만 시간 초과에 걸리게 된다. 잘못접근하는 대부분의 이슈는 하나의 체스판을 전체 탐색을 할경우 생기게 된다. 비숍은 대각선으로 움직인다. 그렇다면 대각선에는 비숍이 위치할 수 없다. 아래처럼 2,2 에 비숍이 위치할 경우 대각선에 위치한 모든 좌표에는 비숍을 놓을 수 없다. B 또 여기서 하나 중요하게 고려해야할게 있는데 2, 2에 비숍을 놓았을경우 비숍의 좌표 기..
-
[백준 2661] - [백트래킹] - 좋은 수열 (JAVA)알고리즘/백트래킹 2018. 12. 26. 16:13
문제링크 : https://www.acmicpc.net/problem/2661 이 문제는 아주 쉽게 백트래킹으로 접근 할 수 있다. 모든 경우의 수를 탐색하면서 조건에 성립되면 결과를 출력하면 된다. 이 문제에서 제시하는 조건은 다음과 같다.임의의 길이의 인접한 두 개의 부분 수열이 동일하지 않아야 한다. (나쁜 수열이면 안된다.)나올 수 있는 좋은 수열 중에서 가장 작은 수를 출력해야 한다. 첫번째 조건을 확인하는 함수 하나를 만들고 두번째 조건은 첫번째로 좋은 수열이 나온 좋은 수열이 제일 작은 수열이기 때문에 좋은 수열이 나오면 모든 탐색을 종료 시키면 되기 때문에 따로 조건을 확인하는 함수를 만들 필요는 없다. 좋은 수열인지 확인하는 함수는 아래와 같이 만들었다. public static bool..