알고리즘 문제/Leetcode283 [leetcode][122] Best Time to Buy and Sell Stock II 문제 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ 주식 가격 배열이 주어진다. 어떤 주식을 샀을 때 해당 주식을 팔기 전까지는 주식을 구입할 수 없다고 하자. 주식을 사고 판다고 했을 때 얻을 수 있는 최대 이익은 얼마인가? 투 포인터로 해결했다. 처음에는 DP로 했었는데 이건 그렇게하면 TLE 난다. 다시 생각해보니 주식을 사고 나서 최대가를 찍었을 때 파는 거다. 주식가격이 상승 곡선이 시작하기 전 가장 최소값을 찍었을 때, 주식을 구입한다. 상승 곡선이 끝날 때, 주식의 가격이 최대가 됐을 때 주식을 판다. 주식을 판 다음 날부터 다시 위 과정을 반복한다. 이를 배열 끝날때까지 반복한다. 상승 곡선이 끝나기 전에 배열이 종.. 2020. 4. 6. [leetcode][207] Course Schedule 문제 : https://leetcode.com/problems/course-schedule/ numCourses 개의 코스가 있다. 이 코스들은 선행되는 코스들이 있을 수 있다. 선행되는 코스들을 모두 수강한 경우, 해당 코스를 수강할 수 있다. 코스들의 개수(numCourses), 선행 코스들에 대한 정보(prerequisites)가 주어질 때, 모든 코스들을 수강할 수 있는지 구해라. 위상정렬(topological sort) 관련 문제다. 1. 코스를 선수 과목으로 보는 코스들의 번호를 저장하는 2차원 배열. 2. 코스를 수강하기 위해 선행되어야 하는 코스의 수를 저장하는 1차원 배열. 3. 남은 선수 코스의 개수가 0이여서 수강할 수 있는 코스를 저장하는 큐. 총 3개의 자료구조를 사용했다. 먼저 .. 2020. 4. 3. [leetcode][200] Number of Islands 문제 : https://leetcode.com/problems/number-of-islands/ 2차원 배열 grid가 있다. grid는 1(육지)이나 0(물)로 이루어져있다. 연결되어 있는 1들의 테두리가 모두 0들로 둘러쌓여 있다면 이를 하나의 육지로 본다. grid의 테두리도 0으로 감싸여있다고 한다. grid에 있는 육지의 수를 구해라. DFS, BFS 연습하기 좋은 문제다. 기본적인 구현으로도 풀 수 있다. grid를 전부 탐색하면서 육지를 발견하면 해당 위치를 기준으로 dfs나 bfs를 돌린다. 이 때, 육지를 발견했으므로 정답에 1을 더해준다. 돌리면서 4방면(상하좌우)의 grid 요소들을 탐색하며 이가 육지(1)인 경우 물이나 육지 이외의 사인으로 바꾸어 탐색한 위치라고 표시한다. (연결된.. 2020. 3. 30. [leetcode][152] Maximum Product Subarray 문제 : https://leetcode.com/problems/maximum-product-subarray/ 정수형 배열 nums가 주어질때, subarray의 원소들의 곱 중 최대를 구해라. 곱한다고 했을 때, 최대값이 될 가능성이 있는 경우는 현재 탐색중인 원소가 양수인 경우 가장 큰 양수를 곱하는 경우이고. 탐색중인 원소가 음수인 경우 가장 작은 음수를 곱하는 경우이다. 즉, 배열을 탐색해나가면서 원소의 곱이 가장 큰 경우와 가장 작은 경우를 변수에 저장해둔다. // let, now = 탐색중인 원소 값 // let, maxProducts = 연속되는 원소들의 곱들 중 최대 // let, minProducts = 연속되는 원소들의 곱들 중 최소 maxProducts = max(now, maxProd.. 2020. 3. 24. [leetcode][139] Word Break 문제 : https://leetcode.com/problems/word-break/ 문자열 s, 단어 리스트가 주어질 때 단어 리스트들로 문자열 s를 만들 수 있는지 구하는 문제. 단어는 사용하지 않아도 되고 여러번 사용해도 된다. DP로 해결했다. dp[i] = s[i..]를 단어 리스트로 만들 수 있는지 여부(true, false) 저장. index를 기준으로 s[index]와 문자[0]가 같다면 s[index~] prefix가 문자와 같은지 비교하고 같다면 index+문자길이를 index로 다시 탐색한다. 만약 탐색중 dp[index]가 이미 있다면 이를 반환한다. (이미 s[index..]를 탐색했다는 것을 의미) 시간복잡도는 O(|s| x |wordDict|). 문자가 같은지 비교해야 되기 때문.. 2020. 3. 18. [leetcode][567] Permutation in String 문제: https://leetcode.com/problems/permutation-in-string/ 문자열 s1, s2가 주어졌을 때, s2 서브 문자열에서 s1 문자열 문자들이 전부 존재하는지 구하는 문제. 예를 들어, s1="ab", s2="eidbaooo" 라면 true. s1="ab", s2="eidboaoo" 라면 false. 투포인터로 풀었다. 문자열 s1을 전부 탐색하면서 문자개수를 저장한다. (let, arr) s2 서브 문자열 범위의 시작 위치와 종료 위치를 변수 s, e에 저장한다. s2 문자열을 탐색하면서 탐색 중인 문자 위치를 e라 하자. (let, nowChar = s2[e]) 만약 arr[nowChar] 이 0 보다 크다면 arr[nowChar]를 1 감소시키고 다음 문자를 탐.. 2020. 3. 10. 이전 1 ··· 31 32 33 34 35 36 37 ··· 48 다음