DP | LeetCode - 322. Coin Change Java

https://leetcode.com/problems/coin-change  간단한 풀이갖고 있는 동전의 종류가 주어지고, 이 동전을 조합하여 가장 적은 개수의 동전으로 목표 금액을 맞추는 경우의 수를 구하는 문제이다. 동전은 종류만 주어지고, 사용할 수 있는 개수의 제한은 없으므로 경우의 수만 생각하면 된다. amount가 작고, 동전의 경우의 수가 적을 경우에는 완전 탐색으로도 구할 수 있겠지만, 중복의 최소화를 생각하면 DP로 푸는 것이 적절하다. 목표 금액 amount는 3원, 동전의 종류는 1, 2원이 있다고 가정할 때, 0부터 3원을 가장 적은 동전의 개수로 만드는 방법은 다음과 같을 것이다.금액0원1원2원3원경우x{1}{2}{1,2}, {2,1}가짓수0112 그렇다면, 3원을 만드는 경우의 ..

• format_list_bulleted Algorithm/LeetCode
• · 2024. 8. 28.
• textsms

Dijkstra | LeetCode - 743. Network Delay Time Java

https://leetcode.com/problems/network-delay-time/  1부터 n까지, n개의 노드가 주어지고, 출발 노드와 노드를 이동하는데 소요되는 시간이 2차원 배열의 형태로 주어진다. 이 때, 모든 노드를 순회할 때의 최소 시간을 구하는 문제이다. 우선, 이 문제를 해결할 때, 양수의 가중치가 있는 그래프의 형태이므로 최소 비용(시간)으로 도착하는 방법을 구할 때 다익스트라 알고리즘을 사용하면 좋겠다고 생각했다.코드의 동작은 다음과 같다.주어진 연결 정보를 ArrayList를 이용한 인접 리스트로 변환한다.시작 노드 k를 우선순위 큐에 넣고 거리를 0으로 설정하여 시작점을 예약한다.시작점으로부터 각 노드까지의 거리를 저장하는 거리 테이블(배열)을 선언하여 각 노드까지의 거리를 ..

• format_list_bulleted Algorithm/LeetCode
• · 2024. 8. 27.
• textsms

DP | 70. Climbing Stairs Java

https://leetcode.com/problems/climbing-stairs/ n 번 만큼 계단을 오르는데 1계단을 오를 수도 있고 2계단을 한번에 오를 수도 있다.이 때 n번째 계단에 오르는 경우의 수의 개수를 구하는 문제이다.(이때, 1 계단을 오를 때, 경우의 수를 구하는 방법은 작은 범위의 범위를 포함하게 된다.이 말을 쉽게 풀어보자면, 이렇게 볼 수 있다. - 바닥에서 3번 계단으로 가는 경우의 수는하나씩 오르는 경우 1가지  계단을 2개 오르고 한 번 오르는 경우 2가지3가지가 있다. 바닥에서 1번째 계단까지의 경우의 수는 1번 경우와 3번 경우의 경우의 수가 1개로 같다.그렇다면, 1번과 3번의 경우를 모두 구하는 것 보다 시작 지점으로부터 i번째 계단까지 올라가는 경우의 수를 미리 구..

• format_list_bulleted Algorithm/LeetCode
• · 2024. 8. 24.
• textsms

DFS | LeetCode - 200. Number of Islands Java

https://leetcode.com/problems/number-of-islands/description/ 서론그래프를 탐색만 하는 그래프 탐색의 기초적인 문제이다. 섬은 1, 바다는 0으로 표시된 2차원 배열(인접 행렬)이 주어지는데, 이 때 섬이 몇 개인지 알아내는 문제로, 상, 하, 좌, 우의 4방향으로 탐색하며 연결된 모든 섬의 땅을 탐색하는 문제이다.BFS, DFS 중 하나를 선택해서 구현하면 된다. 프로세스는 다음과 같다.1. 인접 행렬을 탐색하며 값이 1인 요소를 찾는다2. 방문 했는지 확인한다.3. 방문하지 않았다면 방문을 체크하고 그 인덱스와 연결된 모든 1인 요소를 방문하며 체크한다.4. 연결된 모든 땅을 체크하면 섬의 개수 +1을 한다.5. 주어진 인접 행렬의 마지막 인덱스까지 반복..

• format_list_bulleted Algorithm/LeetCode
• · 2024. 7. 30.
• textsms

BFS | LeetCode - 841. Keys and Rooms java

https://leetcode.com/problems/keys-and-rooms/description/  0부터 n-1까지의 번호가 붙은 방들이 있고, 잠겨있는 방 문을 열기 위해서는 각 방에 놓여있는 방 번호와 일치하는 열쇠로 문을 열 수 있다.모든 방은 잠겨있으므로 열쇠가 필요하다. 2차원 배열이 주어지고, 배열의 1차원 인덱스는 각 방의 번호를, 2차원 인덱스의 요소들은 열쇠를 뜻한다.예를 들어 다음과 같은 배열이 주어진다면,Input: rooms = [[1],[2],[3],[]] rooms[0] = {1,2} 이므로, 0번째 방에서는 1번 방과 2번 방을 갈 수 있는 열쇠를 얻을 수 있음을 뜻한다. 이러한 상황에서 가장 많은 방을 탐색할 수 있는 경우의 방 개수를 구하는 문제이다. 이 문제는 인접..

• format_list_bulleted Algorithm/LeetCode
• · 2024. 7. 23.
• textsms

DFS | N-Queens Java

https://leetcode.com/problems/n-queens/ 체스판에서 서로 공격할 수 없도록 퀸을 배치하는 방법을 모두 찾는 문제이다.체스에서 퀸은 상, 하, 좌, 우, 대각선 방향으로 체스판의 끝까지 이동할 수 있기 때문에 같은 선 상에 있다면 퀸을 놓을 수 없다. 이 문제를 풀기 전에 N-Queen 문제를 풀어보면 도움이 된다. 하지만 두 문제의 풀이는 거의 비슷하기 때문에 어느 쪽을 먼저 풀어보아도 상관 없다!https://i-am-strong-man.tistory.com/152 DFS | N-Queen javahttps://school.programmers.co.kr/learn/courses/30/lessons/12952 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭...

• format_list_bulleted Algorithm/LeetCode
• · 2024. 7. 20.
• textsms