아스

php를 실행하기 위해서는 XAMPP라는 외부 프로그램이 필요하다. XMAPP는 Apache, Mysql 등의 프로그램을 모아서 설치해주고 apache와 mysql의 실행을 관리해 준다. xmapp에서 설치해주는 apache 서버를 사용해서 php를 로컬에서 실행할 수 있다. 

xampp 설치는 해당 링크에서 할 수 있다. installer 파일이 실행되면 설치 창이 뜰 텐데, 추천하는 선택지(recommend)를 선택해서 클릭해서 설치해주면 된다. 

사실 php파일의 실행에서 mysql은 필요하지 않다. 다만 대부분의 백엔드에서는 데이터베이스를 사용하는 것이 일반적이므로 필요할 경우 xampp를 사용하면 mysql과 php를 연결한 뒤, apache와 mysql을 같이 실행할 수 있다는 장점이 있다. 

php는 xampp가 설치된 디렉토리를 /xampp라고 하면, /xampp/htdocs 폴더 내부를 기본 실행 디렉토리로 한다. (변경하는 방법이 분명 있겠지만 여기서는 그 방법을 모르므로 이 디렉토리로 파일들을 옮겨서 실행했다.)

영상에서는 여기에 폴더를 하나 만들고, 그 디렉토리 내부에 여러 개의 php 프로젝트를 두던데 이렇게 진행하면 관리하기에 편리할 것 같았다. 

apache와 필요에 따라서 mysql까지 구동하고 나면(start 버튼을 눌러서 간단히 구동할 수 있다), localhost/dashboard url을 통해 기본 페이지를 로딩할 수 있다. 이 경로가 /xampp/htdocs 경로에 해당한다. 앞서 폴더를 하나 만들고 그 안에 여러 프로젝트 디렉토리를 만들었으므로, /localhost/dashboard/folder_name/project_name/... 이런 식으로 url을 입력하면 원하는 php 파일을 브라우저에 띄울 수 있다. 

참고한 포스트

https://www.youtube.com/watch?v=tcoIVp1eNgM

프로그래머스에서 SQL 문제를 풀면서 나왔던 함수들을 정리해 보았다. 

☑️SQL 함수/필터링 기능 예시

✅ IS NULL / IS NOT NULL

: WHERE 컬럼명 IS NOT NULL

위 SQL문의 경우 컬럼명이 NULL이 아닌 데이터만 조회한다. 

✅ LIKE

: WHERE 컬럼명 LIKE "글자 형식"

WHERE 절의 조건으로 문자열 타입에 대해 더 구체적인 조건으로 필터링할 때 사용한다. 

예를 들어 특정 단어를 포함하는 경우에도 글자 형식을 잘 지정해서 사용할 수 있다. 아래 SQL문은 ADDRESS의 값이 서울-로 시작하는 레코드만 조회한다. 

WHERE ADDRESS LIKE "서울%"

LIKE의 자세한 사용에 대해서는 문서를 참고하자. 

LIKE는 주로 어떤 단어를 앞이나 뒤에 포함하는 레코드를 필터링할 때 많이 사용된다. 

"단어%" : '단어'로 시작하는 레코드

"%단어" : '단어'로 끝나는 레코드

"%단어%" : '단어'를 포함하는 레코드

✅ DATE_FORMAT

: DATE_FORMAT(컬럼명, "바꾸려는 형식")

컬럼이 날짜 타입일 경우 문제에서 요구하는 출력 형식이 따로 있을 때 주로 사용한다. 

예를 들어 '2022-03-05 01:13:00' 인 날짜 형식을 '2022-03-05'로 출력해야 하는 경우가 있다. 

두 번째 매개변수에서는 날짜 타입의 컬럼명을 어떤 형식으로 출력하고 싶은지를 명시해 준다. 자세한 정보는 공식문서에 나와 있지만 많이 사용되는 값들은 정해져 있다. 대소문자가 구별되니 주의하자. 

%Y: 연도를 4자리 값으로 출력

%m: 월을 숫자로 출력

%d: 일을 숫자로 출력

앞선 예시처럼 출력하려면 다음과 같이 입력하면 된다. 

DATE_FORMAT(DATETIME, "%Y-%m-%d")

✅ YEAR, MONTH, DAY

: YEAR(컬럼명), MONTH(컬럼명), DAY(컬럼명)

날짜 데이터에서 년, 월, 일 데이터를 추출해 준다. 시간이나 분 정보를 추출해 주는 함수(HOUR, MINUTE 등)도 있지만 위의 함수들이 더 많이 쓰인다. 

# DATETIME = '2022-05-26'
YEAR(DATETIME)	# 2022
MONTH(DATETIME) # 5
DAY(DATETIME) # 26

✅ IFNULL

: IFNULL(컬럼명, "출력할 값")

NULL값인 데이터를 다른 값으로 출력해 준다. 

아래 예시의 경우 NAME의 값이 NULL이면 "NO NAME"으로, NULL이 아니면 원래 값으로 출력한다. 

IFNULL(NAME, "NO NAME")

✅ MAX, MIN

: MAX(컬럼명), MIN(컬럼명)

해당 컬럼에서 가장 큰 값, 가장 작은 값을 출력해 준다. 

아래 예시의 경우 STUDENT_SCORE 테이블의 SCORE 컬럼 데이터들 중 가장 큰 값을 출력하고, 이때 컬럼 이름은 MAX_SCORE로 출력한다. 

SELECT MAX(SCORE) AS MAX_SCORE FROM STUDENT_SCORE

✅ SUM, AVG, COUNT

: SUM(컬럼명), AVG(컬럼명), COUNT(컬럼명)

해당 컬럼의 합, 평균, 레코드 개수를 구할 수 있다. 

아래 예시의 경우 STUDENT_SCORE 테이블의 SCORE 컬럼 데이터들의 평균값을 반올림한 값을 보여주고, 컬럼 이름은 AVG_SCORE로 출력한다. 

SELECT ROUND(AVG(SCORE)) AS AVG_SCORE FROM STUDENT_SCORE

참고한 포스트

https://www.w3schools.com/sql/sql_like.asp

☑️TIP

더 많은 SQL 문제들 찾아보기

☑️계기

원래 SQL과는 접점이 없는 사람이었는데 이번에 코테를 준비하면서 처음 SQL 문제를 접하게 되었다. 단기간에 공부하는 데는 프로그래머스의 SQL 고득점 Kit가 효과적이라는 말을 들어서 무작정 연습문제를 풀면서 공부했다. 

그 결과 어렵고 복잡한 문제는 아직 못 풀지만 초급-초중급 난이도까지의 문제는 간단한 문법으로 풀리는 것 같아서 까먹기 전에 내용을 정리해 보려고 한다. 

SQL 문법 정리

1. 기본 조회

특정 조건을 걸지 않고 모든 데이터를 조회한다. 

✅ 전체 컬럼의 전체 데이터 조회

: SELECT * FROM 테이블명

데이터베이스의 모든 컬럼에 대해서 모든 데이터를 조회하는 SQL문이다.

*을 사용하면 모든 컬럼 이름을 나열하지 않고 전체를 불러올 수 있다. 

SELECT * FROM ANIMAL_INS

✅ 특정 컬럼의 전체 데이터 조회

: SELECT 컬럼1, 컬럼2, ... 컬럼N FROM 테이블명

해당 SQL문을 실행하면 USER_INFO 테이블의 컬럼 중에서 USER_ID, USER_NAME, USER_ADDRESS 컬럼의 데이터만 불러온다. 

SELECT USER_ID, USER_NAME, USER_ADDRESS FROM USER_INFO

✅ 특정 컬럼의 이름을 바꿔서 조회

: SELECT 컬럼1 AS C1, 컬럼2 AS C2, ... 컬럼N AS CN FROM 테이블명

위의 SQL문과 리턴하는 데이터는 같지만 리턴할 때의 컬럼 명이 다르다. 

SELECT USER_ID AS UID, USER_NAME AS UNAME, USER_ADDRESS AS UADDRESS FROM USER_INFO

보통 컬럼 이름을 그냥 바꾸지는 않는다. 컬럼에 다른 SQL 함수를 적용하면 컬럼 이름이 변경되는데, 다시 원래 컬럼 이름으로 출력하기 위해서도 사용한다. 

2. 조건 추가

주어진 조건에 맞는 데이터만 불러온다. 

WHERE 키워드를 사용하고, SELECT와 FROM 바로 뒤에 조건을 붙인다. 

✅ 조건 명시하기

: SELECT 컬럼명 FROM 테이블명 WHERE 조건

아래 예시의 경우, 전체 데이터들 중 나이가 9세 이상인 유저 데이터만 불러온다. 

SELECT UID, UNAME, UAGE FROM USER_INFO WHERE UAGE >= 9

✅ 조건 여러 개를 동시에 만족하는 데이터 추출하기

: SELECT 컬럼명 FROM 테이블명 WHERE 조건1 AND 조건2

아래 예시의 경우, ID가 10 미만이고 나이가 9세 이상인 유저 데이터만 불러온다. 

SELECT UID, UNAME, UAGE FROM USER_INFO WHERE UID < 10 AND UAGE >= 9

✅ 조건 여러 개 중 하나 이상 만족하는 데이터 추출하기

: SELECT 컬럼명 FROM 테이블명 WHERE 조건1 OR 조건2

아래 예시의 경우, ID가 10 미만이거나 나이가 9세 이상인 유저 데이터만 불러온다.

SELECT UID, UNAME, UAGE FROM USER_INFO WHERE UID < 10 OR UAGE >= 9

3. 정렬

ORDER BY 키워드를 사용한다. 여러 컬럼을 기준으로 오름차순(ASC) 또는 내림차순(DESC)으로 정렬할 수 있다. 

지정된 순서가 있는 것은 아니지만 보통 맨 마지막에 쓰는 것이 일반적이다. 

: ORDER BY 컬럼A ASC, 컬럼B DESC

위의 커맨드는 컬럼A의 값을 오름차순대로 정렬한 다음, 컬럼A의 값이 같은 데이터가 있는 경우 컬럼B의 값을 기준으로 내림차순으로 정렬해 준다.

4. 그룹별로 데이터 묶기

GROUP BY 키워드를 사용한다.

데이터를 추출한 뒤 특정 컬럼의 값이 같은 레코드들을 묶을 수도 있다. 보통 컬럼별로 그룹을 묶어서 제시할 때 사용한다. 

: GROUP BY 컬럼명

GROUP BY를 사용하는 경우 맨 처음에 SELECT 뒤에는 일반 컬럼명보다는 SQL 함수를 적용한 컬럼들이 오는 경우가 많다. 보통 그룹별로 데이터를 제시할 때는 그룹별 데이터의 평균, 합, 최댓값 등을 제시하기 때문이다. 

아래 예시에서는 상품코드별로 가장 비싼 상품의 가격을 조회한다. 

SELECT PRODUCT_CODE, MAX(PRICE)
FROM PRODUCTS
GROUP BY PRODUCT_CODE

5. 여러 개의 테이블 데이터 묶기

JOIN 키워드를 사용한다. 

테이블 A와 테이블 B가 있을 때, 두 테이블이 같은 컬럼을 공유하는 경우 사용할 수 있다. 

:

SELECT A.컬럼1, B.컬럼2

FROM 테이블A (AS) A

JOIN 테이블B (AS) B ON A.공유컬럼 = B.공유컬럼

위의 SQL문은 '공유컬럼'이라는 같은 컬럼을 공유한 테이블A와 테이블B를 조인해서 A의 컬럼1과 B의 컬럼2에 대한 데이터를 조회한다. 

아래 SQL문은 BOOK_ID라는 컬럼을 공유하는 BOOK_INFO 테이블과 BORROW_INFO 테이블을 조인한 뒤, BOOK_NAME과 BORROW_ID 두 컬럼에 대한 데이터를 조회한다. 

SELECT A.BOOK_NAME, B.BORROW_ID
FROM BOOK_INFO A
JOIN BORROW_INFO B ON A.BOOK_ID = B.BOOK_ID

사실 JOIN에 대해서는 INNER JOIN, OUTER JOIN 등 여러 가지가 있고 내용이 많지만 초중급 단계의 문제는 그 이상을 다루지는 않았던 것 같다. 기회가 된다면 JOIN 기능에 대해서도 자세히 정리해 보고 싶다. 

6. 그룹별 데이터 필터링

HAVING 키워드를 사용한다. 

필터링이라는 점에서 WHERE과 기능이 유사하지만, HAVING은 항상 GROUP BY 이후에 사용한다는 점이 다르다. 

즉 WHERE 문은 데이터를 그룹별로 나타내기 전에, 어떤 조건의 데이터를 GROUP BY에 적용할지를 필터링한다. 

반면 HAVING문은 데이터를 그룹별로 나타낸 이후, 어떤 조건의 그룹화된 데이터를 최종 조회할지를 필터링한다. 

WHERE과 HAVING의 자세한 차이는 여기를 참고하자. 

참고한 포스트

https://cocoon1787.tistory.com/684

https://www.javatpoint.com/where-vs-having

https://www.w3schools.com/sql/func_mysql_date_format.asp

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

leetcode 297번 ( https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/ )

✅교재를 참고하지 않은 풀이

📌BFS

(1) 직렬화

직렬화(TreeNode -> string) 로직에서는 root 노드 하나를 입력으로 받아서 그 아래 있는 노드들을 문자열 형식으로 출력해야 한다. 따라서 root 노드에서 시작해서 자식 노드들을 레벨 순서대로 순회해야 한다. 

1. 트리 전체의 노드를 데크에 레벨 순서대로 담기

이전 문제에서도 트리 전체를 탐색하는 데 BFS 방법을 사용한 것처럼, 큐(여기서는 데크)를 이용하면 트리의 모든 노드를 레벨 순서대로 순회할 수 있다. 파이썬의 데크 자료형은 리스트와 거의 유사하지만 내부적으로는 투 포인터를 사용해서 구현되었기 때문에 리스트의 맨 앞과 맨 뒤에서 원소를 추가하거나 삭제하는 데 O(1)이 소요된다. 

2. 불필요한 null 노드 제거하기

그러나 이대로 리스트로 변환할 수는 없고 추가 작업이 필요하다. 문제의 예시에서는 null인 노드가 있더라도 그 레벨보다 더 낮은 레벨에 노드가 존재하는 경우 'null' 값으로 표시되어야 하기 때문에 데크의 중간중간 null 값이 들어있다. 

위 그림의 경우 노드 값만 순서대로 나타내면 [1,2,3,4,5]이지만 중간의 빈 노드도 포함하기 때문에 실제로는 [1,2,3,null,null,4,5]가 리턴되어야 한다. 이렇게 나타내려면 left, right 자식 노드가 전부 null인 '2'번 노드를 탐색할 때도 2번 노드의 자식 노드를 큐에 추가해야 한다. 

그러나 이 방법대로 탐색하면 결과는 [1,2,3,null,null,4,5,null,null]로 출력된다. 4, 5번의 자식 노드가 없지만 2번과 같은 방법으로 탐색하여 null인 자식 노드가 큐에 추가되었기 때문이다. 

이를 수정하기 위해서 큐의 맨 뒤의 원소부터 탐색해서, null이 아닌 값이 나올 때까지 지우면 불필요한 null 노드(leaf 노드의 자식 노드)를 제거할 수 있다. 

3. 큐를 문자열로 변경

지금까지 작업했던 큐(데크) 형태의 자료형을 문자열로 바꿔서 출력해야 한다. str()로 큐를 문자열 형식으로 바꿔 준 다음, 출력 형식에 맞게 공백을 제거하고 "None"을 "null"로 바꾸는 추가 작업을 해서 바꿔준다. 

전체 직렬화 코드는 다음과 같다. 

def serialize(self, root):

    # use bfs
    if not root:
        return "[]"

    queue = collections.deque([root])
    array = []

    while queue:
        for _ in range(len(queue)):
            elem = queue.popleft()
            if elem is None:
                array.append(None)
            else:
                array.append(elem.val)
                queue.append(elem.left)
                queue.append(elem.right)

    while True:
        if array[-1] is None:
            array.pop()
        else:
            break

    result = str(array).replace(" ", "").replace("None", "null")
    return result

(2) 역직렬화

역직렬화(string->TreeNode) 로직에서는 앞서 문자열로 바꾼 값을 변환해서 트리의 모든 값을 left, right 자식 노드로 포함한 root 노드를 리턴해야 한다. 

1. 문자열을 리스트(배열)로 변환

앞서 추가 처리를 통해 데크를 문자열로 변환했었는데 이번에는 반대로 작업한다. 문자열의 앞뒤로 붙은 괄호[]를 제거한 뒤 ,로 구분된 원소들을 .split() 메소드를 사용해서 배열로 변환한다. 그러면 트리의 각 노드들의 값이 문자열 형태로 순서대로 저장된 배열을 얻을 수 있다. 

위의 트리 노드의 경우 ["1", "2", "3", "null", "null", "4", "5"]의 문자열 값들이 저장된 배열을 얻을 수 있다. 

2. 큐를 사용해서 배열의 값들을 추가로 트리 노드에 할당하기

위 배열의 값을 root 노드부터 순서대로(부모->자식 방향으로) 할당해야 한다. 앞서 레벨 순서대로 탐색하기 위해서 큐를 사용했는데, 같은 이유로 여기서도 큐를 사용한다. 

우선 root 노드의 값(1번 배열의 첫 번째 원소)을 가진 트리 노드를 선언한 뒤 해당 노드를 원소로 가진 큐를 선언한다. 트리 노드를 선언하는 데 사용된 배열의 값은 배열에서 제거해 준다. 

여기서의 배열은 큐가 아닌 리스트이지만 pop(0) 메소드를 사용하면 맨 앞에서도 원소를 제거할 수 있다. (물론 큐와 달리 O(1)이 아니라 O(n) 만큼의 시간이 걸린다.)

2-1. 배열의 값에 따라서 할당 방식을 다르게 하기

1번 배열의 맨 앞에서부터 값을 제거했을 때, 해당 값이 "null"일 수도, 문자열 형식의 숫자일 수도 있다. 

null 값이라면 트리 노드를 선언해서 값을 할당하지 않고 None 값을 할당하자.

반면 문자열 형식의 숫자(ex. "1")라면 해당 값을 숫자로 변환한 뒤 이 값을 value로 갖는 트리 노드를 선언해서 연결해 주자. 

이때 트리 노드는 위의 레벨에서 아래 레벨로, 왼쪽부터 오른쪽으로 할당되므로 한 노드의 자식 노드에 값을 할당할 때도 왼쪽 자식 노드부터 할당해 준다. 

전체 역직렬화 코드는 다음과 같다. 

def deserialize(self, data):

    if data == "[]":
        return None

    string = data.replace("[", "").replace("]", "")
    array = string.split(",")

    root = collections.deque([TreeNode(array.pop(0))])
    head = root[0]

    while root and array:
        elem = root.popleft()
        if elem is not None:
            if array:
                if array[0] == "null":
                    array.pop(0)
                    elem.left = None
                    root.append(None)
                else:
                    elem.left = TreeNode(int(array.pop(0)))
                    root.append(elem.left)
            if array:
                if array[0] == "null":
                    array.pop(0)
                    elem.right = None
                    root.append(None)
                else:
                    elem.right = TreeNode(int(array.pop(0)))
                    root.append(elem.right)

    return head

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

leetcode 617번 ( https://leetcode.com/problems/merge-two-binary-trees/ )

✅교재를 참고한 풀이

📌재귀

문제에서 주어진 기본함수를 재귀함수로 사용해서 문제를 푸는 방법이다. 

두 개의 트리를 합쳐야 하므로, 재귀함수에서는 두 트리 각각의 노드 하나씩을 입력으로 받는다. 

만약 두 트리 모두 노드가 있다면 두 노드값의 합을 값으로 가진 노드를 리턴한다. 

if root1 and root2:
    node = TreeNode(root1.val+root2.val)

노드를 리턴하기 전, 자식 노드들에 대해서도 새 값을 가진 TreeNode를 할당해 주어야 한다. 

왼쪽, 오른쪽 자식 노드에 대해서 각각 재귀함수를 호출해서 TreeNode를 계산해 준 다음에 값을 리턴한다. 

node.left = self.mergeTree(root1.left, root2.left)
node.right = self.mergeTree(root1.right, root2.right)

return node

두 트리 중 하나의 노드만 있다면 해당 노드를 리턴한다. 

해당 코드의 경우, 두 트리의 노드가 모두 없을 때에는 None을 리턴하게 된다.

else:
    return root1 or root2

💡post-order traversal(후위 순회)

코드가 실행되는 순서는 다음과 같다.

1. 현재 노드의 값(두 트리를 합쳤을 때 현재 노드의 위치에 오는 값) 계산

2. 현재 노드의 왼쪽 subtree들의 값 계산

3. 현재 노드의 오른쪽 subtree들의 값 계산

그러나 실제로는 2번과 3번(left subtree, right subtree의 값)이 계산된 후에야 parent 노드의 값이 계산되므로, 이 재귀함수는 postorder(후위 순회) 방식으로 탐색한다. 

후위 순회 방식에서는 다음 순서로 탐색한다. 

1. 노드의 left subtree

2. 노드의 right subtree

3. 노드 자신

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

leetcode 226번 ( https://leetcode.com/problems/invert-binary-tree/ )

✅교재를 참고하지 않은 풀이

📌DFS

이진 트리의 root 노드가 입력으로 주어질 때, 이진 트리를 좌우로 반전시키고 해당 트리의 root 노드를 리턴하는 문제이다. 

좌우로 반전시키려면 root 노드를 기준으로 왼쪽 subtree와 오른쪽 subtree를 바꾸면 된다. 

root 노드를 기준으로 모든 노드를 좌우 반전하려면 결국은 leaf 노드에서부터 작업을 시작해야 한다. 만약 leaf 노드까지 가지 않고 root 노드 바로 아래 레벨의 노드만 바꾼다면 아래 레벨의 노드들은 반전되지 않기 때문이다. 

예를 들어 다음과 같은 이진 트리를 입력받았다고 해 보자. 

만약 root 노드 바로 아래 레벨의 노드들 위치만 바꾸게 된다면 트리는 이런 모양이 된다. 

그러나 좌우 반전 트리는 모든 레벨의 노드들의 위치가 바뀌어야 하므로 위의 방법으로는 풀 수 없다. 좌우 반전은 아래처럼 7, 2 노드의 하위 노드들의 위치도 모두 바뀌어야 한다. 

따라서 재귀 함수를 사용해서 DFS 탐색으로 leaf 노드를 찾은 뒤, 해당 노드부터 다시 위 레벨로 올라오면서 자기 아래에 있는 두 노드의 위치를 바꾸는 방식으로 구현한다. 

또한 파이썬이 아닌 다른 언어(자바나 C언어)에서는 두 변수의 값을 바꿀 때 임시로 다른 변수 하나를 추가하는 방법을 쓴다. 

int a = 1;
int b = 2;

int temp = a;
a = b;
b = temp;

그러나 파이썬에서는 다중 할당을 사용할 수 있다. 

a = 1
b = 2

a, b = b, a

전체 코드는 다음과 같다. 

class Solution(object):

    def invertTree(self, root):
    
        def dfs(node):
            if not node:
                return
                
            dfs(node.left)
            dfs(node.right)
            
            if node.left and node.right:
                node.left, node.right = node.right, node.left
            elif node.left:
                node.left, node.right = None, node.left
            elif node.right:
                node.left, node.right = node.right, None
            
        head = root
        dfs(root)
        return head

✅교재를 참고한 풀이

📌재귀를 사용한 파이썬 방식

위의 DFS 방식을 그대로 사용하고 코드를 더 간소화할 수 있다. 중첩 함수를 사용하지 않고 주어진 함수를 그대로 호출해서 사용했다. 

if root:
    root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
    return root
return None

📌BFS

위에서는 leaf 노드부터 좌우 반전을 시작해야 한다고 적었지만 교재를 보니 BFS를 사용해서도 좌우 반전을 할 수 있었다. 

BFS의 경우 재귀함수로 구현이 불가능하므로 큐를 선언한 뒤 while문을 사용해서 큐의 앞에서 원소를 빼내고, 그 아래 레벨의 노드를 다시 큐의 맨 뒤에 넣으면서 구현했다. 

DFS는 leaf 노드부터 탐색이 진행되지만 BFS에서는 root 노드부터 시작해서 아래로 내려가면서 노드를 바꾼다. 

전체 코드는 다음과 같다. 

class Solution(object):

    def invertTree(self, root):
        queue = collections.deque([root])

        while queue:
            current = queue.popleft()
            if current:
                current.left, current.right = current.right, current.left
                queue.append(current.left)
                queue.append(current.right)

        return root

📌DFS

위의 코드에서 한 줄만 바꾸면 BFS 대신 DFS로 구현할 수 있다고 한다. 

BFS는 FIFO인 큐를 사용하는 반면 DFS는 LIFO인 스택을 사용하므로, 큐의 맨 앞에서부터 노드를 빼내던 로직을 큐의 맨 뒤에서부터 노드를 제거하도록 수정하면 된다. 

참고한 포스트

https://velog.io/@hysong/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%8B%A4%EC%A4%91-%ED%95%A0%EB%8B%B9Multiple-Assignment

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

leetcode 687번 ( https://leetcode.com/problems/longest-univalue-path/ )

✅교재를 참고하지 않고 시도: DFS -> 실패

한 노드에 대해서 2개의 자식 노드가 있을 때, 해당 노드와 자식 노드의 값이 같을 때 DFS 탐색을 하고 값을 1씩 증가시키는 로직을 구현했다. 

그러나 위 그림처럼 여러 개의 값이 연속되는 트리가 입력으로 주어지면 중간에 다른 값이 나올 때는 DFS 탐색이 되지 않게 되어 오류가 발생한다. 

따라서 값이 연속되건 되지 않건 모든 경우에 DFS 탐색이 되어야 하고, 다만 노드와 자식 노드의 값이 같은지 다른지에 따라서 DFS 탐색을 한 값을 그대로 사용하거나 바꾸도록 구현해야 하겠다. 

class Solution(object):
    longest = 0

    def longestUnivaluePath(self, root):
        
        def dfs(node):

            if not node or (not node.left and not node.right):
                return 0

            left, right = 0, 0
            if node.left and node.val == node.left.val:
                left = dfs(node.left)
            if node.right and node.val == node.right.val:
                right = dfs(node.right)

            if left != 0 and right != 0:
                self.longest = max(self.longest, left + right + 2)
            elif left != 0:
                self.longest = max(self.longest, left)
            elif right != 0:
                self.longest = max(self.longest, right)
                
            return max(left, right) + 1

        result = dfs(root)
        return self.longest

✅교재를 참고해서 시도: DFS 

1. 클래스 변수 사용

교재에서도 DFS를 사용해서 진행하였다. 이전 문제와 같은 이유로 클래스 변수를 선언하고 가장 긴 동일값의 경로는 해당 변수에 저장하는 방법을 사용했다.

중첩 함수 내부에서 지역 변수를 사용하지 않은 이유는, '가장 긴 동일값의 경로'는 정수 형식이라서 불변 객체(immutable object)이고, 불변 객체인 변수는 중첩 함수의 내부에서 같은 이름으로 사용되더라도 값이 변경되지 않기 때문이다. 즉 중첩 함수 내부에서 값을 바꿔도 중첩 함수 바깥의 로컬 변수의 값이 변경되지 않는다. 

대신에 클래스 변수는 클래스 내부의 메소드에서 모두 공유되는 변수이므로 중첩 함수에서 변경하건, 바깥 함수에서 변경하건 클래스 변수의 값이 모두 변경된다. 

class Solution(object):
    longest = 0

    def longestUnivaluePath(self, root):
        // code

2. 모든 경우에 대해서 DFS 탐색을 하고 경우에 따라 세분화

DFS 탐색은 leaf 노드에 도달할 때까지 계속 자식 노드를 호출하다가 leaf 노드가 발견되면 여기서부터 탐색을 시작한다. 그러므로 leaf 노드에 도달했을 때 실행할 base case를 만들어 주자.

leaf 노드 하나에 대해서만 DFS 탐색을 실행한다고 가정하면 당연히 가장 긴 경로값은 0이므로 0을 리턴한다. 

if node is None:
    return 0

모든 경우에 대해서 DFS 탐색을 한다. 이때 이진 트리라서 왼쪽, 오른쪽 두 방향으로 탐색이 가능하므로 왼쪽 자식 노드와 오른쪽 자식 노드 모두에 대해서 각각 탐색을 진행한다. 

left = dfs(node.left)
right = dfs(node.right)

이때 left와 right는 각각 왼쪽, 오른쪽 자식 노드까지 DFS 탐색을 했을 때 가장 긴 경로를 나타낸다. 

이는 DFS 중첩 함수의 리턴값으로, 클래스 변수에 저장되는 값과는 다르다. 

DFS 중첩 함수의 리턴값은 leaf 노드에서부터 올라가면서 탐색을 시작하고, 계속 같은 값을 가진 노드가 나올 때마다 1씩 증가한다. 중간에 다른 값인 노드가 나오면 다시 0으로 초기화된다. 

if node.left and node.val == node.left.val:
    left += 1
else:
    left = 0
    
if node.right and node.val == node.right.val:
    right += 1
else:
    right = 0
    
return max(left, right)

반면 클래스 변수에 저장되는 값은 DFS 중첩 함수에서 리턴되는 값과 자기 자신을 계속 비교해서 더 큰 값을 저장한다. DFS 탐색 중 중간에 다른 값인 노드를 만나서 리턴값이 0으로 초기화되더라도 클래스 변수의 값은 초기화되지 않는다는 차이가 있다. 

self.longest = max(self.longest, left + right)

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

leetcode 543번 ( https://leetcode.com/problems/diameter-of-binary-tree/ )

✅교재를 참고하지 않은 풀이: BFS

1차 시도(실패)

이진 트리의 직경(diameter)은 가장 거리가 먼 두 노드간의 거리이다. 

그래서 root 노드를 기준으로 왼쪽 subtree에서 가장 root에서 멀리 떨어진 노드와 오른쪽 subtree에서 가장 root와 멀리 떨어진 노드의 거리를 잰 뒤, 둘을 합하면 될 것이라고 생각하고 접근했다. 

그러나 예외가 있었다. 

위의 트리처럼 한쪽 subtree에만 많은 노드가 위치한 경우, root를 기준점으로 나눠서 계산한 직경(=7)보다 하나의 subtree 안의 다른 노드를 기준으로 계산한 직경(=8)이 더 컸다. 

class Solution(object):

    def diameterOfBinaryTree(self, root):

        if root is None or (root.left is None and root.right is None):
            return 0

        heightLeft = 0
        heightRight = 0

        queueLeft = collections.deque([root.left])
        queueRight = collections.deque([root.right])

        if root.left is not None:
            while queueLeft:
                heightLeft += 1
                for _ in range(len(queueLeft)):
                    current = queueLeft.popleft()
                    if current.left:
                        queueLeft.append(current.left)
                    if current.right:
                        queueLeft.append(current.right)

        if root.right is not None:
            while queueRight:
                heightRight += 1
                for _ in range(len(queueRight)):
                    current = queueRight.popleft()
                    if current.left:
                        queueRight.append(current.left)
                    if current.right:
                        queueRight.append(current.right)
        
        return heightLeft + heightRight

따라서 root 노드만을 기준으로 왼쪽, 오른쪽 subtree의 leaf 노드까지의 거리를 비교하면 안 되고 모든 노드를 기준으로 이 작업을 반복해서 가장 큰 값을 구하면 된다. 

✅교재를 참고한 풀이: DFS

BFS를 사용하지 않고 DFS를 사용하면 더 간단하게 풀 수 있었다. 

위의 경우 BFS는 맨 위의 root 노드부터 시작했지만 DFS는 leaf 노드에 도달하기 전까지는 탐색을 계속한다. 

DFS의 경우 재귀로 구현할 수 있고, 가장 긴 직경 값은 변수를 하나 선언하고 그 값을 업데이트 하면서 진행하면 된다. 그러나 가장 긴 직경 값은 숫자 변수인데, 숫자형은 변할 수 없기 때문에(immutable) 재귀함수 내부에 업데이트 로직을 작성해도 값이 바뀌지 않는다. 

그러므로 여기서는 직경 값 변수를 클래스 내부 변수로 선언했다. 이러면 self.longest 으로 해당 클래스 내부 변수에 접근할 수 있으므로 재귀 함수로도 같은 변수에 접근해서 값을 업데이트 할 수 있다. 

class Solution(object):
    longest = 0
    
    def diameterOfBinaryTree(self, root):
        //

이제 dfs()를 실행할 재귀함수 내부를 보자. 

재귀함수는 항상 반복적인 코드와 기본 상태(base case)가 필요하다. dfs()는 TreeNode 타입의 노드를 매개변수로 받고 dfs 탐색을 진행한 뒤 해당 노드의 레벨을 숫자로 리턴한다. 이 노드가 null 값일 경우 탐색을 하지 말아야 하므로 이 상태를 base case로 정하자. 

이때, null인 노드는 leaf 노드보다 더 하위 단계에 위치하므로 0이 아니라 -1을 리턴한다. 

if node is None:
    return -1

반복 로직의 경우, 한 노드를 기준으로 left subtree, right subtree 각각에 대해 dfs를 실행한다.

left = dfs(node.left)
right = dfs(node.right)

반복 로직이 실행되는 경우는 해당 노드가 left, right subtree를 가진 노드라고 볼 수 있다. 

(leaf 노드의 경우, null 값을 갖는 노드를 left, right subtree로 갖고 있다고 볼 수 있다.)

따라서 left, right subtree의 높이를 계산해서 더 큰 것을 선택한 다음에 1을 더해 준다. 해당 노드는 left, right subtree의 부모 노드이기 때문이다. 

return max(left, right) + 1

또한 가장 큰 직경 값도 업데이트 해 주어야 한다.

앞서 dfs()에서도 높이를 계산할 때 left, right subtree의 높이에다 1을 더했다.

한 노드를 중심으로 계산한 직경이 가장 크다는 의미는 직경을 계산하는 두 노드가 각각 해당 노드의 left subtree, right subtree에 위치한다는 말이다. 그러므로 두 subtree의 높이를 더한 뒤 1을 두 번 더해야 한다. 

self.longest = max(self.longest, left + right + 2)
return self.longest