📕문제 LeetCode 20. Valid Parentheses 문제 설명 괄호들로 이루어진 문자열이 유효한지 확인하는 문제다. 조건 열린 괄호는 같은 유형의 괄호로 닫아야 한다. 열린 괄호는 올바른 순서대로 닫혀야 한다. (=열린 순서가 늦은 순서대로 닫혀야한다.)
LeetCode 226. Invert Binary Tree주어진 이진트리를 좌우반전시키는 문제다.해당 노드가 자식을 가지지 않을 때까지 재귀적으로 left값, right값을 바꾼다.invertTree 함수 자체를 재귀함수로 활용하여 코드를 깔끔하게 만들었다.
LeetCode 21. Merge Two Sorted Lists정렬된 두개의 연결 리스트 list1, list2를 하나의 정렬된 연결 리스트로 병합하는 문제다.Example 1Input: list1 = 1,2,4, list2 = 1,3,4Output: 1,1,2,3,4
LeetCode 100. Same Tree주어진 두 이진트리 q와 p가 같은지 판별하는 문제다.Example 1Input: p = 1,2,3, q = 1,2,3Output: true두 트리를 비교했을 때 같지 않은 조건은 다음과 같다.두 트리의 모양이 다를 떄같은 위치
LeetCode 70. Climbing Stairs한 번에 1칸 또는 2칸을 오를 수 있을 때 n칸의 계단을 오르는 경우의 수가 몇개인지 구하는 문제다.n = 3 일 때1 + 1 + 12 + 11 + 2계단을 오를 수 있는 경우의 수는 3가지다.직접 몇개의 계단에 대해
LeetCode 104. Maximum Depth of Binary Tree이진트리의 root가 주어졌을 때 트리의 높이를 구하는 문제다.Input: root = 3,9,20,null,null,15,7Output: 3오답!제출한 첫번째 코드다. 아이디어는 다음과 같다.
LeetCode 347. Top K Frequent Elements주어진 숫자 리스트에서 가장 많이 출현한 숫자를 k개 구하는 문제다.리스트를 순회하며 해당 숫자가 딕셔너리에 key로 존재하면 해당 값에 1을 더한다.존재하지 않는다면 딕셔너리에 해당 숫자를 key로 추
📕문제 [LeetCode] 128. Longest Consecutive Sequence 문제 설명 정렬되지 않은 숫자 리스트에서 가장 긴 연속된 숫자의 개수를 구하는 문제다. 예를들어 [100,4,200,1,3,2] 가 주어졌을 때 가장 긴 연속된 숫자는 [1,2,3
\[LeetCode] 15. 3Sum숫자 리스트에서 중복 사용 없이 3개의 숫자합이 0이 되는 조합을 찾는 문제다.예를들어 -1, 0, 1, 2, -1, -4 에서 3개의 숫자합이 0인 조합은 -1, -1, 2, -1, 0, 1 2개다.처음 생각한 아이디어는 다음과 같
\[LeetCode] 153. Find Minimum in Rotated Sorted Array1에서 n번만큼 회전된 길이가 n인 정렬된 리스트가 주어졌을 때 가장 작은 수를 출력하는 문제다.이 때 회전이란 0, 1, 2 가 있을 때 1번 회전하면 2, 0, 1, 2번
\[LeetCode] 3. Longest Substring Without Repeating Characters문자열 s에서 중복된 문자를 포함하지 않는 부분 문자열의 최대 길이를 구하는 문제다.투포인터변수 설명left: 부분 문자열의 시작 인덱스right: 부분 문자열
\[LeetCode] 424. Longest Repeating Character Replacement대문자로 이루어져있는 문자열과 k가 주어졌을 때, k개만큼 문자를 교체해서 만들 수 있는 같은 문자로 이루어진 부분 문자열의 최대 길이를 구하는 문제다.알고리즘 스터디에
📕문제 [Leetcode] 98. Validate Binary Search Tree 문제 설명 주어진 트리가 이진탐색트리(BST)인지 판별하는 문제다. BST가 되기위한 조건 왼쪽 서브트리의 모든 값은 현재 노드 값보다 작아야 한다. 오른쪽 서브트리의 모든 값은 현
\[Leetcode] 19. Remove Nth Node From End of List링크드 리스트의 끝에서 n번째 노드를 제거하는 문제다.예를들어 1, 2, 3, 4, 5가 주어지고 n이 2인 경우, 끝에서 2번째 노드인 4를 제거한 1, 2, 3, 5를 반환하면 된
📕문제 [Leetcode] 143. Reorder List 문제 설명 연결 리스트의 순서를 주어진 규칙대로 재배치하는 문제다. 규칙은 다음과 같다. [1, 2, 3, 4, 5 ... n-2, n-1, n]을 재배치하면 [1, n, 2, n-1, 3, n-2 ...]이
\[LeetCode] 79. Word Search문자가 있는 m x n 테이블에서 주어진 단어가 존재하는지 판별하는 문제다. 인접한 셀은 연결된 것으로 순차적으로 방문한 문자로 단어를 이룰 수 있으며, 방문한 셀은 재방문할 수 없다.예를들어 위와 같은 테이블에서 단어
\[Leetcode] 39. Combination Sum숫자 후보들로 합이 target이 되도록 하는 조합을 구하는 문제다. 이 때 각 후보들은 중복이 가능하다.BackTrackingbackTracking()함수는 현재까지 선택한 숫자 조합을 저장한 리스트인 prevL
\[Leetcode] 230. Kth Smallest Element in a BSTBST에서 k번째로 작은 숫자를 구하는 문제다.이전에 풀었던 98.Validate Binary Search Tree와 코드가 유사하다.BST는 중위순회하면 오름차순이라는 점을 이용한다.탐
\[Leetcode] 207. Course Schedule과목의 개수인 numCourses와 각 과목을 수강하기 위한 선수과목을 나타내는 리트스인 prerequisites가 주어졌을 때 모든 과목을 수강할 수 있는지 구하는 문제다.예를 들어 numCourses = 2,
📕문제 [[Leetcode] 200. Number of Islands]
📕문제 [Leetcode] 211. Design Add and Search Words Data Structure 문제 설명 단어 등록과 단어 검색을 할 수 있는 자료구조를 만드는 문제다. 생성자와 자료구조를 word를 등록하는addWord(word) 함수, 자료구조
\[Leetcode] 198. House Robber도둑이 훔칠 수 있는 최대 금액을 구하는 문제다.집에 존재하는 돈의 액수는 배열의 형태로 주어지고, 연속된 두개의 집을 털게되면 경찰에게 발각된다.예를들어 1,2,3,1이 주어졌을 때 훔칠 수 있는 최대 금액은 1+3
\[Leetcode] 213. House Robber II\[Leetcode] 198. House Robber에서 확장된 문제다.도둑이 훔칠 수 있는 최대 금액을 구하는 문제다.집에 존재하는 돈의 액수는 배열의 형태로 주어지고, 연속된 두개의 집을 털게되면 경찰에게 발
\[Leetcode] 5. Longest Palindromic Substring문자열에서 가장 긴 palindromic substring(대칭 부분문자열)을 찾는 문제다.첫 아이디어는 스택을 이용하는 것이었다.스택을 이용해 문자열을 하나씩 검사하며 가장 긴 대칭 부분문
\[Baekjoon] 1932. 정수 삼각형정수 삼각형에서 맨 위부터 시작해 아래에 있는 수 중 하나를 선택해서 내려오면서 더할 때 최댓값을 구하는 문제다.위 그림에선 최댓값이 $7+3+8+7+5 = 30$ 이 된다.아래로 내려가면서 숫자가 더해지는 경우는 세가지가 있
\[Baekjoon] 1904. 01타일하나의 타일로 이루어진 1과, 두개의 타일로 이루어진 00 타일이 존재할 때 N개의 타일로 만들 수 있는 이진수열의 종류가 몇개인지 구하는 문제다.N = 1 일 때 만들 수 있는 이진수열은 1 1개.N = 2 일 때 만들 수 있는
📕문제 [Baekjoon] 1541. 잃어버린 괄호 문제 설명 숫자와 +, -로 이루어진 문자열에서 적절하게 괄호()를 사용해 만들 수 있는 최솟값을 구하는 문제다. 예를들어 100-50+50 이 주어졌을 때의 최솟값은 100-(50+50) = 0이 된다. 📝
📕문제 [Baekjoon] 6593. 상범 빌딩 문제 설명 정육면체 모양의 빌딩에서 출발지에서부터 시작해 도착지에 도착할 수 있는지, 가능하다면 걸리는 최단 거리를 구하는 문제다. 인접한 칸인 동, 서, 남, 북, 상, 하로만 움직일 수 있으며 일부 칸은 막혀있어
\[Baekjoon] 2458. 키 순서키가 모두 다른 N명의 학생끼리 M번의 키 비교가 이루어졌다.이 때 자신의 키가 몇 번째인지 알 수 있는 학생이 총 몇명인지 구하는 문제다.예를 들어 6명의 학생이 있고 다음과 같이 6번의 키 비교가 이루어졌다고 하자.1번 학생의
분할정복(Divide and Conquer)은 문제를 작은 부분 문제로 나누고, 각각을 해결한 후 전체 문제의 답을 구하는 알고리즘 기법이다.보통 재귀(Recursion)를 활용해 문제를 점진적으로 해결한다.분할정복의 3단계는 다음과 같다.분할(Divide) - 문제를
\[Baekjoon] 18222. 투에-모스 문자열0과 1로 이루어진 무한한 문자열 X가 존재할 때 k번째에 무슨 문자가 오는지 구하는 문제다.문자열 X는 다음과 같은 규칙으로 이루어진다.X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자
다익스트라(Dijkstra)는 한 정점(시작 정점)에서 부터 모든 정점까지의 최단 거리를 각각 구하는 알고리즘이다.이 때 그래프는 음의 간선을 포함하지 않아야 한다.다익스트라 알고리즘은 다이나믹 프로그래밍, 그리디 알고리즘 기법을 사용한 알고리즘이라고 볼 수 있다.그
📕문제 [Baekjoon] 1446. 지름길 문제 설명 D킬로미터의 도로에 N개의 지름길이 존재한다고 했을 때, 출발지에서부터 목적지까지 운전하는 최소 거리를 구하는 문제다. 지름길은 시작 지점, 끝 지점, 지름길의 길이 형태로 주어지며, 모든 지름길의 시작 지점은
백트래킹이란? 백트래킹(BackTracking)은 탐색 알고리즘 중 하나로, 탐색을 통해 정답을 찾아가다 가능성이 없다고 판단하면 해당 분기에 대한 탐색을 중단하고 되돌아가서 정답을 다시 찾아가는 기법이다. 더이상 탐색할 필요가 없는 상태를 제외(가지치기)시키며 탐색
\[Baekjoon] 14620. 꽃길칸마다 비용이 다른 N x N 크기의 화단에서 3개의 꽃을 피울 수 있는 최소 비용을 구하는 문제다.꽃은 심은 칸을 기준으로 상하, 좌우로 잎이 피며 서로 다른 꽃이 만나거나 화단 밖으로 나가지 않아야 한다.꽃은 심은 칸을 포함해
집합은 어떤 명확한 조건을 만족시키는 서로 다른 대상들의 모임이다.분리집합은 말 그대로 분리된 집합이다.다른 말로 서로소 집합이라고도 하며 각각의 집합이 공통 원소를 가지고 있지 않은 집합을 말한다.전체 집합 U에서 분리 집합 A, B는 다음과 같은 조건을 만족한다.A
\[Baekjoon] 4195. 친구 네트워크Fred, Barney, Barney, Betty 와 같이 새로운 친구 관계가 주어질 때마다 해당 친구 네트워크에 존재한 인원 수를 출력하는 문제다.친구의 친구와 같이 관계를 따라갔을 때 연결되어 있으면 같은 친구 네트워크에
재귀 함수란? 재귀 함수란 자기 자신을 호출하는 함수다. 즉, 함수 내부에서 자기 자신을 다시 실행하는 구조를 가진 함수로 특정 조건이 만족될 때 까지 반복 호출된다. 재귀 함수는 크게 두 가지 요소로 구성된다. 기저 조건(Base case): 재귀 호출을 멈추는 조
\[Baekjoon] 30678. 별 안에 별 안에 별 찍기패턴에 따라 별을 찍는 문제다.아래는 양의 정수 $i$에 대해 Star$i$의 패턴이다.$i=0$$i=1$$i=2$is_star: 해당 칸에 별을 찍을지 판단하는 함수.재귀 형태로 가장 큰 패턴에서부터 작은 패
\[Baekjoon] 2660. 회장 뽑기모임에서 회장을 선출하기 위해 후보를 선정하는 문제다.회원들 간의 친구 여부가 주어졌을 때, 모든 회원과 친구인 회원은 1점, 모든 회원과 친구이거나 친구의 친구이면 2점, ... 이런 식으로 점수가 매겨진다.가장 작은 점수인
\[Baekjoon] 12908. 텔레포트 3크기가 무한인 격자판이 존재할 때 시작점인 (xs, ys)에서부터 도착점인 (xe, ye)까지 가는 데 걸리는 최소 시간을 구하는 문제다.기본적으로 상하좌우로 한 칸씩 이동하는 데 1초씩 걸린다.추가로 두 구간((x1, y1
📕문제 [Baekjoon] 5557. 1학년 문제 설명 줄 지어있는 숫자가 주어질 때 숫자 사이에 +혹은 -를 넣어 마지막 수를 만들 수 있는 올바른 등식을 만드려고 한다. 예를 들어 "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4
\[Baekjoon] 1253.좋다N개의 수 중 어떤 수가 다른 두 수의 합으로 나타낼 수 있을 때 그 수를 좋은 수라고 한다.이 때 N개의 수 중에서 좋은 수가 몇개인지 구하는 문제다.수가 같더라도 위치가 다르면 다른 수로 친다.ex) ..., 0, 0, ... 에서