HackerRank_Medium_Common Child && 스택의 비밀

https://www.hackerrank.com/challenges/common-child/problem?isFullScreen=true

Common Child | HackerRank

 

---

 

두개의 같은 길이의 문자열을 주어지고 이 문자열의 순서를 바꾸지 않고

두 문자열에서 공통으로 가지고 있는 문자들의 집합 중 제일 긴 문자의 집합을 구하는 문제이다. 

즉,  Longest Cmmon Substring (LSC 최장 공통 부분 수열)을 찾는 문제다! 

 

LSC를 구하기 위해 2차원 백터를 사용하였다. 

처음에는 2차원 배열을 만들어서 문제를 풀었는데 답이 다르거나 Segment Fault 오류가 발생하였다. 

그 이유는 맨 마지막에 설명하겠다. 

 

Hackerrank는 main 함수가 있고 main 함수에서 문제를 해결하는 함수를 호출한다. 

그리고 정답을 그 함수 안에 구현 하는 것이다. 

#include <bits/stdc++.h>

using namespace std;

/*
 * Complete the 'commonChild' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. STRING s1
 *  2. STRING s2
 */

int commonChild(string s1, string s2) {
    
	vector<vector<int>> common(s1.length()+1, vector<int>(s2.length()+1, 0));
    
    for(int i = 1; i <= s1.length(); ++i)
    {
        for(int j = 1; j <= s2.length(); ++j)
        {
            if(s1[i-1] == s2[j-1])
            {
                common[i][j] = common[i-1][j-1] + 1;
            }
            else
            {
                common[i][j] = max(common[i-1][j], common[i][j-1]);
            }        
        }
    }
    return common[s1.length()][s2.length()]; 
}
int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string s1;
    getline(cin, s1);

    string s2;
    getline(cin, s2);

    int result = commonChild(s1, s2);

    fout << result << "\n";

    fout.close();

    return 0;
}

 

 

2차원 백터는 각 문자열을 비교하고 그 값을 저장한다. 

commom[0][0]은 0인 상태로 index 1 부터 비교한 값을 저장하는데 

같은 문자라면 1을 더해준다. 

이때 더해줄때 대각선 방향의 값을 더해주는데 처음엔 잠시 이해가 되지 않았다. 

    if(s1[i-1] == s2[j-1])
    {
        common[i][j] = common[i-1][j-1] + 1;
    }

 

같은 문자열을 찾았을 때 common[i - 1][j - 1]을 보는 것은 

"NO" 와 "S" 에서 같은 문자가 있었는지 보는 것이다. 

"NO" 와 "S" 에서 같은 문자의 수와 "NOH" 와 "SH" 에서 같은 문자의 수를 합한 것이다!

 

그리고 같은 문자가 아닐 때는 둘 중에 큰 값으로 하는 데 이는 또 표를 그려서 보면 이해하기 쉽다! 

    else
    {
        common[i][j] = max(common[i-1][j], common[i][j-1]);
    }

 

S1[7] == 'N'과 S2[4] == 'A'가 같지 않다. 

이때는 이전값과 윗값을 비교하는데 마찬가지로 "NOH'와 "SHINCHAN"에서 공통 부분 수열인 "NH"와 

"NOHA"와 "SHINCHA"의 공통 부분 수열인 "NHA" 중 더 긴 값을 가져오는 것이다. 

 

확실히 잘 이해가 되지 않으면 하나하나 그려보고 적어가면서 이해하면 좋은 거 같다. 

 

---

 

처음에 문제를 풀때는 int의 2차원 배열을 만들었었다. 

이렇게 하니 몇문제는 오답이 나왔고 몇 문제는 맞았으며 또 나머지 몇 문제는 Segment Fault가 발생하였다. 

int commonChild(string s1, string s2) {
    
    //vector<vector<int>> common(s1.length()+1, vector<int>(s2.length()+1, 0));
    
    int common[s1.length()+1][s2.length()+1] = {0};
    .
    .
    .
    }

 

 

내가 만든 배열은 스택에 선언한 배열이다. 

그렇기 때문에 컴파일러가 할당할 스택 공간의 양을 알아야 하고 런타임에 계산된 값을 사용할 수 없다고 한다. 

 

그래서 int [5001][5001] common = {0}; 으로 해보았는데 모든 문제에서 segment fault가 발생했다. 

미리 크기를 정해줬는데 왜일까 싶었다. 

그 이유는 이렇하면 스택에 선언되기 때문이다! 

 

스택은 한정된 메모리 공간을 가진다. 

int 는 일반적으로 4 byte (= 32-bit) 인데 배열로 선언한다면 

5001 * 5001 * 4 = 100,040,004 byte = 97,695.31640625 KB = 95.405582427978515625 MB로 

int [5001][5001]은 약 95MB가 된다. 

 

나는 Visual Studio Code를 사용해서 컴파일러마다 스택의 크기를 설정할 수 있지만 기본값을 볼순없다. 

Visual Studio에서는 Default 값이 1MB로 예약되있다 한다. 

그러다보니 95MB는 스택에겐 굉장히 큰 값이다. 

 

동적으로 크기를 정해야하는 게 있다면 편하게 vector를 사용하자. 

 

 

https://learn.microsoft.com/ko-kr/cpp/cpp/arrays-cpp?view=msvc-170

배열 (C++)