학교 시험이 얼추 끝나고 싸강 시험만 남아서 여유가 좀 생겨 코테에 다시 집중해보려 한다!
오늘부터 1/13일에 있을 naver AI boostcamp 준비 시작.
한달 동안 죽었다 생각하고 도전해볼 생각이다

문제 풀이

타겟 넘버 - DFS/BFS

1. BFS

from collections import deque
def solution(numbers, target):
    answer = 0
    queue = deque()
    queue.append([0, numbers[0]])
    queue.append([0, -1*numbers[0]])
    while queue:
        idx, num = queue.popleft()
        idx += 1
        if idx == len(numbers):
            if num == target:
                answer += 1
        else:
            queue.append([idx, num+numbers[idx]])
            queue.append([idx, num-numbers[idx]])
    return answer

< 풀이 과정 >
그동안 그래프 문제는 행렬 문제와 유사하게 생긴 것만 풀다가 이런 형태로 접근하니 색다르게 느껴졌고 문제 풀이를 하고자 접근하는데 시간이 좀 걸렸다.

• 쉽게 생각해보면 numbers[0]을 기준으로 +다음 인덱스, -다음 인덱스가 다음 노드로 이어지는 그래프 형태로 볼 수 있다.
• queue라는 deque를 생성해준 후 while문을 돌려 다음 numbers값을 계산해주기 위해 현재의 numbers를 popleft()로 idx, num을 빼주어 처리한다.
• 이후 인덱스를 1씩 더해주면서 주어진 numbers길이보다 짧은 경우 queue에 다음 numbers값을 더하거나 빼준 것을 추가해주고 계산이 다 끝난 이후 target과 일치하는 num이 있는 경우 answer에 1을 더해준다.

2. DFS

answer = 0

def dfs(idx, num, numbers, target):
    global answer
    if idx == len(numbers):
        if num == target:
            answer += 1
        return
    else:
        dfs(idx+1, num+numbers[idx], numbers, target)
        dfs(idx+1, num-numbers[idx], numbers, target)

def solution(numbers, target):
    global answer 
    dfs(0,0,numbers,target)
    return answer

< 풀이 과정 >
DFS를 이용한 풀이 DFS함수를 새로 만들어서 문제를 해결하였다.

• answer를 전역변수로 idx, num, numbers, target으로 변수를 사용하는 dfs함수 만들기
• idx가 numbers 길이와 같으면 결과물인 num이 target과 일치하면 answer에 1을 더해주고 아닌 경우 idx+1, num+-numbers[idx], numbers, target을 다시 불러온다

[3차] 압축 - 2018 카카오 블라인드 채용

def solution(msg):
    alpha = {}
    for i in range(26):
        alpha[chr(65+i)] = i+1
    idx = 0
    number = 27
    check =''
    answer = []

    while idx < len(msg):
        check += msg[idx]
        if check in alpha:
            idx += 1
        else:
            alpha[check] = number
            number += 1
            answer.append(alpha[check[:-1]])
            check = ''
    answer.append(alpha[check])
    return answer

< 풀이 과정 >
문제를 보자마자 알파벳 별 indexing을 위해 chr함수와 dictionary 구조를 이용하였다.

• 인덱스 변수 idx, 주어진 문자 이외의 문자 발견 시 색인번호 출력 위한 변수 number, w+c 이후 msg내의 문자 속하는 지 확인 위한 변수 check 생성
• while 문으로 인덱스 크기가 len(msg)보다 작아야만 실행되도록 하고 현재 주어진 인덱스 문자만 check 문자열에 추가
• check 문자가 alpha내의 존재할 경우 다음 인덱스 검사
• check 문자가 alpha내의 없는 경우 새로운 문자 색인번호 지정
• 이후 answer로 w만 출력해야 하므로 check[:-1]이용하여 출력값 answer리스트에 추가
• while문 다 돈 이후 제일 마지막 check문자가 w이므로 이를 출력하기 위해 answer.append 실행

더 맵게

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while scoville[0] < K:
        mixing = heapq.heappop(scoville) + heapq.heappop(scoville)*2
        heapq.heappush(scoville, mixing)
        answer += 1
        if scoville[0] < K and len(scoville) == 1:
            return -1
    return answer

< 풀이 과정 >
sorting과 pop이 필요하다면 heapq로 해결하는 것이 가장 효율적이다.
heapq는 이전에 공부했던 적이 있어 바로 문제 풀이를 할 수 있었다.

• 자료구조가 리스트인 scoville을 heap으로 변환 (heapify)
• heap으로 인해 알아서 오름차순 정렬된 힙 scoville에서 첫번째 값이 K보다 작은 경우 음식 섞기 진행하고 섞은 음식 힙에 넣고 횟수 + 1 처리 (heappop, heappush)
• 이후 음식을 다 섞어도 K를 넘지 못하면 -1을 리턴

위 문제를 풀면서 heap을 다시 정리해보고자 한다.

• heapq (오름차순 정렬된 트리 형태 구조) - 최소힙, 최대힙 존재
  heapify(list) : 리스트 > 힙 자료구조 변환 가능
  heappop(heap) : 힙 내 최솟값 리턴
  heappush(heap, number) : 힙에 숫자 추가

• 최소힙의 경우 루트노드가 최솟값으로 시작
  위 문제는 최소힙 case로 해결 가능.

• 최대힙의 경우 루트노드가 최댓값으로 시작
  그러나 최대힙의 경우 부호 변경이 필수!!
  < 부호 변경 하는 방법 >
  heapq.heappush(heap, -number)
  -heapq.heappop(heap)
  위와 같은 방법을 통해 부호 변환하여 큰 숫자부터 출력 가능!