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는 계산한 값을 저장하는 테이블(보통 배열이나 리스트)을 사용합니다. 동적 계획법의 두 가지 기..

벨만-포드 알고리즘 (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. 남은 숫자들: 마지막에 남은 숫자들은 모두 소수입니다.에라토스테네스의 체 알고리즘의 핵심:-..

`List`는 순서가 있는 원소들의 집합을 나타내는 자료구조입니다. `List`는 중복 원소를 허용하며 각 원소가 인덱스를 가지는 순서가 있는 컬렉션입니다. 자바에서 `List`는 `java.util.List` 인터페이스를 구현한 다양한 클래스들로 제공됩니다.List의 특징1. 중복 원소 허용: `List`는 같은 값을 여러 번 저장할 수 있습니다.2. 순서 보장: `List`는 원소들이 추가된 순서대로 저장되며, 각 원소는 인덱스를 가지고 있어 순차적으로 접근할 수 있습니다.3. 인덱스를 통한 접근: `List`는 인덱스를 통해 특정 원소를 빠르게 조회할 수 있습니다.4. 동적 크기: `List`는 동적으로 크기가 늘어나고 줄어듭니다. 즉, 배열과 달리 크기를 미리 정의할 필요가 없습니다.List를 구..

`Set`은 집합을 나타내는 자료구조입니다. 집합은 중복된 원소가 없고 원소들 간에 순서가 중요하지 않은 데이터 구조입니다. `Set`은 기본적으로 중복을 허용하지 않으며, 각 원소가 한 번만 존재하도록 보장합니다.Set의 특징:1. 중복 허용하지 않음: `Set`에 값을 추가할 때 이미 존재하는 값은 추가되지 않습니다.2. 순서 없음: `Set`은 원소의 순서를 보장하지 않으며, 일반적으로 `HashSet`과 같은 구현체는 내부적으로 순서에 상관없이 원소를 저장합니다.3. 자동 정렬이 없음: `HashSet`은 정렬되지 않지만, `TreeSet`은 원소들을 자동으로 오름차순으로 정렬하여 저장합니다.4. 효율적인 검색: `Set`의 주요 특징 중 하나는 중복 원소를 자동으로 제거하고 검색, 추가, 삭제 ..

1. 조합 (Combination)조합은 주어진 원소들 중에서 순서를 고려하지 않고 특정 개수의 원소를 선택하는 경우를 말합니다. 즉, 선택된 원소들의 순서가 중요하지 않으며, 같은 원소를 여러 번 선택할 수 없습니다.예시:주어진 원소 `{1, 2, 3}`에서 2개를 선택할 때:- 가능한 조합은 `{1, 2}, {1, 3}, {2, 3}`입니다.수학적 정의:- `n`개의 원소 중에서 `r`개를 선택하는 조합의 수는 `C(n, r) = n! / (r! * (n - r)!)`입니다. 조합 구현:- 조합을 구하는 방법은 순열과 달리 순서가 중요하지 않으므로, 중복을 피하면서 원소를 선택하는 방식으로 구현됩니다. 재귀적으로 원소를 선택하고, 선택된 원소를 포함한 조합을 탐색합니다. 백트래킹 방식을 사용합니다.i..

1. 순열 (Permutation)순열은 주어진 원소들 중에서 순서를 고려하여 특정 개수의 원소를 선택하는 경우입니다. 주어진 원소들에서 중복 없이 선택한 원소들의 순서가 중요합니다.예시:주어진 원소 `{1, 2, 3}`에서 2개를 선택할 때:- 가능한 순열은 `(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)`입니다.수학적 정의:- `n`개의 원소 중에서 `r`개를 선택하는 순열의 수는 `P(n, r) = n! / (n - r)!`입니다. 순열 구현:- 백트래킹은 가능한 모든 경우의 수를 시도하면서 불필요한 부분은 빠르게 가지치기하여 탐색을 줄이는 기법입니다. 순열을 구할 때 주로 사용되며, 각 원소를 선택하는 모든 경우를 탐색합니다. import java.util.*..