로재의 개발 일기 로재의 개발 일기

순열을 사용하여 조합을 만들어내는 방법입니다. 로직을 설명하면 vector 를 2개를 선언하고 하나는 원소를 삽입하는 vector list를 또 다른 하나는 순서 제어를 위해서 next_permutation을 사용할 vector idx를 만듭니다. 이어서 몇 개의 원소를 뽑을지 결정하는 변수 r 만큼 idx에 1을 list의 크기 (n이라고 하겠습니다) - r 만큼 idx에 0을 넣습니다. 그 뒤로 idx를 next_permutation을 사용하여 반복하여 idx의 원소가 1일 때마다 list의 원소를 출력해주면 됩니다. 저는 내림차순으로 출력하기 위해서 desc라는 함수를 따로 작성하였습니다. 소스코드 12345678910111213141516171819202122232425262728293031323..

삽입 정렬은 배열을 그룹을 두 개로 나누어 E = {5,4,3,2,1} 이 있다고 하면 {5}를 key로 두고, 이보다 작은 index을 확인하여, 삽입하는 정렬 방법이다. 그 다음의 key는 4... 3.. 2 .. 1 순이다. 아래 소스에서는 j를 유심히 잘 봐야 한다. #include using namespace std; int main(){ int size,i,j; cin >> size; int *arr = new int[size]; for(i = 0; i > arr[i]; for(i = 0; i = 0; j--){ if(key >= arr[j]) break; arr[j+1] = ..

버블 정렬은 인접한 원소들을 교환하며, 이 모습이 흡사 거품들이 뾰로록 일어나는 것과 같다고 하여, Bubble Sort라고 불립니다. (교환 정렬이라고도 불립니다. Exchange Sort) ...더보기 이해 E[5] = {95, 75, 85, 100, 75}이며 이를 오름차순으로 정렬한다면. (95, 75), 85, 100, 50 => 75, 95, 85, 100, 50 75, (95, 85), 100, 50 => 75, 85, 95, 100, 50 75, 85, (95, 100), 50 => 75, 85, 95, 100, 50 75, 85, 95, (100, 50) => 75, 85, 95, 50, 100 자, 여기에서 마지막 요소가 배열의 최댓값으로 들어갔습니다. (75, 85), 95, 50, ..

간단하게 말해서, 선택 정렬은 입력된 값 중 원소를 선택하여 정렬하는 방식이다. ...더보기 이해 (원소1), (원소 2), 원소 3, 원소 4, 원소 5 (원소 1), 원소 2, (원소 3), 원소 4, 원소 5 ...... (원소 1), 원소 2, 원소 3, 원소 4, (원소 5) 까지 비교하여 원소 1에 최소 값이 들어갔으므로(오름차순이라면) 이제는 index 1부터 정렬을 시작하여 원소 1, (원소 2), (원소 3), 원소 4, 원소 5 ... 원소 1, (원소 2), 원소 3, 원소 4, (원소 5) 까지 비교하는 하는 방식이다. 최종적으로는 원소 1, 원소 2, 원소 3, (원소 4), (원소 5) 를 비교하게 된다. #include using namespace std; int main(){..

C++의 STL에서 vector 사용시, pair container와 함께 쓰이고는 하는데,이때, x좌표 오름차순 혹은 y좌표 오름차순으로 나타내고자 할때, sort의 세번째 인자로사용자 함수 bool compare를 작성하여, 사용하기도 한다. 1234567891011121314151617181920212223242526272829#include#include#include using namespace std; bool sortbyfirst(const pair &a, const pair &b) { return (a.first > n; // 입력 횟수 vectorv; while(n--){ int x,y; cin >> x >> y; v.push_back(make_pair(x,y)); } sort(v.beg..

1차원 동적 배열을 생성하기 위해서는자바에서 배열을 생성할 때와 비슷하게 생성하면 됩니다.123456789101112131415161718#include using namespace std; int main(){ int n; cin >> n; int *list = new int[n]; for(int i = 0; i > list[i]; for(int i = 0; i

Bitmask란 비트위에 마스크를 씌우는 방식을 통해서어떤 위치에 집합의 원소가 존재하는지 아닌지, 추가하는 등의 행위를 말합니다. 주로 이를 마스크와 같다고 하여, 비트마스크라고 말합니다. 간단한 예시를 들자면, 네가지 원소를 가질 수 있는 집합이 있습니다. 우리는 이를 {1,2,3,4}로 나타낼 수 있습니다. 이 집합을 보다 효율적이고 간결하며 가독성있게 나타낼 수 있는 것이, 바로 비트표기이며 우리는 이를 1111(2)로 나타낼 수 있습니다. (오른쪽부터 원소 1입니다) 이 집합의 원소 중, 세번째 원소가 존재하는 지 확인하고자 한다면, 우리는 마스크를 씌울 수 있는데 이것이 비트마스크입니다. 1111(2) & 0100(2) => 0100(2) > 0 으로 세번째 원소가 존재하게 됨을 알 수 있습니..

next_permutation => 직역하자면, 다음 수열이라는 의미입니다. STL에서 제공하는 함수이며 vector, 배열로 구현이 가능합니다. // 사전 순으로 정렬 1 3 4 2 의 다음 수열은 1 4 2 3 이 됩니다.이때 1 4 2 3 을 만들기 위해서 4가지 단계를 거치는데 1. 어디까지가 감소 수열인가 찾기.1 3 4 2 (감소 수열 4 2) 이떄 i = 2 2. i-1보다 작거나 같으며, 가장 뒤에 있는 수 j 를 찾기1 3 4 2 (2보다 작으며, 가장 앞에 있는 수를 찾습니다)이때 j = 3 (2를 가르킵니다)의 이전 인덱스 j = 2( 4를 가르킵니다) 3. 그 둘을 Swap 시킵니다.1 4 3 2 4. i -1 이후로 뒤집습니다.1 4 2 3 1234567891011121314151..