Algorithm (57) 썸네일형 리스트형 [백준] 1003번: 피보나치 함수 문제링크 : https://www.acmicpc.net/problem/1003 문제풀이 정답 비율이 29%로 낮아서 어려운 문제인 줄 알았는데.. 왜 이렇게 낮은지 모르겠다. 1) fibonacci(2) 호출 시 fibonacci(1) 호출 --- 1 출력 fibonacci(0) 호출 --- 0 출력 2) fibonacci(3) 호출 시 fibonacci(2) 호출 --- 1, 0 출력 fibonacci(1) 호출 --- 1 출력 여기에서 fibonacci(2)는 또 구할 필요 없이 1번에서 구한 개수를 가져다 쓰면 된다. 따라서 fibonacci(N)을 호출했을 때 출력되는 개수는 fibonacci(N-1)을 호출했을 때 출력되는 개수 + fibonacci(N-2)를 호출했을 때 출력되는 개수와 같다... [백준] 2579번: 계단 오르기 문제링크 : https://www.acmicpc.net/problem/2579 문제풀이 동적 계획법으로 풀 수 있는 문제이다. 계단 오르는 데는 다음과 같은 규칙이 있다. 1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 3. 마지막 도착 계단은 반드시 밟아야 한다. 점수가 25인 계단까지 올라가려면, 아래와 같은 방법이 존재한다. n-2 까지의 최댓값 + n n-3 까지의 최댓값 + n-1 + n 의 식으로 25까지의 최댓값을 구할 수 있다. n-1 까지의 최댓값을 구하지 않는 이유는 n-1 까지 두 개의 계단을 올라온 경우가 최댓값이라고 하면 25까지 연속해서 올라갈 수 없기 때문이다. (아래 그림은 15까지 세 계단을 올라오는 경우.. [백준] 9095번: 1, 2, 3 더하기 문제링크 : https://www.acmicpc.net/problem/9095 문제풀이 처음에 문제를 잘못이해해서 시간이 오래 걸렸다..^-^ 블로그 글들을 참고해서 보다가 잘못이해했다는 것을 깨달았다. 이 문제도 마찬가지로 동적 계획법으로 해결할 수 있다. 방법의 수를 적다 보면 다음과 같은 규칙을 찾을 수 있다. 방법의 수는 앞 세 개 숫자의 방법의 수를 합한 것과 같다. 소스코드 /* * 백준 9095번: 1, 2, 3 더하기 */ #include using namespace std; int main() { int T; cin >> T; int arr[11]; arr[0] = 0; arr[1] = 1; arr[2] = 2; arr[3] = 4; for (int i = 4; i < 11; i++) {.. [백준] 1463번: 1로 만들기 문제링크 : https://www.acmicpc.net/problem/1463 문제풀이 동적 계획법(Dynamic programming)으로 풀 수 있는 문제이다. 2와 3은 각각의 수로 나눠지므로 1로 저장해놓았는데, 어차피 계산 결과 1이 나오니 1로 초기화해놓을 필요는 없을 것 같다. 4인 경우부터 예를 들어보면 다음과 같다. 예) 4의 연산 횟수 최솟값 ① 4는 2로 나눠지므로 2로 나눈다. --- 1번 ② 2에서 1을 빼면 (혹은 2로 나누면) 1이 된다. --- 1번 ②번의 경우 2에서 1이 되는 횟수는 1번으로, 이미 배열에 횟수를 저장해놓았다. 따라서 arr[2]의 값에 1을 더하면 4의 연산 횟수 최솟값이 된다. 예) 5의 연산 횟수 최솟값 ① 5는 3, 2로 나눠지지 않으므로 1을 뺀다.. [Algorithm] 동적 계획법 (Dynamic Programming) 동적 계획법이란? - 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다. - 각 하위 문제를 해결 & 계산한 뒤 저장한다. - 후에 같은 문제가 나왔을 때 계산하지 않고 저장한 값을 사용한다. - 대표적인 예로 피보나치 수열을 구할 때 사용한다. 예) 피보나치 수열 - 첫째 및 둘째 항이 1이며, 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 피보나치 수열을 구하는 함수를 fib()라고 정의하고, 피보나치의 다섯번째 항을 구한다고 하면, 계산은 다음과 같다. 값이 계속해서 중복되어 계산되는 것을 볼 수 있다. 하위 값을 계산하면서 미리 저장해놓으면 fib(5)는 앞의 두 값만 더하면 구할 수 있다. [백준] 1181번: 단어 정렬 문제링크 : https://www.acmicpc.net/problem/1181 문제풀이 : 입력받은 데이터를 sort()함수로 정렬한다. 1. 길이비교 2. 길이가 같은 경우는 사전순대로 정렬해야 하므로 비교 함수를 따로 정의하여 같이 넘겨준다. 소스코드(C++) /* * 백준 1181번: 단어 정렬 */ #include #include #include using namespace std; bool compare(string a, string b) { if (a.length() == b.length()) return a > N; string* arr = new string[N]; f.. [백준] 1427번: 소트인사이드 문제링크 : https://www.acmicpc.net/problem/1427 문제풀이 : algorithm 헤더파일을 선언한 후 sort()함수로 정렬, reverse()함수로 내림차순으로 정렬한 후 출력한다. 소스코드 /* * 백준 1427번: 소트인사이드 */ #include #include #include using namespace std; int main() { string N; cin >> N; sort(N.begin(), N.end()); reverse(N.begin(), N.end()); cout [백준] 2108번: 통계학 문제 링크 : https://www.acmicpc.net/problem/2108 문제 풀이 - 산술평균 : 데이터를 입력받을 때 합계를 미리 구해놓고 round함수를 이용해 반올림하여 출력한다. - 중앙값 : algorithm 헤더파일을 선언하고, sort() 함수를 이용해 데이터를 정렬한 후 가운데 인덱스에 해당하는 값을 출력한다. - 최빈값 : 문제를 보면 데이터는 절대값 4000을 넘지 않는다는 조건이 있다. 그 말은, -4000 ~ 4000의 범위에만 데이터가 존재한다는 뜻이다. 0 포함 8001개의 데이터를 위한 카운트 배열을 할당하고, 각 숫자가 몇 번 입력되는지 저장한다. 카운트 배열을 돌면서 가장 많이 나타나는 값을 구한다. 단, 최빈값이 여러 개인 경우에는 두번째로 작은 값을 출력해야 하.. 이전 1 2 3 4 5 6 7 8 다음
