'Algorithm' 카테고리의 글 목록 (6 Page)

본문 바로가기

Algorithm

[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.. 더보기

[Algorithm/Java][프로그래머스] 문자열 내림차순으로 배치하기 [프로그래머스] 문자열 내림차순으로 배치하기 https://programmers.co.kr/learn/courses/30/lessons/12917 문제접근 문자열 s를 char[] 배열로 넣어서 Arrays.sort를 이용해서 오름차순으로 정렬한 뒤 오름차순으로 정렬된 배열 temp를 역순으로 result에 하나씩 더해주었다. Code import java.util.*; class Solution { public String solution(String s) { char[] temp = s.toCharArray(); Arrays.sort(temp); StringBuilder result = new StringBuilder(); for(int i= temp.length-1; i>=0; i--){ resul.. 더보기

[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.. 더보기

[Algorithm/Java][LeetCode] 21. Merge Two Sorted Lists [LeetCode] 21. Merge Two Sorted Lists https://leetcode.com/problems/merge-two-sorted-lists/ 문제접근 두 개의 정렬된 연결리스트를 하나의 정렬된 연결리스트로 합치는 문제이다. 연결리스트에서 가장 중요한 것은 첫번째 노드를 잃어버리면 안되는 것이다.(첫번째를 잃어버리면 다 잃어버린다.) 그래서 MergeList에 아무값이나 넣어서 초기화하고 next부터 첫번째 노드를 연결해 주었다. temp를 이용해서 next를 연결해 주었고 list1과 list2 둘 중 하나가 null이 될 때까지 두개를 비교해서 더 작은 값을 가진 list를 temp를 이용해서 연결해 주었다. 그리고 마지막에 둘 중 하나가 null이 되면 while문을 빠져나와서.. 더보기

이전 1 ··· 3 4 5 6 7 8 9 다음

티스토리툴바