개발의변화

https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/description/?envType=study-plan-v2&envId=dynamic-programming 아직도 문제를 직관적으로 해결하지 못하는 것 같다. 한시간만에 풀긴 했으나 아직도 이분탐색의 디테일한 조건처리를 헷갈리는 것 같다. 또한 전형적인 LIS 알고리즘 문제였지만 LIS를 그저 외우기만 할 뿐 활용하는 능력이 없었기에 애를 먹은 것 같다. import java.util.*; class Solution { public int[] longestObstacleCourseAtEachPosition(int[] obstacles) { int []..

https://leetcode.com/problems/create-maximum-number/ 스택을 활용한 그리디 문제였다. 배열의 0부터 해당 인덱스까지에서 최대 수를 구하는 것으로 생각해야 하는 부분들이 많았다. public static int [] findMaxArray(int length, int [] nums) { int maxPop = nums.length - length; Stack s = new Stack(); int [] result = new int [length]; for (int i = 0; i 0 && !s.isEmpty() && s.peek() < nums[i]) { s.pop(); maxPop--; } s.ad..

https://leetcode.com/problems/3sum-closest/ 투포인터를 활용하여 이분탐색을 해야했다. 먼저 정렬을 하고 양 끝 점의 투포인터 아이디어를 떠올렸으나 정렬을 안하고도 풀 수 있는 방식이 있는지에 대한 고민을했다. 하지만 딱히 다른 방도가 없었고 정렬을 한다음 움직이기 시작하기로 했다. 아이디어는 다음과 같다. start로 반복문을 순회하면서 인덱스를 올리고 end는 배열의 끝 인덱스 mid는 start의 바로 앞에 두어서 3개의 값을 구하면서 만약 값이 target보다 크다면 end를 줄이고 작다면 mid를 올리는 방식으로 구현했다. class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.so..

https://leetcode.com/problems/count-vowels-permutation/description/?envType=study-plan-v2 전형적인 탑다운 문제였던 것 같다. 정해진 규칙에 맞게 진행하면서 마지막 배열의 값을 리턴하면 되는 문제였다. 특히 DP를 사용할 때는 항상 초기 설정이 중요한 것 같다. 1차원 배열을 쓸지, 2차원 배열을 쓸지 row,col의 값으로 어떠한 값을 넣어서 기준을 잡을지 조금 더 깊은 고민을 해봐야 겠다. class Solution { public int countVowelPermutation(int n) { long [][] arr = new long[n+1][5]; long N = (int)Math.pow(10,9) + 7; for (int i..

https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/description/ DP에 대한 더욱 더 깊은 이해를 위해 리트코드의 문제들을 풀려고 한다. 해당 문제는 메모리제이션을 활용하여 풀었어야 했던 문제였다. 1. 다음 동전주머니로 이동시킨다. 2. 다음 동전주머니로 이동시키지 않을 떄 2-1. 0부터 뽑아야 하는 동전개수 만큼 반복문을 돌린다. 2-1-E. 동전개수보다 동전주머니의 길이가 작을 수도 있기에 반복문의 끝조건을 MIN(동전개수, 동전주머니의 길이)로 잡는다. 2-2. 반복문에 순회하는 동전주머니의 인덱스에 해당하는 값을 더한다. 2-3. 더하면서 해당 DP[pile][coin] = MAX(DP[pile][coin], DP[p..

https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제가 트리로 풀어야 하나? 라는 생각이 들었지만 그래프 노드를 만들고 그냥 문제풀이처럼 부모노드를 탐색하는 방식을 활용하면 되었다. 조금 까다로웠던 건 10% 이익를 부모 노드가 가지는 것인데 그렇게 되면 90%의 이익을 자식노드가 가지는 것이 아닌 원금에서 10%를 뺀 가격을 추가해줘야 했다. import java.util.*; class Solution { public int[] soluti..

https://school.programmers.co.kr/learn/courses/30/lessons/81303?language=java 링크드리스트를 활용해서 나타냈어야 하는 문제였습니다. for (int i = 0; i < n; i++) { arr[i] = new Node(i,i); } public static class Node { int e; int next; int prev; Node (int e, int c) { this.e = e; this.prev = c - 1; this.next = c + 1; } } 노드들의 이전값과 다음 값을 저장하는 링크드리스트를 구현하여 삭제시에 해당 노드의 이전 노드와 다음 노드의 next,prev를 수정하는 방식으로 활용하려고 했습니다. if (arr[idx..

진짜....... 아이디어가 생각나지도 않고 기준점을 어떻게 잡아야 하는지도 감이 전혀 오지 않았다. 일주일 본다고 달라지진 않을 것 같아서 봐로 답지를 확인했다... 찾아보니 미니맥스 알고리즘, 알파-베타 가지치기 정말 생소한 알고리즘을 활용한 것인데 인공지능 알고리즘였다.. 키포인트는 내가 승리하거나 패배하는 것은 결국 상대방이 패배하거나 승리하는 것에 기인된다라는 것이 중점이었던 것 같다. 오랜만에 벽이 느껴져서 작성해본다... // 2022 KAKAO BLIND RECRUITMENT - 사라지는 발판 // 백트래킹 class Solution7_LSH { public static int[] dx = {-1, 1, 0, 0}; public static int[] dy = {0, 0, -1, 1}; p..