https://www.acmicpc.net/problem/2003



n이 10000 이하이고, 시간 제한이 0.5초이기 때문에, n^2 풀이로 풀게 되면 시간 초과가 날 것이다.


따라서 O(n)에 해결할 수 있도록 투포인터를 사용하도록 한다.



초기에 st와 en을 모두 시작점으로 정해두고, en이 범위 밖으로 벗어날 때까지 진행해준다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
 
using namespace std;
int n, m, arr[10001];
int main(void) {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
 
    int st = 0, en = 0, cnt = 0;
    long long Sum = arr[0];
 
    while (1) {
        //합이 부족해서 en이 우측으로 움직이는 건데, en이 밖으로 나갔다는 것은 더 볼 필요가 없다는 것
        //st가 우측으로 움직여봤자 합은 더 감소하기 때문에
        if (en >= n) break; 
        
        if (Sum == m) {
            Sum += arr[++en]; //딱 만족할 때 en 증가
            cnt++;
        }
 
        else if (Sum < m) Sum += arr[++en];
 
        else {
            
            Sum -= arr[st++];
            if (st > en) {
                en = st;
                Sum = arr[en];
            }
        }
    }
    cout << cnt;
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1339번: 단어 수학 (C++)  (0) 2019.08.29
백준 1644번: 소수의 연속합 (C++)  (0) 2019.08.29
백준 13458번: 시험 감독 (C++)  (0) 2019.08.29
백준 14500번: 테트로미노 (C++)  (0) 2019.08.29
백준 14503번: 로봇 청소기 (C++)  (0) 2019.08.28

An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

  • A[P] + A[Q] > A[R],
  • A[Q] + A[R] > A[P],
  • A[R] + A[P] > A[Q].

For example, consider array A such that:

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20

Triplet (0, 2, 4) is triangular.

Write a function:

int solution(vector<int> &A);

that, given an array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.

For example, given array A such that:

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20

the function should return 1, as explained above. Given array A such that:

A[0] = 10 A[1] = 50 A[2] = 5 A[3] = 1

the function should return 0.

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [0..100,000];
  • each element of array A is an integer within the range [−2,147,483,648..2,147,483,647]


문제는 위와 같다.


조건은 저렇게 위에 세 개의 부등식으로 나와있지만, 정렬을해서 확인하면 작은 두 원소의 합이 가장 큰 원소보다 크면 성립하게 된다.


오버플로우 방지를 위해 하나의 항을 이항해서 계산해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
#include <algorithm>
int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    if(A.size() < 3) return 0;
    sort(A.begin(), A.end());
    for(int i = 0 ; i <= A.size()-3 ; i++){
        if(A[i] > A[i+2]-A[i+1]) //오버플로우 방지
            return 1;
    }
    return 0;
}
 
cs


저작자표시 비영리 변경금지

https://www.acmicpc.net/problem/13458



총감독관은 무조건 1명은 존재해야 하기 때문에 기본적으로 답은 n부터 시작한다.


시험장마다의 인원보다 b가 크다면, 총감독관 혼자 커버할 수 있기 때문에 시험장 인원을 0으로 갱신해준다.


그렇지 않다면 시험장 인원에서 총감독관이 감시하고 있는 인원의 수인 b를 감소시켜준다.



다음으로 필요한 부감독관의 수를 계산한다. 1명이라도 부감독관이 감시할 수 있는 사람보다 수가 많으면 부감독관 한 명이 더 필요하기 때문에, 갱신한 시험장 인원을 c로 나눈 나머지가 0인지 아닌지에 따라서 부감독관의 인원을 정한다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<algorithm>
using namespace std;
int n, arr[1000001], b, c;
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) 
        cin >> arr[i];
    cin >> b >> c;
 
    for (int i = 0; i < n; i++) {
        if (arr[i] <= b) arr[i] = 0;
        else arr[i] -= b;
    }
    
    long long ans = n;
    
    for (int i = 0; i < n; i++) {
        if (arr[i] % c != 0) ans = ans + (arr[i] / c) + 1;
        else
            ans = ans +  (arr[i] / c);
    }
    cout << ans;
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1644번: 소수의 연속합 (C++)  (0) 2019.08.29
백준 2003번: 수들의 합 2 (C++)  (0) 2019.08.29
백준 14500번: 테트로미노 (C++)  (0) 2019.08.29
백준 14503번: 로봇 청소기 (C++)  (0) 2019.08.28
백준 14888번: 연산자 끼워넣기 (C++)  (0) 2019.08.27

https://www.acmicpc.net/problem/14500


이차원 배열로 주어지는 격자에서, 모든 테트로미노 모양을 다 넣어보면 된다.


주어지는 다섯개의 테트로미노를 회전 또는 대칭해서 얻을 수 있는 모양들까지 포함해서 계산해주면 된다.


가능한 모양은 총 19개이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<vector>
using namespace std;
int row, col, m[501][501];
int Max = -1;
 
//가능한 모양은 총 19개이다
vector<int> vr[19] = { { 1,2,3 },{ 0,0,0 },{ 0,1,1 },{ 1,2,2 },{ 0,0,-1 },{ 0,1,2 },{ -1,-1,-1 },{ 0,0,1 },{ -1,0,1 },{ -1,0,0 },{ 1,1,2 },{ 1,1,2 },
{ 0,-1,-1 },{ -1,-1,-2 },{ 0,1,1 },{ 0,-1,-2 },{ 1,1,1 },{ -1,-2,-2 },{ 0,0,1 } };
 
vector<int> vc[19] = { { 0,0,0 },{ 1,2,3 },{ 1,0,1 },{ 0,0,1 },{ 1,2,2 },{ 1,1,1 },{ 0,1,2 },{ 1, 2, 1 },
{ 1,1,1 },{ 1,1,2 },{ 0,1,0 },{ 0,1,1 },{ 1,1,2 },{ 0,1,1 },{ 1,1,2 },{ 1,1,1 } ,{ 0,1,2 } ,{ 0,0,1 } ,{ 1,2,2 } };
 
void calculate() {
    int cnt = 0;
    for (int con = 0; con < 19; con++) {
 
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int Sum = m[i][j];
                bool isBreak = false;
 
                for (int k = 0; k < 3; k++) {
                    int nr = i + vr[con][k];
                    int nc = j + vc[con][k];
                    if (nr < 0 || nc < 0 || nr >= row || nc >= col) {
                        isBreak = true;
                        break;
                    }
                    Sum += m[nr][nc];
 
                }
                if (!isBreak)
                    if (Sum > Max) Max = Sum;
            }
        }
    }
 
}
int main(void) {
    cin >> row >> col;
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            cin >> m[i][j];
 
    calculate();
    cout << Max << '\n';
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2003번: 수들의 합 2 (C++)  (0) 2019.08.29
백준 13458번: 시험 감독 (C++)  (0) 2019.08.29
백준 14503번: 로봇 청소기 (C++)  (0) 2019.08.28
백준 14888번: 연산자 끼워넣기 (C++)  (0) 2019.08.27
백준 11328번 Strfry (C++)  (0) 2019.08.25

삽입 정렬에 대해 정리해보자.


삽입 정렬은, 선택 정렬 그리고 버블 정렬과 함께 대표적인 시간 복잡도 O(n^2) 알고리즘이다.



하지만 삽입 정렬은, 필요할 때까지만 삽입(스왑)이 일어나기 때문에, 정렬할 배열이 거의 정렬되어 있는 상태라면 다른 선택 정렬, 버블 정렬보다 훨씬 빠른 속도를 보여준다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{   
 
    int a[10] = {-100, 10, 13, -5, 4, 12 , -5, 6, -1000, 2};
    
    int n = 10;
   
   //삽입 정렬 오름차순
   for(int i = 0 ; i < n - 1 ; i++){ //while문 내부 비교 구문에서, j와 j+1을 비교하기 때문에 n-2까지만 들어가도록
       int j = i;
       while(j >= 0 && a[j] > a[j + 1]){ //i의 앞쪽까지는 이미 정렬이 돼있다고 본다.
           swap(a[j], a[j + 1]); //따라서 swap이 일어나지 않으면 그 cycle의 정렬은 끝난 것
           j--;
       }
   }
    
    for(int i = 0 ; i < 10 ; i++)
        cout << a[i] << ' ';
 
    return 0;
}
cs


저작자표시 비영리 변경금지

'Computer Science > Algorithm Theory' 카테고리의 다른 글

C++ 알고리즘 체크리스트  (0) 2021.10.16
퀵, 머지, 힙 정렬 알고리즘 간단 정리  (0) 2019.10.06
버블 정렬 알고리즘 구현 (C++)  (0) 2019.08.28
선택 정렬 알고리즘 구현 (C++)  (0) 2019.08.28
Counting Sort (C++)  (0) 2019.08.23

버블 정렬 알고리즘에 대해 정리해보자.


이름에서도 알 수 있듯이, 하나의 원소와, 인접원소를 한 칸씩 움직이면서 비교해가는 모습이 거품이 생기는 것 같아서 버블 정렬이다.


굉장히 비효휼적인 알고리즘이고, 시간 복잡도가 O(n^2)이다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{   
 
    int a[10] = {-100, 10, 13, -5, 4, 12 , -5, 6, -1000, 2};
    
    //버블 정렬 오름차순
    for(int i = 0 ; i < 10 ; i++){
        for(int j = 1 ; j < 10 - i ; j++){ //한 번의 시행에 가장 끝 숫자 결정
            if(a[j-1] > a[j]) swap(a[j-1], a[j]);
        }
    }
    
    for(int i = 0 ; i < 10 ; i++)
        cout << a[i] << ' ';
 
    return 0;
}
cs


저작자표시 비영리 변경금지

'Computer Science > Algorithm Theory' 카테고리의 다른 글

퀵, 머지, 힙 정렬 알고리즘 간단 정리  (0) 2019.10.06
삽입 정렬 알고리즘 구현 (C++)  (0) 2019.08.28
선택 정렬 알고리즘 구현 (C++)  (0) 2019.08.28
Counting Sort (C++)  (0) 2019.08.23
최대 공약수 gcd, 최소 공배수 lcm  (0) 2019.08.19

가장 먼저 정리할 정렬 알고리즘은 선택 정렬(insertion sort) 알고리즘이다.


이름에서도 알 수 있듯이, 오름차순으로 정렬한다고 하면, 매 수행에서 가장 작은 값을 선택해서 가장 앞으로 보내는 것이다.


시간 복잡도는 O(n^2)이다.


다음은 특정 배열을 오름차순으로 정렬하는 코드이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
#include <iostream>
#include<algorithm>
using namespace std;
 
int main(){
 
    int a[5] = {1,4,-1,2,6}, idx;
    
    //선택 정렬
    for(int i = 0 ; i < 5 ; i++){
        int Min = a[i];
        for(int j = i+1 ; j < 5 ; j++){
            if(Min > a[j]){
                Min = a[j];
                idx = j;
            }
        }
        swap(a[i], a[idx]);
    }
    
    //결과 출력
    for(int i = 0 ; i < 5 ; i++)
        cout << a[i] << ' ';
    
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'Computer Science > Algorithm Theory' 카테고리의 다른 글

삽입 정렬 알고리즘 구현 (C++)  (0) 2019.08.28
버블 정렬 알고리즘 구현 (C++)  (0) 2019.08.28
Counting Sort (C++)  (0) 2019.08.23
최대 공약수 gcd, 최소 공배수 lcm  (0) 2019.08.19
기하 및 그래프 알고리즘 간단 정리  (0) 2019.08.17

파이썬의 bs4 그리고 requests를 활용해서 크롤링을 할 때에, 한글 인코딩 문제로 아래와 같은 에러가 발생할 수 있다.



본인은 conda 가상 환경에서 python 3.6 버전을 이용해서 cgv의 상영 시간표를 크롤링하다가 이러한 에러를 만났다.



UnicodeEncodeError: 'cp949' codec can't encode character '\xa0' in position 162673: illegal multibyte sequence



인코딩과 관련된 문제는 대부분 한글과 관련해서 발생하는 문제이다.



코드 상단에 아래와 같은 코드를 추가해주면 해결할 수 있다.


1
2
3
4
import sys
import io
sys.stdout = io.TextIOWrapper(sys.stdout.detach(), encoding = 'utf-8')
sys.stderr = io.TextIOWrapper(sys.stderr.detach(), encoding = 'utf-8')

cs


저작자표시 비영리 변경금지

'Programming Language > Python' 카테고리의 다른 글

tkinter를 활용한 간단한 GUI 프로그램  (0) 2019.08.27
python 데이터 타입, 자료형 및 기본적인 내용  (0) 2019.08.26

https://www.acmicpc.net/problem/14503



로봇의 위치와 방향을 관리하며 bfs를 돌려주면 된다. 모든 순간에 로봇은 하나이기 때문에 큐에는 최대 하나의 좌표(로봇의 좌표)만 들어갈 수 있다.




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
struct Robot {
    int r, c;
}bot;
int dir;
int row, col, m[51][51];
bool vis[51][51];
queue<Robot> q;
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };
int cnt = 1;
pii getBackPos(int r, int c, int dir) {
    if (dir == 0)
        return { r + 1, c };
    else if (dir == 1)
        return { r, c - 1 };
    else if (dir == 2)
        return { r - 1, c };
    else
        return { r, c + 1 };
}
void bfs(Robot bot) {
    q.push(bot);
    vis[bot.r][bot.c] = true; // 로봇 시작 위치 청소
    while (!q.empty()) {
        Robot cur = q.front();
        q.pop();
        //int doneCnt = 0;
        bool goBack = true;
        for (int i = 0; i < 4; i++) {
            dir = (dir + 3) % 4;
            int nr = cur.r + dr[dir];
            int nc = cur.c + dc[dir];
            if (nr < 0 || nc < 0 || nr >= row || nc >= col || vis[nr][nc] !=0 || m[nr][nc] != 0) {
                //doneCnt++;
                continue;
            }
 
            else {
                //printf("%d, %d 방향 %d에서 %d, %d 방향 %d로 이동\n", cur.r, cur.c, cur.dir, nr, nc, (cur.dir+3)%4);
                q.push({ nr, nc });
                vis[nr][nc] = true;
                cnt++;
                goBack = false;
                break;
            }
        }
        //if (doneCnt == 4) {
        if(goBack){
            //dir = (dir + 1) % 4;
            //printf("%d %d 방향 %d 상태에서 후진시도\n", cur.r, cur.c, cur.dir);
            pii tmp = getBackPos(cur.r, cur.c, dir);
            if (tmp.first < 0 || tmp.second < 0 || tmp.first >= row || tmp.second >= col
                 || m[tmp.first][tmp.second] == 1)
                return;
 
            //후진 가능한경우
            else {
                q.push({ tmp.first, tmp.second});
                
            }
    
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> row >> col;
    cin >> bot.r >> bot.c >> dir;
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            cin >> m[i][j];
    
    bfs(bot);
    
    cout << cnt;
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 13458번: 시험 감독 (C++)  (0) 2019.08.29
백준 14500번: 테트로미노 (C++)  (0) 2019.08.29
백준 14888번: 연산자 끼워넣기 (C++)  (0) 2019.08.27
백준 11328번 Strfry (C++)  (0) 2019.08.25
백준 11722번 가장 긴 감소하는 부분 순열 (C++)  (0) 2019.08.25

https://www.acmicpc.net/problem/14888


두가지를 생각해주면 된다.


1. + + - - * 이런 상황처럼 같은 연산자가 중복해서 들어가는 경우를 생각해서 연산자를 뽑아야한다.

순열로 뽑아야하므로 같은 것이 포함된 순열을 구현해주면 된다.


2. 연산자 우선순위가 없기 때문에, 단순히 숫자와 연산자를 분리해서 배열에 담은 뒤에, 하나씩 빼서 계산해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<vector>
#include<set>
using namespace std;
 
vector<int> oprV; //뽑힐 수 있는 연산자들
vector<int> v; //뽑힌 연산자들 저장
set<vector<int> > st;
int n, num[12], oprCnt[4];
bool isused[12];
 
int calc(int a, int opr, int b) {
    if (opr == 0) return a + b;
    else if (opr == 1) return a - b;
    else if (opr == 2) return a * b;
    else if (opr == 3) return a / b; 
}
void func(int k) {
 
    if (k == n - 1) {
        st.insert(v); //set으로 중복 제거
        return;
    }
    
    for (int i = 0; i < n - 1; i++) {
        if (!isused[i]) {
            v[k] = oprV[i];
            isused[i] = true;
            func(k + 1);
            isused[i] = false;
        }
    }
}
int main(void) {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> num[i];
 
    for (int i = 0; i < 4; i++) {
        cin >> oprCnt[i];
        while (oprCnt[i]--) { // + - * /    0 1 2 3 
            oprV.push_back(i);
            v.push_back(0);
        }
    }
 
    func(0);
 
    //중복 제거 하고 연산자 뽑은 결과
    int mx = -1111111111;
    int mn = 1111111111;
 
    for (set<vector<int> >::iterator itr = st.begin(); itr != st.end(); itr++) {
        vector<int> tmp = *itr;
        int res = num[0];
 
        for (int i = 0; i < tmp.size(); i++) 
            res = calc(res, tmp[i], num[i + 1]);
        
        if (res < mn) mn = res;
        if (res > mx) mx = res;
    }
    cout << mx << '\n' << mn << '\n';
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 14500번: 테트로미노 (C++)  (0) 2019.08.29
백준 14503번: 로봇 청소기 (C++)  (0) 2019.08.28
백준 11328번 Strfry (C++)  (0) 2019.08.25
백준 11722번 가장 긴 감소하는 부분 순열 (C++)  (0) 2019.08.25
백준 13300번 방 배정 (C++)  (0) 2019.08.25

+ Recent posts

티스토리툴바