Algorithm 개념 및 문제풀이/Leetcode5 Leetcode 17번 문제 풀이 개요 Leetcode 에서 알고리즘 문제를 풀고 배운 내용을 정리하기 위해 작성하였습니다. 문제 : 17. Letter Combinations of a Phone Number 주어진 번호에 해당하는 문자들을 조합해서 나올 수 있는 모든 문자들을 출력하기 https://leetcode.com/problems/letter-combinations-of-a-phone-number/ 풀이 이 문제는 생각보다 간단한 풀이로 풀 수 있다. 문자열이 두개 주어지는 다음 경우를 보자. 위 그림처럼 abc, def 2개의 문자열을 조합해 결과를 출력하면 ad, ae, af ... cf 까지 총 9개가 나온다. 이는 두 문자열을 이중 for loop 로 조합해서 만들 수 있는데 이를 응용하여 다른 문자열들도 조합하는 것이 .. 2020. 2. 5. Leetcode 15번 문제 풀이 개요 Leetcode 에서 알고리즘 문제를 풀고 배운 내용을 정리하기 위해 작성하였습니다. 문제 : 15. 3Sum 주어진 배열에서 요소 3개를 골라 합했을 때 0이 되는 것들만 배열로 추려내서 반환하기. 단 중복되는 것은 피하기(not allowed duplicate triplets) 풀이 문제 풀이를 위해서 먼저 주어진 배열을 오름차순으로 정렬해야 한다. 정렬을 하면 합했을 때 0이 되는 요소를 찾기 쉬워지기 때문이다. 그래서 만약 다음과 같이 정렬을 했다고 하자. 현재 배열 요소가 -2 라면, 그 다음 요소와 배열 마지막 요소로부터 인덱스를 줄여나가면서 적합한 요소를 추려낸다. 이 때 현재 배열 요소의 다음 값 인덱스를 low, 배열 마지막 요소 인덱스를 high 라고 하자. 현재 배열 요소가 -2.. 2020. 2. 3. Leetcode 4번 문제 풀이 개요 Leetcode 에서 알고리즘 문제를 풀고 배운 내용을 정리하기 위해 작성하였습니다. 문제 : 4. Median of Two Sorted Arrays 주어진 두 배열들에서 중간값(Median)을 구해야 함. ** 중간값은 말 그대로 배열의 중간에 위치한 값임. 이 때 배열요소의 갯수가 홀수이면 중간에 있는 요소가 정답이 되지만 짝수이면 중간위치 주변의 값들의 평균이 정답이 됨. 풀이1 : Bruce force 주어진 두 배열을 합친 후, 합쳐진 배열에서 중간값을 찾음. 이 때의 시간복잡도는 O(m + n) 이며 공간복잡도 또한 O(m + n) 으로 동일함. 풀이2 : Binary Search Binary Search 로 풀기 위한 방법에는 배열을 적당히 나누는 기법이 들어가는데, 이에 대한 이해가 .. 2020. 1. 24. Leetcode 5번 문제 풀이 개요 Leetcode 에서 알고리즘 문제를 풀고 배운 내용을 정리하기 위해 작성하였습니다. 문제 : 5. Longest Palindromic Substring 주어진 문자열 내에서 팰린드롬인 문자열을 찾아 반환해야 함. 풀이1 : Brute force 설명 Brute force(무차별 대입) 방식으로 풀 경우, 문자열 내 모든 문자마다 접근해서 팰린드롬인지 확인하여야 한다. 이 경우 시간 복잡도는 O(N^3) 이 나온다 ** 시간 복잡도가 O(N^3) 인 것은 루프로 각 문자마다 접근을 하고, 팰린드롬인지 검사를 위해 이중 루프를 돌기 때문이다. (이중 루프를 어떤 방식으로 도는지에 대해선 정확히 모르고, 좀 더 자료조사가 필요) 그러므로 무차별 대입보다 좀 더 나은 방법이 필요하다. 다른 방법으로 DP.. 2020. 1. 12. Leetcode 3번 문제 풀이 개요 Leetcode 에서 알고리즘 문제를 풀고 배운 내용을 정리하기 위해 작성하였습니다. 문제 : 3. Longest Substring Without Repeating Characters 문자열내에서 중복이 없는 가장 긴 문자열의 길이를 반환해야 함. 풀이1 : Brute force 설명 Brute force(무차별 대입) 방식으로 풀 경우, 주어진 문자열 내 모든 문자들을 검사하여 풀 수 있다. 각각의 문자별로 루프를 돌아서 가장 긴 substring의 길이를 반환한다. 구체적으로는 다음과 같다. 전체 문자열 길이만큼 루프를 돌면서 조건에 따라 임시 문자열에 각 문자를 대입한다 조건 1 : 만약 임시 문자열이 비어 있으면 최초 문자를 대입한다 조건 2 : 만약 특정 문자와 임시 문자열을 중복 체크하여.. 2020. 1. 9. 이전 1 다음
