전체 글
-
[백준 11723] 집합알고리즘/백준 2019. 3. 16. 23:42
다른 방법을 사용하여 충분히 풀 수 있지만, 비트마스크를 사용하여 풀 수 있습니다. 비트마스크란? 참고하면 좋은 글 : https://redcoder.tistory.com/11 출처 : https://www.acmicpc.net/problem/11723 문제 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.check x: S에 x가 있으면 1을, 없으면 0을 출력한다.toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)al..
-
[백준 10974] 전체 수열알고리즘/백준 2019. 3. 16. 23:32
STL을 사용하지 않고 푸는 것이 목적이였기 때문에, 직접 next_premutation을 구현하였다.생각보다 까다로운 것, 다음에 기억할 수 있을까? 출처 : https://www.acmicpc.net/problem/10974 문제 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 출력 첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.예제 입력 1 3 예제 출력 1 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 1234567891011121314151617181920212223242526272829303132333435363738394041#include using ..
-
[백준 10972] 다음 수열알고리즘/백준 2019. 3. 16. 23:27
사실 STL을 사용하면 매우 쉽게 풀 수 있는 문제이지만, 직접 구현을 하거나 STL에 구현이 되어 있다는 것을 모르면, 귀찮아지는 문제이다.배열의 인덱스 가지고 재미있게 코딩할 수 있다는 점이 상당히 놀랍다.참고하면 좋은 글 : https://redcoder.tistory.com/7 출처: https://www.acmicpc.net/problem/10972 문제1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.1, 2, 31, 3, 22, 1, 32, 3, 13, ..
-
[C++] [Algorithm] C++에서 next_permutation 함수( prev_permutation 함수)를 통해서 순열 구하기C_C++ 프로그래밍/C_C++ 프로그래밍 2019. 3. 16. 23:20
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..