문제 프로그래머스 - 미로 탈출 명령어 해결 방법 맨해튼 거리 공식으로 미로 탈출 조건에 부합하지 못한다면 바로 impossible 을 반환하고 종료한다. 빠른 문자열 순인 d, l, r, u 순으로 탐색하도록 dx, dy 를 구성하고 DFS 탐색을 진행한다. 시간 초과를 막기 위해 탐색을 진행하면서 맨해튼 거리를 계산해 탈출 조건을...

문제 BOJ 27961 - 고양이는 많을수록 좋다 해결 방법 복제 마법의 경우 0마리 ~ k마리 이하의 고양이를 추가할 수 있으므로 단순히 복제 마법만 사용해 고양이 수를 증가시키면 된다. 정답 코드 - JAVA import java.io.*; import java.util.*; public class Main { publi...

문제 프로그래머스 - 도넛과 막대 그래프 해결 방법 추가된 노드를 삭제하면 여러 그래프로 분리된다는 점과 각 그래프에 속하는 노드의 특징을 이용해 문제를 해결한다. 들어오는 간선이 없고 나가는 간선이 2개 이상이라면 추가된 노드이다. 8자 모양 그래프의 중간 노드는 들어오는 간선과 나가는 간선이 각각 2개이다....

문제 BOJ 1461 - 도서관 해결 방법 책들의 원래 위치를 - 와 + 에 따라 각자 다른 우선순위 큐에 입력한다. 이때 우선순위 큐는 내림차순으로 설정한다. 책을 최대로 들고 이동하는 거리 * 2 를 결괏값이 저장한 후 마지막 책을 놓은 뒤에는 다시 돌아올 필요가 없으므로 나온 결괏값에 가장 먼 거리...

문제 BOJ 1253 - 좋다 해결 방법 숫자를 배열로 입력한다. 배열을 정렬한다. 투 포인터를 사용해 답을 구한다. 단, 다른 수 두 개의 합으로 나타내야 하므로 자신인 경우에는 넘어가야 한다. 정답 코드 - JAVA import java.io.*; import java.util.*; pub...

문제 프로그래머스 - 다단계 칫솔 판매 해결 방법 해시맵을 사용하여 판매원과 판매원의 관계를 저장한다. 해시맵을 사용하여 문자열과 문자열의 인덱스를 저장한다. 객체 그래프 탐색을 사용해 계산한다. 정답 코드 - JAVA import java.io.*; import java.util.*; class Solution { p...

다익스트라 알고리즘 개념 음의 가중치가 없을 때 단일 출발지에서 모든 노드까지의 최단 경로를 구하는 알고리즘이다. 작동 원리 시작 노드를 0으로 설정하고, 다른 노드들의 최단 거리를 무한대로 설정한다. 방문하지 않은 노드 중 가장 거리가 짧은 노드를 선택하고, 해당 노드를 통해 다른 노드로 가는 경로를 탐색하여 경로를 갱신한다. ...

문제 BOJ 1240 - 노드사이의 거리 해결 방법 그래프를 입력받을 때 양방향으로 저장한다. 두 노드의 거리를 DFS로 구한다. 정답 코드 - JAVA import java.io.*; import java.util.*; public class Main { static int N; static int M; s...

문제 BOJ 2458 - 키 순서 해결 방법 그래프를 입력받을 때 정방향과 역방향을 모두 탐색할 수 있도록 입력받는다. DFS 탐색을 정방향과 역방향으로 각각 탐색하는데 이때 같은 visited 배열을 사용하여 진행한다. 모든 정점이 방문 되었다면 ret 을 증가시킨다. 정답 코드 - JAVA import java.io.*; i...

그리디 알고리즘 개념 지금 가장 좋은 선택을 반복적으로 진행하여 최적의 해를 구하는 방법이다. 선택의 순간마다 최적의 선택을 고르기 때문에 항상 최적의 해를 보장하지는 않는다. 그리디 문제의 특징 선택한 방법이 이후의 선택에 영향을 주지 않거나, 영향을 주더라도 최적해가 유지되는 경우에 사용한다. 문제 자체가 부분 문제로 쪼개질 때, ...