Algorithm20 [Easy] Leetcode | 20. Valid Parentheses | String, Stack - 문제 스택의 대표적인 문제인 괄호 검사 알고리즘 문제이다. 괄호로 이루어진 문자열이 주어지는데 이 문자열 속 괄호들이 쌍에 맞으며 순서 또한 맞는지 검사하는 문제이다. - 풀이 스택의 LIFO (Last In First Out) 성질을 이용하여 순서와 쌍을 검사한다. 대략적인 알고리즘은 문자열의 크기만큼 루프를 돌면서 열린 괄호는 모두 스택에 저장한다. 따라서 시간 복잡도는 O(n)이 될 것이며 최악의 경우 스택에 n개 모두 저장하므로 공간 복잡도는 O(n)이 될 것이다. 만약 닫힌 괄호( ')', '}', ']' ) 가 나온다면 무조건 스택의 top(마지막에 저장한 괄호)과 쌍이 맞아야 하므로 top이 쌍이 맞지 않다면 false를 반환하며 쌍이 맞다면 top의 요소를 pop한다. 이 과정을 반복하.. 2020. 1. 29. [Easy] Leetcode | 1. Two Sum | Array, Hash table - 문제 integer를 요소(원소)로 가지는 array(nums)와 target이 주어진다. array의 요소 중 2개의 요소를 더해 target을 만드는 요소의 인덱스 2개를 반환하는 함수를 만드는 문제이다. 정답은 정확히 1개가 존재하며, 동일한 요소를 중복으로 사용할 수 없다고 가정한다. 위의 예를 보면 2와 7을 더하면 target이 되므로 0과 1이 담긴 배열을 반환하면 정답이다. - 풀이 우선 크게 2가지 방법이 있다. 첫 번째 방법은 이중 루프를 사용하여 모든 경우를 한 번씩 확인하는 것이다. 따라서 이 경우 모든 조합을 다 체크하므로 시간복잡도는 n*(n-1)/2 => O(n^2)이 될 것이다. 그리고 반복 횟수와 상관없이 반환할 요소는 2개이므로 공간 복잡도는 O(1)이 될 것이다. 다.. 2020. 1. 28. 이전 1 2 3 4 다음
