분류 전체보기
-
[백준-11726]-[다이나믹프로그래밍] - 2 x N 타일링알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 9. 14:58
문제링크 : https://www.acmicpc.net/problem/11726 이 문제는 문제만 그림이지 1과 2로 입력받은 수 N을 만드는 문제이다. 이런식으로 길이 2 * 5의 타일에 2 * 1 타일 로 길이 1을 1 * 2 타일 두개로 길이 2를 채울 수 있다. 그럼 1,2로 5를 만드는 경우의 수를 구하면 된다. 5를 1 또는 2로 만들 수 있는 경우의 수는1 + 1 + 1 + 1 + 11 + 1 + 1 + 21 + 1 + 2 + 11 + 2 + 1 + 11 + 2 + 22 + 1 + 22 + 2 + 1여기서 끝이 1로 끝나는 것들 2로 끝나는 것들을 모아보면- 1로 끝나는 것들 1 + 1 + 1 + 1 + 11 + 1 + 2 + 11 + 2 + 1 + 12 + 2 + 1끝자리 1을 제외하고 나..
-
[백준-2193]-[다이나믹프로그래밍] - 이친수알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 9. 14:11
문제링크 : https://www.acmicpc.net/problem/2193 이 문제는 흠.. 좀 여기에 정리해 가면서 풀어봐야겠다. 머리가 딸리니 연습장에 그려가면서 하기엔 악필이라 영 내가 알아보기가 힘들다 어느정도 풀이법이 보인다. 하나 하나 정리해가면서 해봐야지 자 친절하게 문제에서 이친수가 무엇인지 설명을 해주었다. 이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.위의 두 조건은 잊지 말아야지. 그리고 N 자리 이친수가 몇개 존재하는지 알아봐 달라고 한다. 별걸 다 알고 싶어하네 또다시 빡친다.그래도 뭐 풀어야지 일단 자리수 별로 이친수를 구해보면서 규칙을 찾아봐야겠다. 1 자리는 1 2 자리는 1 03 자리는 1 0 ..
-
[백준-1003]-[다이나믹프로그래밍] - 피보나치 수열알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 9. 13:06
문제링크 : https://www.acmicpc.net/problem/1003 이문제는 생각보다 쉽게 방법을 찾았다. 다행이다. 문제에서 친절하게 C++ 피보나치 DP 소스를 제공해줬다. 하지만 이문제를 푸는데 대략적인 힌트만 줄 뿐 저 소스를 이용할 필요는 없다. 숫자 5까지의 피보나치를 계산해보면서 이 문제를 어떻게 풀어가야할지 방법을 파악해보자. 1234567891011int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }}Colored by Color Scriptercs 숫자 0..
-
[백준-1149]-[다이나믹프로그래밍] - RGB 거리알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 9. 12:28
문제링크 : https://www.acmicpc.net/problem/1149 이문제를 이해하는데 오래걸렸지만 한번 이 문제를 이해하니 쉽게 이해하지 못한 내 자신이 한심해졌다. 문제의 설명을 보게 되면 3개의 행에 입력받는 N개의 열이 존재하고 이웃끼리는 같은 색을 할 수 없다고 한다. 이웃의 조건은 i번째 기준 i-1, i+1 이 기준이라하니 아래 위로는 같은 색을 선택 할수 없다고 하는조건이다. 그냥 같은 색으로 칠하면 안되나 빡친다. R G B 1 번째 26 40 83 2 번째 49 60 57 3번째 13 89 99 이문제를 풀기 위해서는 R,G,B의 색상 최소 값을 가지고 있는 배열이 필요하다. (int[] price index의 0 = R, 1 = G, 2 = B 를 나타낸다.)문제를 푸는 과..
-
[백준-2579]-[다이나믹프로그래밍] - 계단 오르기알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 8. 17:21
문제 경로 : https://www.acmicpc.net/problem/2579 이문제 같은 경우에는 점화식을 찾는데 굉장히 오래 걸렸다. 머리가 별로 안좋은가 보다. 굳이 점수까지 세면서 계단을 올라야 하나 좌절을 하던중 주변의 힌트와 오랜 시간의 고뇌덕에 찾았다 방법을 문제에서 제공하는 조건은 이렇다.연속된 계단 두개는 밟을 수 있고 세개는 밟을 수 없다. 한계단을 오른 뒤 다음다음 계단을 바로 밟을 수 있다. 마지막 계단은 무조건 밟아야 한다. O O X O 이런식이나 O X O O 또는 O X O X 이런식으로 계단을 밟을 수 있다.마지막 계단은 무조건 밟아야 한다 라고 하니 아래와 같이 경우의 수 두가지가 보인다. 마지막 전 계단을 밟은 경우 이 경우는 마지막 전전 계단은 밟지 않았다는거고 전전..
-
[백준-9095]-[다이나믹프로그래밍] - 1,2,3 더하기알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 8. 16:14
문제링크 : https://www.acmicpc.net/problem/9095 이문제는 다이나믹프로그래밍 공부하다보면 제일 기본문제로 나오는 문제이다.이런 문제가 공통점을 찾고 점화식 구하기가 제일 쉽다. 이런문제만 나왔으면 좋겠다. 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 숫자 1, 2, 3 으로 원하는 정소 n 을 만드는 경우의 수를 구하라 이다. 예제로 주어진 4로 구해보면 1+1+1+1 , 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 총 7가지의..
-
[백준-1463]-[다이나믹프로그래밍]-1로 만들기알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 8. 15:29
문제 링크 https://www.acmicpc.net/problem/1463 DP 문제에서 중요한 점화식을 구해보고자 2부터 1이 되는 경우를 5정도까지 구해보았다. 2 같은 경우 {2 - 1, 2 / 2 } 정도가 있고 최소 횟수는 1 이다. 3 같은 경우 { 3 -1 -1 , 3 / 2} 가 있고 2로는 나눌수 없기 때문에 최소 횟수는 1 이다.4 같은 경우 { 4 -1 -1 -1 , 4 / 2 /2 , 4 -1 / 3 ) 등을 생각 할 수 있고 최소 횟수는 2 가 된다. 5 같은 경우 { 5 -1 -1 -1 -1, 5 -1 2/ 2 , 5 -1 / -1/ 3) 등을 생각할 수 있으며 최소 횟수는 3이 된다. 어느정도 공통점이 보이는거 같다. 2와 3은 일단 넘어가고 4와 5를 보자면 4에서 1을 빼..
-
[알고리즘]-[정렬]-퀵정렬(JAVA)알고리즘/정렬 2018. 10. 30. 18:41
퀵정렬 (quick sort)개념 원소를 하나 정하여(여기서는 배열의 맨 앞 요소를 기준으로 정함) 이 원소를 pivot 이라 지칭하고 pivot 보다 작거나 같은 수들과 큰 수들을 좌우로 나누면서 정렬하는 방식pivot 의 위치는 정렬 후의 위치로 확정된다.pivot의 왼쪽과 오른쪽의 자리는 바뀌지 않는다. 왼쪽은 pivot 보다 무조건 작거나 같은 원소들, 오른쪽은 pivot 보다 무조건 큰 원소들이 위치한다.재귀함수 디자인의 과정작성하려는 함수의 역할을 말로 명확하게 정의한다. 1234 // arr을 start 부터 end 까지 퀵정렬하는 함수 public void quickSort(int arr[], int start, int end) { }Colored by Color Scriptercs 함수가..