99클럽 코테 스터디 7일차 TIL C++ DFS(완전탐색), 경우의 수

오늘의 학습 키워드

문제1 : DFS(완전탐색), 경우의 수

https://school.programmers.co.kr/learn/courses/30/lessons/84512?language=cpp

공부한 내용 본인의 언어로 정리하기

문제1 : DFS(완전탐색), 경우의 수

 

(1) dfs로 combination 만들기(조합)

DFS는 그래프나 트리와 같은 구조에서 노드를 탐색하는 방법 중 하나로, 가능한 깊이까지 탐색한 후 더 이상 탐색할 수 없을 때 다시 돌아가 다른 경로를 탐색하는 방식입니다.
fillMap 함수는 문자열을 생성하기 위해 재귀적으로 호출됩니다. 이 함수는 현재 문자열(str)과 탐색의 깊이(level)를 인자로 받아서 문자열을 계속 확장해 나갑니다. 이는 DFS의 전형적인 형태입니다.
for (int i = 0; i < alpha.length(); i++) 루프를 통해 각 알파벳('A', 'E', 'I', 'O', 'U')을 추가하여 새로운 문자열을 생성하고, 이를 다시 fillMap에 전달하여 탐색을 계속합니다.

 

(2) 경우의 수로 시간 최적화
문제를 조금 더 수학적으로 생각한다면, 아래와 같은 그림을 그려볼 수 있습니다.
예를 들어서 EIO의 사전적 순서를 구한다고 해봅시다. A, E, I, O, U의 5개 문자를 가질 수 있으므로, 아래와 같은 경우의 수를 고민할 수 있습니다.

• 문자열의 첫번째 자리에는 A와 E를 쓸수 있습니다. A로 시작하는 문자열은 625 + 125 + 25 + 5 + 1 = 781 개가 있습니다.

자리수	E	I	O			개수(경우의 수)
5자리	A	5개(AEIOU)	5개(AEIOU)	5개(AEIOU)	5개(AEIOU)	625
4자리	A	5개(AEIOU)	5개(AEIOU)	5개(AEIOU)		125
3자리	A	5개(AEIOU)	5개(AEIOU)			25
2자리	A	5개(AEIOU)				5
1자리	A					1

• 문자열의 첫번째 자리에 E를 사용할때, 두번째 자리에는 A, E, I를 쓸수 있습니다. EA 또는 EE로 시작하는 문자열은 250 + 50 + 10 + 2 = 312 개가 있습니다.

자리수	E	I	O			개수(경우의 수)
5자리	E	2개(AE)	5개(AEIOU)	5개(AEIOU)	5개(AEIOU)	250
4자리	E	2개(AE)	5개(AEIOU)	5개(AEIOU)		50
3자리	E	2개(AE)	5개(AEIOU)			10
2자리	E	2개(AE)				2

• 문자열의 세번째 자리에는 A, E, I를 쓸수 있습니다. EIA 또는 EIE 또는 EII로 시작하는 문자열은 75 + 15 + 3 = 93 개가 있습니다.

자리수	E	I	O			개수(경우의 수)
5자리	E	I	3개(AEI)	5개(AEIOU)	5개(AEIOU)	75
4자리	E	I	3개(AEI)	5개(AEIOU)		15
3자리	E	I	3개(AEI)			3

 

• 추가로, E, EI, EIO 의 문자열을 가질 수 있다. (이 값은 문자열의 길이와 동일한 개수를 갖는다.)

 

(3) 전체 풀이 dfs

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

static map<string, int> m_mapWord;
string alpha = "AEIOU";

void fillMap(string str, int level) {
    if (level > 5) return; 

    m_mapWord[str] = m_mapWord.size(); 
    for (int i = 0; i < alpha.length(); i++) {
        fillMap(str + alpha.at(i), level + 1); 
    }
}

int solution(string word) {
    fillMap("", 0);
    int answer = m_mapWord[word];
    return answer;
}

 

(4) 전체 풀이(최적화)

> 최적화1

#include <string>
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

int solution(string word) {
    int ans = 0, num;
    string m_str = "AEIOU";
    
    if (word.length()>=1){
        num = m_str.find(word.at(0));
        ans += num * (5*5*5*5 + 5*5*5 + 5*5 + 5 + 1);
    }
    
    if (word.length()>=2){
        num = m_str.find(word.at(1));
        ans += num * (5*5*5 + 5*5 + 5 + 1);
    }
    
    if (word.length()>=3){
        num = m_str.find(word.at(2));
        ans += num * (5*5 + 5 + 1);
    }
    
    if (word.length()>=4){
        num = m_str.find(word.at(3));
        ans += num * (5 + 1);
    }
    
    if (word.length()>=5){
        num = m_str.find(word.at(4));
        ans += num * (1);
    }
    
    return ans + word.length();
}

 

 

> 최적화2

#include <string>
#include <iostream>

using namespace std;

int solution(string word) {
    int ans = 0;
    string m_str = "AEIOU";
    int length = word.length();
    
    // 각 문자의 가중치를 미리 계산하여 배열에 저장
    int weights[] = {781, 156, 31, 6, 1}; // 5^4, 5^3, 5^2, 5^1, 5^0
    
    for (int i = 0; i < length; i++) {
        int num = m_str.find(word.at(i)); // 현재 문자의 인덱스
        ans += num * weights[i]; // 해당 문자의 가중치와 인덱스를 곱하여 더함
    }
    
    // 길이에 따른 추가 계산
    return ans + length; // 각 문자열 길이에 1을 추가하여 반환
}

오늘의 회고

오늘 학습한 내용을 통해 DFS(깊이 우선 탐색)와 조합 생성에 대해 깊이 이해할 수 있었습니다. 앞으로도 이러한 접근 방식을 통해 다양한 문제에 도전하고, 효율적인 코드 작성 방법을 계속해서 연습해야겠다는 다짐을 하게 되었습니다.