전체 글 검색 결과

해당 글 200건

알고리즘 풀이 - 백준 15661(링크와 스타트, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 관련 문제인 14889번 풀이 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 N명의 인원을 2팀(스타트팀, 링크팀)으로 나누어 능력치를 계산하는 문제. 각 팀에는 1명 이상 있어야 한다. 이전 문제인 스타트와 링크는 무조건 팀을 반으로 했으나 이 문제는 두 팀의 인원이 달라도 된다. 2. 풀이 이 문제는 우선 N명의 사람들을 두 팀으로 나누되 최소 1명은 배정되도록 해야 한다. 우선 팀을 배정하는 작업을 수행하려면 그 경우의 수를 모두 따져봐야 하므로 완전 탐색을 통해 해결 해야 한다. 그 이후, 능력치를 계산하기 위해서 배정된 상태에서 값을 계산하기만 하면 된다. 즉, 팀을 배정 시의 완전 탐색..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 2. 16. 23:14

알고리즘 풀이 - 백준 14889(스타트와 링크, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 2. 풀이 이 문제는 우선 N명의 사람들을 반으로 나누어 팀을 배정한 뒤 그에 따라 능력치를 계산해야 한다. 우선 팀을 반으로 배정하는 작업을 수행하려면 그 경우의 수를 모두 따져봐야 하므로 완전 탐색을 통해 해결 해야 한다. 그 이후, 능력치를 계산하기 위해서 배정된 상태에서 값을 계산하기만 하면 된다. 즉, 팀을 배정 시의 완전 탐색을 어떻게 사용하느냐의 문제이다. ① 재귀로 팀 배정하기 재귀를 통해 스타트, 링크팀을 각각 배정하는 방법을 사용할 수 있다. 현재 함수 상태를 통해 몇 명의 플레이어를 선택했는지 확인하고 전체 선택이 완료되면 팀 능력치를 계산한다. N명을..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 2. 16. 22:28

알고리즘 풀이 - 백준 14501(퇴사, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 퇴사하고자 하는 상담사. N+1일 후 퇴사 시, N일 간 최대한 많은 상담을 하고자 할 때, 상담으로 얻는 수익의 최대값을 구하는 문제 2. 풀이 이 문제는 완전 탐색(재귀) 와 DP를 이용한 해결이 모두 가능한 문제이다. ① 완전 탐색으로 해결하기 각 상담 일자에 상담을 시도하여 가능한 경우를 모두 테스트 후 그 결과 중 가장 수익이 높은 경우를 비교할 수 있다. 즉, 1일차에 상담을 시작 후 상담이 끝난 일자 부터 그 이후에 상담이 가능한 모든 일자에 테스트를 하고 그 결과 값을 저장한다. 같은 방법을 2일차부터 N일차에 시작하여 동일하게 결과를 얻고 그 결과를 비교하..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 2. 16. 18:51

알고리즘 풀이 - 백준 1759(암호 만들기, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 C개의 알파벳 소문자가 주어질 때, L개의 알파벳으로 암호를 만드는 모든 경우의 수를 출력한다. 암호는 알파벳 사전 순서로만 구성되며, 최소 1개의 모음, 최소 2개의 자음으로 구성된다. 전체 내역은 사전 순으로 출력 2. 풀이 이 문제는 나열된 문자들 C개 중 L개를 선택하여 선택 가능한 경우에 출력하는 문제이다. 그러므로 C개의 문자 중 L개를 선택하는 모든 경우를 다 살펴보아야 한다. 재귀를 이용하는 것이 가장 쉬운 방법인데, 재귀를 이용 시에는 탈출 조건을 정해야 한다. 탈출 조건은 다음과 같다. → 조건 : L개를 선택한 경우이며 자음이 2개 미만 / 모음이 1개..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 2. 15. 21:48

알고리즘 풀이 - 백준 9095(1, 2, 3 더하기, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 이 문제는 1,2,3의 합으로 N을 나타내는 경우의 수를 출력하는 문제이다. 여기에서 DP로 푸는 방법을 설명한 바 있다. 이번에는 완전 탐색(재귀)를 이용하여 해결해본다. 2. 풀이 1, 2, 3을 모두 더하는 경우의 수를 완전 탐색으로 찾아보자. 찾은 후 그 결과가 현재 구하고자 하는 N의 값과 일치한다면 그 경우는 성공적인 것이며, 이외의 경우는 추가 연산이 필요하거나 실패한 경우이다. 즉, 이 내용을 재귀 함수로 구현할 수 있다. 재귀는 현재 함수의 상태를 지속적으로 넘김으로써 구하고자 하는 조건에 일치 시 탈출 조건을 만들어 전체 결과를 구하는 방법이다. 여기서 ..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 2. 15. 20:40

알고리즘 풀이 - 백준 6603(로또, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 2. 풀이 숫자 1~49 중 6개에서 13개(K의 범위)가 주어지는데, 이 중 6개를 골라 오름차순의 순서대로 고르는 방법이다. 이 문제는 기본적으로 선택의 문제이므로 6개가 선택될 때까지 재귀 방식으로 해결하거나 혹은 순열을 이용하여 해결할 수 있다. ① 재귀로 해결하기 재귀 메소드를 구현하여, 현재 몇 개의 숫자가 선택되었는지, 선택된 숫자를 저장하여 6개가 모두 선택되면 그 내용을 출력하는 방식으로 해결할 수 있다. ② 순열로 해결하기 이것은 선택의 문제인데 이를 순서의 문제로 치환하는 방법을 사용하면 해결할 수 있다. K개의 숫자가 주어질 때, 선택된 숫자는 1로,..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 2. 14. 22:54

알고리즘 풀이 - 백준 10971(외판원 순회 2, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 백트래킹 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 1~N까지의 도시 간 이동 비용이 NxN으로 주어질 때, 모든 도시를 순회하는 비용 중 가장 적은 비용으로 순회하는 경우의 비용을 구한다.(비용은 비대칭적, 1→2로 갈 때와, 2→1로 갈 때의 비용은 다를 수 있다.) 2. 풀이 유명한 TPS(외판원 순회) 문제이다. 이 문제는 풀 수 있는 방법이 다양하다. ① 완전 탐색 + 백트래킹 사용법 DP를 이용하는 것과 큰 차이는 없다고 보는데, 기본적으로 모든 도시를 탐색을 하는 방법이다. 그러나 이미 방문한 경우와 갈 수 없는 경우 및 이전 방문으로 계산된 최소 비용을 넘어서는 경우를 제외..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 2. 14. 21:36

알고리즘 풀이 - 백준 10819(차이를 최대로, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 순열 중에서 인접 수 끼리의 차이의 합이 가장 큰 결과값을 구하는 문제 2. 풀이 이전 / 다음 순열 문제의 로직을 그대로 사용해서 풀 수 있는 문제이다. 현재 주어진 숫자의 배열에서 최초 순열까지 이전 순열을 구하면서 인접 수 차이 합 중 최대를 구하고, 최종 순열까지 다음 순열을 구하며 동일한 작업을 수행하면 된다. 또는, 정렬을 수행한 뒤, 다음 순열을 구해가며 인접 수 간 차이 합 중 최대를 구한다. 아래의 코드에서는 이 방법을 사용하였다. 다음 순열을 구하는 방법은 아래 내용을 참고한다.(자세한 순열 관련 내용은 상단의 완전 탐색 포스팅 링크를 통해 참고) ※ 순..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 2. 14. 10:20