[TIL] 24.03.27 알고리즘, 챌린지반 과제

1. 알고리즘 문제 해결

 

도로포장(백준 1162):

 다익스트라 알고리즘에 DP가 섞인 문제. 사실 DP라고 의식하지 않아도 풀다 보면 DP를 이용해서 풀게 된다. 당연하게도 브루트포스로는 풀 수 없다. 도로 중에서 포장할 도로를 고르는 경우의 수만 해도 50,000C20까지 주어질 수 있고, 각 경우의 수마다 최소 비용도 계산해야 한다.

 

 이 문제를 해결하기 위한 로직은 꽤나 심플하다. 다익스트라 알고리즘을 사용하되, 다음 경로를 탐색할 때 도로를 포장하는 경우와 포장하지 않는 경우를 둘 다 고려해서 우선순위 큐에 넣어주는 것이다. 뭐 특정 개수 이하로 벽을 뚫고 미로를 탈출하라든지, 길의 종류가 있고 각 종류별로 제한된 수만큼만 이용하라든지 하는 DFS, BFS와 맥락이 정확히 같다.

 

 이제 저 방법을 적용하기로 마음 먹었다면, dist 혹은 cost 등의 다익스트라 상의 promising 여부를 판단하기 위한 자료구조를 생각해야 한다. 일반적인 다익스트라 알고리즘에서는 길이가 노드의 개수인 1차원 배열이면 충분하지만, 이 경우엔 다르다. 탐색 시에, 이전까지 사용한 도로 포장 횟수가 같다면 비용이 적은 선택지가 유리하고, 비용이 같다면 사용한 도로 포장 횟수가 적은 쪽이 유리하다. 또, 도로 포장 횟수가 더 적고 비용도 적은 선택지가 있다면 당연히 그쪽이 유리하다.

 

 따라서 문제 조건을 기준으로 하면 K*N의 2차원 배열을 가지고, 사용한 포장 횟수 별로 최소 비용을 갱신하고, 우선순위 큐 상에서 top을 뽑아 확인할 때 costs[0..현재 사용한 포장 횟수][top이 가리키는 노드]를 모두 확인해, 더 적은 비용이 있다면 가지치기 해주면 된다. 엄밀하게는 현재 사용한 포장횟수-1인 경우까지는 비용이 같아도 가지치기 해줄 수 있다(위에서 말한 비용이 같고 도로 포장 횟수가 적은 경우들). 인접 노드로 나아갈 때는 당연히 현재 사용한 포장 횟수를 이용해, 다음 노드로 도로를 포장하며 진출하는 경우와 포장하지 않고 진출하는 경우를 모두 따져주면 된다.

 

 하나 주의해야 할 것은 탐색 시, 도로 비용의 총합이 50,000 * 1,000,000까지 증가할 수 있으므로 자료형 선택을 신경써서 해줄 필요가 있다. 이 내용들만 제외하면 나머지는 일반적인 다익스트라 알고리즘의 구현과 같다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 999987654321

using namespace std;

typedef long long int ll;

struct cmp {
    bool operator()(pair<pair<int, ll>, int>& l, pair<pair<int, ll>, int>& r) {
        if(l.first.second==r.first.second) {
            return l.second > r.second;
        }else {
            return l.first.second > r.first.second;
        }
    }
};

vector<vector<pair<int, int> > > adjList; //node, cost
vector<vector<ll> > costs;
priority_queue<pair<pair<int, ll>, int>, vector<pair<pair<int, ll>, int> >, cmp > pq;

int n, m, k;

void dijkstra() {

    for(auto edge: adjList[1]) {
        costs[0][edge.first] = min((ll)edge.second, costs[0][edge.first]);
        pq.push({{edge.first, edge.second}, 0});

        costs[1][edge.first] = 0;
        pq.push({{edge.first, 0}, 1});
    }

    while(!pq.empty()) { // {{node, cost}, covered}
        int curNode = pq.top().first.first;
        ll curCost = pq.top().first.second;
        int curCovered = pq.top().second;
        pq.pop();
        
        bool flag = false;
        for(int i=0; i<curCovered; i++) {
            if(costs[i][curNode]<=curCost) {
                flag = true;
                break;
            }
        }
        if(costs[curCovered][curNode]<curCost) flag = true;

        if(flag) continue;

        if(curNode==n) {
            cout << curCost;
            break;
        }

        for(auto edge: adjList[curNode]) {
            auto nextNode = edge.first;
            auto newCost = curCost+edge.second;

            if(costs[curCovered][nextNode]>newCost) {
                costs[curCovered][nextNode] = newCost;
                pq.push({{nextNode, newCost}, curCovered});
            }
            if(curCovered<k && costs[curCovered+1][nextNode]>curCost) {
                costs[curCovered+1][nextNode] = curCost;
                pq.push({{nextNode, curCost}, curCovered+1});
            }
        }
    }
}

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

    cin >> n >> m >> k;

    adjList.assign(n+1, vector<pair<int, int> >());

    int start, target, cost;

    for(int i=0; i<m; i++) {
        cin >> start >> target >> cost;

        adjList[start].push_back({target, cost});
        adjList[target].push_back({start, cost});
    }
    
    costs.assign(k+1, vector<ll>(n+1, INF));
    costs[0][1] = 0;

    dijkstra();
    
}

 

 

2. 챌린지반 과제

 오늘은 챌린지반 과제의 4주차 부분을 미리 시도해보았다. 회원가입 페이지에서 다양한 유효성 검증을 구현해 리팩터링 하는 부분이었는데, MVVM을 이용해야 의미가 있을 것 같았다. 그러다 보니 예전에 봐놓았던 외국 강의가 떠올라서, 조금 더 깔끔한 방법으로 에러 처리를 해보기로 했다.

 본 과제의 요구사항에 따라, 기존의 코드에서는 Validation이라고 해야 Activity 내에서 각 항목이 빈 칸인지 정도만 확인하고 있었다. 하지만 챌린지반 4주차 내용에서는 각 항목들이 입력되었는지, 비밀번호 길이 등의 제약 확인, 비밀번호 재확인, 이메일 유효성 검증을 요구하고 있었다.

 

 나는 따로 만든 Result 및 Error 인터페이스를 이용하고, ViewModel 내에 Validator를 주입해서 사용하는 형태로 청사진을 그렸다. 

 

typealias RootError = Error

sealed interface Result<out D, out E: RootError> {
    data class Success<out D, out E: RootError>(val data: D): Result<D, E>
    data class Error<out D, out E: RootError>(val error: E): Result<D, E>
}

Result.kt

sealed interface Error

Error.kt

enum class AuthError: Error {
    EXIST_BLANK,
    INVALID_EMAIL,
    CONFIRM_UNMATCHED,
    INVALID_LENGTH,
    NO_LOWERCASE,
    NO_UPPERCASE,
    NO_DIGIT,
    NO_SPECIAL_SIGN
}

AuthError.kt

 

 물론 이번에는 Result도 회원가입을 할 때만 사용하고, 에러 또한 AuthError 만을 다루게 되겠지만, 어느정도 확장을 염두에 두고 위와 같이 작성했다. 눈치껏 알 수 있는 부분이지만, Result.kt 내의 RootError로 typealias를 지정한 Error는 직접 만든 Error 인터페이스를 가리킨다.

 

 그리고 UserDataValidator 클래스를 일단 생성한 후에, ViewModel에 주입하도록 파라미터를 지정했다.

...
class SignUpViewModel(
    private val userDataValidator: UserDataValidator
): ViewModel() {
...

 

 물론 DI 라이브러리를 이용해서 주입하는 것이 이상적이겠지만, 이번 과제의 의도는 DI 라이브러리의 활용이 아니기 때문에, Activity 차원에서 직접 주입할 수 있도록 했다. 당연하게도 Activity에서 ViewModel을 생성할 때 직접 인스턴스를 주입하려면 ViewModelProvider.Factory를 구현해서 써야 한다.

class SignUpViewModelFactory(private val userDataValidator: UserDataValidator): ViewModelProvider.Factory {
    override fun <T : ViewModel> create(modelClass: Class<T>): T {
        if(modelClass.isAssignableFrom(SignUpViewModel::class.java)) {
            return SignUpViewModel(userDataValidator) as T
        }
        throw IllegalArgumentException("Unknown ViewModel class")
    }
}

class SignUpActivity: AppCompatActivity() {

    private val signUpViewModel: SignUpViewModel by viewModels {
        SignUpViewModelFactory(UserDataValidator())
    }
...

 

 위와 같이 ViewModelProvider.Factory를 구현해 by viewModels 호출 시 인자로 넘겨주었다. 이제 ViewModel 내의 회원가입을 담당하는 메소드를 실행했을 때, 입력받은 유저 정보의 validation을 실행할 로직을 UserDataValidator 내에 작성해준다. 이 때 해당 로직의 결과로는 처음에 생성해둔 Result를 반환해야 할 것이다.

 

class UserDataValidator {

    fun validateUserData(name: String, email: String, id: String, password: String, passwordConfirm: String): Result<Unit, AuthError> {
        if(name.isBlank() || id.isBlank() || password.isBlank() || passwordConfirm.isBlank()) {
            return Result.Error(AuthError.EXIST_BLANK)
        }

        if(!Patterns.EMAIL_ADDRESS.matcher(email).matches()) {
            return Result.Error(AuthError.INVALID_EMAIL)
        }

        val pwValidResult = validatePassword(password, passwordConfirm)
        if(pwValidResult is Result.Error) {
            return pwValidResult
        }

        return Result.Success(Unit)
    }

    private fun validatePassword(password: String, passwordConfirm: String): Result<Unit, AuthError> {
        if(password!=passwordConfirm) {
            return Result.Error(AuthError.CONFIRM_UNMATCHED)
        }

        if(password.length !in 8..16) {
            return Result.Error(AuthError.INVALID_LENGTH)
        }

        val hasDigit = password.any { it.isDigit() }
        if(!hasDigit) {
            return Result.Error(AuthError.NO_DIGIT)
        }
        
        ...

 

 위와 같은 느낌으로 작성해주었다. 비밀번호와 관련된 validation이 많아서 따로 분리해주었다. 직관적으로 알 수 있지만, 유효성 검증 과정 도중 invalid 한 부분을 발견하면 그에 맞는 AuthError를 담은 Result.Error를 반환하고, 모두 통과했다면 Result.Success를 반환하게 된다.

 이제 이를 곧바로 ViewModel 내에서 사용하게 되면, Result가 Success인지 Error인지도 처리해야 하지만, 꽤나 지저분하게 모든 AuthError에 대해 when 문으로 처리해야 할 것이다.

 

 UI 쪽에서는 모든 행위와 그 결과는 일종의 이벤트고, 각 이벤트를 어떻게 처리해야할 지에만 관심이 있다. 따라서 UserEvent를 구현해서 ViewModel 내의 LiveData로 생성하고 이를 Activity에서 observe 할 수 있도록 한다. 물론 Channel을 이용해 Flow로 전달하는 것도 매력적인 방법이지만, 커리큘럼 상 Flow는 이후에 배우게 될 것이므로 LiveData를 이용하도록 했다. Channel 클래스를 하나 생성할까도 싶었지만, 그거까진 과한 것 같아 LiveData만 적절하게 활용하기로 했다.

 

sealed interface UserEvent {
    data object None: UserEvent
    data object Success: UserEvent
    data class Error(val msg: String): UserEvent

    data class RegisterSuccess(val user: User): UserEvent
}

 

 UserEvent는 위와 같이 구현했다. None는 아무런 이벤트가 없는 상황(단순하게 LiveData 하나만 이용하기 때문에 필요해진 부분), Success는 사용하진 않을 예정이나 이벤트의 성공여부만 필요할 때를 위한 기본 성공 클래스, Error는 에러 메시지를 들고 있는 기본 실패 클래스이다. ResgisterSuccess는 회원가입이 완료되었을 때, Intent로 넘겨줄 유저 정보가 필요하기 때문에, 이를 위해 구현한 성공 클래스이다. 

 UserEvent.Error는 에러 메시지를 쥐고 있어야 하기 때문에, 위에서 생성해둔 에러들에 대해 미리 메시지화 시킬 수 있는 확장 함수 등을 구현해둔다면 코드가 한결 간결해질 것이다. 

fun AuthError.asText(): String {
    return when(this) {
        AuthError.EXIST_BLANK -> "모든 정보를 입력해주세요."
        AuthError.INVALID_EMAIL -> "잘못된 형식의 이메일입니다."
        AuthError.CONFIRM_UNMATCHED -> "재확인 비밀번호가 일치하지 않습니다."
        AuthError.INVALID_LENGTH -> "비밀번호는 8자~16자 사이로 입력해주세요."
        AuthError.NO_LOWERCASE -> "비밀번호에는 소문자가 1개 이상 포함되어야 합니다."
        AuthError.NO_UPPERCASE -> "비밀번호에는 대문자가 1개 이상 포함되어야 합니다."
        AuthError.NO_DIGIT -> "비밀번호에는 숫자가 1개 이상 포함되어야 합니다."
        AuthError.NO_SPECIAL_SIGN -> "비밀번호에는 특수문자가 1개 이상 포함되어야 합니다."
    }
}

fun User.asText(): String {
    return "이름: ${this.name}, 아이디: ${this.id}\n비밀번호: ${this.password}";
}

 

 이처럼 간단하게 구현했다. 이것 또한 리소스 아이디나, String 중 하나를 받아 UI에 바로 출력할 수 있는 문자로 변환할 수 있는 컨버터가 하나 있으면 좋을 것이다. 저렇게 하드 코딩된 문자열보단 strings.xml에서 참조하는 게 좋을테니까.

 밑의 User 클래스의 확장 함수도 미리 작성했는데, 저번 주차에 있던 이름, 아이디, 비밀번호 Toast 출력 로직 때 유용하게 쓰일 것 같아서다. 참고로 UserClass는 별 내용은 없고, 이름, 아이디, 비밀번호, 이메일 정보를 String으로 가지고 있는 Data class다.

 

...
    private var user = User()

    private val _userEvent = MutableLiveData<UserEvent>(UserEvent.None)
    val userEvent: LiveData<UserEvent> get() = _userEvent

    fun registerAuth(nameStr: String, email: String, idStr: String, passwordStr: String, passwordConfirmStr: String) {
        _userEvent.value = UserEvent.None

        when(val result = userDataValidator.validateUserData(nameStr, email, idStr, passwordStr, passwordConfirmStr)) {
            is Result.Error -> {
                val errorMessage = result.error.asText()
                _userEvent.value = UserEvent.Error(errorMessage)
            }
            is Result.Success -> {
//                _nameString.value = nameStr
//                _idString.value = idStr
//                _passwordString.value = passwordStr
                // 원래는 서버에 등록
                registerUser(nameStr, idStr, passwordStr)
                _userEvent.value = UserEvent.RegisterSuccess(getAuth())
            }
        }
    }
    ...

 

 재료들이 완성되었으니, ViewModel 내의 회원가입 메소드를 마저 작성해준다. 회원가입 버튼을 누르면 해당 메소드가 호출되는데, 앞서 의도한 것처럼 LiveData인 userEvent를 이용해 이벤트 처리 결과를 알리도록 한다. 

 

 메소드 내에서는 구현해둔 validator의 메소드를 이용해 유효성 검증을 시도하고 그 결과를 Result 클래스로 받아 처리해주었다. when의 조건식 안에서 result라는 변수에 그 결과를 받아 바로 이용할 수 있도록 했다.

 결과가 Result.error라면 아까 생성해둔 AuthError.asText()를 통해 에러 메시지를 바로 생성하고 이를 UserEvent.Error로 래핑해 바로 LiveData에 반영한다.

 결과가 Resut.Success라면 원래는 서버에 유저 정보를 넘기고 등록하는 절차를 거쳐야 할 것이고 이는 또 Network Error 등을 처리할 수 있는 Result 클래스로 받아 처리하는 것이 맞을 것이다. 하지만 서버도 없고, 그것을 위한 과제도 아니므로 적당히 메소드만 분리해 처리했다. 위에서 구현했던 것에 맞게 User를(getAuth()가 단순히 ViewModel이 쥐고 있는 user를 리턴하는 형태임) 넘겨주고 있다.

 

...
private fun setClickListeners() {
        findViewById<Button>(R.id.signUpButton).setOnClickListener {
            val nameString = findViewById<EditText>(R.id.nameInputEditText).text.toString()
            val emailString = findViewById<EditText>(R.id.emailInputEditText).text.toString()
            val idString = findViewById<EditText>(R.id.idInputEditText).text.toString()
            val passwordString = findViewById<EditText>(R.id.passwordInputEditText).text.toString()
            val passwordConfirmString = findViewById<EditText>(R.id.passwordConfirmInputEditText).text.toString()

            signUpViewModel.registerAuth(nameString, emailString, idString, passwordString, passwordConfirmString)
        }
    }
...
    
private fun setObservers() {
signUpViewModel.userEvent.observe(this) { event ->
    when (event) {
        is UserEvent.Error -> {
            makeToast(event.msg)
        }

        is UserEvent.RegisterSuccess -> {
            val userInfo = event.user
            makeToast(userInfo.asText())
            val intent = Intent().putExtra(
                SignInActivity.USER_INFO,
                arrayListOf(userInfo.id, userInfo.password)
            )
            setResult(RESULT_OK, intent)
            finish()
        }

        UserEvent.None -> {}
        UserEvent.Success -> {}
    }
}
    ...

 

 마지막으로 Activity에서는 그저 ViewModel 내의 userEvent만 Observe하며 이벤트 종류에 맞게 처리해줄 뿐이고, 회원가입 버튼을 눌렀을 때도 그저 UI의 데이터들을 긁어다가 ViewModel의 registerAuth()에 전달할 뿐이다.

 훨씬 코드가 간결해 보인다.

 

 

 

의도한 동작들이 잘 처리됨을 확인했다. 아마 4주차의 내용은 이정도로 구현해서 마무리 할 것 같다!