Binary Search Tree란? 👉 개념 Binary Search Tree(BST)는 효율적인 탐색을 위한 데이터 저장 방법이다. 👉 규칙 노드에 저장되는 키는 유일하다. 부모의 키 값이 왼쪽 자식 노드의 키 값보다 크다. 부모의 키 값이 오른쪽 자식 노드의 키 값보다 작다. 왼쪽과 오른쪽 서브트리도 BST이다. 👉 장단점 장점 탐색 연산 시간복잡도가 O(log N)이다. (명확히 말하면 O(h)) 단점 편향 트리의 경우 저장 순서에 따라서 한 쪽으로만 노드가 추가되는 경우가 발생한다. 최악의 경우는 탐색 시간복잡도가 O(N)이다. 배열보다 많은 메모리를 사용한다. Leetcode 문제를 통한 BST 구현 BST를 직접 구현하는 것이 도움이 될 것이라 생각하여 아래 문제를 풀어보았다. 1. 탐색: ..

🤔 문제. Palindromic Substring: 거꾸로 뒤집어도 같은 문자열, 예를들어 aaa, baaab 등. 🤗 풀이. 문자열 DP 문제이다. start포인트와 길이를 담을 변수를 지정한다. (기존 Palindromic Substring의 정보를 저장할 용도) for문을 실행하여 end포인트를 이동시켜준다. 특정 조건일 때 start 포인트와 길이를 변경한다. 기존 Palindromic Substring에 end포인트의 문자를 포함했을 때, Palindromic을 만족한다. Ex. aaa 기존 Palindromic Substring에 end포인트의 문자와 Substring의 앞의 문자를 포함했을 때, Palindromic을 만족한다. Ex. baaab HTML 삽입 미리보기할 수 없는 소스

🤔 문제. 2차원 배열을 시계방향으로 돌리는 간단한 문제입니다. 🤗 풀이. [단순 구현] 처음 풀었던 방식은 순수한 구현이었다. 끝에서 부터 한 바퀴씩 돌며 좌표를 담는 xy_list와 값을 담는 v_list를 만든 뒤, v_list 값을 수정해서 matrix를 재구성하였다. 통과는 했지만, 실행 시간이 오래걸렸다. HTML 삽입 미리보기할 수 없는 소스 [간단한 방법] 위에서는 2차원 배열을 1차원 배열로 바꿔서 풀려는 시도를 했다. 하지만 2차원 배열을 전체적으로 움직이며 푸는 방법이 있었다. matrix를 행을 중심으로 뒤집는다. matrix를 대각선을 중심으로 뒤집는다. HTML 삽입 미리보기할 수 없는 소스 실행속도는 2배 정도 차이난다... 역시 알고리즘 문제는 구현 전에 생각을 해야한다! 😓

🤔 문제. Array에서 3개를 골라 0이 되는 sub-array를 구하는 문제입니다. 처음에는 2Sum을 구한 후에 하나씩 확인하며 구성하는 것으로 구현했는데, 시간초과가 나버렸습니다... 시간을 좀 더 들여 고민한 결과 정렬 후 투포인트로 문제를 풀었습니다. 🤗 풀이. Array를 sort한다. for문을 통해 값을 하나 잡고, left/right 포지션을 지정한다. 투포인트를 옮기면서 합이 0이되는 Array를 저장한다. (이때 중요한 점은 정답에 같은 Array는 포함되지 않도록 함으로 같은 과정을 최소화하는 방향으로 진행한다.) HTML 삽입 미리보기할 수 없는 소스

알고리즘을 공부하기 위해서 릿코드의 문제를 풀어보고자 했다. 파이썬이 주언어라서 파이참을 자주 이용하는데, 릿코드와 파이참을 연결할 수 있다고 하여 연결하여 사용하고 있는 중이다. 파이참에 릿코드 연결하기 File > Settings > Plugins > Leetcode 검색 > Install 클릭 > OK 클릭 우측에 leetcode 창이 나타난다. 우선 릿코드를 실행하기 위해서 로그인을 하면 문제를 풀 수 있다. 릿코드 플러그인에서는 아래와 같은 다양한 기능을 사용할 수 있는데, 자주 사용하는 기능은 아래와 같다. 테스트 케이스로 코드 실행하기 테스트 케이스 구성하기 코드 제출하기 타이머 실행 이제 릿코드 플러그인 도움받아 편리하게 알고리즘 공부를 즐겨보자! 👊