Algorithm (5) 썸네일형 리스트형 [Java] 10971번: 외판원 순회 2 🌎 Link : https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 💡 접근 방법 1. 문제 이해 첫째 줄에 도시의 개수 N이 주어진다. 그리고 N개의 도시를 모두 방문하는 최소의 비용을 구하는 문제다. 예를 들어 1->2->3->4->1 이렇게 방문가능하다. 여기서 포인트가 있다. 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획 N = 4 일경우 1.. [Java] 15664번: N과 M(10) 🌎 Link : https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 💡 접근 방법 1. 문제 이해 기존 N과 M시리즈 문제를 풀면서 어느 정도 백트레킹에 대한 감을 익히고 있다. 하지만 이 문제의 특징이 몇 가지가 있다. 중복된 수열은 출력하지 마라 수열은 사전순으로 출력해라 고른 수열은 비내림차순이어야 한다(오름차순, 값이 같아도 된다) 2. 문제 풀이 중복된 수열은 출력하지 마라 이를 해결하기 위해 자료구조 Set을 사용할 예정이다. 하지만.. [Java] 2023번: 신기한 소수 🌎 Link : https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 💡 접근 방법 1. 문제 이해 7331은 신기한 소수이다. 이유는 7 / 73 / 733 / 7331 이 모두 소수이기 때문이다. 그러면 앞에서부터 뒤에 숫자를 붙여주면서 소수인 경우 백트레킹을 돌려주면 되는 문제다. 우선 소수를 구하는 코드는 여러 가지의 방법이 있다. 여기서 나는 제곱근을 이용해서 소수를 구 할 생각이다. private static boolean is.. [Java] 19942번: 다이어트 🌎 Link : https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 💡 접근 방법 1. 문제 이해 & 적합한 알고리즘 찾기 식재료의 각각의 조합에 따라서 원하는 영양소를 넘는 최소비용을 구해야 하기 때문에 백트레킹이 적합해 보인다. 하지만 이전에 풀이했던 문제와 다르게 백트레킹이 탈출할 포인트를 depth가 아닌 다른 부분을 정해야 했다. 항상 depth로만 풀이하다가 조금 혼란스러웠다. 우선 백트레킹의 틀을 어느 정도 작성해 놓고 어떤 것을 구.. [Java] 15686번: 치킨 배달 🌎 Link : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 💡 접근 방법 1. 문제 이해 & 적합한 알고리즘 찾기 최대 치킨집의 개수(M) 개에서 가장 작은 치킨거리를 구하는 문제다. 모든 최대 치킨집의 개수를 확인하면서 최소의 값을 찾으면 되기 때문에 백트레킹을 사용을 하는 게 좋아 보인다. 비슷한 알고리즘으로 브루트 포스가 있는데 차이점을 확인해 보자. 브루트 포스 : 모든 경우의 수를 확인함 / 노가다 / 최적해.. 이전 1 다음
