Algorithm 썸네일형 리스트형 [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][백준] 2805번 나무 자르기 [백준] 2805번 나무 자르기 https://www.acmicpc.net/problem/2805 문제접근 처음에는 감이 안잡혀서 밑에 알고리즘 분류가 이분 탐색이라고 써져있어서, 옛날에 배운 기억으로 코드를 작성했다. left, right, mid를 이용해서 값을 찾았다. 만약 딱 떨어지는 값이 없을 경우, 적어도 m을 넘겨야하기 때문에 right값을 return하도록 했다. Code import java.util.Arrays; import java.util.Scanner; public class BOJ2805 { static int cutHeight(int[] trees, int m){ Arrays.sort(trees); int left = 0; int right = trees[trees.length.. 더보기 [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][프로그래머스] 이상한 문자 만들기 [프로그래머스] 이상한 문자 만들기 https://programmers.co.kr/learn/courses/30/lessons/12930# 문제접근 문자열을 공백 기준으로 나누고 나눠진 단어들을 기준으로 짝수는 대문자로, 홀수는 소문자로 바꾸는 문제이다. split함수를 이용해 단어를 나누고, 반복문으로 짝수, 홀수를 구분해서 대문자,소문자로 바꿔주었다. Code class Solution { public String solution(String s) { String[] words = s.split(" "); StringBuilder answer = new StringBuilder(); for(int i = 0; i answer.length()) // 입력 문자열 뒤에 공백이 더 있을 경우 answer... 더보기 [Algorithm/Java][BOJ] 3052번 나머지 [백준] 백준 3052번 나머지 https://www.acmicpc.net/problem/3052 문제접근 10개의 입력들을 42로 나누어서 서로 다른 나머지 값들이 몇 개가 있는지 출력하는 문제였다. 서로 다른 값이라는 키워드를 보고 Set 자료구조를 사용하면 되겠다고 생각이 들었다. Set은 데이터의 중복을 제거해주기 때문에 따로 중복 검사를 하지않고 나머지를 add 해주고 Set의 크기만 출력하면 되는 문제이다. Code import java.util.Scanner; import java.util.HashSet; public class Main { public static void main(String[] args) { HashSet hs = new HashSet(10); Scanner sc = n.. 더보기 [Algorithm/Java][BOJ] 백준 2908번 상수 [백준] 2908번 상수 https://www.acmicpc.net/problem/2908 문제접근 문자열을 뒤집는 문제이므로 StringBuilder의 reverse() 함수를 이용하기로 했고, 입력이 세자리 수 두개이기 때문에 BufferedReader를 쓰지않고 그냥 Scanner를 사용하여 입력을 받았다. Code import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); String[] input = sc.nextLine().split(" "); int max = -1; for(String num: input){ StringBuilder.. 더보기 이전 1 2 3 4 5 6 7 8 다음
