[programmers][c++] 모음사전, 피로도

모음사전

프로그래머스 모음사전 문제

완전 간단한 dfs문제였다. 그러나 완전탐색 카테고리에 있어서 방향 잡기가 다소 난해했다. 실제 코테에서 이런 문제를 보게되면 완전탐색보다는 dfs 키워드를 먼저 떠올릴 것 같다. 문제를 봤을 때 올바른 풀이 방법을 떠올리는게 중요한데, 카테코리가 나눠진 문제들을 풀면 그런 연습을 할 수 없는게 아쉽다. 오히려 방해된다.

#include <string>
#include <vector>

using namespace std;
int answer, cnt;
char words[5]={'A','E','I','O','U'};

void wordcnt(string now, string ans){
    if(now==ans)
        answer=cnt;
    if(now.length()>5)
        return;
    cnt++;
    for(int i=0;i<5;i++)
        wordcnt(now+words[i],ans);
}

int solution(string word) {
    wordcnt("",word);
    return answer;
}

피로도

프로그래머스 피로도 문제

이 문제도 dfs로 쉽게 풀 수 있다.

내림차순 정렬을 위해 커스텀 컴페어 함수를 작성했다. 최소필요피로도 가 높은 던전부터 탐색해야 더 효율적인 탐색이 가능하다고 생각했기 때문이다. 그러나 던전 개수가 적은 편이고 오름차순 정렬을 사용했을 경우 조건에 따라 break를 걸 수 있기 때문에 비슷할 것 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int ans;
bool visits[9];

bool compare(vector<int> a, vector<int> b){
    if(a[0]>=b[0])
        return true;
    else
        return false;
}

void dfs(vector<vector<int>> dungeons, int k, int cnt){
    if(k<=0)
        return;
    ans=max(cnt,ans);
    cout<<ans<<'\n';
    for(int i=0;i<dungeons.size();i++){
        if(dungeons[i][0]>k||visits[i])
            continue;
        visits[i]=true;
        dfs(dungeons,k-dungeons[i][1],cnt+1);
        visits[i]=false;
    }
    return;
}

int solution(int k, vector<vector<int>> dungeons) {
    sort(dungeons.begin(),dungeons.end(),compare);
    dfs(dungeons, k, 0);
    return ans;
}

근황

최근에 코테를 준비하느라 게시물 업로드 빈도가 줄었다.

그래도 백준 문제를 꾸준히 풀고 있는데 엄청난부자2, 긴자리계산 등의 간단한 문제에서 자료형을 커스텀해야 하는 c++의 한계를 느꼈다.

자료의 크기 문제나 숙지해야 할 컨테이너의 범위 등 모르면 틀려야지 싶은 문제들이 종종 있다. 당연히 기본적인건 공부해야 하지만 딥한 분야 (예를 들면 BigInteger를 c++로 구현하는 방법) 등 배우고 싶지 않은 분야도 공부해야 하는게 아쉽다. 파이썬은 이를 직접 구현할 필요가 없다. 그래서 위에서 언급한 문제도 솔브드 난이도 브론즈5ㅋㅋ 이 문제들은 편법을 써서 파이썬으로 풀었다.

실제 코테에서도 입맛에 맞게 언어를 바꿔가며 풀면 면접관 분들이 꽤나 당황하실듯! 그래서 이번 코테를 마무리하면 파이썬을 배우기로 했다. 다행히 주변에 파이썬 쓰는 사람들이 많다. 후후 새로운 언어 설레