22.03.29. 풀었던 문제들

* stringstream, istringstream 정리하기

* dp

* 빠른 피보나치 구하기(고속행렬곱)

​

programmers lv. 2

​

1. 피보나치 수

기본적으로는 db로 풀면 된다. 시간복잡도가 올라가면, 고속 행렬 곱으로 풀면 된다.

​

​

2. 최솟값 만들기

규칙 찾기 문제다.

​

​

3. 최댓값과 최솟값

string parsing 문제이다. 그냥 for문 돌려서 풀 수도 있지만.. 아무래도 stringsteam을 공부하긴 해야 겠다. istringstream도 한번 봐 보자.

​

​

4. 다음 큰 숫자

2진수에서 1의 개수를 세는 방법이다. 이것도 정리해 보자.

​

​

5. 땅따먹기

되게 유명한 DP 문제다.

land[i]를 보고 있을 때, land[i+1]에서 최댓값을 뽑기 위해서는 land[i]에서 고른 index를 제외한 값들 중 최댓값을 골라야 한다. 그러므로 점화식은

land[i][0] = max(land[i][1], max(land[i][2], land[i][3]))

이 된다. 마찬가지로 land[i][1], ... , land[i][3]도 동일하다. 이렇게 점화식을 세우고 dp 돌리면 된다.

​

​

6. 숫자의 표현

DP로 풀 수도 있고, two-pointer로도 풀 수 있다.

​

​

7. [3차] n진수 게임

string + 규칙 찾기 문제.

* 진법 전환 시 꿀팁 : 아래처럼 10진수를 넘어가는 경우, 미리 digit string을 선언해 두고 나머지 값에 해당하는 값을 찾아오면 된다.

string toNotation(int number, int notation){
    if(number == 0) return "0";
    string digit = "0123456789ABCDEF";
    string result = "";
    while(number){
        result = digit[number % notation] + result;
        number /= notation;
    }
    return result;
}

 

8. 올바른 괄호

예전이었으면 stack으로 풀었겠지만... 이제 나도 발전했다. stack 쓰지 않고 숫자로 처리해버렸다.

​

​

9. 가장 큰 정사각형 찾기

dp로 푸는 문제다. 나중에 한번 더 풀어보자! 이 문제는 조곰 모호하다.