Algorithm/LeetCode
[LeetCode] Divisor Game (Dynamic Programming)
약 한시간 가량 풀어봤는데 풀리지 않아서 Discuss답변을 봤습니다. leetcode.com/problems/divisor-game/discuss/979796/Java-all-approach-Easy-Recursive-Memoization-DP 문제 이해를 위한 설명 이 문제는 쉽지만 이해하기 어렵습니다. 문제에서 Alice는 1부터 N까지 숫자를 선택할 수 있고, 자신의 승리를 최적화하기 위해 선택합니다. Bob도 마찬가지로 최선을 다합니다. 숫자가 2이면 Alice의 순서로 시작하여 1을 선택하고 이깁니다. 3일 경우 Alice가 1을 선택하고 밥이 1을 선택하여 앨리스가 집니다. 숫자 4일 경우 4 = Alice -> (4-1) - gives 3 to Bob 3 = Bob -> (3-1) - gi..
[LeetCode] Fibonacci number with Dynamic Programming
요약 재귀함수를 사용해서 풀면 비효율적인 호출이 많아진다. -> 다이나믹 프로그래밍을 활용하자. 재귀함수로 해결할 시 시간복잡도 O(2^n) 다이나믹 프로그래밍으로 해결시 시간 복잡도 O(N) 멘토님의 키워드 왜 n은 30까지로 해놨을까? 30이 넘으면 어떻게 되는지 돌려보기. -> overflow?! n이 30, 50, 100, 500일때 구해보기. 구글에 int32 range, unsigned int32 range 등으로 검색하면 Type Name Bytes Range of Values __int32 4 -2,147,483,648 to 2,147,483,647 unsigned __int32 4 0 to 4,294,967,295 __int64 8 -9,223,372,036,854,775,808 to 9..
[LeetCode] Divisor Game
LeetCode문제 링크 leetcode.com/problems/divisor-game/ Divisor Game - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 엘리스와 밥이 교대로 게임을하며, 엘리스가 먼저 시작합니다. 처음에는 칠판에 숫자 N이 있습니다. 각 플레이어의 차례에 해당 플레이어는 다음과 같이 이동합니다. 0 < x < N 이며 N % x == 0인 x를 선택한다. 칠판의 숫자를 N에서 N -x로 바꾼다. 둘 중 하나가 이동하지 못하게 되면 게임..
[LeetCode] Fibonacci number (피보나치 수열)
LeetCode 문제 링크 leetcode.com/problems/fibonacci-number/ Fibonacci Number - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 피보나치 수열 계산기 (100까지) ko.numberempire.com/fibonaccinumbers.php 피보나치 수열 생성기 피보나치 수열 생성기 ko.numberempire.com 대표적인 재귀함수를 사용하는 문제이다. ko.wikipedia.org/wiki/%ED%94%BC%E..
[LeetCode] Sort Colors
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. Example 1:Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2] Example 2: Input: nums = [2,0,1] Output: [0,1,2] Example 3: ..
[LeetCode] Make The String Great
문제 소문자와 대문자가 섞인 문자열 s가 주어진다. 인접한 문자가 서로 같은 알파벳이면서 대 소문자로 차이가 난다면 쌍소멸 시키는 문제인듯 하다. 조건 2글자 이상 자료구조에 저장시켜서 지금저장 시킨것과 2차례전에 저장시킨것이 ASCII코드 +- 32차이가 나는지 확인하고 만약 그렇다면 모두 날려버리기 vice-versa == 이 경우에도 그 반대의 경우에도 마찬가지이다. 구글링하다가 c++ stack으로 푸신 분이 계셔서 ArrayList로 접근 class Solution { public String makeGood(String s) { String result = ""; ArrayList temp = new ArrayList(); for(int i = 0; i < s.length(); i++) { t..