코딩: 말하기, 듣기, 쓰기 -1

03/22/2022

백트랙킹

백트랙킹: BFS, DFS 와같은 완전탐색을 효율적으로 만들어주는것. 즉, 모든것을 다 보겠다는것. → 브루트포스랑 비슷하다. 그런데 한번 방문한 곳은 안가도록 효율적으로 만드는 방식이다. 필요없는 부분 다 가지치기해서 시간복잡도 줄이는 것.

트리

뿌리와 가로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료구조.

by Hanghae99

by 파이썬 알고리즘 인터뷰

높이 = 현재위치 + 리프
깊이 = 루트 + 현재노드

Diagnol traverse

https://leetcode.com/problems/diagonal-traverse/

문제보자마자 드는생각:
이건 보아하니 역순 뭔가 써야할거같은데. 내가 봤을땐 이거 뭔가 규칙있다. 대각선 올라가고 내려가고 방향설정 해주고. 음..
우선 스타트 1로 끊어주고. 몇행 몇렬인지 알아야하고. For 문 두개 돌려줘야 행렬에 각 밸류를 뽑아낼수있지않을까...?
그리고 짝수 번째 대각선마다 대각선이 내려가는 것을 볼 수 있다.
2 (0, 1), 4 (1,0) -> 인덱스 합이 같음 1로 같음
3 (0, 2), 5(1, 1) 7(2, 0) -> 인덱스 합이 같음 2로 같음
그리고 인풋값도 생각해보자. 우선 3x3 행렬이야.
대각선들이 나올 갯수들을 생각해봐야할것같다왠지.. 그래야 뭔가 수치화 해서 넣을 수 있을듯. 여기선 5개가 나온다. 그렇다면 4x4에서는 몇개가 나올까? 대각선의 갯수 = M + N - 1

def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
	    num_rows = len(mat) # 행의 길이
        num_cols = len(mat[0]) #열의 길이
        diagonals = [[] for _ in range(num_rows + num_cols - 1)] #대각선 갯수로 리스트 만들어 주기
        
        for i in range(num_rows):
            for j in range(num_cols):
                diagonals[i+j].append(mat[i][j])
                #대각선 만들어준 리스트에다가 값들 일단 저장. 키값 밸류값 이렇게. 키값은 인덱스합들로 분류.
        
        res = diagonals[0] # 1
        
        for x in range(1, len(diagonals)):
            if x % 2 == 1: #인덱스를 갖고 2로 나누어지면 역순, 아니면 정순으로 해준다 그러고 리턴!
                res.extend(diagonals[x])
            else:
                res.extend(diagonals[x][::-1])
        return res

이렇게 짠 코드풀이가 나와 생각이 제일 맞았고, 내가 추구하는 정말 직관적인 코드였다. 나도 비슷하게 짰으나, for문에서 막혔다. 오늘 문제를 풀어봤는데 내가 정말 디테일이 부족한것같다. 문법에 대한 정확한 이해가 부족해서 그런가, 아니면 내가 스스로 생각하는 힘이 부족해서그런가. 개선하기위해서 접근을 어떻게했고, 어떻게 풀어낼수있는지 지속적으로 생각하는 힘을 만들어야한다. 부족하다.

이진트리의 최대깊이

https://leetcode.com/problems/maximum-depth-of-binary-tree/

문제보자마자 드는생각:
이건뭘까..? 인풋 보니까 null, null이 있는데...이건 분명 저기 가지는 카운트를 안친다 그런 느낌인거고. 가지가 두개로 갈라지니까, 왼쪽 오른쪽 느낌 가줘야하는거고. 그전에 저 루트 시작 어떻게 해줘야하는데. 어디서 봤는데 재귀로 가지 뻗는거 많이 쓰인다고 했는데.. 음..그리고 내가봤을땐, BFS로간다. 왜냐하면 3 -> 9 -> 20 순으로 가는데 DFS느낌 아니고 너비탐색느낌가니까. 이건 확실하다. 그렇다면, BFS 쓴다는 뜻은 Queue 쓴다는거고, 이거 쓴다는건 데크 필요하다는거고. 그러면 while <queue? 이런 느낌 가줘야하는데 맞겠지? 흠.
대충 느낌:
루트노드 초기화.
담아줄 데크 초기화.
while < 담아줄데크:
가지만들어주는 함수(?):
조건 맞으면 레프트 =
조건 맞으면 라이트 =
리턴 가지만들어주는 함수(?)
.
.
.
이런건가...

고민 후....튜터 강의도보고 혼자 끙끙앓다가...

def test_max_depth(lst):
    if not root:
        return 0

    q = deque([root])
    depth = 0

    while q:
        depth += 1
        for _ in range(len(q)):
            cur = q.popleft()
            if cur.left:
                q.append(cur.left)
            if cur.right:
                q.append(cur.right)

    return depth

대충 비슷한것 같기도하고... 우선 대체적인 구조는 비슷한 것같다. 하지만, 떨어지는건 디테일함. 데크를 이용해서 큐를 사용하여 초기화 해주는것 맞고. 그리고 depth라는 주머니를 만들어서 카운트를 할 것을 만들어주고. 그후에 큐에 어떠한 값이 있으면 돌아가게끔 while문을 만들어주고, 그다음에 depth 1 증가. 그다음에 for문을 만들어준다. 이걸 내가 생각을 이어가지 못했다. q의 길이만큼 반복하도록 한다...이게 좀 어렵다. 부모노드의 길이만큼 돌려준다. 그다음에 큐에서 밸류 꺼내서 왼쪽인지 오른쪽인지 봐주고 나와서 다시 for문 나온다음에 다시 while문 진입. for문의 역할은 부모노드가 있는지 없는지 확인하고 그다음에 자식노드가 왼쪽인지 오른쪽인지 봐주는 것이다. 큐 길이로 for문 돌린다는 것 자체부터가 인풋의 길이만큼 돌린다는 말인데...이런 것을 생각하는 센스가 없다. 이런식으로 계속 문제접근 연습 해보면 금방 구현 가능하지 않을까?