morgankim

https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  Idea아래에서 위로 올라가면서 계산하는 방식으로 풀어야겠다고 생각했다. 0번째 줄에서 1번째 줄의 두 경로 중 큰 수 선택, 1번째 줄에서 2번째 줄의 두 경로 중 큰 수 선택 ... length - 2 번째 줄에서 length - 1번째 줄의 두 경로 중 큰 수 선택 순으로 이어진다. 즉, 맨 아래 줄은 계산할 필요가 없으니까 triangle.length - 2 부터 계산했다. 현재 위치에서 두 경로 중 더 큰 경로를 선택하다보면, tri..

https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  Review오랜만의 코테 공부...처음에 헷갈렸던 포인트는 m과 n을 반대로 설정했다는 것.. 그냥 문제의 그림을 돌려서 좌표로 생각하면 된다! 만약 문제가 좌표로 나왔다면 m과 n을 그대로 설정하면 된다. 그래도 한 번 틀려봤으니 다음에는 어떻게 풀어야 할지 잘 판단할 수 있을 것 같다.그리고 DFS로도 풀 수 있을 것 같아서 풀어봤다.  CodeDP ver.)class Solution { public int solution(int m..

동적 계획법(DP, Dynamic Programming)은 복잡한 문제를 해결하기 위해 그 문제를 더 작은 부분 문제로 나누고, 각 부분 문제를 한 번만 해결하여 그 결과를 저장하고 재사용하는 방법론입니다. DP는 주로 중복된 계산을 피하고 문제를 효율적으로 해결하기 위해 사용됩니다. 동적 계획법의 주요 특징1. 중복된 계산 제거: 동일한 부분 문제를 여러 번 계산하지 않고, 한 번 계산한 값을 저장해두고 다시 사용합니다.2. 부분 문제: 큰 문제를 해결하기 위해서는 작은 문제들의 해결이 필요합니다.3. 최적 부분 구조: 전체 문제의 최적 해결은 부분 문제의 최적 해결을 바탕으로 합니다.4. 메모리 사용: DP는 계산한 값을 저장하는 테이블(보통 배열이나 리스트)을 사용합니다. 동적 계획법의 두 가지 기..

https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  Review첫 번째 코드처럼 ㄹㅈㄷ 대충 풀려고 하다가 테케 몇 개에서 오류 떠서 수정...ㅎ 이론상으로는 완벽한 것 같은데 말이죠... 큼큼 아무튼 그래서 아래처럼 다시 풀었습니다 쉬운 문제였어요  Code틀린 풀이)import java.util.*;class Solution { public int[] solution(int brown, int yellow) { int[] answer = new int[2]; ..

https://school.programmers.co.kr/learn/courses/30/lessons/72413?language=java 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  Idea오랜만에 AI 추천 문제에 도전했다. 가중치가 있는 경로 찾기 문제여서 다익스트라 개념을 가장 먼저 떠올렸다.  Codeimport java.util.*;class Solution { public int solution(int n, int s, int a, int b, int[][] fares) { int distS[] = dijkstra(n, s, fares); int distA..

벨만-포드 알고리즘 (Bellman-Ford Algorithm)  벨만-포드 알고리즘은 최단 경로를 구하는 알고리즘으로, 특히 음의 가중치를 갖는 간선이 있는 그래프에서도 동작하는 알고리즘입니다. 다익스트라 알고리즘과 달리 음의 가중치를 처리할 수 있다는 점에서 중요한 특성을 가집니다. 기본 아이디어벨만-포드 알고리즘은 그리디 방식이 아닌 동적 계획법(DP)을 기반으로 하는 알고리즘입니다. 각 단계에서 모든 간선을 한번씩 탐색하면서, 각 노드의 최단 거리를 점차적으로 갱신합니다. 알고리즘 동작 원리1. 초기화:   - 시작 노드의 거리는 0, 나머지 노드들은 무한대(`INFINITY`)로 설정합니다.  2. 간선 완화(Relaxation):   - 그래프의 모든 간선 `(u, v)`에 대해, `dist[..

다익스트라 알고리즘 (Dijkstra's Algorithm)  다익스트라 알고리즘은 주어진 그래프에서 출발 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘입니다. 특히, 음의 가중치가 없는 그래프에서 최단 경로를 찾는 데 사용됩니다. 이 알고리즘은 그리디 알고리즘으로 분류되며, 우선순위 큐를 이용하여 효율적으로 구현됩니다. 기본 아이디어1. 출발 노드에서 시작하여, 다른 모든 노드로 가는 최소 비용을 차례대로 계산합니다.2. 최단 거리를 찾는 방법은 우선 최단 거리가 확정된 노드를 하나씩 확정하면서, 그 노드와 연결된 다른 노드들의 거리를 갱신하는 방식입니다.3. 우선순위 큐(Priority Queue) 를 사용하여, 현재까지 계산된 최소 비용을 기준으로 가장 작은 값을 가진 노드를 먼저 처..

에라토스테네스의 체 (Sieve of Eratosthenes) 는 주어진 범위 내에서 소수를 구하는 알고리즘입니다. 이 방법은 모든 자연수 중에서 소수만을 찾아내는 알고리즘으로, 시간 복잡도가 `O(n log(log n))`으로 매우 효율적입니다. 기본 아이디어는 2부터 시작하여 각 숫자의 배수를 모두 지워 나가는 방식입니다.에라토스테네스의 체 개념:1. 배수 지우기: 2부터 시작하여, 2의 배수들(4, 6, 8, ...)을 모두 지웁니다. 그다음 3의 배수들(6, 9, 12, ...)을 지우고, 4는 이미 지워졌으므로 5의 배수들(10, 15, 20, ...)을 지웁니다. 이런 식으로 숫자를 지워 나갑니다.2. 남은 숫자들: 마지막에 남은 숫자들은 모두 소수입니다.에라토스테네스의 체 알고리즘의 핵심:-..

https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  Review순열 + DFS 의 문제였다. 우선, 주어진 숫자들로 만들 수 있는 모든 수를 구하기 위해 순열을, 중복되지 않는 소수만 저장할 수 있도록 Set을 사용했다. 각 자리에 숫자를 하나씩 추가하면서, 그 숫자가 사용되었는지 visited 배열을 통해 확인하고, 사용된 숫자는 다시 선택되지 않도록 했다. 수가 조합될 때마다 문자열로 만들어 소수 판별을 해주었다. 이때, 평소에 사용하던 소수판별법이 아니라, 에라토스테네스의 체 개념을 사용..

https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  IdeaDFS로 슥삭 하고 풀었다. 그런데 생각해보니 완전탐색 문제네... 점심 먹고 와서 다시 풀어야징  Codeimport java.util.*;class Solution {    List list = new ArrayList();        public int solution(String word) {        dfs("", 0);        return list.indexOf(word);    }        private vo..