10804. https://www.acmicpc.net/problem/10804 10804번: 카드 역배치 1부터 20까지 오름차순으로 놓인 카드들에 대해, 입력으로 주어진 10개의 구간 순서대로 뒤집는 작업을 했을 때 마지막 카드들의 배치를 한 줄에 출력한다. www.acmicpc.net [풀이] 배열 혹은 문자열의 내부 요소를 뒤집는 STL지원 함수 reverse()를 사용하면 된다. 배열에서는 reverse(a, a+5) 와 같이 사용하면 되고 문자열에서는 reverse(a.begin(), a.begin + 5) 와 같이 사용하면 된다. #include using namespace std; int card[20]; int a,b; int main(){ ios::sync_with_stdio(0); c..
c++
2309. 조합 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net [풀이] 순열, 조합 문제이며 세 가지 풀이가 있다. 첫 번째로, 직관적으로 9명 중 7명을 선택하는 조합 문제로 해결할 수 있다. 조합 문제는 크게 이중 for문, 재귀함수 두 가지 방법으로 풀 수 있는데 9C7은 9C2이므로 이중 for문으로 조합을 구현하는 것이 가장 쉽다. ( 3중까지는 중첩 for문으로 작성하는 것이 좋다. ) #include using namespace std; ..
1. push_front(value) list a = {1,2,3}; a.push_front(9); [결과] a is 9 1 2 3 2. push_back(value) list a = {1,2}; a.push_back(1); [결과] a is 1 2 1 3. insert(idx, value) list a = {1,2,3,4}; auto it = a.begin(); it++; a.insert(it ,10); [결과] a is 1 100 2 3 4 4. erase(idx) erase()는 iterator를 반환하기 때문에 iterator it 를 계속 사용하려면 반환받아야 한다. iterator를 반환받지 않고 동일한 iterator를 사용하면 런타임에러가 발생한다. // 1. 반환받지 않은 경우 list ..
순열과 조합은 이미 중고등학교 때 배운 개념일텐데, 코딩테스트를 준비할 때에도 중요한 개념이다. 순서에 상관 있게 뽑는 것을 순열 순서에 상관 없이 뽑는 것을 조합 이라고 한다. 예를 들어, {1,2,3} 에서 3개를 순열로 뽑으면 3P3으로 {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1} 여섯 가지(3!), 3개를 조합으로 뽑으면 3C3으로 {1,2,3} 한 가지이다. 순열 1. STL next_permutation c++에서는 next_permutation() 함수를 제공하는데, 이는 오름차순을 기준으로 정렬된 배열을 순열로 만든다. 반드시 오름차순 정렬되어 있어야 한다. next_permutation()의 매개변수(parameters)는 순열을 시작할 ..
array, vector의 가장 큰 요소의 주소를 추출하는 함수 max_element 이다. 반환형이 이터레이터이기 때문에 값을 끄집어내기 위해 에스터리스크 *을 사용해야 하고, begin() 값과의 차를 통해 인덱스를 끄집어낼 수도 있다. 예시 코드로 확인하자. #include using namespace std; int main() { vector v {1,2,3}; int max = *max_element(v.begin(), v.end()); auto max_idx = max_element(v.begin(), v.end()) - v.begin(); cout
array, vector 의 합을 구해주는 함수로 std::accumulate() 가 있다. 파이썬의 sum과 같다고 보면 된다. parameter는 accumulate (first, last, initial value) 로 사용하면 되는데, initial value는 sum의 초기값으로 항상 정해주어야 한다. 사용 예시를 아래 코드를 보자. 배열의 합을 구할 때는 sum의 초기값을 1로 정해주었다. #include using namespace std; int main() { vector v {1,2,3}; int v2[3] = {1,2,3}; cout T accumulate( InputIt first, InputIt last, T init ); (until C++20) template< class In..
unique 는 범위 안에 있는 요소 중 앞에서부터 서로를 비교해가며 중복되는 요소를 제거하고 나머지 요소들은 삭제하지 않고 그대로 두는 함수이다. O(n)의 시간복잡도를 가진다. 중복되는 요소를 제거하고 나머지 요소들을 그대로 둔다는 게 어떤 말인지 감이 안오는데 아래 코드와 결과값을 보자. #include using namespace std; int main() { vector v {1,1,2,2,3,3,2,2,4,4,5,5}; unique(v.begin(), v.end()); for (int i : v) cout
sort() 는 배열 등 컨테이너들의 요소를 정렬하는 함수이다. 보통 array나 vector를 정렬할 때 쓰이며 O(nlogn)의 시간복잡도를 가진다. sort()의 parameter는 3가지인데 이 중 2개는 필수로 넣어야한다. 즉 sort() 함수는 두 가지 형태로 오버로딩 되어 있다. template void sort(T start, T end); template void sort(T start, T end, Compare comp); 또한 범위는 [first, last) 이다. 즉 크기가 5인 배열을 sort하고 싶다면 sort(a, a+5) 라고 하면 된다. 구체적인 사용 예시는 아래 코드를 확인하자. #include using namespace std; int main() { int a[5]..
배열을 복사할 때 for loop, memcpy(), copy() 등 여러가지 방법이 존재한다. 그 중 copy() 함수를 통해 array와 vector에서 깊은 복사를 할 수 있기 때문에 copy()에 대해 정리해보려 한다. 다음은 벡터 origin을 target에 copy() 하는 코드이다. #include using namespace std; int main() { vector origin = {0, 1, 2}; vector target(3); copy(origin.begin(), origin.end(), target.begin()); for (int i:origin) cout
배열을 초기화할 때 int a[10] = {0, }; 과 같이 초기화하기도 하고 fill() 이나 memset() 을 사용하기도 한다. 위 방법들의 사용법, 장단점을 정리해보자. 1. std::fill() fill()은 O(n)의 시간복잡도를 가지며 fill (first, last, val) 으로 초기화한다. 모든 값으로 초기화 가능하며 [first, last)까지 val로 초기화된다. 일부 값만 초기화할 수도 있긴하다. 아래 코드는 배열 a[10], b[10][10] 의 모든 값을 0으로 초기화하는 과정이다. int a[10]; int b[10][10]; fill(&a[0], &a[10], 0); fill(&b[0][0], &b[9][10], 0); a[10] = { 0, 0, 0, 0, 0, 0, 0..
