본문 바로가기

Algorithm/LeetCode9

[Medium] 5. Longest Palindromic Substring 길이 [1, 1000] 범위의 문자열 s가 주어지면, 그 안에서 가장 긴 팰린드롬을 찾아 반환하는 문제이다. 팰린드롬이란 "aba", "abba", "eye"처럼 거꾸로 읽어도 동일한 단어를 말한다. 문제 유형은 DP로 분류되어 있었는데, 처음엔 DP로는 어떻게 풀지 방법이 생각이 안나서 그냥 나이브한 방법으로 풀었고, 두 번째에는 디스커션을 확인하여 DP로 풀었다. 1) 우선 내가 푼 방법이다. 나는 s의 첫 문자부터 시작해서 끝까지 순회를 할 것이다. 현재 문자가 s[i]라면 맨 뒤에서부터 s[i]와 동일한 문자를 찾는다. 찾은 위치의 인덱스가 j라고 했을 때, [i, j] 범위를 검사하여 팰린드롬인지 확인한다. s[j]는 가장 뒤에서부터 찾은 문자이므로 s[i]에 대해선 가장 긴 팰린드롬이 된다. .. 2021. 9. 27.
[Easy] 338. Counting Bits int타입 n이 주어지면 n+1 길이의 int형 배열을 생성하고 이 배열의 i번 째 원소를 i를 이진수로 나타내었을 때 1의 개수로 채워서 반환하는 문제이다. 즉 3번째 원소는 3(0011)의 1의 개수인 2이다. 처음엔 그냥 쉽게 bitset 클래스를 이용하여 풀었는데, 분류가 DP로 되어 있어서 DP 풀이법을 봤더니 내 머리로는 생각도 못했을 방법이었다. 우선 bottom-up 방식으로 낮은 원소부터 채운다. 그리고 i번째 값은 두 부분으로 나누어서 구한다. 한 부분은 첫 번째 비트 부분이고 한 부분은 나머지 비트 부분이다. 예를 들어 i가 3일 경우, 3을 2로 나눈다. 2로 나누는 것은 1bit만큼 right shift 하는 것과 같다. 그러면 0011이 0001이 되고 이는 십진수로 1이다. 그.. 2021. 9. 26.
[Easy] 121. Best Time to Buy and Sell Stock 각 [i] day의 주식 가격이 담긴 int형 배열이 주어지고, 주식을 사고 팔아야 할 때 수익을 최대화하면 수익이 얼마인지 구하는 문제이다. 예를 들어 첫 번째 예에서 가격이 1일 때 사서 6일 때 팔면 수익이 5로 최대가 된다. 처음엔 배열 profit을 선언하고 profit[i]를 i에서 살 때 최대 수익으로 정의했었다. 그러면 price[i]를 기준으로 그 뒤에 가격들에 대하여 한 번씩 확인하였다. 즉 이중 루프가 되는데 시간 초과가 떴다. 아직 알고리즘 문제를 많이 접해보지 않아서 그런지 방법이 바로 생각나지 않았다. 생각을 좀 해보다가 profit[i]를 i에서 살 때가 아닌 팔 때의 최대 수익으로 정의하였더니 쉽게 풀렸다. 우선 profit[0]은 항상 0이 된다. 그리고 i 이전의 min .. 2021. 9. 26.
[Easy] Leetcode | 101. Symmetric Tree | TREE BFS DFS - 문제 주어진 이진 트리가 중심을 기준으로 대칭인지 판별한다. - 풀이 다른 여러가지 방법이 있겠지만, 내가 풀이한 방법은 다음과 같다. 1. root 노드를 기준으로 왼쪽 서브트리는 전위 순회(preorder)를 한 결과를 vector에 순서대로 저장한다. 2. root 노드를 기준으로 오른쪽 서브트리는 root-right-left 노드 순으로 순회한 결과를 vector에 순서대로 저장한다. 3. 위에서 구한 두 vector의 요소를 서로 비교하여 다른 요소가 있다면 false를 반환, 모두 같으면 true를 반환한다. 아래 코드에서 1번 예제인 [1, 2, 2, 3, 4, 4, 3] 트리를 예를 들어 위 방법을 적용해보면 다음과 같다. 1. leftSubTree: [2, 3, 4] 2. rightS.. 2020. 4. 24.
[Easy] Leetcode | 70. Climbing Stairs | Dynamic programming - 문제 계단을 오르는 데 정상까지 오르려면 n번의 step을 거쳐야 한다. 한 번에 오를 수 있는 계단의 수는 1 또는 2 step이다. 정상까지 오를 수 있는 방법의 수는? Note: n은 양의 정수로 주어진다. - 풀이 n을 1부터 조금씩 나열해보면 규칙이 보인다. n=1) 1 n=2) 2 n=3) 3 n=4) 5 n=5) 8 n=6) 13 ... 피보나치 수열이다. 즉, 위의 각 결과가 f의 함수의 결과라고 했을 때 각 결과는 다음과 같다. n=1) 1 n=2) 2 n=3) f(2) + f(1) n=4) f(3) + f(2) n=5) f(4) + f(3) n=6) f(5) + f(4) ... 재귀 함수로 구현하면 시간 복잡도는 지수 시간의 복잡도를 가진다. O(2^n) 이 경우 시간 초과로 테스트.. 2020. 4. 20.
[Easy] Leetcode | 53. Maximum Subarray | dynamic programming - 문제 integer 배열이 nums로 주어지는데, nums의 연속적인 부분 배열의 합 중 최댓값을 찾아 반환해주는 함수를 작성하는 문제이다. (부분 배열은 최소 1개의 요소를 가짐) - 풀이 연속적인 부분 배열의 최대합을 구하기 위해 다음과 같은 계획을 세웁니다. 다른 풀이 방법은 더 빠른 시간 복잡도를 가질 수 있지만, 해당 방법은 선형 시간(O(n))의 복잡도를 가진다. 1. 각 요소를 마지막 요소로 가지는 부분 배열들의 합(sum) 중 가장 큰 값을 벡터(subArrayMaxSum)에 저장한다. => 즉, subArrayMaxSum라는 벡터의 [i]번 째 요소엔 nums[i]를 마지막 요소로 가지는 부분 배열의 합 중 가장 큰 합이 들어있다. 2. subArrayMaxSum의 요소 중 가장 큰 .. 2020. 4. 18.

티스토리툴바