Programming/알고리즘 수강내용 정리(10)
-
2-3. 재귀함수 사용하기
재귀 함수 함수 내에서 자기 자신을 다시 호출하는 함수이다. 이 함수를 잘 사용하면 N번의 반복문을 보다 보기 쉽게 작성할 수 있다. 단, 다중 루프문을 사용한 것보다 복잡도가 줄어들지는 않을 수 있다. 재귀 함수는 잘 짜는게 중요한데, 항상 다음의 경우를 고려해야 한다. 조건에 맞지 않는 경우(불가능한 경우) 정답을 찾은 경우 재귀 호출을 하는 경우(다음의 경우를 실행하는 경우) 9095 1, 2, 3 더하기, 백준 온라인 저지 정수 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제. 주어진 N이 3일 경우, 1, 2, 3의 합으로 나타내는 방법은 아래의 표와 같다. N=4 1+1+1+1 1+1+2 1+2+1 1+1+2 2+1+1 2+2 1+3 3+1 이 때, Ngoal, 즉 합산 결과가 ..
2019.05.13 -
2-2. 순열
순열 1~N까지 이루어진 순열로, 크기는 항상 N이며 겹치는 숫자가 존재하지 않는다. 크기가 N인 순열은 총 N!개가 존재한다. 순열을 사전순으로 나열했을 때, 다음에 오는 순열과 이전에 오는 순열을 찾을 수 있다. N이 3인 경우 사전순으로 나열한 수열은 다음과 같다. 아래의 표에서 1번째 순열은 오름차순으로 정렬된 순열이 되며, 마지막 순열(6번째 순열)은 내림차순으로 정렬된 순열임을 알 수 있다. 순서 수열 1번째 순열 123 2번째 순열 132 3번째 순열 213 4번째 순열 231 5번째 순열 312 6번째 순열 321 다음 순열 10972 다음 순열, 백준 온라인 저지 위에서 정리한 내용을 토대로 다음에 오는 순열을 찾을 수 있다. A\[i-1\] < A\[i\]를 만족하는 가장 큰 i를 찾는..
2019.05.12 -
2-1. 브루트 포스(주먹구구식), N중 for문
Brute Force 브루트 포스는 모든 경우의 수를 계산해보는 방법이다. 단, 경우의 수를 계산하는 데 걸리는 시간이 주어진 문제의 시간 제한을 넘지 않아야 한다. Brute Force 방식으로 문제를 풀 때 가능한 경우의 수를 모두 계산해본다. 직접 계산을 통해서 구하며, 대부분 손으로 계산해볼 수 있다. 모든 방법을 찾는다. 대표적으로는 직접 계산하는 방법, 반복문 사용, 순열 사용, 재귀 호출, 비트마스크를 사용하여 직접 계산하는 방법이 있다. 각각의 방법을 이용해 답을 구해본다. 그리고 시간 제한을 초과하지 않는 방법을 찾는다. Brute Force 문제의 시간복잡도는 보통 O(경우의 수*방법 1개를 시도해보는데 걸리는 시간 복잡도)가 된다. 일곱 난쟁이 일곱 난쟁이, 백준 온라인 저지 아홉명의..
2019.05.07 -
1. 수학 / 최대공약수, 최소공배수, 소수
나머지(모듈러) 연산 나머지 연산이 중요한 이유는 C의 int, Java의 long long처럼 최대 크기가 제한되어있는 자료형이 주어졌을 때, 결과값이 너무 클 경우 해당 자료형에 들어가지 못하기 때문이다. 이럴 경우에 나머지 연산을 이용하여 몫을 구하라는 내용이 문제에 포함되게 된다. 아래의 규칙을 잘 알아두자. (A+B)%M = ((A%M)+(B+M))%M (AxB)%M = ((A%M)x(B+M))%M 위의 규칙은 나누기일 경우에는 성립하지 않는다. (A-B)%M = ((A%M)-(B%M)+M)%M 뺄셈의 경우에는 먼저 모듈러 연산을 한 결과가 음수일 수 있기 때문에, 위와같이 계산해야한다. 최대공약수(GCD) 일반적으로 최대공약수가 필요한 경우는 정답이 분수일 때, 기약분수의 형태로 나타낼 때이다..
2019.05.06