땡땡

문제 설명

최대공약수

<유클리드 호제법>

2개의 자연수의 최대공약수를 구하는 알고리즘.

2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 c라고 하면(단,a>b), a와 b의 최대 공약수는 b와 c의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지를 구하고, 이 과정을 반복하여 나머지가 0이 되었을때 나누는 수가 a와 b의 최대공약수이다.  

int GCD(int a, int b)
{
	int c;
	while (b != 0)
	{
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}

최소공배수

a * b = GCD(a, b) * LCM(a, b)

-> LCM(a,b) = GCD(a,b) / a*b

int LCM(int a, int b)
{
	return a * b / GCD(a, b);
}

코드

//최대 공약수
int GCD(int a, int b)
{
	int c;
	while (b != 0)
	{
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}

//최소 공배수
int LCM(int a, int b)
{
	return a * b / GCD(a, b);
}

int solution(vector<int> arr) 
{
	int answer = arr[0];

	for (int i = 1; i < arr.size(); i++)
	{
		answer = LCM(arr[i], answer);
	}
	return answer;
}

문제 설명

길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다.
배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면

• A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
• A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
• A에서 세번째 숫자인 2, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)

즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 A, B의 크기 : 1,000 이하의 자연수
• 배열 A, B의 원소의 크기 : 1,000 이하의 자연수

입출력 예

코드

#include <algorithm>

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;

    sort(A.begin(), A.end());                 // 오름차순 정렬
    sort(B.begin(), B.end(), greater<int>()); // 내림차순 정렬
    
    for(int i = 0; i < A.size(); i++)
    {
        answer += A[i] * B[i] ;
    }
    
    return answer;
}

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

입출력 예

코드#1

bool solution(string s)
{
    bool answer = false;
    int size = s.size();
    int check = 0;
    
    for(int i = 0 ; i< size; i++)
    {
        if(s[i] == '(')  check++;
        if(check > 0)
        {
            if(s[i] == ')')  check--;
        }
    }
    
    //첫 시작이'(' , 끝이 ')'
    if(check == 0 && s[0] == '(' && s[size-1] == ')') answer = true;
    
    return answer;
}

코드#2 : Stack 활용

#include <stack>

bool solution(string s)
{
    stack <char> stk;
    bool answer = false;
    int size = s.size();
    
    for(int i = 0; i < size; i++)
    {
        if(s[i] == '(') stk.push(s[i]);
        else 
        {
            if(!stk.empty() && stk.top() == '(') stk.pop();
            else                                 stk.push(s[i]);
        }
    }
    
    if(stk.empty()) answer = true;

    return answer;
}

1. 생성

헤더 파일 : <string>

①  string str("abcd");  // 바로 생성

②  string str1;                 // 선언 후 값 주기

      str1 = "abcd";

③  string str2(str1);

* 문자열 끝에 null이 들어가지 않는다.

2. 인자 접근

① str.at(index);

해당 위치(index)에 해당하는 문자를 반환한다. index가 범위를 벗어나면 예외 리턴.

함수 예시 : str.at(0);    // "Hello" -> 'H'를 리턴

② str.operator[index]

일반 배열처럼 대괄호를 이용해서 인자에 접근 가능하다. 

해당 위치(index)에 해당하는 문자를 반환한다.

*at과 다른 점 : index(인덱스) 범위를 검사하지 않기 때문에 at 함수보다는 빠르다.

하지만 예외를 리턴하지 않는다. 

함수 예시: str[0];    // "Hello" -> 'H'를 리턴

③ str.front();

맨 앞 인자를 반환한다.

함수 예시: str.front();    // "Hello" -> 'H'를 리턴

④ str.back();

맨 뒤 인자를 반환한다.

함수 예시: str.back();    // "Hello" -> 'o'를 리턴

3. size 관련 함수

① str.size();

사이즈를 반환한다.

함수 예시: str.size();    // "Hello" -> 5를 리턴

② str.length();

길이를 반환한다. (size()와 같다고 생각하면 된다.)

함수 예시: str.length();    // "Hello" -> 5를 리턴

③ str.capacity();

할당된 메모리 크기(bytes)를 반환한다.

메모리 할당을 size(길이)에 대비해서 여유롭게 한다.

size(길이)가 capacity(메모리)를 넘게 될 때 새롭게 더 큰 capacity(메모리)를 할당한다.

함수 예시 : str1.capacity();    // "HelloHello" size(길이)는 10, capacity(메모리)는 15

함수 예시 : str2.capacity();    // "HelloHelloHelloH" size(길이)는 16, capacity(메모리)는 31

④ str.resize(n); , str.resize(n,c);

string을 n만큼의 크기로 만든다. 

만약 그 크기가 원래 사이즈보다 작다면, 남은 스트링을 버린다.  

만약 그 크기가 원래 사이즈 보다 크다면, 빈 공간으로 남은 공간을 채운다.

만약 c를 사용한다면 남은 공간을 c로 채울 수 있다.

함수 예시 : str.resize(5)          // "HelloHello" -> "Hello" size는 5

함수 예시 : str.resize(6)          // "Hello" -> "Hello " size는 6, 제일 뒤에 빈칸

함수 예시 : str.resize(10, 'v') // "Hello" -> "Hello vvvv" 

⑤ str.shrink_to_fit();

string 길이에 비해 낭비되고 있는 capacity(메모리)를 줄이는 함수이다.

함수 예시 : str.resize(5);                // "HelloHelloHelloH" 

                                                                  > "Hello" size(길이)는 5지만  capacity(메모리)는 여전히 31

함수 예시 : str.shrink_to_fit();    // "Hello"처럼 size(길이) 5가 된 string의 capacity(메모리)에

                                                                    알맞게 str의 capacity(메모리)가  31->15으로 줄어든다.

⑥ str.reserve(n);

string을 넣기 전, 미리 n만큼의 size(길이)에 맞는 capacity(메모리)를 할당하는 함수이다.

⑦ str.clear();

 스트링에 들어있는 문자열을 지우는 함수이다. 

이때, size와 length는 0이 되고, capacity는 그대로 남게 됩니다.

함수 예시 : str.clear();    // "Hello" -> "" 

                                                    size와 lenth는 0이 되고, capacity(메모리)는 15 그대로 이다.

                                                    (메모리 해제X)

⑧ str.empty();

스트링이 비었는지 확인하는 함수이다. 비었으면 true를 반환한다. 

비었음의 기준은 size, length가 0인 것 이다. capacity(메모리)와는 관계가 없다.

함수 예시 : if(str.empty()) { return true; }  

4. 

① str.c_str();

C++의 string 문자열을 C의 문자열로 변경해주는 함수이다.

함수 예시 : const char* arr = str.c_str();    // "HelloHello" -> "HelloHello\0"로 반환.

② str.substr(); , str.substr(index); , str.substr(index, len);

string을 잘라서 반환하는 함수이다.

함수 예시 : str.substr();            // "HelloHello" 그대로 반환.

함수 예시 : str.substr(6);         // "ello"를  반환. index 5 번째 인자부터 끝까지의 string을 반환.

함수 예시 : str.substr(6, 1);    // "e"를 반환. 5번째 인자부터, 1의 길이만큼 string을 반환.

③ str.replace(index, len, str2);

string의 index위치에서 len 길이까지의 범위를 매개변수로 들어온 str2 전체로 대체 하는 함수이다.

함수 예시 : str1.replace(5, 2, str2);

// "HelloHello"의 5번째 인자에서부터 2개를 str2("AAAA")로 대체한다.

     -> "HelloAAAAllo" 로 변경
함수 예시 : str1.replace(str1.find("AAAA"), 2, "He");

// "HelloAAAAllo"에서 "AAAA"를 찾아 "He"로 대체한다.

     -> "HelloHello" 로 변경

④ str.compare(str2); 

매개변수로 들어온 str을 비교해서 같으면 0을 반환하고, 다르면 0이 아닌 값을 반환하는 함수이다.

매개변수로 들어온 스트링의 값보다 작을때(사전순 빠를때) 음수(0보다 작은값)를 반환하고 ,

매개변수로 들어온 스트링의 값보다 클때(사전순 느릴때) 양수(0보다 큰값)를 반환한다.

함수 예시 : str1.compare(str2);

// str1("Hello"), str2("HiHi")는 같지 않기 때문에 0이 아닌 값을 반환하고,

     H까지는 둘이 똑같고, 그다음 str1의 "e"와, str2의 "i"를 비교한다.

    이때, "e"가 "i"보다 사전상 더 앞선글자이기 때문에 str1이 더 작은 글자가 된다.

    그렇기 때문에 음수(0보다 작은값)를 반환하게 된다.

함수 예시 : str1.compare("Hello");

// str1("Hello")와 "Hello"는 같기 때문에 0을 반환한다.

함수 예시 : str1.compare(0, 1, str2);

// str1("Hello")의 0번째 인덱스 부터 길이가 1인 문자열 "H"와 

     str2("HiHi) 를 비교한다. 두 문자열이 다르기 때문에 0이 아닌 수를 반환합니다.

함수 예시 : str1.compare(0, 1, str2, 0, 1);   

// str1("Hello")의 0번째 인덱스 부터 길이 1인 문자열 "H"와 

     str2("HiHi")의 0번째 인덱스 부터 길이 1인 문자열 "H"를 비교한다.

     비교할 문자열이 같기 때문에 0을 반환한다.

⑤ str1.copy(arr, len, index);

복사를 하는 함수이다.

함수 원형 : size_t copy(char* arr, size_t len, size_t index = 0) const;

첫번째 매개변수 : char* 인걸 보면, C언어의 문자열(배열타입)을 받습니다. 

두번째 매개변수 : 복사할 문자열의 길이

세번째 매개변수 : 복사를 시작할 위치

return 값 :  실제로 복사된 길이, arr의 길이를 반환합니다.

함수 예시 :  char arr[10];                                          // 문자열을 복사해서 넣을 빈 배열을 만듭니다.

                      int arrLen = str1.copy(arr, 3, 2);    // index 2부터 3의 길이만큼 복사 -> "Hello"   

                                                                                             실제로 복사된 길이 3 반환

                      arr[arrLen] = '\0';                                 // C의 문자열의 끝에는 '\0'

⑥ str.find(str2); , str.find(str2, index);

매개변수로 들어온 문자열과 일치하는 게 있는지 확인하는 함수이다.  

만약에 일치하는게 있다면, 일치하는 부분의 첫번째 순서(index)를 반환한다.

두번째 매개변수로 들어온 index는 찾을 위치.

함수 예시 : str1.find("Hello");         // str1("HelloHello") 와 "Hello"를 비교

                                                                      -> 일치하는 부분의 첫번째 순서(index)인 0을 반환

함수 예시 : str1.find("Hello", 5);    // str1("HelloHello") 와 "Hello"를 5번째 인자부터 비교

                                                                       -> 일치하는 부분의 첫번째 순서(index)인 5를 반환

⑦ str.push_back(c);

함수를 호출하는 스트링의 맨뒤에 문자 c를 더하는 함수 이다.

함수 예시 : str.push_back('a');      //"HelloHello" -> "HelloHelloa"

⑧ str.pop_back();

함수를 호출하는 스트링의 맨뒤에 있는 문자 하나를 없애는 함수 이다.

함수 예시 : str.pop_back();            //"HelloHelloa" -> "HelloHello"

5. iterator 종류

① str.begin();

문자열의 첫 번째 문자를 가리키는 반복자(iterator 포인터)를 반환

② str.end();

문자열의 마지막의 바로 다음을 가리키는 반복자(iterator 포인터)를 반환

5. 기타 등등

① swap(str1, str2)

str1과 str2를 바꾸는 함수. 서로 참조(reference)를 교환해서 스왑을 한다.

함수 예시 : swap(str1, str2);       // str1("Hello") ,str2("HiHi") -> str1("HiHi"), str2("Hello")

② operator+

이어붙이기

함수 예시 : str1 += str2;                // str1("HiHi") += str2("Hello") = str1("HiHiHello") 

*[개발자 지망생]님 블로그를 보고 공부하며 제가 보기 편하게 정리 한 글 입니다.*

출처: https://blockdmask.tistory.com/338 [개발자 지망생]

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

• n은 2 이상 100,000 이하인 자연수입니다.

입출력 예

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

코드

int solution(int n) {
    int fibo[100001];
    int answer = 0;
    
    fibo[0] = 0;
    fibo[1] = 1;
    
    for(int i = 2 ; i<= n; i++)
    {
        fibo[i] = fibo[i-1] + fibo[i-2];
        fibo[i] = fibo[i] % 1234567;
    }
    
    answer = fibo[n];
    
    return answer;
}