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


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


굉장히 비효휼적인 알고리즘이고, 시간 복잡도가 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

티스토리툴바