• 오름차순으로 된 배열의 인덱스를 제곱하여 오름차순으로 출력하시오

풀이

풀이 1 - sort

간단하게 제곱한 후 sort 라이브러리를 이용해 정렬하여 리턴하는 방식이다.

class Solution {
public:    
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i=0; i<nums.size(); i++){
            nums[i]*= nums[i];
        }
        sort(nums.begin(), nums.end());
        return nums;
    }
};

풀이 2 - two pointer

주어진 벡터의 left 와 right 포인터를 두고 그 값을 서로 비교하며 더 큰 값을 새로운 배열에 저장한다.

class Solution {
public:    
    vector<int> sortedSquares(vector<int>& nums) {
        int n=nums.size();
        int left=0; int right=n-1;

        vector<int> sorted(n);
        int pos = n-1;

        while(left<=right){ //-4,-1,0,3,10
            if(abs(nums[left])<abs(nums[right])){
                sorted[pos--] = pow(nums[right], 2); right--;
            }
            else { // 1 9 16 100
                sorted[pos--] = pow(nums[left], 2); left++;
            }
        }
        return sorted;
    }
};

참고

• https://butter-shower.tistory.com/226

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

//since the given array is sorted array, I will use binary search

class Solution {
public:
    int firstBadVersion(int n) {
        int left=1; 
        int right = n;
        int middle;

        while(left <right){
            //middle = (left+right)2; 범위 오류남
            middle = left +(right-left)/2;
            if(isBadVersion(middle))
                right = middle;
            else
                left = middle+1;

        }
        return right;
    }
};

• NxN 크기 종이에 -1 0 1 저장

1. 종이가 모두 같은 수로 되어있으면 종이 그대로 사용
2. 1이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해 1의 과정을 반복

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

풀이

분할정복으로 푸는 문제

#include <bits/stdc++.h>
using namespace std;
int output[3];  // -1 0 1 개수 저장
int arr[2187][2187];

void paper(int x, int y, int N){
    int first = arr[x][y];
    bool flag = true;

    for(int i = x; i < x + N; i++){
        for(int j = y; j < y + N; j++){
            if(arr[i][j] != first){
                flag = false;
                break;
            }
        }
    }

    if(flag) {// 다 똑같으면 개수 ++
        output[first + 1]++;
    }
    else {// 다르면 분할 
        for(int i = x; i < x + N; i += N/3 ){
            for(int j = y; j < y + N; j += N/3){
                paper(i, j, N/3); 
            }
        }
    }
}

int main(){
    int N;

    cin >> N;

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> arr[i][j];
        }
    }

    paper(0, 0, N);

    for(int i = 0; i < 3; i++){
        cout << output[i] << endl;
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n;
void bar(int count){
    for(int i=0; i<count; i++){
        cout <<"____";
    }
}

void func(int count){
    bar(count); 
    cout << "\"재귀함수가 뭔가요?\"\n";
  if(n==count) {
      bar(n);
      cout <<"\"재귀함수는 자기 자신을 호출하는 함수라네\"\n";
  }
  else{
    bar(count); cout<< "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n";
    bar(count); cout << "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n";
    bar(count); cout << "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n";
    func(count+1);
  }
  bar(count);
  cout << "라고 답변하였지.\n";

}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n";
  func(0);

}

1) 함수의 정의 int func(int n, int r, int c) 2^nx2^n 배열에서 (r,c)를 방문하는 순서를 반환하는 함수 2) base condition if(n=0) return 0; 3) 재귀 식 (r,c)가 1번 사각형일 때 return func(n-1, r, c); (r,c)가 2번 사각형일 때 return halfxhalf+func(n-1, r, c-half); (r,c)가 3번 사각형일 때 return 2xhalfxhalf+func(n-1, r-half, c); (r,c)가 4번 사각형일 때 return 3xhalfxhalf+func(n-1, r-half, c-half); *half = 2^n-1 (한변 길이의 절반)

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

int func(int n, int r, int c){
  if(n == 0) return 0;
  int half = 1<<(n-1);
  if(r < half && c < half) return func(n-1, r, c);
  if(r < half && c >= half) return half*half + func(n-1, r, c-half);
  if(r >= half && c < half) return 2*half*half + func(n-1, r-half, c);
  return 3*half*half + func(n-1, r-half, c-half);
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, r, c;
  cin >> n >> r >> c;
  cout << func(n, r, c);
}

전형적인 하노이탑 문제

풀이

n번을 3번 기둥으로 옮기려면 1~n-1번을 2번 기둥으로 옮긴 후 n을 3번 기둥으로 옮길 수 있다. 즉 풀이 순서는

1. n-1개 원판을 기둥 1에서 2로 옮긴다
2. n번 원판을 기둥1에서 기둥 3으로 옮긴다.
3. n-1개의 원판을 기둥 2에서 기둥 3으로 옮긴다.

1) 함수의 정의 void func(int a, int b, int c) 원판 n개를 a번 기둥에서 b번 기둥으로 옮기는 방법을 출력하는 함수 2) base condition n=1일때 cout << a<<' '<<b<<'\n'; 3) 재귀 식 n-1개의 원판을 기둥 a에서 기둥 6-a-b(a도 b도 아닌 기둥 이게 왜???)로 옮긴다. func(a, 6-a-b, n-1) n번 원판을 기둥 a에서 b로 옮긴다. cout << a<<' '<<b<<'\n'; n-1개의 원판을 기둥 6-a-b에서 기둥 b로 옮긴다. func(6-a-b, b, n-1);

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

void func(int a, int b, int n){
  if(n == 1){
    cout << a << ' ' << b << '\n';
    return;
  }
  func(a, 6-a-b, n-1);
  cout << a << ' ' << b << '\n';
  func(6-a-b, b, n-1);
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int k;
  cin >> k;
  cout << (1<<k) - 1 << '\n'; //(1<<k) == 2^k
  func(1, 3, k);
}

풀이2 - 인자 4개 사용

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

void hanoi(int n, int start, int to, int bypass) //1 3 2
{
    if(n == 1)
        cout << start<<' '<<to<<'\n';
    else{
        //n-1을 3번을 사용해 2번으로
        hanoi(n-1,start,bypass,to);//1 2 3
        cout << start<<' '<<to<<'\n';
        //2번에 있던 n-1을 1을 사용해 3으로 
        hanoi(n-1,bypass,to,start); // 2 3 1
    }
}
int main() {
    int num;
    cin >> num;
    cout << (1<<num) -1 << "\n";
    hanoi(num,1,3,2);
}

자연수 A를 B번 곱한 수를 C로 나눈 나머지를 구하시오 a,b,c는 모두 2,147,483,647이하의 자연수이다.

풀이

int형의 범위가 -2,147,483,647~2,147,483,647이므로 A,B,C는 모두 int 형으로 둘 수 있음

풀이 1 - 시간초과

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

void multiplication(long long a, int b, int c){ //10 11 12
    if(b==0) {cout << a; return;}
    a*=a; a%=c; b--;
    multiplication(a, b, c);
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long a;
    int  b, c;
    cin >>a>>b>>c;

    multiplication(a, b, c);

    return 0;
}

재귀를 사용해서 푸는 문제 아닌가...? 왜 시간초과가 떴을까? long long끼리 곱하는 연산 때문인가??

a값이 변경되는 곳에서 문제가 생겼다. 원래 의도한 풀이는 10X10, 10X100 이렇게 되어야 하는데 위의 코드대로 실행을 시키면 10 X10, 100 X 100, 1000 X 1000 이렇게 변하는 문제가 있었다. 이를 해결하기 위해서 tmp 변수를 넣었다. 그래도 안된다! b번 곱하는 것이라면 시간복잡도가 O(N)이 나온다. O(N)으로 풀어도 안되나..?

풀이 2 - 분할 정복

이 문제에는 두가지 문제점이 있다.

1. 숫자의 범위가 자료형의 표현 범위보다 커진다.
2. O(n)의 시간복잡도로 문제를 풀어도 시간제한에 걸린다.

1번은 연산을 할 때마다 c로 나누어서 해결이 가능하다. 2번은 분할 정복으로 해결이 가능하다.

long long pow(long long a, long long b, long long c){ //10 11 12
    if(b==1) return a%m;
    long long val = pow(a, b/2, m);
    val = val*val%m;
    if(b%2==0) return val; //b가 짝수이면 그냥 반환
    return val*a%m; //홀수이면 한번 더 곱하고 나눠서 반환
 }

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

using ll = long long;

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

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll a,b,c;
  cin >> a >> b >> c;
  cout << POW(a,b,c);
}

b를 짝수일때, 홀수일때로 나누어서 생각한다. 2^10이면 b가 짝수인데, 2^10 = 2^5x2^5이고 2^5 = 2^2x2^2x2이고 2^2 = 2X2이다. 이를 생각해보면 b를 계속 2를 나누어 연산하게 되고, 연산한 값을 변수에 저장하고 계산하면 시간 복잡도는 O(logn)이 된다. (n==b)

재귀란 자기 자신을 호출하여 해결하는 기법이다. 재귀에서의 가장 기본적인 원칙은 Divide and Conquer, 즉 순환이 일어날 때마다 문제의 크기는 줄어드는 것이다. factorial, 이항계수, 이진트리 알고리즘, 이진탐색, 하노이 탑을 구현하는데 유용한 방식이다.

구조

int facotrial(int n){
    if(n<=1) return 1; //recursion을 멈추는 부분
    else return n*factorial(n-1); //recursion을 호출하는 부분

재귀는 1. 재귀를 멈추는 부분과 2. 재귀를 호출하는 부분 두 파트로 나누어져있다.

Recursion vs Iteration

대부분의 재귀는 반복의 형태로 구현되어있다. 재귀는 함수의 주소를 callback하는데 걸리는 overhead가 있기 때문에 대체로 실행속도가 느리다. 여기서 중요한 것은 이 느린 실행속도를 divide and conquer로 어떻게 줄이느냐 관건이다.

재귀는 항상 memory & call overhead가 iteration에 비해 크다. 함수를 불러오는 과정에서 생기는 overhead이기 때문이다. 재귀함수가 자기 자신을 호출할 때 스택 영역에 계속 누적이 된다. 대부분 stack 영역은 따로 설정하지 않으면 1MB등의 작은 크기로 설정이 되어있다. 때문에 재귀를 잘못 구현하면 stack overflow 문제에 직면할 수 있다.

대체로 iteration이 recursion보다 빠른데, factorial, 이항계수, 이진트리 알고리즘, 이진탐색, 하노이탑과 같은 문제에서는 recursion이 iteration보다 좋은 선택이 된다. 하지만 피보나치를 구현할 때 recursion은 추천하지 않는 방법인데, 왜인지 한번 살펴보자. 예를 들어, 재귀형식으로 구현된 피보나치가 있다고 해보자.

int fibo(int n){
    if(n<=1) return 1;
    return fibo(n-1)+fibo(n-2);

피보나치 수열은 정의 자체가 재귀로 되어있기 때문에 구현하기 어렵지 않다. 하지만 이렇게 됐을 때 어마어마한 시간복잡도에 직면할 수 있다. 호출한 함수를 또 호출한다는 문제가 발생하기 때문이다. 또한 만약 fibo(n)이 호출되었을 경우, 시간복잡도가 2^n이 된다. 따라서 피보나치를 구현할 때는 iterator 방식으로 구현하는 것이 좋다.

연습문제 1 - 거듭제곱

int func(int a, int b, int m){
    int val = 1;
    while(b--) val *=a;
    return val%m;
}

func(6,100,5)를 넣으면 1이 아니라 0이 나온다 왜일까? int형의 overflow 때문이다. 6을 100번 곱하면 int 자료형의 범위를 넘어가게 된다. 때문에 범위를 long long으로 바꾸고, 100번을 모두 곱한후 나머지를 구하는 것이 아니라 매번 곱할 때마다 나머지를 구하는 것이 메모리 측면에서 효율적이다.

1629- 곱셈

• 2차원 배열, 높이 정보는 각 인덱스에 양의 정수로 저장
• 바다는 0
• 동서남북의 0의 개수만큼 본인의 높이에서 빼기
• 각 칸의 높이는 0보다 줄어들지 않음
• 한 덩어리 빙산이 주어질 때 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간을 구하시오

풀이

BFS 두개가 필요할 듯

• 빙산이 매년 녹는 것을 저장하는 Board[n][m], 해당 박스에 대한 bfs 돌림 돌릴 때마다 년++
• 빙산이 몇개인지 세는 bfs
• 다 녹을 때까지 두덩어리 이상으로 분리되지 않으면 0 출력
  • board가 모두 0이면 cout << 0
• bfs를 한번 돌릴때마다 빙산의 개수가 몇개인지 센 후 빙산의 상태 업데이트하기

풀이 1- 틀린 풀이 (board값의 갱신이 반영되는 풀이)

while(!Q.empty()){
                auto cur = Q.front();
                Q.pop();

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

                    //범위 걸어주기
                    if(nx<0||nx>n||ny<0||ny>m) continue;
                    if(board[nx][ny]==0) amount++; continue; //0의 개수 저장
                    if(vis[nx][ny]!=0) continue;

                    vis[nx][ny]=1;

                    Q.push({nx, ny});
                }
                board[cur.X][cur.Y]-=amount;


            }

원래는 한 칸에 대해 동서남북을 읽고 나면 0의 칸의 개수(amount)를 세어서 그 개수만큼을 해당 칸에서 빼는 형태로 하려 했는데, 이렇게 진행하면 한 칸이 진행될때마다 보드가 갱신이 되어서 인접해있는 칸의 빙산의 높이를 제대로 갱신할 수 없다는 문제점이 있다. 예를 들어 2높이의 빙산이 위, 왼쪽의 0의 칸의 개수에 따라서 0이 되어버리면 아래의 3높이의 빙산은 갱신된 값에 영향을 받아 3개를 빼, 높이가 0이 된다.

하지만 문제에서는 이렇게 갱신된 값이 아닌 원래 보드의 빙산의 높이만을 반영해야 한다. 따라서 1번의 풀이는 옳지 않다.

풀이 2 -

그러면 갱신된 값이 다음 칸의 높이를 계산하는 데 영향을 미치지 않게하려면 어떻게 해야할까? 만약 vis가 아닌 dist로 보드와 크기가 같은 판에 해당 노드의 상하좌우에 0이 몇개 존재하는지 저장하는 것은 어떨까?

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

#define X first
#define Y second

int board[1001][1001];
int dist[1001][1001]; //각 칸에 인접한 0의 개수를 저장하는 배열

int n, m, years, iceberg;
int dx[4] = { 1 , -1, 0, 0 };
int dy[4] = { 0 , 0, 1, -1 };


void printBoard(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout << board[i][j]<< ' ';
        }
        cout << '\n';
    }
    cout << '\n';
}


void printDist(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout << dist[i][j]<< ' ';
        }
        cout << '\n';
    }
    cout << '\n';
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n>>m;

    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin >> board[i][j];

    cout << "---------------------\n";

    //빙산 덩어리의 개수를 구함
    //빙산은 매년 상하좌우로 0의 개수만큼 녹음
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            //칸이 바다이거나 방문한 곳이거나 빙산 덩어리 개수가 2개 이상이면 pass
            if(board[i][j]==0 || dist[i][j]!=0) continue;
            //iceberg++; //빙산 덩어리 개수

            queue<pair<int, int>> Q;
            Q.push({i,j}); //1,1
            cout << i<<j<<".. \n";

            //dist에 갱신하기
            while(!Q.empty()){
                auto cur = Q.front(); //1,1
                Q.pop();

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

                    //범위 걸어주기
                    if(nx<0||nx>n||ny<0||ny>m) continue;
                    if(board[nx][ny]==0) {amount++; continue; }//0의 개수 저장
                    if(dist[nx][ny]!=0) continue;

                    dist[nx][ny]=1;
                    Q.push({nx, ny});
                }
                dist[cur.X][cur.Y]= amount;
                printDist();


            }
        }
    }




    return 0;
}

• 본인또는 다른 사람 한명만 선택 가능
• 서로가 서로를 선택하거나 본인을 선택한 경우에만 팀이 됨

풀이

입력 예제

i 1 2 3 4 5 6 7 j 3 1 3 7 3 4 6 v 1 0 1 0 0 0 0 t 0 0 1 0 0 0 0

본인으로부터 시작해서 본인으로 못끝남 (1,3) -> (3,3) if(i ==j) -> 본인 혼자 팀 (방문함, 팀 형성1으로 갱신) if(j가 방문 안했고)이고 본인으로 시작해서 본인으로 끝남

21->13->(방문했으므로 못감)33 i 1 2 3 4 5 6 7 j 3 1 3 7 3 4 6 v 1 1 1 0 0 0 0 t 0 0 1 0 0 0 0

47->76->64 (처음과 끝이 같은 경우에 해당 i들의 t를 모두 1로 변경) i 1 2 3 4 5 6 7 j 3 1 3 7 3 4 6 v 1 1 1 1 0 1 1 t 0 0 1 1 0 1 1

53-> 33(방문했으므로 못감) i 1 2 3 4 5 6 7 j 3 1 3 7 3 4 6 v 1 1 1 1 1 1 1 t 0 0 1 1 0 1 1

풀이 1

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

#define X first
#define Y second

int board[100001];
int vis[100001][2];

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


void print(int n){
    for(int i=1; i<=n; i++){
        cout << i<<' ';
    }
    cout << '\n';
    for(int i=1; i<=n; i++){
        cout<< vis[i][0]<< ' ';
    }
    cout << '\n';
    // for(int i=1; i<=n; i++){
    //     cout<< vis[i][1]<< ' ';
    // }
    cout << "\n\n";
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int count=0;

    cin >> T;
    while(T--){
        fill(board, board+100001, 0);
        fill(vis[0], vis[100001],0);

        cin >> n;
        for(int i=1; i<=n; i++){
                             //1 2 3 4 5 6 7
            cin >> board[i]; //3 1 3 7 3 4 6

            //본인 혼자 팀인 경우
            if(i == board[i]){
                vis[i][0]=1;// 방문으로 바꿈
                //vis[i][1]=1; //팀 여부 1: 팀 형성 0: 팀 형성 x
                count++;
            }
        }

        cout << "cnt: "<< count<<'\n';

        for(int i=1; i<=n; i++){
            //시작하는 원소 넣기
            queue<pair<int, int>> Q; //47
            Q.push({i,board[i]}); //47
            //현재노드 방문으로 설정
            vis[i][0]=1; //1 1 1 1 0 0 1
            int first = i;//처음 원소 4
            int cnttmp=0; //팀이 되는 개수 0

            while(!Q.empty()){ //76
                //print(n);
                auto cur = Q.front(); //76
                Q.pop();

                int next = cur.Y; //6
                //next 거르기:방문했거나 범위를 벗어나면 pass
                if(vis[next][0]==1||next<1||next>n) continue;

                if(first == board[next]){//처음과 끝이 같음 1!=3
                    count += cnttmp; //2
                    cout << "cnt: "<<count<<'\n';
                }
                cout << "cnttmp: "<<cnttmp<<' ';
                vis[next][0]=1; //방문으로 변경
                cnttmp++; //1
                Q.push({next, board[next]});  //큐에 다음노드 넣기

            }
        }

        cout << n-count<<'\n';

    }


    //vis가 0인 원소는 팀에 속하지 못함

    return 0;
}

#: 벽 .: 지나갈 수 있는 공간 J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간) F: 불이 난 공간 RxC (1~1000)

입력예제

4 4
####
#JF#
#..#
#..#

풀이

불은 지훈이가 한 번 이동할 때마다 상하좌우로 한칸씩 늘어난다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. -> 범위 밖으로 나가면 탈출한 것!

지훈이가 한번 움직일떄마다 불이 상하좌우로 퍼져야한다.

풀이 1 - 틀린 풀이

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

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

char board[1001][1001];
int dist[1001][1001]={-1};
int dist2[1001][1001]={-1};

int R, C;
queue<pair<int, int>> Q;
queue<pair<int, int>> Q2;

void fire(){
    while(!Q2.empty()){
        auto cur = Q2.front();
        Q2.pop();


        //상하좌우 확인하기
        for(int dir=0; dir<4; dir++){
            int nx = cur.first+dx[dir];
            int ny = cur.second+dy[dir];

            //범위 확인하기
            if(nx<0||ny<0||nx>=R||ny>=C) continue;
            //방문했거나 벽이면 pass
            if(dist2[nx][ny]>=0 || board[nx][ny]=='#') continue;

            dist2[nx][ny] = dist2[cur.X][cur.Y]+1;
            Q2.push({nx, ny});

        }

    }
}

void bfs(){
    while(!Q.empty()){
        auto 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||ny<0||nx>=R||ny>=C) {
                cout << dist[cur.X][cur.Y]+1; return;}
            //방문했거나 벽이거나 불이 나 있으면 pass
            if(dist[nx][ny]>=0 || board[nx][ny]=='#'||board[nx][ny]=='F') continue;

            dist[nx][ny] = dist[cur.X][cur.Y]+1;
            Q.push({nx, ny});

        }

    }
    cout << "IMPOSSIBLE";
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> R>>C;
  int fi, fj;

  for(int i=0; i<R; i++){
      for(int j=0; j<C; j++){
          cin >> board[i][j];
          if(board[i][j]=='J') {
              dist[i][j]=0;
              Q.push({i, j});
          }
          if(board[i][j]=='F'){
              Q2.push({i,j});
              dist2[i][j]=0;
          }
      }
  }

  fire();
  bfs();


  return 0;
}

현재 코드에서 지훈이가 움직이고 불이 한칸만 움직이게 하려면 어떻게 해야할까? bfs 두개를 동시에 돌리는 방법을 모르겠다.

풀이 2 - 정답코드

결국 모르겠어서 정답코드를 확인했다. 정답 코드에서 가장 중요했던 부분은

if(dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y]+1) continue; // 불의 전파 시간을 조건에 추가

이 부분이다. bfs를 동시에 돌리지 않고, 지훈이와 불에 대한 bfs를 따로 돌린 후, 각 dist에 저장된 거리(시간)를 비교하여 불이 지훈이보다 빨리 도달한 경우에는 해당 칸에 지훈이가 갈 수 없는 것이므로 continue를 해준다.

어떻게 이런 생각을...

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

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

char board[1001][1001];  
int dist[1001][1001];
int dist2[1001][1001];


int R, C;
queue<pair<int, int>> Q;
queue<pair<int, int>> Q2;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

    cin >> R>>C;

  for(int i = 0; i < R; i++){
    fill(dist[i], dist[i]+C, -1);
    fill(dist2[i], dist2[i]+C, -1);    
  }

  cin >> R>>C;

  for(int i=0; i<R; i++){
      for(int j=0; j<C; j++){
          cin >> board[i][j];
          if(board[i][j]=='J') {
              dist[i][j]=0;
              Q.push({i, j});
          }
          if(board[i][j]=='F'){
              Q2.push({i,j});
              dist2[i][j]=0;
          }
      }
  }

  //불에대한 bfs
  while(!Q2.empty()){
        auto cur = Q2.front();
        Q2.pop();


        //상하좌우 확인하기
        for(int dir=0; dir<4; dir++){
            int nx = cur.first+dx[dir];
            int ny = cur.second+dy[dir];

            //범위 확인하기
            if(nx<0||ny<0||nx>=R||ny>=C) continue;
            //방문했거나 벽이면 pass
            if(dist2[nx][ny]>=0 || board[nx][ny]=='#') continue;

            dist2[nx][ny] = dist2[cur.X][cur.Y]+1;
            Q2.push({nx, ny});

        }

    }

    //사람에 대한 bfs
    while(!Q.empty()){
        auto cur = Q.front();
        Q.pop();


        //상하좌우 확인하기
        for(int dir=0; dir<4; dir++){
            int nx = cur.X+dx[dir];
            int ny = cur.Y+dy[dir];

            //범위 확인하기-> 범위 밖으로 나가면 탈출 성공
            if(nx<0||ny<0||nx>=R||ny>=C) {
                cout << dist[cur.X][cur.Y]+1; 
                return 0;
            }
            //방문했거나 벽이거나 불이 나 있으면 pass
            if(dist[nx][ny]>=0 || board[nx][ny]=='#') continue;
            if(dist2[nx][ny] != -1 && dist2[nx][ny] <= dist[cur.X][cur.Y]+1) continue; // 불의 전파 시간을 조건에 추가

            dist[nx][ny] = dist[cur.X][cur.Y]+1;
            Q.push({nx, ny});

        }

    }
    cout << "IMPOSSIBLE";

  return 0;
}

• 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

• 충격적인 조건...

• n*m 행렬에서 0은 이동, 1은 벽
• (0,0) -> (n,m)까지 이동하는데 걸리는 최단 경로 출력

풀이

아... 입력받을 때 띄어쓰기가 없는것을 못봐서 엄청 헤맸다 ㅠㅠ

풀이 1 - segmentation fault

board의 인덱스 하나하나에 접근해서 벽을 허물어서 각 케이스에 최단 경로가 얼마가 나오는지 구해서 minimum을 비교한다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

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

char board[1000][1000];
int dist[1000][1000];

int N, M;

void bfs(){
    queue<pair<int, int>> Q;
    Q.push({0,0});
    dist[0][0]=1;

    while(!Q.empty()){
        auto 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||ny<0||nx>=N||ny>=M) continue;
            //방문했거나 벽이면 pass
            if(dist[nx][ny]>0 || board[nx][ny]=='1') continue;

            dist[nx][ny] = dist[cur.X][cur.Y]+1;
            Q.push({nx, ny});

        }

    }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> N >> M;

  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
      cin >> board[i][j];


    //벽 안허물고 bfs 돌리기
    bfs();
    int nonbreak=-1;
    if(dist[N-1][M-1]!=0) nonbreak = dist[N-1][M-1]-1;
    fill(dist[0], dist[0]+1000, 0);

    //벽 허물어서 bfs 돌리기
    vector<int> tmp;
    int flag=0;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(board[i][j]=='1'){
                board[i][j] = '0';
                bfs();
                if(dist[N-1][M-1]==0) board[i][j] = '1';continue;
                tmp.push_back(dist[N-1][M-1]-1); flag=1;
                board[i][j] = '1';
                fill(dist[0], dist[0]+1000, 0);
            }
        }
    }

    if(flag ==0 && nonbreak==-1) cout <<-1;
    else if(nonbreak!=-1){ //벽 뚫는거랑 비교
        cout << min(nonbreak, *min_element(tmp.begin(), tmp.end()));
    }
    else{ //벽 뚫는게 최단시간 (벽 안뚫으면 길이 없음)
        cout << *min_element(tmp.begin(), tmp.end());
    }


  return 0;
}

일단 이 풀이는 for문을 두번 돌려서 시간초과가 나온다.

풀이 2 - 1인 곳만 bfs 돌리기

입력받을 때 1인 곳만 따로 벡터에 담아서 bfs를 돌렸는데 이것도 시간초과가 나온다.. ㅎㅎ

풀이 3 - 정답코드 (dist를 두개 두기)

벽을 부수지 않고 이동하는데 걸리는 시간을 dist[][][0]에 넣고 벽을 하나 부수고 이동하는데 걸리는 시간을 dist[][][1]에 넣는다. 벽을 하나만 부수는 것을 어떻게??? -> 벽을 부수는 경우에는 큐에 {nx, ny, 1}이렇게 마지막 원소에 벽을 부쉈다는 것을 명시해서 저장한다. 이후 위에서 벽을 부수는 여부를 결정하기 전에 마지막 원소인 broken을 확인하여 1이면 벽을 이미 부순 경우이기 때문에 벽을 부수지 않고 bfs를 돌려주고, 0이면 벽을 부수지 않은 경우이기 때문에 벽을 한번 부수고 bfs를 돌려준다.

정리

1. 큐에서 뽑아온 원소의 broken 상태를 확인한다.
2. broken이 1이면 이미 벽을 부순 상태 -> 그냥 bfs 돌려주기
3. broken이 0이면 벽을 부수지 않은 상태 -> 1을 만나면 벽을 부숴주고 해당 노드를 큐에 푸시해주기

int bfs() {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      dist[i][j][0] = dist[i][j][1] = -1; //우선 방문하지 않았음을 명시하기 위해서 -1로 초기화한다. 
  // 첫번째 방문하는 원소는 1로 거리를 세팅한다. 
  dist[0][0][0] = dist[0][0][1] = 1;
  queue<tuple<int, int, int>> q;
  q.push({0,0,0});

  while (!q.empty()) {
    int x, y, broken;
    tie(x, y, broken) = q.front();
    if(x == n-1 && y == m-1) return dist[x][y][broken];
    q.pop();
    int nextdist = dist[x][y][broken] + 1;
    for (int dir = 0; dir < 4; ++dir) {
      int nx = x + dx[dir];
      int ny = y + dy[dir];
      if(OOB(nx, ny)) continue;      
      if (board[nx][ny] == '0' && dist[nx][ny][broken] == -1) {
        dist[nx][ny][broken] = nextdist;
        q.push({nx, ny, broken});
      }      
      // (nx, ny)를 부수는 경우
      if (!broken && board[nx][ny] == '1' && dist[nx][ny][1] == -1) {
        dist[nx][ny][1] = nextdist;
        q.push({nx, ny, 1});
      }      
    }
  }
  return -1;
}

전체 코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

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

char board[1000][1000];
int dist[1000][1000][2];
// dist[x][y][0] : 벽을 하나도 부수지 않고 (x,y)까지 오는데 걸리는 비용
// dist[x][y][1] : 벽을 하나만 부수고 (x,y)까지 오는데 걸리는 비용, (x,y)가 벽이라서 부수는 경우 포함
int n, m;

bool OOB(int x, int y){
  return x < 0 || x >= n || y < 0 || y >= m;
}

int bfs() {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      dist[i][j][0] = dist[i][j][1] = -1;
  dist[0][0][0] = dist[0][0][1] = 1;
  queue<tuple<int, int, int>> q;
  q.push({0,0,0});
  while (!q.empty()) {
    int x, y, broken;
    tie(x, y, broken) = q.front();
    if(x == n-1 && y == m-1) return dist[x][y][broken];
    q.pop();
    int nextdist = dist[x][y][broken] + 1;
    for (int dir = 0; dir < 4; ++dir) {
      int nx = x + dx[dir];
      int ny = y + dy[dir];
      if(OOB(nx, ny)) continue;      
      if (board[nx][ny] == '0' && dist[nx][ny][broken] == -1) {
        dist[nx][ny][broken] = nextdist;
        q.push({nx, ny, broken});
      }      
      // (nx, ny)를 부수는 경우
      if (!broken && board[nx][ny] == '1' && dist[nx][ny][1] == -1) {
        dist[nx][ny][1] = nextdist;
        q.push({nx, ny, 1});
      }      
    }
  }
  return -1;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      cin >> board[i][j];
  cout << bfs();
  return 0;
}

• 각 칸은 금으로 채워져있거나 비어있음
• 한번에 한칸 이동할 수 있고 동서남북상하로 움직일 수 있음
• 바깥면은 모두 금이라 탈출할 수 없음
• L: 층수, R: 행 , C: 열
• 1-30까지만 있음
• 막혀있는 칸: #
• 비어있는 칸: .
• 시작지점: S ,탈출 출구: E
• 입력의 끝은 L, R, C가 모두 0
• 시작지점, 출구는 항상 한개

풀이

BFS 정석 풀이대로 풀었다

1. 빌딩의 상태를 입력받을 board와 시작점에서부터 해당 칸까지의 거리를 저장할 dist 배열을 만든다.
2. 빌딩의 상태를 입력받아 board에 저장한다.
3. 각 빌딩의 칸을 0,0,0인 S에서부터 시작하여 각 칸의 상하좌우앞뒤의 상태를 확인한다.
4. 여기에서 상태란 1) 벽 여부 2) 방문여부 두가지가 된다.
5. 1) 벽이 아니고 2) 방문하지 않은 칸이면 큐에 넣고 해당 칸의 방문거리를 현재 칸의 거리 +1 로 변경하여 거리를 저장한다.
6. 모든 칸을 다 돌고 나면, 해당 빌딩을 탈출하는데 걸린 최단 시간을 출력한다.
   • 최단 시간은 탈출구 E가 적힌 칸의 dist가 된다. 따라서 dist[i-1][j-1][k-1]의 정수가 최단시간이 된다.
   • 만약 dist[i-1][j-1][k-1]안에 적힌 수가 0이면 해당 칸을 방문하지 못했다는 뜻이므로 trapped를 출력한다.

풀이 1 - 33%에서 틀린 코드

#include <bits/stdc++.h>
using namespace std;
int L, R, C;


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

int main (void){
    ios::sync_with_stdio(0);
    cin.tie(0);


    int flag =0; //0: 탈출 불가능, 1: 탈출 가능

    while(1){
        char board[31][31][31];
        int dist[31][31][31];

        cin >> L>>R>>C;
        if(L==0&&R==0&&C==0) break; //셋다 0이면 테스트케이스 끝

        //입력받기
        for(int i=0; i<L; i++){
            for(int j=0; j<R; j++){
                for(int k=0; k<C; k++){
                    cin >> board[i][j][k];
                }
            }
            cout << "\n";
        }

        //돌면서 확인
        for(int i=0; i<L; i++){
            for(int j=0; j<R; j++){
                for(int k=0; k<C; k++){
                    //벽이거나 방문했으면 pass
                    if(board[i][j][k]=='#'|| dist[i][j][k]>0) continue;
                    //첫 원소 넣기
                    queue<tuple<int, int, int>> Q;
                    Q.push(make_tuple(i,j,k));
                    dist[i][j][k]=1;//처음 지점 거리를 1로 설정

                    while(!Q.empty()){
                        auto current = Q.front();
                        Q.pop();
                        //상하좌우위아래 확인
                        for(int dir=0; dir<6; dir++){
                            int nx = get<0>(current)+dx[dir];
                            int ny = get<1>(current)+dy[dir];
                            int nz = get<2>(current)+dz[dir];


                            //범위 확인
                            if(nx<0||ny<0||nz<0||nx>30||ny>30||nz>30) continue;
                            //방문했거나 벽이면 패스
                            if(dist[nx][ny][nz]>0||board[nx][ny][nz]=='#') continue;
                            //둘다 아니면 큐에 푸시해서 방문 리스트에 추가
                            Q.push(make_tuple(nx, ny, nz));
                            dist[nx][ny][nz] = dist[get<0>(current)][get<1>(current)][get<2>(current)]+1;

                        }



                    }
                }
            }
        }

        //돌고나서 확인
        if(dist[L-1][R-1][C-1]==0){
            cout<< "Trapped!\n";
        }
        else cout<< "Escaped in "<< dist[L-1][R-1][C-1]-1<<" minute(s).";

        //빌딩, 거리 초기화
        // fill(board[0], board[0]+29, 0);
        // fill(dist[0], dist[0]+29, 0);

    }


    return 0;
}

왜 33%에서 틀릴까?

1) 출력 오류 -> 아님

• 출력 오류일 줄 알고 board를 입력받는 부분에서 \n를 출력하는 부분을 빼줬다.
• 아니었음

2) 범위 확인 오류 -> 아닌듯 우선 테스트 케이스는 잘 맞는다.. 출력 오류도 아니고.. 범위 확인을 할 때 0보다 작거나 30보다 크면 continue를 하게 해뒀다. 그런데 생각해보니 건물은 30칸까지만 사용할 수 있다. 조건에 L, R, C가 1부터 30까지만 가능하다. 즉 배열에서 인덱스 0부터 29까지만 사 용한다는 것이다. 그러면 다음 인덱스가 30에 접근하려고 하면 안된다. 왜냐, 그곳은 없는 인덱스이니깐!! 따라서 nx>30을 nx>=30으로 변경해줬다. 다시 제출하니.. 여전히 33%에서 틀린다.

3) 확인하는 칸의 범위 -> 아님 for문을 3번 돌려서 각 칸에 접근했었는데 모든 칸의 거리를 구하는 것이 아니라 단순히 마지막 칸에 도달하는데 얼마의 시간이 드는지만을 구하는 문제이기 때문에 for문을 3번 돌릴 필요 없이 시작 지점만 큐에 넣고 큐가 빌때까지만 돌려주면 된다. 시간복잡도가 월등히 줄어듦

왜 틀렷을까..................

3)까지 수정한 풀이

#include <bits/stdc++.h>
using namespace std;
int L, R, C;


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

int main (void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    while(1){
        //테스트케이스를 돌떄마다 초기화
        char board[31][31][31];
        int dist[31][31][31] ={0};

        cin >> L>>R>>C;
        if(L==0&&R==0&&C==0) {
            // cout << "is breaked\n";
            break; return 0;
        } //셋다 0이면 테스트케이스 끝


        //입력받기
        for(int i=0; i<L; i++){
            for(int j=0; j<R; j++){
                for(int k=0; k<C; k++){
                    cin >> board[i][j][k];
                }
            }
            //cin << "\n"; //각층에는 빈줄 존재
        }

        //첫 원소 넣기
        queue<tuple<int, int, int>> Q;
        Q.push(make_tuple(0,0,0));
        dist[0][0][0]=1;//처음 지점 거리를 1로 설정

        while(!Q.empty()){
            auto current = Q.front();
            Q.pop();
            //상하좌우위아래 확인
            for(int dir=0; dir<6; dir++){
                int nx = get<0>(current)+dx[dir];
                int ny = get<1>(current)+dy[dir];
                int nz = get<2>(current)+dz[dir];


                //범위 확인
                if(nx<0||ny<0||nz<0||nx>=L||ny>=R||nz>=C) continue;
                //방문했거나 막혀있는 칸이면 패스
                if(dist[nx][ny][nz]>0||board[nx][ny][nz]=='#') continue;
                //둘다 아니면 큐에 푸시해서 방문 리스트에 추가
                Q.push(make_tuple(nx, ny, nz));
                dist[nx][ny][nz] = dist[get<0>(current)][get<1>(current)][get<2>(current)]+1;

            }
         }

        //돌고나서 확인
        if(dist[L-1][R-1][C-1]==0){
            cout<< "Trapped!\n";
        }
        else cout<< "Escaped in "<< dist[L-1][R-1][C-1]-1<<" minute(s).\n";


    }


    return 0;
}

33%에서 틀린 이유!

시작지점이 항상 0,0이 아니다!!!

문제에 명시되어있는데 테스트케이스를 보고 간과했다.. 당연히 0,0부터 시작하는줄..

?? 문제 이해가 안간다

풀이 1 -31%에서 틀린 코드

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

#define X first
#define Y second

int F, S, G, U, D;
int dist[1000001];

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> F>>S>>G>>U>>D;

  //10층짜리 건물 /S층에서 G층까지 가야함
  //위로 2층, 아래로 1층
  int dx[2] ={U, D*-1};

  queue<int> Q;
  dist[S]=0;
  Q.push(S);

  while(!Q.empty()){
      int cur = Q.front();
      Q.pop();

      for(int dir=0; dir<2; dir++){
          int next = cur+dx[dir];

          //범위 확인
          if(next<=0 || next>F) continue;
          //방문여부 확인
          if(dist[next]>0) continue;

          dist[next] = dist[cur]+1;
          Q.push(next);
      }
  }

  if(dist[G]==0) cout <<"use the stairs";
  else cout << dist[G];

}

현재 동호가 있는 층수와 스타트 링크가 있는 층수가 같은 경우를 못걸러준다.

풀이 2 - 시작점과 끝점이 같을 경우를 고려한 풀이 66%에서 틀린 코드

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

#define X first
#define Y second

int F, S, G, U, D;
int dist[1000001];

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> F>>S>>G>>U>>D;

  //10층짜리 건물 /S층에서 G층까지 가야함
  //위로 2층, 아래로 1층
  int dx[2] ={U, D*-1};

  //출발점 저장
  queue<int> Q;
  dist[S]=0;
  Q.push(S);

  if(S==G) {cout << 0; return 0;}

  while(!Q.empty()){
      int cur = Q.front();
      Q.pop();

      for(int dir=0; dir<2; dir++){
          int next = cur+dx[dir];

          //범위 확인
          if(next<=0 || next>F) continue;
          //방문여부 확인
          if(dist[next]!=0) continue;

          dist[next] = dist[cur]+1;
          Q.push(next);
      }
  }

  if(dist[G]==0) cout <<"use the stairs";
  else cout << dist[G];

}

음.. 출발한 후 출발점을 다시 지나가는 경우를 고려하지 않음

풀이 3 - 맞은 코드

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

#define X first
#define Y second

int F, S, G, U, D;
int dist[1000001];

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> F>>S>>G>>U>>D;

  //10층짜리 건물 /S층에서 G층까지 가야함
  //위로 2층, 아래로 1층
  int dx[2] ={U, D*-1};

  //출발점 저장
  queue<int> Q;
  dist[S]=1;
  Q.push(S);

  if(S==G) {cout << 0; return 0;}

  while(!Q.empty()){
      int cur = Q.front();
      Q.pop();

      for(int dir=0; dir<2; dir++){
          int next = cur+dx[dir];

          //범위 확인
          if(next<=0 || next>F) continue;
          //방문여부 확인
          if(dist[next]!=0) continue;

          dist[next] = dist[cur]+1;
          Q.push(next);
      }
  }

  if(dist[G]==0) cout <<"use the stairs";
  else cout << dist[G]-1;

}

적록색약과 굉장히 비슷한 문제였다.

1. 지도의 상태를 나타내는 board[][], 방문 여부를 나타내는 isVist[][]
2. 시작점 큐에 넣기

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

#define X first
#define Y second
int board[26][26];
int isVisit[26][26];

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

int N;
vector<int> cpx;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N;

  string lines;

  for(int i=0; i<N; i++){
      cin >> lines;
      for(int j=0; j<N; j++){
          board[i][j]= lines[j]-'0';
      }
  }


  for(int i=0; i<N; i++){
      for(int j=0; j<N; j++){
          if(isVisit[i][j]!=0 || board[i][j]==0) continue;

          queue<pair<int, int>> Q;
          Q.push({i, j});
          isVisit[i][j]=1;

          int houses=1;
          while(!Q.empty()){
              auto cur = Q.front();
              Q.pop();

              //상하좌우 확인
              for(int k=0; k<4; k++){
                  int nx = cur.X+dx[k];
                  int ny = cur.Y + dy[k];

                  if(nx>=N||nx<0||ny<0||ny>=N) continue;
                  //다음 노드를 방문했거나 현재와 다른 단지인 경우
                  if(isVisit[nx][ny]==1 || board[nx][ny]==0) continue;

                  isVisit[nx][ny]=1;
                  Q.push({nx, ny});
                  houses++;
              }
            }
            cpx.push_back(houses);
      }
  }

  sort(cpx.begin(), cpx.end());
  cout << cpx.size()<<'\n';
  for(auto c:cpx){
      cout << c <<'\n';
  }

}

https://may9noy.tistory.com/365 아 또 안돼 왜

또 무한 로딩이 된다 찾아보니 jenkins에서 실행시 마지막 line에서 return 되는게 없어 무한 로딩이 된다고 한다. 근데 실행은 정상이었다는데 내거는 실행도 안된다. 대체 뭐가 문제일까 진짜

..

서버가 아예 먹통이 되어서 또 강제로 중지하고 재시작해줬다. 진 짜 짜 증 나

https://devroach.tistory.com/23

• Docker Root Dir: /var/lib/docker

드뎌 빌드 성공!!

webhook 설정 후 빌드가 잘 되길래 ngrok는 따로 설치하지 않았다.

빌드 서버 배포

jenkins 관리 > 플러그인 관리 > publish over ssh 설치 설치 후 jenkins 관리 > 시스템 설정 > publish over ssh 란에 정보를 입력한다.

정보를 입력하기 위해서는 ssh 접속을 위한 key pair를 생성해야 하는데 아래 명령어로 생성 가능하다.

ssh-keygen -t rsa -b 2048 -C "<comment>"-f key-03

key-01 이라는 이름으로 키값이 생성되었다.

cat key-01 해당 키 값을 복사해서 jenkins 정보란에 입력한다.

• Name : 본인이 지정하고 싶은 이름 chevita-Backend
• Host name: aws 서버 ip주소
• Username: ec2-user
• Remote Directory: pwd로 본인의 경로 찾기 : /home/ec2-user

공개키

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQDEGRx1gmAS8k0WChudQmxL4Ze1Nb+ZGTcDqRRcjPfuRW9fXHTvdCfQcQzS+NEgGBtaggKldZ4jgMg89ZnRBsQ3fdkieoxizsf0xEtyDbTpDTwnRsZ/H4JTJKOUcW/AcDN6Fk+AOqsLdGBF1oZqNO9sW1zp2YTybbMFUTr26HvjUW6pnaONZR0LVr1DPpMm/SEnOQqcbAFNVQt2dbg5JUFVhhUw2RYnAmD41St+7/MMOmz7DE7f50XESVL/MXS2c5nyvxZEG4uh+Z6R+qxlhAxeDtpKRvYcY5nM/q7FV7KfyrEHsuceGwFrKfmqHBJ/PchGdAKJRFB1KU7fDT7Hwa2j

여기서 궁금한 점.. 나는 이미 ec2 amazon linux server가 있는데 새로 서버를 생성해야하나?? 이미 있는 서버를 배포할 수는 없나? 현재까지의 로직

1. ec2로 서버 구축
2. ec2에 jenkins 설치
3. github에 새로운 코드가 push되면 webhook으로 jenkins가 자동인식해서 자동 빌드

--TODO!-- 4. 빌드된 내용을 서버로 배포해야함 (어떻게??) https://blog.jiniworld.me/94

기존에 서비스 중이었던 앱을 새로 빌드한 애플리케이션으로 교체하여 실행시키려면

1. 서비스 중이던 애플리케이션 종료
2. 백업 폴더 비우기
3. 백업 폴더에 기존 애플리케이션 복사
4. deploy된 최신 빌드 애플리케이션 복사
5. 애플리케이션 실행

기존 애플리케이션을 백업할 필요가 없다면 2,3번 대신 기존 애플리케이션을 삭제하는 과정을 거치면 된다.

1. Post build task 플러그인 설치

post build task 플러그인은 빌드가 성공했을 경우에만 후 조치로 기존 앱을 종료시키고 새로운 앱으로 교체 및 시작하는 과정을 진행하도록 도와주는 역할을 한다. 플러그인 매니저에서 설치 가능! 나는 이미 설치를 해뒀기 때문에 건너뛰겠다.

2. 빌드 후 조치 - Post build task 설정 추가

다시 프로젝트로 돌아가서 프로젝트 구성을 변경하자 빌드 후 조치 > Post build task 빌드 성공 시 콘솔에 출력하는 결과를 작성하자

1. 빌드 성공시 Log text: BUILD SUCCESS operation: --AND-- SCRIPT: echo "Build 성공"
2. 빌드 실패시 Log text: BUILD FAILURE operation: --AND-- SCRIPT: echo "Build 중 에러 발생"

3. demo 앱 배포 후 재시작

기존에 서비스 중이었던 애플리케이션을 새로 빌드한 애플리케이션으로 교체하여 재실행시키는 script를 작성해보자!

jenkins home directory를 확인해보자 jenkins> jenkins 관리 > 시스템 설정 부분 > jenkins_home 디렉토리 확인 가능

ssh로 접근 불가 오류... 다시 winscp로 접속하려 했더니 어제까지 멀쩡하게 접속되던게 오늘 갑자기 서버 거부가 뜬다.. 어제 putty에서 키를 새로 발급한 것 때문에 권한 문제가 생긴듯 하다.. 그래서 새로운 키를 발급해서 ec2에 ssh로 접속해볼 예정이다.. 프라이빗 키 교체하기

이 글은 해당 aws 사용설명서를 참고하여 작성했습니다.

1. 새 키 페어 생성

1. 아마존 인스턴스 탭에 들어가서 네트워크 및 보안 > 키페어 로 이동
2. 오른쪽 상단에서 새로운 키페어 생성 이름: chevita-Backend 키페어 유형: rsa 프라이빗 키 파일 형식: pem 새로 생성한 키를 바탕화면에 저장했다.

2. 원본 인스턴스와 루트 볼륨에 대한 정보 가져오기

키 페어를 변경하려면 기존 인스턴스의 정보가 필요하다.

1. 기존 인스턴스의 세부정보 탭에서 인스턴스 id와 ami id를 기록한다. 기존 인스턴스: i-01d9db61b33510f91 AMI 이름 : amzn2-ami-kernel-5.10-hvm-2.0.20221103.3-x86_64-gp2

2. 네트워킹 탭에서 가용 영역을 기록한다. ap-northeast-2c

3. 루트 디바이스 이름: /dev/xvda 블록 디바이스 이름에 매치되는 볼륨 id 기록: vol-0354dca7f523c7676

3. 원본 인스턴스 중지

1. 인스턴스 상태 > 인스턴스 중지

4. 임시 인스턴스 시작

1. 임시 인스턴스를 실행합니다.

2. 탐색 창에서 Instances(인스턴스)를 선택한 후 Launch instances(인스턴스 시작)를 선택합니다.

3. 이름 및 태그(Name and tags) 섹션에서 이름(Name)에 임시(Temporary)를 입력합니다.

4. 애플리케이션 및 OS 이미지(Application and OS Images) 섹션에서 원본 인스턴스를 시작하는 데 사용한 것과 동일한 AMI를 선택합니다. 이 AMI가 표시되지 않는 경우 중지된 인스턴스에서 사용 가능한 AMI를 만들 수 있습니다. 자세한 내용은 Amazon EBS-backed Linux AMI 생성 섹션을 참조하세요.

5. 인스턴스 유형(Instance type) 섹션에서 기본 인스턴스 유형을 유지합니다.

6. 키 페어(Key pair) 섹션의 키 페어 이름(Key pair name)에서 사용할 기존 키 페어를 선택하거나 새로 하나 생성합니다.

   • 새로만든 chevita-Backend 키로 설정해줬다.

7. 네트워크 설정(Network settings) 섹션에서 편집(Edit)을 선택한 다음 서브넷(Subnet)에 대해 원본 인스턴스와 동일한 가용 영역에 있는 서브넷을 선택합니다.

   • 기존 인스턴스 세부 정보에서 subnet id를 확인할 수 있다. 해당 subnet id를 copy해서 똑같은 id로 설정해준다.

8. 요약(Summary) 패널에서 시작(Launch)을 선택합니다.

5. 원본 인스턴스에서 루트 볼륨을 분리하고 임시 인스턴스에 연결

1. 탐색 창 > 볼륨 > 원본 인스턴스에 대한 루트 디바이스 볼륨 원본 인스턴스에 대한 루트 디바이스 볼륨 분리
2. 볼륨 > 작업 > 볼륨 연결

5단계까지 진행 https://docs.aws.amazon.com/ko_kr/AWSEC2/latest/UserGuide/TroubleshootingInstancesConnecting.html#step-1-create-new-key-pair