알고리즘 공부 (스텍, BFS문제)

프로그래머스 lv2. 올바른 괄호

def solution(s):
    stack = []
    for i in s:
        if i == '(':  
            stack.append(i)
        else:  
            if stack == []:  
                return False
            else:
                stack.pop() 
    
    return stack==[]

괄호가 올바르면 펄스, 올바르지 않다면 투르를 뱉는 풀이 방식이다.
스텍 문제도 그렇고, 큐 문제도 그렇고 머리속으로 그리는게 제일 중요한 것 같다.
어떻게 원소가 들어가고, 나가는지 에 대해 정확한 파악이다.

프로그래머스 lv2. 타겟넘버

def solution(numbers, target):
    answer = 0
    leaves = [0]
    for num in numbers:
        tmp = []
        for parent in leaves:
            tmp.append(parent + num)
            tmp.append(parent - num)
        leaves = tmp
    for leaf in leaves:
        if leaf == target:
            answer += 1
    return answer

BFS 을 이용한 풀이 방법이다.
아직 BFS, DFS 의 풀이 방식이 익숙하지는 않다.

BFS (Breadth-First Search)

• BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다

• BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다

• 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다

• 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다

• 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다

알고리즘은 공부는 연습이 답이다. 현재 CS준비, 이력서, 포토폴리오 등 할게 너무나도 많지만

새벽에 하는 알고리즘 스터디를 꾸준하게 진행해야 할 것 같다.