'leetcode' 태그의 글 목록

본문 바로가기

leetcode

[Algorithm/Java][LeetCode] 121. Best Time to Buy and Sell Stock [LeetCode] 121. Best Time to Buy and Sell Stock https://leetcode.com/problems/best-time-to-buy-and-sell-stock 문제접근 가장 싸게 사서 가장 비싸게 샀을 때 얻는 이윤을 구하는 문제이다. 다이나믹 프로그래밍을 이용해서 dp배열에 지금까지 중에서 가장 싼 값을 저장하고 현재 날짜의 가격 prices[i]와 그 전날까지 가장 싼 가격 dp[i-1]을 빼서 이윤을 구한 다음 max와 비교한다. 그리고 오늘 가격이 dp[i-1]보다 싸다면 dp[i]를 오늘 가격으로 바꿔주고 아니라면 dp[i-1]을 넣어준다. Code class Solution { public int maxProfit(int[] prices) { int max.. 더보기

[Algorithm/Java][LeetCode] 101. Symmetric Tree [LeetCode] 101. Symmetric Tree https://leetcode.com/problems/symmetric-tree 문제 접근 루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리가 대칭인지를 파악하는 문제이다. BFS처럼 큐를 이용해서 반복문으로 풀려고 했으나, 뭔가 잘 안되서 재귀함수를 이용했다. 왼쪽과 오른쪽 서브트리의 노드를 재귀 함수를 이용해 비교 나올 수 있는 경우의 수 4가지 1. 양쪽 노드가 모두 null인 경우(아무 문제 없이 끝까지 트리를 순회 헀으므로 true) 2. 한쪽 노드만 null인 경우(비대칭이므로 false) 3. 양쪽 노드의 값이 다른 경우(비대칭이므로 false) 4. 양쪽 노드의 값이 같은 경우(지금까지는 대칭이므로 추가적인 트리 순회 - 재귀 함수.. 더보기

[Algorithm/Java][LeetCode] 70. Climbing Stairs [LeetCode] 70. Climbinh Stairs https://leetcode.com/problems/climbing-stairs/ 문제접근 처음에는 재귀를 이용해서 풀어보려고 해서 제출을 했지만 시간 초과가 나왔다. 그래서 DP 방식으로 풀어보았다. DP 방식으로 풀기 위해서는 점화식?을 발견해야 한다. 뭔가 굉장히 어려워 보이지만 갑자기 감이 잡힌다.(규칙을 찾는 느낌?) 계단은 한번에 1칸 또는 2칸을 이동할 수 있다. 그러면 1번째 계단을 올라가려면 0번째에서 시작해야한다. 그리고 2번째 계단을 올라가기 위해서는 0번째거나 1번째 계단에서 시작해야한다. 또, 3번째 계단을 올라가기 위해서는 1번째거나 2번째 계단에서 시작해야한다. 여기서 n번째 계단을 오르기위해서는 n-1번째와 n-2번째 .. 더보기

[Algorithm/Java][LeetCode] 53. Maximum subarray [LeetCode] 53. Maximum subarray https://leetcode.com/problems/maximum-subarray/ 문제접근 주어진 배열에서 연속되는 값을 더한 sum이 가장 큰 subarray의 sum을 찾는 문제이다. 처음에 이 문제를 보자마자 다이나믹 프로그래밍인 것 같아서 dp라는 배열을 만들고 dp[i]는 i번째 인덱스까지 중에 가능한 가장 큰 subarray의 값을 저장하는 배열로 만들어서 풀었다.(방법1) 근데 방법1로 풀고보니까 굳이 dp라는 배열을 만들어서 일일이 다 저장할 필요 없이 현재인덱스 전의 subarray값(dp[i-1])만 알면 될 거 같았다. 즉 배열을 만들지 않고 dp[i-1]을 저장하는 sum이라는 변수를 만들어서 dp[i-1] 이전 값(dp[.. 더보기

[Algorithm/Java][LeetCode] 20. Valid Parentheses [LeetCode] 20. Valid Parentheses https://leetcode.com/problems/valid-parentheses/ 문제접근 괄호가 올바른 괄호인지 잘 닫히고 열렸는지를 확인하는 문제이다. 비슷한(똑같은) 문제를 백준에서 풀어봐서 Stack을 이용하면 된다는 것을 알고 있었다. 여는 괄호일 때는 Stack에 push를 해주고 닫힌 괄호일 때는 Stack에 top이 같은 종류의 괄호인지 확인하고 pop하거나 아니라면 false를 리턴해준다. 이때 예외처리할 상황은 2가지이다. 열린 괄호로만 이루어져있을때. 닫힌 괄호로만 이루어져있을때. 1번처럼 열린 괄호로만 이루어져있다면 for문을 빠져나왔을 때 Stack이 비어있지 않을 것이고, 2번처럼 닫힌 괄호로만 이루어져 있다면 sw.. 더보기

이전 1 다음

티스토리툴바