알고리즘
-
[백준-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 함수가..
-
[알고리즘]-[정렬]-합병정렬(JAVA)알고리즘/정렬 2018. 10. 30. 15:53
합병정렬 (merge sort)개념배열을 절반으로 나누어 각각을 정렬한 후, 합치는 정렬 알고리즘시간 복잡도는 O(n log n) 이다. 처리과정정렬을 해야할 배열을 절반으로 나누어 왼쪽 배열 오른쪽 배열을 정렬한다.정렬된 왼쪽 배열 오른쪽 배열을 순서대로 합친다.위의 처리과정을 크게 두가지로 나눌 수 있다. 그럼.. 첫번째 순서에서 절반으로 나뉘어진 왼쪽 배열 오른쪽 배열의 정렬을 어떻게 정렬 할것인가? 라는 의문이 생기는데그 절반으로 나뉘어진 두 배열도 똑같이 또 절반으로 나누고 정렬된 배열을 순서대로 합치면 된다.그렇다는것은 재귀적으로 절반으로 나뉘어지지 않을때까지 배열이 나뉘어질 것이고 그 순간부터 하나하나 나뉘어진 배열을 합치면서 정렬이 진행된다. 정확한 순서는 아래 애니메이션을 보면 코드는 감..
-
[알고리즘]-[정렬]-삽입정렬 (JAVA)알고리즘/정렬 2018. 10. 30. 12:12
삽입정렬(insertion sort)개념배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬 알고리즘 이다.정렬의 시작은 두번째 요소부터 시작되며 본인의 왼쪽으로는 이미 정렬된 상태라 생각하면 된다.왼쪽의 값이 비교하려는 요소값보다 작을떄까지 위치를 왼쪽으로 이동시키면 된다.처리과정정렬의 시작은 두번째 요소인 4부터 왼쪽의 값들과 비교를 하면된다.처음은 비교할 값이 14 하나 뿐이고 4가 14보다 작기떄문에 값을 서로 교체한다. 4와 14는 이미 정렬이 됐고 정렬할 다음 요소는 세번째 요소인 8이다. 같은 방법으로 왼쪽의 정렬된 요소들과 비교를 하여 자기 위치를 찾아가면 된다.자세한 처리과정은 아래 애니메이션을 참고하면 된다. 소스 (JAVA)1234..