99클럽 코테 스터디 1일차 TIL - 모음사전

 

알아보기 - 추후 개별글로 작성예정

 

우선 완전탐색에 대한 개념을 알아보자.

In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically checking all possible candidates for whether or not each candidate satisfies the problem's statement.

출처 :https://en.wikipedia.org/wiki/Brute-force_search

완전탐색이란 영어로 brute-force search, exhaustive search , generate and test 라고 불린다.

해석을 해보자면  컴퓨터과학에서 가장 일반적인 문제풀이 방법으로, 후보들이 문제의 조건을 만족하던 아니던, 가능한 모든 후보를 확인하는 방법이다.

즉, 다시말해 모든 경우를 일일이 다 확인한다는 이야기다.

내가 아는 구현 방법은 단순 for문, while문, dfs로 모든 경우의 수를 탐색하도록 코드를 짜는 것이다.

 

풀이 과정 1

이 문제는 사실 예전에 한 번 풀어본적이 있는 문제이다. 그 때 당시에는 사전순 개념을 생각해서 풀었다.

이게 무슨말인가 하면, 만약주어진 word가  E라고 하자.

E가오기전에  A로 시작하는 1자리 문자 A, 2자리 문자 A+(A,E,I,O,U), 3자리 문자인 A +(A,E,I,O,U) +(A,E,I,O,U)

4자리 문자인 A +(A,E,I,O,U) +(A,E,I,O,U) +(A,E,I,O,U)  5자리 문자인 A+(A,E,I,O,U) +(A,E,I,O,U) +(A,E,I,O,U) +(A,E,I,O,U) 의 조합이 사전순으로 앞에 존재한다는 뜻이다. 

각 경우의 수를 세어보면 1,5,25,125,625 순으로 늘어나는 것을 알 수 있다. 

그렇다면 E는 몇번째 문자일까? 

앞의  경우의 수를 모두 합하면 781이라는 수가 나온다. 따라서 E는 782번째 문자가 된다.

이 원리로 생각해보면, EI의 경우는 E 문자 이후 EA~~~ EE~~~의 경우의수를 모두 지나온 값이니 782+(125+25+5+1)*2+1=1095번째 문자가 된다.

이를 종합해 보면, 제시된 단어의 자리에 따라 해당 문자에 오기까지 필요한 경우의 수들을 누적해주면 다음과 같은코드를 짤 수 있다.

def solution(word):
    answer=0
    dic={"A":0,"E":1,"I":2,"O":3,"U":4}
    part_sum=[781,156,31,6,1]
    for x in range(len(word)):
        answer+=(dic[word[x]])*part_sum[x]
    answer+=len(word)
    return answer

 

풀이 과정 2

사실 1번 풀이가 더 좋은 풀이 인것 같지만, 완전탐색을 복습해 볼겸 이렇게 풀어보았다.

이번 방법은 나에게 제일 익숙한 dfs로 구현한 완전탐색 방법이다.

이번 로직은 다음과 같다.

1. 빈 배열로 시작하여 사전순으로 알파벳을 일일히 다 추가하며 word_stack에 쌓는다.

2. 5자리가 넘는 문자열은 해당되지 않으니, word_stack에 추가하기 전에 반환한다.

3. join을 활용해서  string으로 변환한 값을 words에 모두 차례대로 추가한다.

4. 이를 "dic" dictionary에 번호대로 추가하여 문자를 넣으면 바로 인덱스값을 반환하도록 하였다.

def solution(word):
    words=[]
    def dfs(word_stack):
        if len(word_stack)>5:
            return
        words.append("".join(word_stack))
        for alpha in ["A","E","I","O","U"]:
            dfs(word_stack+[alpha])
    dfs([])
    dic={}
    for i in range(len(words)):
        dic[words[i]]=i
    return dic[word]

 

오늘의 회고

- 문제를 푸는것보다도 처음 써보는 장문의 풀이가 시간도 몇십배 오래걸리고, 쉽지 않음을 느꼈다.

- 이 TIL을 꾸준히 진행하면서, 나의 글쓰기 능력이 늘어날 것이라 믿는다.

- 내일은 코테 스터디와 운영체제 인강을 듣고, 이전에 신청해 두었던 도커를 공부할 것이다.