99클럽 코테 스터디 7일차 중복순열, DFS

오늘의 학습 키워드

중복순열, DFS

오늘은 풀이 방법 2가지에 따른 개념 정리와 코드 풀이를 진행할 것이다!
왜냐하면 이 문제에서 풀이 방법을 생각하지 못해서 구글링을 통해 풀었기 때문🥲..

오늘의 문제

프로그래머스 코딩테스트 연습 > 완전탐색 > 모음사전

https://school.programmers.co.kr/learn/courses/30/lessons/84512

문제 설명

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• word의 길이는 1 이상 5 이하입니다.
• word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

입출력 예

word	result
"AAAAE"	6
"AAAE"	10
"I"	1563
"EIO"	1189

입출력 예 설명

입출력 예 #1
사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다. "AAAAE"는 사전에서 6번째 단어입니다.

입출력 예 #2
"AAAE"는 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"의 다음인 10번째 단어입니다.

입출력 예 #3
"I"는 1563번째 단어입니다.

입출력 예 #4
"EIO"는 1189번째 단어입니다.

---

풀이1. 중복 순열

코드

from itertools import product

def solution(word):
    dictionary = []
    for i in range(1, 6):
        # 길이 i인 중복 순열을 생성하여 모든 경우의 단어를 만든다.
        dictionary.extend(list(map(''.join, product(['A', 'E', 'I', 'O', 'U'], repeat=i))))
    dictionary.sort()  # 사전 순으로 정렬 (사실상 이미 사전순)
    return dictionary.index(word) + 1

1. itertools 라이브러리

from itertools import product

• Python의 itertools 모듈에서 product 함수를 가져옴.
• product()는 데카르트 곱(Cartesian product)을 생성하는 함수로, 중복 순열을 만들 수 있다.

데카르트 곱(Cartesian product)이란?

• 두 집합의 모든 가능한 쌍을 조합하여 만들어진 집합
• 두 개 이상의 리스트가 있을 때, 각 리스트의 모든 요소들을 하나씩 조합하여 새로운 모든 경우의 수를 만드는 것
• ex)
  A = [1, 2]
  B = ['a', 'b']
  A와 B의 데카르트 곱은 다음과 같은 조합들을 포함하게 됨:
  (1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')
• itertools.product() 함수는 이러한 데카르트 곱을 계산하여 모든 가능한 조합을 반환.
• 이 문제에서는 ['A', 'E', 'I', 'O', 'U']를 여러 번 반복해서 가능한 모든 중복 조합을 생성하는 데 사용.

중복 순열이란?

• 순열의 일종으로, 특정 집합에서 원소를 중복해서 선택하여 가능한 모든 조합을 생성하는 방식
• 집합이 ['A', 'B']이고 길이가 2인 중복 순열을 생성한다고 하면, 가능한 조합:
  ('A', 'A'), ('A', 'B'), ('B', 'A'), ('B', 'B')
• 여기서 각 원소가 여러 번 선택될 수 있다는 것이 중복 순열의 특징.
• 중복을 허용하지 않는 일반적인 순열과는 다르게, 원소를 중복해서 고르는 모든 경우의 수를 다루는 방식.
• 코드에서 사용된 itertools.product()는 이러한 중복 순열을 생성하는 데 사용. repeat=i 매개변수를 통해 특정 길이의 중복 순열을 만들고, 이를 이용해 주어진 문자 집합으로 만들 수 있는 모든 단어를 생성

2. 중복 순열을 사용하여 가능한 모든 단어 생성

def solution(word):
    dictionary = []
    for i in range(1, 6):
        # 길이 i인 중복 순열을 생성하여 모든 경우의 단어를 만든다.
        dictionary.extend(list(map(''.join, product(['A', 'E', 'I', 'O', 'U'], repeat=i))))

• dictionary = [] : 가능한 모든 단어를 저장할 빈 리스트를 생성.
• for i in range(1, 6): : 길이가 1부터 5까지의 모든 단어를 생성.
• product(['A', 'E', 'I', 'O', 'U'], repeat=i) : 모음 리스트에서 중복을 허용하며 길이가 i인 모든 가능한 조합을 생성.
  • 예를 들어, repeat=2이면, ('A', 'A'), ('A', 'E'), ..., ('U', 'U')와 같은 모든 조합을 생성.
• map(''.join, product(...)): 각 조합을 문자열로 변환. 예를 들어, ('A', 'E')는 'AE'로 변환.
• dictionary.extend(...): 변환된 문자열을 dictionary 리스트에 추가. 이렇게 해서 길이 1부터 5까지 모든 가능한 단어가 dictionary 리스트에 저장.

3. 사전 순으로 정렬

	dictionary.sort()

• 리스트를 사전 순으로 정렬. itertools.product()로 생성된 조합은 이미 사전 순으로 만들어지기 때문에 이 단계는 생략해도 되지만, 코드의 명확성을 위해 사용.

4. 주어진 단어의 순서를 반환

	return dictionary.index(word) + 1

• 주어진 단어 word가 dictionary에서 몇 번째 위치에 있는지 찾기.
• index() 함수는 리스트에서 주어진 요소의 위치를 반환하는데, 이때 0부터 시작하므로 +1을 해주어 1부터 시작하는 순서로 반환.

---

풀이2. DFS

DFS란?
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

• 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
• 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
• 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
• 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

코드

dictionary = []

def dfs(word):
    global dictionary

    dictionary.append(word)

    if len(word) == 5:
        return

    for x in ["A", "E", "I", "O", "U"]:
        dfs(word + x)

def solution(word):
    dfs("") 
    return dictionary.index(word)

1. 단어를 저장할 빈 리스트 생성

dictionary = []

• 가능한 모든 단어를 저장하기 위한 빈 리스트. DFS를 통해 생성한 단어들을 이 리스트에 저장.

2. DFS 함수 정의

def dfs(word):
    global dictionary

    dictionary.append(word)

    if len(word) == 5:
        return

    for x in ["A", "E", "I", "O", "U"]:
        dfs(word + x)

• dfs(word): : 현재 단어를 입력받아 가능한 모든 단어를 생성하는 재귀 함수.
• dictionary.append(word) : 현재 생성된 단어를 dictionary 리스트에 추가.
  • append()는 리스트에 새로운 요소를 추가하는 메서드
• if len(word) == 5: : 단어의 길이가 5가 되면 더 이상 확장하지 않고 리턴. 문제의 조건에서 단어의 최대 길이는 5이기 때문.
• for x in ["A", "E", "I", "O", "U"]: : 각 모음('A', 'E', 'I', 'O', 'U')에 대해 새로운 단어를 만들어내고, 그 단어로 다시 재귀 호출.
  • 예를 들어, word가 "A"라면 다음 호출에서는 "AA", "AE", "AI" 등이 재귀적으로 호출.

3. 목표 단어의 위치 반환

def solution(word):
    dfs("") 
    return dictionary.index(word)

• dfs("") : 빈 문자열에서 시작하여 가능한 모든 단어를 사전 순서대로 생성.
• return dictionary.index(word) : 목표 단어 word가 dictionary 리스트에서 몇 번째 위치에 있는지 반환. 인덱스를 반환할 때, 파이썬의 리스트 인덱스는 0부터 시작하기 때문에 해당 위치가 곧 사전에서의 순서.

---

오늘의 회고

🔥 이 문제에서 풀이 방법을 생각하지 못해서 구글링을 통해 풀었기 때문에 코드를 먼저 쓰고 풀이와 개념을 함께 정리해보았다. 일단 문제에 대해 이해하고 어떤 풀이를 생각하는지 제일 어려운 것 같다..

🔥 위 풀이 2개말고도 for문 5번을 사용하거나 규칙을 사용해서 하는 풀이들도 있었다. 그렇게라도 풀 수 있게 학습이 더 필요하다ㅜ