[TIL] 24.03.06 알고리즘, 2주차 개인과제

1. 알고리즘 문제 해결

 

 

가장 긴 증가하는 부분 수열(백준 11053):

 줄여서 LIS로 익히 알려진 그 문제이다. 여기서는 주어지는 수열의 크기가 최대 1,000개이기 때문에 O(n^2)의 DP로 간단하게 구현할 수 있다. 이 때 DP 배열이 가지는 값은, 해당 인덱스의 값을 수열의 가장 끝이라고 생각할 때 얻을 수 있는 LIS의 길이이다. 그 값을 얻기 위해서는 앞의 인덱스들에 대해 DP 배열을 모두 탐색보아야 하므로, 결과적으로 O(n^2)이 된다. 

 내 기억으로는 이진탐색을 활용해서 O(n log n)으로 해결되는 문제였던걸로 기억하는데, 취약한 DP 문제들을 충분히 연습하고 나면 찾아서 풀어봐야겠다.

 

#include <iostream>
#include <vector>

using namespace std;

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    
    vector<int> arr(n);

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

    vector<int> dp(n);
    int lis = 1;
    
    for(int i=0; i<n; i++) {
        dp[i] = 1;

        for(int j=0; j<i; j++) {
            if(arr[j]<arr[i]) {
                dp[i] = max(dp[j]+1, dp[i]);
                lis = max(dp[i], lis);
            }
        }
    }

    cout << lis;

}

 

 

2. 2주차 개인과제

 

 

 콘솔 상에서 계산기를 구현하는 과제이다. 기본적인 요구사항 구현에도 물론 힘쓰지만, 그래도 비교적 과제가 여유로울 때 부가적인 경험치를 얻고 싶었다. 전반적인 구조로는 Calculator 클래스에서 로직이 동작하도록 했고, Main.kt에서 그 객체를 생성해 사용하도록 했다. 요구사항의 반영을 위해 실질적 계산이 이뤄지는 PostfixCalculator 클래스 내에는, AbstractOpreation을 상속받아 구현한 각 연산별 Operation 클래스 객체를 보유하고 있다. 또 3개 이상의 수와 괄호를 포함한 연산자 우선순위를 반영해 연산하기 위해 후위 표기식으로 변환 후 계산하도록 했다. 이는 각각 PostfixConverter 및 PostfixCalculator 객체가 담당하도록 했다.

 

 그리고 좀 더 신경써서 작성해 본 것은

1. Calculator 클래스에 싱글톤 패턴 적용하기

2. BigDecimal 클래스 활용

3. 본 로직 자체 구현

4. 깃허브 README 작성

이렇게 4가지 정도였다.

 

 

 

📝 Calculator 클래스에 싱글톤 패턴 적용하기

 

예전에 객체 지향 프로그래밍 관련 과목들을 수강하면서 배웠던 것들을 떠올리며 시도했다. 코틀린 문법으로 직접 구현해보는 건 처음이었던 거 같다.

class Calculator private constructor() {

	...
    
    companion object {
        private var instance: Calculator? = null

	...

        fun getInstance(): Calculator {
            return instance ?: synchronized(this) {
                instance ?: Calculator().also {
                    instance = it
                }
            }
        }
    }
    ...

 

 

 Calculator 클래스 내에 위와 같이 구현하게 됐는데, 사실 처음에는 synchronized()를 이용하지 않았다. 물론 과제를 수행하기 위한 동작 내에서는 전혀 문제가 없었지만, 조금 찾아보니까 멀티 쓰레딩 등을 통해 접근하는 경우 문제가 발생할 수 있기에 코틀린 내에서는 저런식으로 구현하는 것이 어느정도 정형화돼 있었다. 운 나쁘게 인터럽트 잘못 걸리면 race condition 문제가 충분히 발생할 수 있겠다 싶었다.

 그 외 부분에서는 생성자 private로 접근 제한, 클래스 내부에 static한 객체 보유하고 이를 리턴하는 방식 등 학교에서 배웠던 것들 그대로 적용했다. C++에서는 복사 생성자랑 대입 연산자 같은 것도 오버라이딩 했어야 했는데 훨씬 간략하게 끝난 것 같다.

 

 

📝 BigDecimal 클래스 활용

 

 조금 생각해보니 부동소수점 오차 문제랑 기본 자료형들의 지극히 제한적인 표현 범위, 연산 용이성, 소수점 처리 문제 등 산술 과정에서 따져야할 부분이 생각보다 많았다. 마침 예전에 BigDecimal을 활용해 부동 소수점 오차 처리 및 소수점 처리를 간편하게 했던 것이 기억나서 오랜만에 다시 찾아보았다.

 

BigDecimal  |  Android Developers

 

 필요한 요소가 다 있어서, 덕분에 고민할 거리가 많이 줄었다.

 

강력한 소수점 처리 기능

ZeroDivide와 같은 예외들이 발생할 수 있어 그래도 연산마다 예외처리는 해주었다

 

 

📝 본 로직 자체 구현

 

 본말전도가 되면 안되기 때문에, 본 로직 구현도 신경을 썼다. 자료구조와 알고리즘 수업을 들을 때 배웠던 스택과 후위표기식을 이용해서 구현을 했고, 이는 PostfixConverter 및 PostfixCalculator 클래스 내에 작성되어 있다. 유명한 로직이라 간단하게 요약하면 다음과 같다.

 

- 중위표기식을 후위표기식으로 변환

1. 중위표기식 배열을 순회한다.
2-1. 숫자일 경우, 결과 배열에 바로 삽입.
2-2-1. 연산자일 경우, 연산자 스택이 비어있다면 스택에 push.
2-2-2. 비어있지 않다면,
2-2-2-1. 여는 괄호면 연산자 스택에 push.
2-2-2-2. 닫는 괄호면 스택에서 여는 괄호 등장할 때까지 pop해서 결과 배열에 삽입.
2-2-2-3. 일반 연산자라면 우선 순위를 따져서 스택의 top이 현재 비교 중인 연산자보다 우선순위가
		 낮아지거나, 스택이 빌 때까지 pop해서 결과 배열에 삽입. 이후 스택에 현재 연산자 push.
3. 위 과정을 순회 과정 내내 반복.
4. 순회가 끝나면 연산자 스택에 남은 연산자들을 pop해서 결과 배열에 삽입.


- 후위표기식 계산

1. 후위표기식 배열을 순회한다.
2-1. 숫자가 등장하면, 수 스택에 삽입.
2-2. 연산자가 등장하면, 수 스택에서 수를 두 개 pop해서 연산 후 결과값 push.
3. 순회 후, 스택에 남아있는 원소가 모든 연산이 끝난 결과값이다.

 

 근데 이건 clean한 중위표기식을 이용할 수 있을 때 한정이고, 전처리 되지 않은 식을 받아서 처리한다면 또 신경써서 식이 유효한지 검증하는 과정을 거쳐야한다. 나는 입력을 받을 때 clean한 중위표기식을 보장할 수 있도록 처리했다.

 

 

📝 깃허브 README 작성

 

 그래도 README를 마크다운으로 계속 써버릇해야 나한테 좋지 않을까 싶어서, 조금은 구색을 갖추려고 했다. 나는 vs code에서 작성하면 인코딩 문제 때문에, 메모장 등의 UTF-8 환경에서 한글이 깨져서 보인다. 그래서 vs code 내에서 마크다운 미리보기 확장 기능을 이용해 작업 한다음에, IDE 내의 텍스트를 복사해서 메모장으로 붙여넣어서 작성해야 했다.

 

화려하지는 않지만, 그래도 이런 저런 시도는 해본 것 같다. 아래는 그 결과물.

 

 

 

 

 어쩌다보니 TIL도 조금 길게 쓰게 되었는데, 가끔씩은 이렇게 신경써서 작성해보는 것도 나한테 도움이 되는 것 같다.