수학과의 개발자 도전기

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12913

Lv2 문제이고, 스스로 푼 문제다!

이전에 다이나믹 프로그래밍 풀 때 접했던 문제랑 비슷했다. 그동안의 최댓값을 dp의 각 위치에 누적한 다음 마지막 행에서 최댓값을 구하면 된다 

문제 이해 

dp의 (i, j) 위치에는 0부터 i -1행의 수 중 j열이 아닌 값 중에서 제일 큰 값을 누적한 값이 저장되어 있다 

1. 초기화로 0행에 있는 수들을 dp 행렬의 0행에 저장한다

2-1. 1행부터 시작해 land의 (i,j)의 값은 미리 dp[i][j]에 넣어준다 

2-2. i -1 행의 j열을 뺀 나머지 열 중에서 최댓값을 max_num에 누적한다

3. 전 행에서의 j열을 제외한 최댓값을 dp[i][j]에 누적한다 

4. dp의 마지막 행에서 최댓값을 출력해준다 

- 정답 풀이 : 

def solution(land):
    n = len(land)
    
    dp = [[0] * 4 for _ in range(n)]
    for i in range(4):
        dp[0][i] = land[0][i]
        
    for i in range(1, n):
        for j in range(4):
            max_num = 0
            dp[i][j] += land[i][j]
            for k in range(4):
                if k != j:
                    max_num = max(dp[i - 1][k], max_num)
                    
            dp[i][j] += max_num
            
    return max(dp[-1])

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/17684

Lv2 문제이고, 스스로 푼 문제다!

문제 이해

alphabet을 사전처럼 이용하는데 이 사전에 해당 문자가 있을 때까지 진행해야한다고 생각했다.

answer에는 사전에 존재하는 문자열의 인덱스 번호를 누적한다

now는 시작 문자 또는 문자열을 가리킨다 

1. 사전에 없는 문자가 나오면 그 전 문자의 사전번호를 answer에 추가하고, 사전에 그 새로운 문자를 추가한 뒤

2. 마지막 문자를 기준으로 다시 시작한다. (now = nx)

3. 위의 과정으로 진행하면 사전에서 가장 마지막 문자열은 카운트되지 못하고 끝나기 때문에 now 문자의 인덱스를 alphabet에서 가져와 answer에 추가해준다 

- 정답 풀이 : 

def solution(msg):
    alphabet = [0, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
    #사전에 있는 문자까지 진행하고, 그 단어의 인덱스 answer에 추가, 없는 문자열에서 멈추고 사전에 등록     
    answer = []
    msg = list(msg)
    now = msg.pop(0)
   
    while msg:
        nx = msg.pop(0)       
        current = now + nx
        if current not in alphabet:
            alphabet.append(current)
            answer.append(alphabet.index(now))
            now = nx             
        else: # current in alphabet
            now = current
            
    #마지막 남은 문자는 반복문에서 연산되지 않으므로 따로 해당 문자의 인덱스를 answer에 추가해준다
    if now != 0:
        answer.append(alphabet.index(now))
        
    return answer

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/17687

참고한 블로그

Lv2 문제다!

문제이해 

p에 맞춰서 만들기 보다 t * m만큼의 수를 n진법으로 바꾼다음  m으로 나눈 나머지가 p - 1인 인덱스의 값들을 출력한 뒤(p가 말하는 숫자들을 출력해야하므로) t -1까지의 수를 최종으로 출력하면 된다 

1. 1부터 9까지는 정수를 넣고, 10이상인 수는 알파벳으로 바꿔서 data에 저장한다. 이제 들어온 수를 data로 이용해서 n진법으로 바꿀 것이다

2. i번째 수를 n진법으로 바꾸려면 i를 n으로 나눈 나머지에 매칭되는 수를 오른쪽으로 누적해 나간다(temp)

3. 그 값을 누적해야하므로 str_value에 누적해간다 

4. str_value에서 p가 말하는 숫자들을 반복문을 통해 answer에 옮긴 후 t개만큼만 반환하면 된다 

- 정답 풀이 :

def solution(n, t, m, p):
    answer = ''
    
    data = dict()
    
    for i in range(16):
        data[i] = str(i)
        if i > 9:
            data[i] = chr(i + 55)
            
    for i in range(t * m):
        temp = ''
        if i == 0:
            str_value = '0'
            continue
            
        while i > 0:
            temp = data[i % n] + temp
            i //= n
            
        str_value += temp
        
    for i in range(len(str_value)):
        if i % m == p - 1:
            answer += str_value[i]
            
    return answer[:t]

- 시도해본 풀이 :

50 퍼센트에서 계속 틀렸던 풀이다 

이 로직에서는 13, 16같은 10대인 수에만 적용이 된다

50을 13진법으로 표현하면 3A(11)인데, 아래 로직으로하면 30이 출력된다 

def change(number, n):
    mul = 0
    temp = number
    if n > 10 and 10 <= temp <= (n - 1):
        return chr(temp + 55)
    
    while True:
        if temp // n == 0:
            break
        mul += 1
        temp = temp // n 
        
    result = ''   
    for i in range(mul, -1, -1):
        if number // (n ** i) != 0:
            result += str(number // (n ** i))
            number -= (n ** i) * (number // (n ** i))
        else:
            result += '0'
    return result
                
            
def solution(n, t, m, p):
    changed = ''    
    number = 0
    while len(changed) < t * m :
        #숫자를 n진법 수로 변환시키기
        changed += change(number, n)
        number += 1

    changed = list(changed)
    answer = ''
    for i in range(len(changed)):
        if i % m == p - 1:
            answer += changed[i]
                        
    return answer[: t]

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/43165

처음에는 왜 dfs,bfs를 사용하는 건지 이해가 가지 않았지만, 생각해보니 +이든 -이든 숫자들이 차례로 진행되기 때문에 이는 dfs로 진행해야겠다고 생각했다 

문제 이해

탐색이 끝난 후 수의 합을 target과 비교해야하므로 이를 num_sum을 이용해서 진행하고, 숫자도 하나씩 움직여야하므로 idx 변수도 이용한다

1. numbers 내부에 있는 숫자라면 그 숫자를 num_sum에 더하고, 뺀 값으로 dfs를 진행한다

2. numbers에 있는 모든 원소들을 다 사용해야하므로 마지막 인덱스까지 사용했는지 확인하고, 숫자의 총 합이 target과 같으면 갯수 +1 해준다. idx + 1을 통해 숫자도 오른쪽으로 한 칸 옮겨 준다

참고한 블로그

- 정답 풀이 :

answer = 0
def dfs(idx, num_sum, target, numbers):
    global answer
    if idx == len(numbers) and num_sum == target:
        answer += 1
        return True
    if idx != len(numbers):
        dfs(idx + 1, num_sum + numbers[idx], target, numbers)
        dfs(idx + 1, num_sum - numbers[idx], target, numbers)
            
def solution(numbers, target):  
    dfs(0, 0, target, numbers)
    
    return answer

- 시도해본 풀이 :

정확하지는 않지만, 인덱스에 대한 설정이 없어서 틀렸던 것 같다

numbers에서 원소 하나씩 꺼낸 다음 그것을 더했을 때와 - 했을 때의 값을 넣어서 진행한다 

진행하다가 모든 수의 합이 target과 같으면 함수를 멈춘다(일단 모든 원소를 다 사용해야하는데 이렇게 하면 모든 원소를 다 사용하지 않아도 수의 합이 target이 되는 경우가 있어서 이렇게 작성하면 안될 것 같다)

answer = 0
def dfs(numbers, num_sum, target):
    global answer
    diff = [1 , -1]
    if num_sum == target:
        answer += 1
        return True
    
    if len(numbers) > 0:
        x = numbers.pop(0)
        for i in range(2):
            nx = x * diff[i]
            num_sum += nx
            dfs(numbers, num_sum, target)
            num_sum -= nx
            
def solution(numbers, target):    
    dfs(numbers, 0, target)
    
    return answer