알고리즘/백준61 [백준][dp] 11066 파일합치기 파일합치기는 다이나믹 프로그래밍을 이용하여 해결할 수 있다. https://www.acmicpc.net/problem/11066 2018. 1. 24. [백준][그래프] 11403 경로찾기 경로 찾기는 배열과 BFS를 이용하여 간단하게 해결 할 수 있다. https://www.acmicpc.net/problem/11403 2018. 1. 24. [백준] 1991 트리순회 트리를 순회하는 방법을 전위 순회, 루트 -> 왼쪽 -> 오른쪽중위 순회, 왼쪽 -> 루트 -> 오른쪽후위 순회, 왼쪽 -> 오른쪽 -> 루트 https://www.acmicpc.net/problem/1991 2018. 1. 13. [백준][DP] 1149 RGB 거리 https://www.acmicpc.net/problem/1149 이 문제는 다이나믹 프로그래밍으로 해결할 수 있다. 이웃을 같은 색으로 칠할 수 없으므로집을 이동해 가면서 이전에 칠 할 수 있었던 색 중 최소값을 현재의 색의 비용으로 선택하여 다이나믹 테이블에 저장하면 된다 . 2017. 11. 15. [백준][DP] 5721 사탕줍기 대회 https://www.acmicpc.net/problem/5721 DP를 이용하여 해결이 가능하다. 한행만 선택이 가능하므로 행마다 따로 선택할 수 있는 최대값을 계산하여 그 값을 이용하여 따로 최대값을 계산해 준다. 하나를 선택하면 다음을 걸러서 선택할 수 있으므로 점화식은 다음과 같다. dp[i] = Math.max(dp[i - 2] + dp[i], dp[i - 1]) 2017. 10. 26. [백준] 1504 특정한 최단 경로 https://www.acmicpc.net/problem/1504 이 문제는 다익스트라 알고리즘을 이용한다. 두 지점 사이의 경로를 구하기 위해서 다익스트라 알고리즘을 3번 호출하면 된다. * 주어지는 중간 지점이 어느쪽이 더 가까운지 알 수 없기 때문에 2번 호출하여야 한다. 2017. 10. 25. [백준][DP] 1463 1로 만들기 https://www.acmicpc.net/problem/1463 이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있다. i번째 값을 만들 수 있는 경우는i-1 번째에서 1을 더하는 경우i%2 == 0인 경우에서 1을 더하는 경우i%3 == 0인 경우에서 1을 더하는 경우이다. 이 세가지 경우를 for 문을 이용하여 반복하여 해결한다. 2017. 10. 25. [백준][세그먼트 트리] 1275 커피숍2 https://www.acmicpc.net/problem/1275 이 문제는 기본적인 세그먼트 트리문제이다. 구간합을 이용하여 해결하면 된다. 변경되는 값을 잘 기록해 두면 해결 가능한다. 2017. 10. 25. [백준] 1753 다익스트라 알고리즘 다익스트라 알고리즘은 음수를 갖지 않는 유향 그래프에서 출발점과 도착점 사이의 최단거리를 구하는 알고리즘이다. 2017. 10. 12. [백준][다이나믹] 2533 사회망 서비스 다이나믹을 이용하여 해결할 수 있다. 자신이 얼리어답터일 때와 아닐때를 구분하여, 관계를 더하여 가면 해결할 수 있다. 2017. 9. 15. [백준][세그먼트트리] 6549 히스토그램에서 가장 큰 사각형 히스토그램에서 가장 큰 사각형문제는 세그먼트 트리를 이용하여 해결합니다. 2017. 9. 14. [백준][DP] 5557 1학년 1학년 문제는 DP를 이용해서 해결할 수 있습니다. 20까지의 숫자만 이용할 수 있고,+, - 연산만 할 수 있기 때문에 memo[20][연산횟수]로 메모이제이션을 하면 됩니다. 2017. 8. 23. [백준][DP] 11060 점프점프 점프 가능한 곳으로 이동가능 한 최소값을 이용하여 다이나미그 프로그래밍으로 문제를 해결한다. https://www.acmicpc.net/problem/11060 2017. 8. 23. [백준] 1005 ACM Craft 이 문제는 "위상정렬"과 메모이제이션을 이용하여 해결할 수 있다. 인입 간선이 0인 노드를 시작점으로 하여, 건물을 지을 때 걸리는 시간을 메모하여 최종 목적하는 건물을 지을 때 걸리는 시간을 확인하면 된다. https://www.acmicpc.net/problem/1005 2017. 7. 20. [백준][트리] 1197 최소 스패닝 트리(크루스칼 알고리즘) 이 문제는 최소 스패닝 트리를 구현하는 방법중 크루스칼 알고리즘을 이용하여 구현하면 된다. 크루스칼 알고리즘은 그래프 사이 연결의 최소비용을 찾으면 된다. 간선을 비용순으로 정렬하고,가장작은 비용이 들어가는 간선을 사이클이 생기지 않는 순서대로 선택하면된다. 간선 사이의 사이클은 union, find 연산을 이용하여 처리한다. https://www.acmicpc.net/problem/1197 2017. 7. 6. [백준] 1717 집합의 표현(유니온 파인드) 유니온 파인드 상호 배타적 집합이라고도 한다. 2가지 연산으로 이루어져 있다. 1. Find: x가 어떤 집합에 포함되어 있는지 찾는 연산2. Union: x와 y가 퐇마되어 있는 집합을 합치는 연산- 구현은 트리를 이용해서 한다. - parent[i] = i 의 parent 가 저장되어 있음 * parent[] 배열을 각자 자기 번호로 초기화 하는 것에 주의** find 연산에서 결과를 가지고 있다가 저장하고 반환하는 것에 주의 *** 이 union, find 연산은 MST의 크루스칼 알고리즘에 사용된다. https://www.acmicpc.net/problem/1717 2017. 7. 6. [백준][그래프] 2623 음악프로그램 가수의 순서에 따라 인입간선의 개수를 설정하고, 하나씩 제거하면서 DAG로 문제를 해결한다. https://www.acmicpc.net/problem/2623 2017. 7. 4. [백준][위상정렬] 2056 작업 DAG 이 문제도 DAG 형태로 풀 수 있다. 1. 선행관계 처리를 위해 노드별로 인입되는 간선의 개수를 기록한다. 2. 인입 간선이 0인 노드를 큐에 넣어서, 선행 처리가 끝난 노드에서 방문가능 한 노드 들을 차례로 방문하면서 시간을 더해준다. 3. 최종적으로 시간이 가장 많이 걸리는 작업을 출력한다. https://www.acmicpc.net/problem/2056 2017. 6. 27. [백준][다이나믹] 1890 점프 다이나믹 프로그래밍을 이용하여 풀이가 가능하다. 현재위치까지 이동가능한 경우의 수(dp[x][y])를 다음 이동가능한 위치(dp[x+move][y], dp[x][y+move])에 더하여 이동가능한 경우를 모두 더하여 준다. 2 3 3 1 1 2 1 3 1 2 3 1 3 1 1 0 1 0 1 0 0 0 0 0 1 1 0 1 1 0 1 3 3 https://www.acmicpc.net/problem/1890 2017. 6. 26. [백준][다이나믹] 11048 이동하기 이 문제는 DP로 해결 가능하다. 아래와 같이 해결이 가능하다. https://www.acmicpc.net/problem/11048 2017. 6. 26. [백준][트리] 11437 LCA LCA 문제는 우선 트리형태를 구성해서BFS를 이용하여 현재 노드의 부모노드, 깊이를 구한다. 그다음 깊이를 동일하게 설정하고, 한단계씩 올라오면서 부모가 같아지면 그때 부모를 출력하면 해결할 수 있다. https://www.acmicpc.net/problem/11437 2017. 6. 22. [백준][그래프] 1916 최소비용 구하기 - 다익스트라 알고리즘 이 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다. * 주의 사항은 nXn 배열을 이용하여 간선의 정보를 입력 받는데 동일한 경로로 다른 비용의 데이터가 입력되는 경우에 대한 회피만 잘 해주면 된다. https://www.acmicpc.net/problem/1916 2017. 6. 22. [백준][그래프] 1753 최단경로 - 다익스트라 알고리즘 최단경로 문제는 다익스트라 알고리즘을 이용하여 최단경로를 확인한다. 현재 최소값을 가지는 경로를 선택하여 해당 경로 부터의 거리를 확인하면 된다. https://www.acmicpc.net/problem/1753 2017. 6. 22. [백준][최단거리] 11657 타임머신(벨만포드 알고리즘) 시작지점 부터의 최단거리 확인을 위한 알고리즘을 사용하여 처리한다. 음수를 입력받을 수 있기 때문에 벨만포드 알고리즘을 이용한다. https://www.acmicpc.net/problem/11657 2017. 6. 21. [백준][다이나믹] 10844 쉬운계단수 쉬운 계단수는 앞에서 선택된 숫자 다음에 올 수 있는 숫자는 앞숫자-1, 앞숫자+1 이라는 것을 생각하여 해결 할 수 있다. 자리수가 1일때는 1~9까지 9개가 존재한다. 자리수가 2일때부터 다음숫자에 0이 나올 수가 있다. 앞자리가 0, 9일때는 뒤에 1, 8만 올 수 있으므로 하나만 선택가능하다. 하지만 1~8은 -1 또는 +1 인 숫자가 올 수 있다. 이를 이용하여 다음과 같이 해결하면 된다. memo[length][number] = memo[length-1][number - 1] + memo[length-1][number + 1 이 결과를 MOD 로 나눈 나머지를 저장하면 된다. https://www.acmicpc.net/problem/10844 2017. 6. 21. [백준][위상정렬, DAG] 2252 줄세우기 줄세우기 문제는 DAG로 표현할 수 있다. 메모리 절약을 위해 간선의 연결 상태는 리스트로 표현한다. 노드에 입력이 들어는 것을 따로 배열로 표현하여 더이상 연결이 되지 않는 노드는 제거하면 된다. https://www.acmicpc.net/problem/2252 2017. 6. 20. [백준][다이나믹] 1520 내리막길 내리막길은 DFS와 DP를 혼합하여 해결할 수 있는 문제이다. DFS를 이용하여 종점을 찾아서 다시 돌아오면서 DP로 현재 경로에서 종점으로 갈 수 있는 경우를 메모한다. 이미 메모한 곳을 찾으면 해당 값을 반환하면 된다. * -1로 초기화 하여, 방문한 곳을 0으로 표시하면 다시 방문하지 않아도 된다. 최종 위치에서 되돌아 가면서 경로를 표시하고, 새로운 경로로 가면서 최종 위치로 도달할 수 있는 경로를 만나면 그값을 더하여 처리한다. 10 1020 19 18 17 16 15 14 13 12 11 19 18 17 16 15 14 13 12 11 10 18 17 16 15 14 13 12 11 10 9 17 16 15 14 13 12 11 10 9 8 16 15 14 13 12 11 10 9 8 7 15.. 2017. 6. 20. [백준][다이나믹] 2156 포도주 시식 포도주 시식은 포도주를 첫번째로 마시는 경우, 두번째로 마시는 경우, 마시지 않는 경우로 나누어서 생각하면 해결할 수 있다. 6개의 와인잔이 1000, 900, 2, 1, 800, 700 의 순서로 놓여져 있는 경우 다음과 같이 생각할 수 있다. 순서 1 2 3 4 5 6 첫 번째로 마시는 경우 1000 900 1002 1901 2700 2601 두 번째로 마시는 경우 0 1900 902 1003 2701 3400 마시지 않는 경우 0 1000 1900 1900 1901 2701 3번의 경우에 첫 번째로 마시는 경우는 이전에 마시지 않는 경우에서 자신을 더하는 것이다. -> 1000 + 2 = 1002두 번째로 마시는 경우는 이전에 첫번째로 마시는 경우에 자신을 더하는 것이다. -> 900 + 2 = 9.. 2017. 6. 19. [백준] 1003 피보나치 함수 일반적으로 다이나믹 프로그래밍을 이용하여 피보나치 함수를 구현하는 방법을 그대로 이용하면된다. 다른점은 0을 출력하는 것과 1을 출력하는 것을 따로 저장하여 다음 값의 호출에 0과 1을 출력하는 경우를 모두 더하여 출력하면 된다. dp[N][0] : N번째 수의 0 출력 횟수dp[N][1] : N번째 수의 1 출력 횟수 i번째 수의 0과 1출력 횟수는 다음과 같다. dp[i][0] = dp[i-2][0] + dp[i-1][0];dp[i][1] = dp[i-2][1] + dp[i-1][1]; 2017. 6. 1. [백준] 1932 숫자삼각형 숫자 삼각형은 위에서부터 순서대로 아래로 내려가면서 현재 노드까지 최대값을 계산하여 자장하는 다이나믹 프로그래밍으로 해결하면된다. 트리형태를 배열에 저장하면 배열의 상단, 좌상단이 현재의 노드에 접근이 가능한 노드 이므로 이 두개의 값과 현재의 값을 더하여 최대값을 저장한다. 2017. 5. 31. 이전 1 2 3 다음
