settpark / algorithm Goto Github PK

View Code? Open in Web Editor NEW

0.0 0.0 0.0 205 KB

C++ 67.68% C 1.84% Swift 30.48%

algorithm's People

Contributors

Watchers

algorithm's Issues

[C++] BOJ 2178 (행렬의 이해)

행렬을 탐색할 때는 상,하가 x, 좌,우가 y이다.

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

for (int dir = 0; dir<4; dir++) {
    int nx = cur.first + dx[dir];
    int ny = cur.second + dy[dir];

    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
    if (board[nx][ny] != '1' || dis[nx][ny] != -1) continue;
    Q.push({nx, ny});
    dis[nx][ny] = dis[cur.first][cur.second] + 1;
}

위의 코드와 같이 BFS 탐색이 진행 되는데, for문을 처음 돌 때, 현재 위치에서 (1,0)을 증가시킨다. 아래로 한칸 이동하겠다는 뜻이다.
위의 코드는 아래, 오른쪽, 위쪽, 왼쪽 순으로 탐색한다.

ios::sync_with_stdio(0);
cin.tie(0); 로 시간 초과가 나서 복습합니다.
사실 이거 쓰라고 해도 그냥 안 쓰는 경우가 많았는 데, 써야할 필요성을 느꼈습니다.
ios::sync_with_stdio(0); = printf와 cout은 각각의 스트림을 가지고 있는 데, 이를 동기화하는 과정, 이 키워드를 사용하면 두 함수를 섞어서 사용하면 안된다.
cin.tie(0); = cin을 하기전 무조건 cout을 버퍼를 비우고 시작하는 데, 이를 처리하지 않는 코드이다.
ex)

cout << "Enter name;"
cin >> name;

cin.tie(0)를 하게 되면 cout을 flush 하지 않기 때문에, "Enter name"을 출력하지 않고 cin을 처리합니다.
(cout의 버퍼가 가득 차거나 수동으로 flush 해야합니다.)

[C++] BOJ1406, LinkedList

연결리스트에서 연결리스트 삭제 시 유의점

    list<char> LL;
    auto t = LL.begin();

    LL.erase(t); // 이 부분과 같이 삭제를 진행하면 안됨. t는 여전히 삭제된 부분을 가리키고 있음
    t = LL.erase(t); // 이 부분과 같이 삭제 후 t를 갱신하여야 합니다.

삽입 시 주의점

    list<char> LL;
    auto t = LL.end();
    LL.insert(t, 0); // t의 **앞에** 0을 삽입하겠다는 의미입니다.

[C++] BOJ15649 (back tracking)

그래프의 DFS의 개념을 포함하는 듯 하다.
게임의 선택지에서 선택하고 진행하다가 잘못됨을 감지하면 선택하는 부분을 다시 로드해서 게임을 또 진행하는 그런 느낌!

주석을 달아놓은 코드를 보면서 이해하는 게 가장 빠를 듯!

#include <bits/stdc++.h>
using namespace std;

int n, m;
int arr[10]; //선택한 숫자를 담을 배열
bool isused[10]; // 탐색했는지 확인할 배열

void func(int k) {
	if(k == m) { //base condition
		for(int i = 0 ; i<m; i++) {
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}

	for(int i = 1; i<=n; i++) {
		if(!isused[i]) { // arr[i]를 순서대로 채우다가 채워지지 않은 부분이 발견되었을 때,
			arr[k] = i; // i의 값, 처음에 n으로 입력한 limit값에 기반하여 For문으로 넣음
			isused[i] = 1; // 사용했다는 표시를 해줌
			func(k+1); // 계속 파고 들어가면서 모두 탐색하고 함수 빠져 나오면 
			isused[i] = 0; //이슈의 [i]를 false 해줌, 새로 넣기 위해
			//k+1 .. k+1.. 들어갈 때마다 isused를 true하고 false하고를 반복할 거임.
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	func(0);
}

C++ BOJ7576 (BFS 응용)

저번에와 같이 잘못했던 방식으로 cnt를 두고 cnt++; 지속하고 cnt 값을 반환하면 되겠다 했는데,
마찬가지로 단방향이 아닌 경우에 같은 날 익은 토마토가 다른 날 익은 것처럼 처리되기 때문에, 답이 산으로 가버림
결국 마지막에 익은 토마토 (가장 익는데 오래 걸린 토마토를 찾으면 전부 토마토가 익은 것이기 떄문에 거리 구하기랑 똑같다.)

for (int i = 0; i<n; i++) {
    for (int j = 0; j<m; j++) {
        cin >> board[i][j];
        if (board[i][j] == 1)
            Q.push({i,j});
        if (board[i][j] == 0)
            vis[i][j] = -1;
    }
}

그리고 위의 코드와 같이 제일 처음에 초기화 할 때, board[i][j]가 0일 때만 vis[i][j]를 -1로 초기화 해줌으로써,
나중에 탐색할 때 >= 0 조건을 걸어서 익을 수 없는 토마토를 거를 수 있다.

그리고 행렬 자꾸 헷갈리는데 가로길이가 m 세로길이가 n으로 주어지면 행렬을 탐색할 땐 아래와 같이 해야 한다.

for (int i = 0; i<n; i++) {
    for (int j =0; j<m; j++) {
        if (vis[i][j] == -1) {
            cout << -1;
            return;
        }
        ans = max(vis[i][j], ans);
    }
}

[C++] BOJ11729 {Recursive} (Tower of Hanoi)

수학적 귀납법에 대한 정의

a = k일때 성립함을 가정
a = k+1일때 도 성립함을 증명
2,3의 결과로 모든 경우에 대해 성립함을 증명하는 방법

hanoi에 적용

1개의 원판을 a에서 b로 옮길 수 있다 // base condition
n-1개의 원판을 a부터 원하는 곳으로 옮길 수 있다. // 가정
n개의 원판을 a부터 원하는 곳으로 옮길 수 있다. // 성립

void BOJ11729::hanoi(int a, int b, int n) { // n개의 원판을 원하는 곳으로 옮긴다.
    if (n == 1) {  // base condition;
        cout << a << ' ' << b << '\n';
        return;
    }
    hanoi(a, 6-a-b, n-1); // n-1개를 빈곳으로 옮긴다.
    cout << a << ' ' << b << '\n';
    hanoi(6-a-b, b, n-1); // 빈 곳에서 목적지로 n-1개를 옮긴다.
}

아직 아리송하지만 오늘은 어제에 비해 좀 많이 이해했다.

[C++] BOJ10828 (스택의 구현)

BOJ10828
구현은 크게 어렵지 않았으나, 문제의 조건들이 많아 구현안한 부분이 있었음

    else //top
    {
        if(St.empty()) 
            cout << -1 << '\n'; //이 부분을 구현을 안해서 틀렸음
        else 
            cout << St.top() << '\n';
        
    }

stack 구현에 주의사항으로는 top(), pop()을 할 때 꼭 empty 를 통해 비어있는지 확인할 것!
비어있는 데 top(), pop()을 실행할 경우, 런타임 에러가 발생할 수 있음.

[C++] BOJ10866(Deque)

Deque 구현시 유의사항

tail이 항상 뒤에 있기 때문에 size를 절대값으로 반환하거나, tail - head로 접근한다.

    else if (s == "size") {
        cout << tail - head << '\n';
    }

아래의 else if문 내의 else문을 삽입하지 않아 항상 tail--가 실행 돼서 틀렸다.

    else if (s == "pop_back") {
        if (tail - head == 0)
            cout << -1 << '\n';
        else {
            cout << arr[tail-1] << '\n';
            tail--;
        }
    }

위의 코드에서 push_back할때는 값을 추가하고 tail을 증가하기 때문에 값에 접근할 때는 tail-1로 접근하여야 한다.
반대로, push_front의 경우 head를 먼저 이동시키고 값을 추가하기 때문에 arr[head]로 값에 접근해도 된다.
push_front, push_back을 다르게 구현한 이유는 같은 방식으로 구현하면 제일 처음에 같은 인덱스에 값이 들어가거나,
초기화 해놓은 처음 인덱스에 값이 비어버리게 된다.

[C++] BOJ1926 (BFS의 구현)

그림의 수를 Num, 최대 크기를 mx로 두고 알고리즘을 풀었는 데,
Queue에 값을 넣을 때마다 단순히 mx++를 진행하였다. mx는 연속해서 진행 되는 것이 아님에도 (새로운 그림에 들어갈 때마다 초기화 해주어야 한다.)
잘못된 코드

    int num = 0, mx = 0;
    
    for (int i = 0; i < width; i++)
        for (int j = 0; j < height; j++)
            cin >> board[i][j];
    
    for (int i = 0; i < width; i++) {
        for (int j = 0; j < height; j++) {
            if (vis[i][j] || board[i][j] == 0) continue;
            num++;
            queue<pair<int, int>> Q;
            vis[i][j] = 1;
            Q.push({i,j});
            while(!Q.empty()) {
                area++;
                pair<int, int> cur = Q.front(); Q.pop();
                
                for (int dir = 0; dir < 4; dir++) {
                    int nx = cur.first + dx[dir];
                    int ny = cur.second + dy[dir];
                    
                    if (nx > width || nx < 0 || ny > height || ny < 0) continue;
                    if (vis[nx][ny] || board[nx][ny] != 1) continue;
                    vis[nx][ny] = 1;
                    Q.push({nx,ny});
                    mx++; // 해당 부분이 잘못 되었다. BFS의 시작점을 제외하곤 모두 ++를 하게 된다. 
                }
            }
        }
    }

올바른 코드

    for (int i = 0; i < width; i++)
        for (int j = 0; j < height; j++)
            cin >> board[i][j];
    
    for (int i = 0; i < width; i++) {
        for (int j = 0; j < height; j++) {
            if (vis[i][j] || board[i][j] == 0) continue;
            num++;
            queue<pair<int, int>> Q;
            vis[i][j] = 1;
            Q.push({i,j});
            int area = 0; // BFS가 새로 시작될 때마다 새로운 변수를 주고,
            while(!Q.empty()) {
                area++; //pop할때마다 area를 크기를 늘리면 된다.
                pair<int, int> cur = Q.front(); Q.pop();
                
                for (int dir = 0; dir < 4; dir++) {
                    int nx = cur.first + dx[dir];
                    int ny = cur.second + dy[dir];
                    
                    if (nx > width || nx < 0 || ny > height || ny < 0) continue;
                    if (vis[nx][ny] || board[nx][ny] != 1) continue;
                    vis[nx][ny] = 1;
                    Q.push({nx,ny});
                }
            }
            mx = max(mx, area); //BFS가 끝나게 되면 area와 현재의 최댓값을 비교하여 큰 값으로 갱신한다.
        }
    }

C++ BOJ 2178 (나의 잘못된 풀이)

처음엔 아래의 코드와 같이 문제를 해결했고,

    int distance = 0;
    while(!Q.empty()) {
        distance++;
        pair<int,int> cur = Q.front(); Q.pop();
        
        for (int dir = 0; dir<4; dir++) {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (board[nx][ny] != '1' || dis[nx][ny] != -1) continue;
            Q.push({nx, ny});
            dis[nx][ny] = distance;
        }
    }
    cout << dis[n-1][m-1];

4 6
101111
101010
101011
111011

위와 같이 문제가 주어질 때 BFS를 10번 실행할 때까지는 문제가 없다. 왜냐면 단방향이니까 하지만, 문제는 아래처럼 될때이다.

2 -1 9 10 11 12 
1 -1 8 -1 12 -1 
2 -1 7 -1 -1 -1 
3 5 6 -1 -1 -1

위의 결과 처럼 단방향이 아니라 11번째 시행할 때와 같이 오른쪽과 아래에 있으면,
아래쪽 12에 대한 BFS를 진행하고 13을 기록하고

2 -1 9 10 11 12 
1 -1 8 -1 12 -1 
2 -1 7 -1 13 -1 
3 5 6 -1 -1 -1

오른쪽 12에 대한 BFS를 진행하고 14를 기록한다. (14를 기록해야하지만 14를 기록할 수 있는 공간이 없다.)

2 -1 9 10 11 12 
1 -1 8 -1 12 -1 
2 -1 7 -1 13 -1 
3 5 6 -1 -1 -1

따라서 다음 13에 대한 BFS를 실행할 때, 15가 기록되버리고 만다.

2 -1 9 10 11 12 
1 -1 8 -1 12 -1 
2 -1 7 -1 13 15 
3 5 6 -1 15 -1

올바른 코드는 아래처럼 현재 위치에 기록된 값 +1 만큼을 dis[nx][ny]에 기록하는 것이다.

dis[nx][ny] = dis[cur.first][cur.second] + 1;

[C++] BOJ11328

        for (auto e: s1) {
            arr[e-'a']++;
        }
        for (auto e: s2) {
            if (arr[e-'a'] == 0) {
                result = "Impossible\n";
                break;
            }
        }

반례 abc aaa

첫번째 문자열(s1)에서 a가 기록 된 적이 있음
두번째 문자열(s2)에서 "a만" 탐색함.
a는 당연히 있으니까 0이 안나옴. 로직상 문제가 없음.
하지만 두번째 문자열(s2)엔 b,c 또한 있어야 한다.

[C++] Array range-based loop

range-based loop

for ( element : array ) 
cout << element;

ex)

int arr[10] = {1,2,3,4,5,6,7,8,9,10};
for (auto e: arr)
    cout << e; // 1,2,3,4,5,6,7,8,9,10

auto는 타입 추론

[C++] BOJ10845 (Stack)

스택의 구현

크게 어려운 부분은 없었으나

    int MX = 1000005;
    int data[MX];
    
    int head = 0, tail = 0;

    if (command == "back") {
        if (tail - head != 0) cout << data[tail-1] << '\n';
        else cout << -1 << '\n';
    }

가장 마지막 원소에 접근할 때는 tail-1이다!
tail은 항상 마지막 원소 다음을 가리키고 있기 때문에 값이 비어있다. (혹은 쓰레기값이 들어있지렁이)

[C++] DFS의 구현

DFS는 아래와 같이 구현하고, BFS와 달리 Queue대신 Stack을 사용한다.

int board[502][502];
int vis[502][502];
    
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
    
int m = 7, n = 10;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    stack<pair<int, int>> St;
    vis[0][0] = 1;
    St.push({0,0}); // *1
    
    while(!St.empty()) {
        auto cur = St.top(); St.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if (vis[nx][ny] || board[nx][ny] != 1) continue;
            vis[nx][ny] = 1;
            St.push({nx,ny});
        }
    }    
}

자꾸 *1 부분 BFS나 DFS나 구현할 때 깜박하는 데, 저거 안하면 애초에 시작도 안된다.

[C++] BOJ4949 (stack의 활용)

BOJ4949 구현은 어렵지 않았는데 아래의 코드에서

    ios::sync_with_stdio(0);
    cin.tie(0);
    
    while (1) {
        string input;
        getline(cin, input);
        if (input == ".") break;
        stack<char> st;
        
        bool isVaild = true;
        for (auto c: input) {
            if (c=='(' || c == '[') {
                st.push(c);
            }
            else if (c == ')') {
                if (st.empty() || st.top() != '(') {
                    isVaild = false;
                    break;
                }
                st.pop(); // *1
            }
            else if (c == ']') {
                if (st.empty() || st.top() != '[') {
                    isVaild = false;
                    break;
                }
                st.pop(); // *2
            }
            // st.pop() *3
        }
        if (isVaild == false || !st.empty()){
            cout << "no" << '\n';
        }
        else {
            cout << "yes" << '\n';
        }
    }

*3번만 처리해서 문제가 생김!
*1 *2번으로 따로따로 ) 들어올때만 pop() 해야 하는 데,
들어오지 않았는 데도 pop()을 해버려서 와장창 오답이 나옴.
(), {} 다루는 문제였는 데, 나도 그걸 좀 잘 보자...

[C++] BOJ1629 (재귀, 귀납적 사고)

    if (b == 1) return a % m; //base condition
    ll val = POW(a, b/2, m);  //*1
    val = val * val % m;
    if (b%2 == 0) return val;
    return val * a % m;

모든 재귀는 base condition이 있어야 한다. (무한루프를 돌지 않기 위함인 듯함, 주석 부분이 base condition)
귀납적 사고를 해야한다. (위의 코드 *1 POW(a, b/2, m) 부분인 듯함, 아직 자세히 이해 못함)
a^2n = a^n * a^n이니까 POW(a, b/2, m) 이렇게 작성한 듯 함.
k승을 계산했다는 것은 POW(k)는 POW(k/2)를 가지고 있으니까
func(k)가 k, k-1, k-2 ... 1을 출력하면 func(k+1)는 k+1 k k-1 ...1을 출력한다. 를 역으로 발상한 듯 하다.
아직 잘 모르겠음.