[C++] 삼성 SW 역량 테스트 보기 전 알고리즘 정리

1. 입출력 시간 단축

ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

• C++ 표준 스트림과 C 표준 스트림의 동기화를 끈다
• endl 대신 "\n"을 사용하기

 

2. 순열 (next_permutation)

• 서로 다른 n개의 원소에서 r개를 뽑는다
• 순서가 다르면 다른 경우로 판단
• algorithm 헤더의 next_permutation 함수를 사용
  • 오름차순으로 정렬된 값을 가진 컨테이너에만 사용 가능
  • 오름차순으로 순열 생성

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<int> v{ 1, 2, 3 };

    sort(v.begin(), v.end());

    do {
        for (auto i = v.begin(); i != v.end(); i++)
        {
            cout << *i << " ";
        }
        cout << "\n";
    } while (next_permutation(v.begin(), v.end()));

    return 0;
}

 

3. 순열을 이용한 조합 구하기

배열 arr에서 n개의 원소 중 r개의 원소를 택하는 방법은 아래와 같다.

 

1. r개의 원소는 1, (n-r)개의 원소는 0인 배열 temp를 만든다.
2. temp의 모든 순열을 구한다
3. temp의 순열에서 원소가 1인 인덱스만 arr에서 가져온다.

 

next_permutation이 오름차순으로 정렬되기 때문에 조합은 내림차순으로 정렬된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<int> v { 1, 2, 3, 4, 5 };
    vector<int> temp{ 0, 0, 0, 1, 1 };

    sort(v.begin(), v.end());

    do {
        for (int i = 0; i < v.size(); i++)
        {
            if (temp[i] == 1) cout << v[i] << " ";
        }
        cout << "\n";
    } while (next_permutation(temp.begin(), temp.end()));

    return 0;
}

 

4. 2차원 배열의 나선형 알고리즘

• 홀수 길이의 2차원 배열의 중심에서 시작하여 방향을 바꾸며 이동
• 방향을 2번 바꿀 때마다 이동 거리가 1씩 증가한다

 

5. 배열 회전

• 배열 전체를 90도 회전
  • 시계 방향: board[c][n-1-r] = board[r][c]
  • 반시계 방향: board[n-1-c][r] = board[r][c]