문제 https://leetcode.com/problems/word-break/ Word Break - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Medium 두 종류의 메모이제이션을 활용해서 해결하였다. 1. is_contain[i][j] 문자열 s의 i~j 부분 배열이 단어로 분해될 수 있는지 여부를 저장한다. 이를 확인하기 위해 모든 단어들을 언어에서 기본 제공하는 문자열의 find함수로 s에 포함 여부를 확인한다. 이때 s= "aaaaa..

백준에서 어떤 문제를 풀어야 할지 감이 안 오시는 초심자 분 혹은 질 좋은 알고리즘 문제만 뽑아서 풀고 싶은 분들에게 추천드리고 싶은 것이 아래의 릿코드 추천 문제 목록이다. https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time New Year Gift to every fellow time-constrained engineer out there looking for a job, here's a list of the be..

문제 https://leetcode.com/problems/longest-common-subsequence/ Longest Common Subsequence - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Medium 유명한 DP문제. ' text1을 A, text2를 B라고 했을 때 A의 i번째, B의 j번째 알파벳이 동일하다면 적어도 A의 i번째, B의 j번째 이후로는 공통부분 수열(CS)의 길이가 1 이상이 된다. 이처럼 A의 i번째와 B의..

문제 https://leetcode.com/problems/longest-increasing-subsequence/ Longest Increasing Subsequence - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Medium 대표적인 DP문제로 최대 증가 부분 수열(LIS) 문제라고 한다. O(n^2)의 풀이와 O(n log(n))의 풀이가 있는데 두 개 다 소개하도록 하겠다. 1. O(n^2) 풀이 가장 간단한 풀이로 배열의 뒤에서부터 ..

문제 https://leetcode.com/problems/coin-change/ Coin Change - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Medium 유명한 다이나믹 프로그래밍 문제. 처음 풀면은 그리디 방식으로 가장 높은 동전 순서대로 amount값을 만들어 가기 쉽다. 하지만 동전이 [1, 4, 6]로 있을 때 14를 만들어야 된다고 생각해보자. 가장 높은 동전인 6을 먼저 2개 사용하면 나머지 2는 1의 동전 2개로 만들어 총..

문제 https://leetcode.com/problems/missing-number/ Missing Number - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Easy 난이도 순으로 3가지 풀이를 소개하겠다. (가장 중요한 풀이는 3번째라고 생각한다.) 1. 정렬 time complex O(n log n) 가장 쉬운 풀이는 배열을 정렬하고 순서대로 살펴보며 빠진 수를 찾는 것이다. 하지만 배열의 정렬에 큰 복잡도가 소요된다. 2. 전체 합 이..

문제 https://leetcode.com/problems/counting-bits/ Counting Bits - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Easy 위의 그림을 보면 알겠지만 2^k ~ 2^(k+1) -1 의 수들은 k+1 번째 비트가 1이고 나머지는 0 ~ 2^k -1와 뒷부분이 완전히 동일하다. 따라서 0 ~ 2^k -1의 비트에서 1의 수들에 + 1을 붙인 것이 2^k ~ 2^(k+1) -1의 1의 개수가 된다. 따라서 ..

문제 https://leetcode.com/problems/sum-of-two-integers/ Sum of Two Integers - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Medium 어려운 문제라기보다는 비트 연산자를 잘 활용해서 구현을 해야 하는 문제이다. 같은 부호끼리의 합은 두 수를 양수로 고려하고 덧셈 후에 부호를 붙여주면 되기 때문에 같은 부호의 수를 더하는 함수와 다른 부호를 더하는 함수를 따로 구현하였다. 일단 같은 부호라..

문제 https://leetcode.com/problems/container-with-most-water/ Container With Most Water - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Medium 훨씬 간단한 스위핑 풀이가 있지만 정렬을 이용한 본인의 풀이부터 소개하겠다. 정렬을 이용한 풀이 O(n log(n)) pair 자료구조를 이용하여 firt에는 높이, second에는 위치 값을 저장한 다음 높이를 내림차순으로 정렬해주자..

문제 https://leetcode.com/problems/3sum/ 3Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Medium Two Sum문제를 조금 더 발전시킨 문제. 문제 해결의 핵심은 세 개의 값을 더해 0(x + y + z = 0)을 만드는 것보다 y + z = -x 로 두 값을 더해 특정 값을 만드는 것으로 문제를 변형하는 것이다. 따라서 모든 원소 값을 x로 한 번씩 설정하여 스위핑으로 서치를 하면 O(n*n)의 시간 복..