본문 바로가기

Archived(CSE Programming)/알고리즘(C++)

 (55)
브루트포스-N과 M 1. N과 M 문제 참고 : https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 풀이 #include #include #include using namespace std; void make_nm(int, int, int); vector a; vector c; int main() { int m, n; cin >> n >> m; //입력받기 a.assign(10, 0); // 할당 c.assign(10, false); // 할당 make_n..
비트마스크(BitMask) 비트마스크에 공부하기 앞서 기본적인 비트연산에 대해 알아야 한다. 비트연산이랑 &(AND), |(OR), ^(XOR), ~(NOT), (Shift Right) 로 이루어진 bit 간의 연산을 수행하는 것이다. 해당 연산들을 통해 비트마스크를 이용할 수 있는데, 비트마스크란 쉽게 말해 정수로 집합을 나타낼 수 있는 것이다. 570 = 1000111010 = 2^9 + 2^5 + 2^4 + 2^3 + 2^1 으로 나타내서 1,3,4,5,9의 부분집합을 뜻하는 것이다. 배열보다 정수(비트마스크)로 쓰면 공간적인 장점, 다른 배열에 넣을 수 있는 점. 0~N-1 의 정수로 이루어진 집합을 나타낼 수 있다. (1~N 을 쓰려면 2배의 수가 필요 -> 따라서 줄여서 쓰기) 비트마스크 연산 S & (1
재귀함수(Recursive Function) 재귀함수는 기본적으로 반복적으로 함수를 호출해서 많은 메모리를 차지하면서 함수 stack을 통해 메모리에 부담을 주는 것으로 알려져있다. 그럼에도 불구하고 재귀함수를 사용하는 이유는 명확하다. 알고리즘 자체가 재귀적으로 표현이 더욱 쉬울 때가 존재한다. 예를 들어 팩토리얼을 구하는 공식을 살펴보면 다음과 같다. 해당 공식을 보면 n! = (n-1)! * n (n>0) 이 부분 자체가 재귀함수의 형태와 매우 닮아있다. 그래서 몇몇 알고리즘을 계산하는데 있어, 재귀함수가 유용할 때가 존재한다. 재귀함수를 사용할 때 주의해야할 3가지가 있다. 1) 종료조건(실패조건) : 재귀함수 호출 중 조건에 벗어나 그만 호출해야할 때 2) 종료조건(성공조건) : 재귀함수 호출 중 조건을 만족한 답을 구해서 그만 호출해야 ..
순열(Permutation) 구하기 수학에서, 순열(順列, 문화어: 차례무이, 영어: permutation 퍼뮤테이션[*]) 또는 치환(置換)은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 다시 말해, 순열은 숫자 배열의 순서를 뒤섞는 연산이다. 예를 들어 1,2,3 세 숫자 순열은 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 다음과 같이 나열된다. 이러한 순열의 특징 중 하나는 특정 기준점 다음의 오름차순 정렬에서 기준점 다음으로 오는 가장 작은 숫자와 위치를 교환한 후 내림 차순 정렬로 바뀐다. 이러한 특징을 살려, 순열들을 차례로 구하여 값을 구할 수 있다. 1. A[i-1] A[i-1] 를 만족하는 가장 큰 j를 찾는다 3. A[i-1]과 A[j]를 swap 한다 4. A[i]부터 순열을 뒤집는다 ..
브루트 포스(Brute Force) 브루트 포스의 의미는 모든 경우의 수를 다 구해서 문제를 해결하는 것이다. 이러한 브루트 포스의 핵심을 요약하자면 다음과 같다. • 브루트 포스로 문제를 풀기 위해서는 다음과 같은 3가지 단계를 생각해볼 수 있다. 1. 문제의 가능한 경우의 수를 계산해본다. • 직접 계산을 통해서 구한다. 대부분 손으로 계산해볼 수 있다. 2. 가능한 모든 방법을 다 만들어본다. • 하나도 빠짐 없이 만들어야 한다. • 대표적으로 그냥 다 해보는 방법, for문 사용, 순열 사용, 재귀 호출 사용, 비트마스크 사용이 있다. 3. 각각의 방법을 이용해 답을 구해본다. • 이 단계는 보통은 어렵지 않다. 문제에 나와있는 대로 답을 계산해본다. • 브루트 포스 문제의 시간 복잡도는 대부분 O(경우의 수 *방법 1개를 시도해보..
에라토스테네스의 체(소수 구하기) 소수(Prime)는 소수(素數, 발음: [소쑤], 문화어: 씨수, 영어: prime number)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 예를 들어, 5는 1x5 또는 5x1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자(2×3)의 곱이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다. 합성수 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 합성수(合成數, Composite Number)는 1과 자기 자신이 아닌 다른 자연수의 곱으로 나타낼 수 있는 자연수를 의..
최대공약수(GCD) & 최소공배수(LCM) 구하기 최대공약수와 최소공배수는 수학의 기본적인 내용이다. 최대공약수는 말 뜻 그대로, 두 수의 공통적인 약수 중 최대로 큰 약수이다. 최소공배수 또한, 두 수의 공톡적인 배수는 최소로 작은 배수이다. 이러한 최대공약수와 최소공배수를 구하는 방식에 대해 살펴보자. 1. 최대공약수 먼저 최대공약수의 경우, 일일이 약수를 구해서 공통되는 약수 중 가장 큰 약수를 찾는 법이 있지만, 보다 효율적으로 유클리드 호제법을 사용하면 된다. 다음의 과정을 거치면 되는데, 이를 코드로 표현하면 다음과 같다. // 최대공약수 int gcd(int a, int b) { if (b == 0) return a; else { gcd(b, a%b); } } 생각보다 간단하다. 2. 최소공배수 최소공배수 또한 어렵지 않다. 최대공약수를 구..

티스토리툴바