문제 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 DFS로 간단하게 풀 수 있는 문제 접근법 간단한 접근법으로 최대 3개까지의 사다리를 두었을 때의 모든 형태에서 유효성 검사를 수행하는 식으로 접근할 수 있음. 우선 입력으로 들어오는 모든 M개의 사다리를 배열에 저장 주의할 점으로 배열의 크기는 NM이 아닌 NH임 사다리를 표시할 때는 두가지 방법이 존재 해당 좌표에만 1이라는 값으로 표시 → 오른쪽에서 왼쪽으로 가는 경우는 [r][..

문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acm..

문제 2294번: 동전 2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 풀이 다이나믹 프로그래밍으로 분류된 문제로 간단한 메모이제이션을 통해 풀이가 가능. 접근법 입력으로 주어진 동전으로 목표가치 K를 만드는 최소 개수를 구하는 문제로 DP문제인 만큼 Sub Problem을 찾으려 했음. Sub Problem : 각각의 동전으로 1원부터 목표(K)까지의 가치를 만들기위한 사용한 동전의 최소개수 부분 문제를 찾았으니 먼저 해야할 것은 부분 해를 저장할 dp배열을 선언하는 것...

Concept그리디 알고리즘의 한 분류다이나믹 프로그래밍 메모이제이션 기법 활용부분 문제 : 한 정점까지의 최단거리는 방문하는 여러개의 정점들의 최단거리로 이루어져있음.주어지는 그래프에서 시작 정점으로부터 각 정점까지의 최단경로를 찾는 알고리즘Feature우선순위 큐와 거리배열(DP)을 활용하여 로직 구성.한 정점 V까지의 최단거리를 구할 때 V까지로 가는 여러 정점들의 최단 거리 정보를 활용한다는 특징을 가짐.가중치를 가진 그래프에서 최단거리를 구할 때 쓰이는 알고리즘음수 가중치를 가진 그래프에서는 사용불가.우선순위 큐를 활용함으로써 시간복잡도 : O(N * NlogN)Implement인접 리스트를 통한 구현우선 데이크스트라 소스코드를 보자.private static int dijkstra(int st..