uang's blog

이 문제는 유명한 퍼즐인 스도쿠를 구현하면 된다.

스도쿠가 풀리는 입력만 주어지기 때문에 퍼즐을 완성하는 알고리즘만 잘 구현한다면 꽤 쉽게 풀 수 있다.

실제 스도쿠 퍼즐을 사람이 풀기 위해선 다양한 전략, 기법이 필요하지만 컴퓨터가 풀기 위해선 가능한 숫자들을 다 try & error 하는 식으로 해도 빠르게 풀 수 있기 때문에, 백트래킹 + 주먹구구식 대입으로 구현하면 될 것 같다.

문제는 효율적인 백트랙킹을 위해 데이터를 어떤식으로 저장해야 하는가이다.

각 빈칸에 1~9 의 숫자가 들어갈 수 있는지 확인을 위해, row(열), col(행), box(정사각형) bool 타입 배열에 이미 들어간 숫자를 저장하였고, 각 빈칸에 들어갈 수 있는 모든 숫자 후보들을 다 저장하기 위해 2차원 벡터를 이용하였다.

vector< vector< pair< pair<int,int> ,int> > > v;

안쪽 pair<int,int>      : y,x 좌표

바깥쪽 pair의 second : 가능한 숫자 후보

이렇게하면 안쪽 벡터는 같은 빈 칸의 가능한 모든 숫자 후보를 모두  저장할 수 있다.

데이터만 잘 저장해놓으면 재귀함수를 이용해 쉽게 백트래킹을 구현하여 풀 수 있다.

소스코드

#include<stdio.h>
#include<vector>
using namespace std;

int board[10][10];
bool cols[10][10], rows[10][10], box[10][10];
vector< vector< pair< pair<int,int> ,int> > > v;

bool chk(int y,int x, int num){
    if(rows[y][num] || cols[x][num] || box[3*(y/3) + (x/3)][num]){
        return false;
    }
    return true;
}

bool solve(int p){
    if(p == v.size()){
        return true;
    }

    for(int i=0; i<v[p].size(); i++){
        int y = v[p][i].first.first, x = v[p][i].first.second, num = v[p][i].second;
        if(chk(y,x,num)){
            rows[y][num] = cols[x][num] = box[3*(y/3)+(x/3)][num] = true;
            board[y][x] = num;
            
            if(solve(p+1)){
                return true;
            }
            
            rows[y][num] = cols[x][num] = box[3*(y/3)+(x/3)][num] = false;
            board[y][x] = 0;
        }
    }
    return false;
}
int main(){
    
    for(int i=0;i<9;i++){
        for(int j=0;j<9; j++){
            scanf("%d", &board[i][j]);
            if(board[i][j] != 0){
                rows[i][board[i][j]] = cols[j][board[i][j]] = box[3*(i/3) + (j/3)][board[i][j]] = true;
            }
        }
    }
    for(int i=0;i<9;i++){
        for(int j=0;j<9; j++){
            if(board[i][j] == 0){
                vector< pair< pair<int,int>, int> > tmp;
                for(int num=1; num<=9; num++){
                    if(chk(i,j, num)){
                        tmp.push_back(make_pair( make_pair(i,j), num));
                    }
                }
                v.push_back(tmp);
            }
        }
    }

    solve(0);

    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            printf("%d ",  board[i][j]);
        }
        printf("\n");
    }

    return 0;
}

이 문제는 BFS 를 이용해 푸는 미로 문제의 응용버전이라고 볼 수 있다.

이 문제만의 특징은 'A'~'F' 의 문이 있고, 문을 열기 위해선 각 알파벳에 맞는 소문자 'a'~'f' 열쇠를 가지고 있으면 통과할 수 있다.

다행히 문과 열쇠의 종류가 6개 밖에 안되기 때문에, 비트마스크를 이용해 저장할 수 있고

주의할 점은 지나온 길을 다시 가지 않기 위한 visited 변수는 키의 보유 상황에 따라 갈 수 있는 길이 다르기 때문에 이를 고려해야한다.

 소스코드

 풀이 방법

이 문제는 두 지점 사이의 최소 거울 수를 구하는 문제로, 평소 두 지점의 최단거리를 구할 때 사용하는 BFS 를 응용해 "거리" 대신 "거울 수(방향 전환이 일어나는 수)" 를 사용하여 풀 수 있다고 생각했다.

단순 좌표 (y, x) 뿐만 아니라, 사용된 거울 수 및 이동해온 방향 정보가 필요하므로 새로운 구조체를 정의한다.

struct cell{
    int y, x, num, p_dir;
    cell(int y,int x,int num, int p_dir):y(y), x(x), num(num), p_dir(p_dir) {};
};

이동해온 방향(p_dir)을 저장하는 이유는 거울이 사용되는 지점이 방향이 전환되는 시점이기 때문에, 현재 좌표가 어느 방향에서 왔는지 확인하기 위해 필요하다.

이 구조체를 이용해 사용된 거울 수(num) 이 가장 작은 순으로 queue 에서 가져오기 위해 우선순위 큐를 사용한다.

 우선순위 큐의 Comparator 정의

내가 정의한 구조체에서 max-heap 으로 사용할지  min-heap 으로 사용하지 결정하기 위해 compartor를 정의해야 한다.

방법은 구사과 님의 블로그에 자세히 설명돼있다.

풀이에 사용된 방법은 구조체를 이용해 operator() 를 정의해 사용했다.

struct cmp{
    bool operator()(const struct cell& a, const struct cell& b){
        return a.num > b.num;
    }
};

// 중략

priority_queue< cell, vector<cell>, cmp > pq;

* 참고로 greater 는 작은 값을 먼저, less 는 큰 값을 먼저 리턴한다.

* a.num > b.num 는 greater 와 같고, a.num < b.num 은 less 와 같다.

이렇게 정의된 우선순위 큐를 이용하면, 시작지점에서 거울을 사용하지 않고 최대한 이동하여 탐색한 후,

거울  1개, 2개, k개 사용해서 이동할 수 있는 위치를 순차적으로 탐색할 수 있다.

 소스코드

#include<stdio.h>
#include<vector>
#include<queue>
 
using namespace std;
 
struct cell{
    int y, x, num, p_dir;
    cell(int y,int x,int num, int p_dir):y(y), x(x), num(num), p_dir(p_dir) {};
};
struct cmp{
    bool operator()(const struct cell& a, const struct cell& b){
        return a.num > b.num;
    }
};
 
/*
bool operator<(const struct cell a, const strcut cell b){
    return a.num > b.num;
}
*/
int w,h, sy=-1,sx=-1, dy,dx;
int dix[4] = {-1,1,0,0}, diy[4] = {0,0, -1, 1};
char board[111][111];
bool visited[111][111];
bool dir_check(int a, int b){
    return (a<2 && b<2) || (a>=2 && b>=2)  || a == -1;
}
int main(){
    scanf("%d%d",&w,&h);
 
    for(int i=0;i<h;i++){
        scanf("%s", board[i]);
        for(int j=0;j<w;j++){
            if(board[i][j] == 'C'){
                if(sy != -1 && sx != -1){
                    dy = i, dx = j;
                } else {
                    sy = i, sx  = j;
                }
            }
        }
    }
    priority_queue< cell, vector<cell>, cmp > pq;
    // priority_queue< cell, vector<cell>, greater<cell> > pq;
 
    pq.push(cell(sy, sx, 0, -1));
    while(!pq.empty()){
        cell cur = pq.top();
        pq.pop();
        visited[cur.y][cur.x] = 1;
        if(cur.y == dy && cur.x == dx){
            printf("%d\n", cur.num);
            break;
        }
        for(int i=0;i<4;i++){
            int ny = cur.y + diy[i], nx = cur.x + dix[i];
            if(ny >=0 && nx >=0 && nx < w && ny < h) {
                if(!visited[ny][nx] && board[ny][nx] != '*'){
                    // printf("\tnext : (%d, %d) num : %d, is_plus? : %d\n", ny,nx, cur.num, !dir_check(cur.p_dir, i));
                    pq.push(cell(ny, nx, cur.num + (dir_check(cur.p_dir, i) ? 0 : 1), i));
                }
            }
        }
    }
    return 0;
}

"구간 합" 유형 + 값 수정 쿼리 가 있는 문제는 "세그먼트 트리" 를 이용해 풀어야 한다.

구간 합은 보통 prefix sum(psum) 배열을 이용해 [a, b] 의 구간합을 psum[b] - psum[a-1] 로 풀 수 있다.

하지만 구간 값이 변경되는 "K 개의 수정 쿼리"가 있을 때는, 매 수정마다 N 크기의 배열을 다시 계산해야하기 때문에,

전체 복잡도가 O(K*N) 이 된다.

세그먼트 트리는 

     Leaf node      : 배열 값

     Internal node : 자식노드들의 구간 합

을 저장하여, 수정을 O(logN) 만에, 구간 합 계산 또한 O(logN) 번 만에 수행할 수 있는 자료구조이다.

자세한 내용은 백준님 블로그에 설명되어 있다.

이 문제는 값 수정 쿼리가 있는 구간 곱을 계산하는 문제로, 세그먼트 트리를 이용해야하며, 합 대신 곱 연산으로 변경해주면 된다.

#주의할 점

* 곱 연산이기 때문에 발생하는 오버플로우 문제가 있다.

* update 를 하는 방식은 다양하지만, 이전 값과의 차이(difference) 값을 해당 노드마다 곱해주는 방식으로는 WA 를 받는다.

  - difference 값을 계산하면서 발생하는 나눗셈 연산이 문제의 조건인 1000000007 MOD 연산에 영향을 줄 수 있을 것 같다.

  - 따라서 잎 노드의 변경으로부터 다시 계산하는 방식으로 업데이트를 수행한다.

소스코드

1. #include<stdio.h>
2. #include<vector>
3. #define MOD(x) ((x)%1000000007)
4. using namespace std;
5. typedef unsigned long long ull;
6. int n, m, k;
7. ull arr[1000001];
8.  
9. ull make_seg_tree(vector< ull > &v, int node, int start, int end){
10. if(start == end){
11. return v[node] = arr[start];
12. }
13. return v[node] = MOD( make_seg_tree(v, node*2, start, (start+end)/2) *
14. make_seg_tree(v, node*2+1, (start+end)/2 + 1, end));
15. }
16. ull update_seg_tree(vector<ull>&v, int node, int start, int end, int idx, ull val, bool was_zero) {
17. if( idx < start || end < idx) return v[node];
18.  
19. if(start == end) {
20. arr[idx] = val;
21. return v[node] = val;
22. } else {
23. return v[node] = MOD(update_seg_tree(v, node*2, start, (start+end)/2, idx, val, was_zero) *
24. update_seg_tree(v, node*2+1, (start+end)/2+1, end, idx, val, was_zero));
25. }
26. // v[node] = was_zero ? val : MOD((ull)(v[node] / arr[idx] * val)); // difference 를 이용한 수정
27. }
28.  
29. ull get_mul(vector< ull >&v, int node, int start, int end, int left, int right) {
30. if(right < start || end < left) return 1;
31. if(start==end) return v[node];
32. if(left <= start && end <= right){
33. return v[node];
34. }
35. return MOD( get_mul(v, node*2, start, (start+end)/2, left, right) *
36. get_mul(v, node*2+1, (start+end)/2+1, end, left, right));
37. }
38.  
39. int main(){
40. scanf("%d %d %d",&n,&m,&k);
41. for(int i=1;i<=n;i++){
42. scanf("%u",&arr[i]);
43. }
44. vector< ull > v(4*n);
45. make_seg_tree(v, 1, 1, n);
46.  
47. int a, b,c;
48. for(int i=0; i<m+k;i++){
49. scanf("%d %d %d",&a, &b, &c);
50. if(a == 1){
51. //update
52. bool was_zero = arr[b] == 0;
53. ull val = (ull)c;
54. update_seg_tree(v, 1, 1, n, b, val, was_zero);
55. arr[b] = val;
56. } else{
57. //get mul
58. printf("%u\n", get_mul(v, 1, 1, n, b, c));
59. }
60. }
61.  
62. return 0;
63. }

AWS CLI version 2 는 2020년 2월 10일에 Release 되었다.

Version 2 에 새로 추가된 일부 기능은 Version 1 로의 역호환을 지원하지 않을 수 있다.

따라서, Version 2 를 설치해 AWS 서비스들을 공부할 것이며,

앞으로 AWS study 카테고리에서는 데이터 엔지니어링 관련한 서비스들을 사용해보며, 공부한 내용을 정리할 계획이다.

정리할 내용은 주로 간단한 사용법 및 정리해놓으면 유용할 정보들이다.

CLI 2 설치 방법

공식 문서 : https://docs.aws.amazon.com/cli/latest/userguide/install-cliv2.html

$ curl "https://awscli.amazonaws.com/AWSCLIV2.pkg" -o "AWSCLIV2.pkg"
$ sudo installer -pkg AWSCLIV2.pkg -target /

-target 으로 지정한 드라이브에 패키지가 설치되며, 파일들은 /usr/local/aws-cli 의 경로에 설치되며, /usr/local/bin 에 심볼릭 링크로 자동 생성된다. (위 폴더의 사용을 위해 sudo 권한이 필요)

* 디버그 파일 경로 : /var/log/install.log

설치 확인

# Version issue

* CLI version 1 과 version 2 가 모두 설치돼있을 경우, 환경변수 path 상에 앞 순서에 있는 버전이 동작하게 된다.

->  한 버전을 완전히 지운 후, 하나의 버전만 사용할 것을 권장함

* migration from version 1 to version 2 : http://docs.aws.amazon.com/cli/latest/userguide/cliv2-migration.html

IAM user 생성 및 AWS CLI Configuration 

CLI 를 통해 AWS 에 작업을 하기 위해 IAM (Identification and Access Management) 사용자가 필요하다. 

IAM 은 AWS 서비스를 이용하기 위해 필요한 권한을 부여할 수 있다.

1. AWS 사이트에서 [Services] - [Security, Identity, & Compliance] - [IAM] - [Users] 에서 사용자를 추가

2. 사용자 이름 및 액세스 유형 선택

사용자 이름을 정하고, CLI 를 이용하므로 액세스 유형은 프로그래밍 방식 액세스를 선택한다.

3. 권한 설정 선택

권한 설정 방법은 크게 세 가지

        1) 같은 권한을 공유하는 그룹에 새 사용자를 추가

        2) 기존 유저가 갖고 있는 권한을 복사

        3) 직접 권한 새로 부여

가 존재하며, 자세한 권한은 나중에 수정할 수 있으니 모든 액세서 권한을 갖는 관리자 권한으로 넣는다.

4. Tags 설정

생성할 유저에 대한 description 을 태그할 수 있다. (지금은 필요없으니 넘어간다)

5. AWS-CLI configuration

생성한 IAM 유저의 Access key ID 와 Secret access key 값을 이용해 터미널 상에서 설정하면 된다.

$ aws configure

Jenkins + Slack 연동

 이번 포스트에서는 Jenkins와 Slack을 연동하여, Jenkins에서 빌드 결과를 Slack으로 알림 받을 수 있는 방법에 대해 정리한다.

Jenkins - Slack Notification Plugin 설치

Jenkins + Github 연동

프로젝트 준비

 Github + Slack 연동

 먼저 Slack 에서 Apps 의 +버튼을 통해 github을 검색하고  github을 설치한다.

 Slack의 어떤 채널에 연결을 할 지 선택할 수 있다.

설치가  완료되면  슬랙의 채널에서 /github signin 명령어를 통해 깃헙 계정에 로그인하여 연결한다.

로그인이 완료되면, Success! 라고 문구가 뜬다. 그리고,  특정 레퍼지토리랑 연결하기 위해,

/github subscribe [github ID] / [Repository명] 을 입력한다. 그러면 깃헙에 설치가 되어있지 않다고 설치하라는 문구가 뜬다.

설치해보자.

  팝업된 페이지의 밑으로 내려가보면 어떤 레퍼지토리에 액세스 권한을 줄지 선택할 수 있다. 연동할 레퍼지토리를 선택한다.

설치를 완료한 후, 다시 슬랙으로 돌아와 명령어를 다시 한 번 입력하면 해당 레퍼지토리를 github 봇이 구독한다.

깃헙 레퍼지토리에서 커밋, 푸시 등의 이벤트가 발생하면 Slack의 연동한 채널로 notification을 주게 된다.

Github 기초 사용법 - 3

목 차

  issue  :  프로젝트를 진행하면서 발생하는 모든 이슈 (버그 발생, 개발, 풀 리퀘스트 등등)

  Github 기초 사용법 - 2

  이번 포스트에서는 로컬 저장소에서 작업한 내용을 Github의 원격저장소로 push하는 등의 원격저장소 활용방법에 대해 다룬다. github의 기본 명령어 (git init & status & add & commit) 및 Branch 와 충돌관리에 대해 잘 모른다면 이전 포스트 [Project Management/Github] - Github 기초 사용법 - 1를 참고하세요.

목 차

---

2. 원격저장소 연결 (git remote)

 

 Git Bash 터미널로 돌아가 이전 포스트[Project Management/Github] - Github 기초 사용법 - 1에서 작업했던 환경에서  방금 생성한 원격 저장소를 연결해보자. 그리고 git remote -v 로 목록을 확인해보자. 통상적으로 origin이란 별명을 사용한다.

 git remote add [원격저장소 별명] [원격저장소 주소] : 원격저장소 추가

 git remote -v : 원격저장소 목록 확인

e.g. remote add origin https://github.com/lis123kr/github.tutorial.git

 아무 변경사항이 없어보인다. 하지만 추가한 원격 저장소를 통해 이제 로컬 환경의 작업내역을 원격으로 전송할 수 있다.

---

3. git push (로컬 -> 원격)

 git push [원격저장소 별명] [브랜치 명] : 원격저장소에 [브랜치 명]의 작업내용을 전달

 git push 명령어를 통해 원격저장소에 변경 내용을 발행해보자. git push origin --all 을 통해 모든 브랜치를 전송하였다. 그리고 github의 원격 저장소에도 업로드된 것을 확인할 수 있다.

 

---

4. 원격저장소와 로컬저장소 충돌 문제 (git pull & fetch)

 

 이번에는 원격 저장소와 로컬 저장소의 간격을 메우는 과정을 살펴보자. 새로운 기능을 로컬 저장소에서 구현했을 때는, commit하고 push하여 로컬 저장소에 업로드하면 되지만, 다른 팀원이 개발한 내역이 있어 원격 저장소의 작업 내역이 나의 로컬의 작업내역과 다를 때는 내 변경사항을 원격저장소에 업로드(Push)하면 충돌이 발생한다.

 이럴 때는 원격저장소의 변경사항과 나의 로컬저장소의 간격을 없애야한다. 즉, 원격저장소의 최신 변경사항으로 맞추어야 내 로컬 변경사항을 업로드할 수 있다. 이를 위한 명령어가 fetch와 pull이다. 

 git fetch : 원격 저장소의 변경 사항(commit) 들을 로컬저장소로 가져온다. (commit 내역을 가져온다)

 git pull   : 원격 저장소의 변경사항을 가져와 로컬에 병합한다.

 즉, git pull은 git fetch하고 git merge까지 해준다고 볼 수 있다. 그럼 이제 직접 해보자.

원격 저장소와 로컬 저장소의 간격을 만들기 위해 원격 저장소에서 내용을 수정해보자. github 저장소에서 C코드를 선택해 '펜' 버튼을 누르면 바로 수정가능하다. 주석 한줄을 추가한 후 밑에 commit 버튼을 통해 변경을 완료한다.

  

  이로써, 원격저장소에는 commit이 하나 더 생겼다. 내 로컬 환경과 간격이 생겼고, 로컬 환경에서 마찬가지로 주석을 작성해 push해보면 충돌이 발생한다.

 

 당연히 원격저장소와 로컬 저장소가 변경내역이 다르기 때문이다(원격과 로컬 각각 커밋이 하나씩 더 있다) . hint에는 git pull을 사용하라고 알려주지만 git fetch를 사용해보자. git fetch를 하면 아무 변화가 없어보인다. 파일도 로컬에서 변경한 내용 그대로이다. 하지만 git branch -a를 해보면 원격저장소의 임의의 브랜치(origin/master)가 생성되었다.

  

 git merge origin/master를 통해 원격저장소의 변경내역과 병합해보자. 변경내역에 충돌이 없다면 바로 병합이 되지만, 여기서 변경한 내역에는 충돌되는 부분이 있어 충돌이 발생했다. 충돌이 난 부분을 git diff를 통해 확인하고 해결하자.

 

 충돌을 해결한 후 원격저장소에 push하면 이제는 원격저장소와 로컬저장소가 같은 최신의 작업내역을 갖고있기 때문에 push 시 에러가 발생하지 않는다.

 지금까지의 변경내역을 그래프로 그려보면 다음과 같다. 각 점은 commit 내역을 의미하고 branch를 생성하고 병합한 내역과, 원격 저장소에서의 변경과 병합한 내역을 확인할 수 있다. 이 그래프는 Github 레퍼지토리에서 [Insights - Network]를 통해 확인할 수 있다.

   

---

5. fork/clone 와 pull request

 마지막으로 오픈소스의 발전 속도를 가속화하는 기능인 fork와 pull request에 대해 알아보자.

fork               : 다른 사용자의 원격저장소를 내 원격 저장소 복제

clone            : 원격 저장소를 로컬 저장소에 복제

pull request  :  저장소 간의 병합요청

  fork는 말 그대로 다른 사용자의 저장소를 내 저장소에 똑같이 복사하는 기능이다. pull request는 복사한 다른 사용자의 저장소에서 여러 기능 수정 및 추가를 한 후, 나의 변경 내역을 저장소 소유자(오리지널 저장소)에 병합요청을 하는 기능이다. 즉, 다른 사람의 소스를 내가 수정하고 변경요청을 통해 '기여'할 수 있는 기능이다.

 

 이를 직접 실습하기 위해선 또 하나의 계정이 필요하다. (저자는 두 개 있다)  다른 계정으로 지금까지 작업해온 저장소를 fork해보자. 레퍼지토리오른쪽 상단의 fork 버튼을 누르면 된다. fork 된 저장소의 원격 저장소 주소를 복사하여 git Bash에서 새로운 환경에 clone해보자. 

 

 clone한 저장소에서 git remote -v를 해보면 자동으로 복사했던 원격저장소(fork한)의 주소와 연결되어있다. 약간의 코드 수정을 하고 push까지 해보자. 

 

 

 Push까지 완료하면 fork 했던 원격 저장소를 보면 다음과 같이 커밋이 업데이트 되어있고, 기존 저장소와는 다르게 pull request가 있음을 확인할 수 있다. pull request를 해보자.

본 저장소와 fork 저장소의 변경사항을 보여주고 Create pull request 버튼을 통해 pull request를 생성할 수 있다. pull reqeust를 생성할 때, 보통 오픈소스 프로젝트에서는 template이 있어, 템플릿에 맞게 내용을 작성하여 병합요청을 해야한다.  

 다시 소유자의 계정으로 돌아가보자. pull reqeust 메뉴에 다른 사용자가 요청한 pull request가 생성되어있고, 내용을 확인할 수 있다.

 pull request를 받은 본 저장소의 소유자는 변경 내용을 확인하고 적합하다면 merge 버튼을 통해 병합할 수 있고, 또는 변경을 요청하며 병합을 거절할 수 있다.

 

 Merge를 하면 다른 유저가 변경한 코드 변경 내역을 원래의 저장소에 병합하게 된다. 다음 시간에는 위 이미지에서 오른쪽에 보이는 Reviewers 및 Labels, Project, Milestone에 대해 포스트할 계획이다.