Study Log

20200428 알고리즘

1. 단어변환

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항
  • 각 단어는 알파벳 소문자로만 이루어져 있습니다.
  • 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
  • words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
  • begin과 target은 같지 않습니다.
  • 변환할 수 없는 경우에는 0를 return 합니다.
입출력 예
begin target words return
hit cog [hot, dot, dog, lot, log, cog] 4
hit cog [hot, dot, dog, lot, log] 0
입출력 예 설명

예제 #1 문제에 나온 예와 같습니다.

예제 #2 target인 cog는 words 안에 없기 때문에 변환할 수 없습니다.

Solution

from collections import deque
def solution(begin, target, words):
    size = len(begin)
    answer = 0
    ch = [0] * len(words)
    dQ = deque()
    dQ.append(begin)
    while dQ:
        for _ in range(len(dQ)):
            tmp = dQ.popleft()
            if tmp == target:
                return answer
            for i in range(len(words)):
                if ch[i] == 0:
                    cnt = 0
                    for j in range(size):
                        if words[i][j] == tmp[j]:
                            cnt += 1
                    if cnt == size-1:
                        ch[i] = 1
                        dQ.append(words[i])
        answer += 1
    return 0

2. 2xn 타일링

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

  • 타일을 가로로 배치 하는 경우
  • 타일을 세로로 배치 하는 경우

예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한사항
  • 가로의 길이 n은 60,000이하의 자연수 입니다.
  • 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
입출력 예
n result
4 5

Solution

function solution(n) {
    let left = 1
    let right = 2
    for (let i=3; i<=n; i++){
        const answer = (left+right) % 1000000007
        left = right
        right = answer
    }
    return right
}

3. 정수 삼각형

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항
  • 삼각형의 높이는 1 이상 500 이하입니다.
  • 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
입출력 예
triangle result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30

Solution

function solution(triangle) {
    let answer = triangle[0][0] // 삼각형 높이 1 case
    for (let i=1; i<triangle.length; i++){
        triangle[i][0] += triangle[i-1][0]
        for (let j=1; j<triangle[i].length-1; j++) triangle[i][j] += Math.max(triangle[i-1][j-1], triangle[i-1][j])
        triangle[i][triangle[i].length-1] += triangle[i-1][triangle[i-1].length-1]
    }
    
    for (const v of triangle[triangle.length-1]){
        if (answer < v) answer = v
    }
    return answer
}
Written by@[HongDongUk]
공부한 것을 소소하게 적는 블로그.

GitHubFacebook