전체 글 검색 결과

해당 글 200건

알고리즘 풀이 - 백준 15656(N과 M(7), 완전탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 백트래킹 관련 포스팅은 여기를 참조 관련 문제인 N과 M(1)은 여기를 참조 관련 문제인 N과 M(2)는 여기를 참조 관련 문제인 N과 M(3)은 여기를 참조 관련 문제인 N과 M(4)는 여기를 참조 관련 문제인 N과 M(5)는 여기를 참조 관련 문제인 N과 M(6)는 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 이 문제는 N과 M(3)과 동일하지만 N개의 자연수가 10,000이하의 임의의 서로 다른 숫자로 주어진 다는 것만 다르다. 2. 풀이 이 문제는 백트래킹 관련 문제이다.(백트래킹은 상단 링크 포스팅 참조) 이전의 관련 문제(상단 링크 참조)인 N과 M(5), N과 M(6)과의 차이는 같은 숫자를..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 2. 7. 10:56

알고리즘 풀이 - 백준 15655(N과 M(6), 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 백트래킹 관련 포스팅은 여기를 참조 관련 문제인 N과 M(1)은 여기를 참조 관련 문제인 N과 M(2)는 여기를 참조 관련 문제인 N과 M(3)은 여기를 참조 관련 문제인 N과 M(4)는 여기를 참조 관련 문제인 N과 M(5)는 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 이 문제는 N과 M(2)와 같은데 숫자가 1부터 N까지가 아니라 10,000보다 작은 임의의 서로 다른 숫자 N개가 주어진다. 그 중 중복 없이, 오름차순으로 된 M개를 골라 사전 순으로 출력한다. 2. 풀이 이 문제는 백트래킹 문제이다. 이전 N과 M(2)와 유사하지만, 1~N까지의 숫자가 아니라 N개의 숫자가 10,000이하의 임의..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 2. 7. 00:51

알고리즘 풀이 - 백준 15654(N과 M(5), 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 백트래킹 관련 포스팅은 여기를 참조 관련 문제인 N과 M(1)은 여기를 참조 관련 문제인 N과 M(2)는 여기를 참조 관련 문제인 N과 M(3)은 여기를 참조 관련 문제인 N과 M(4)는 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 이 문제는 N과 M(1)과 같은데 숫자가 1부터 N까지가 아니라 10,000보다 작은 임의의 서로 다른 숫자 N개가 주어진다. 그 중 중복 없이, M개를 골라 사전 순으로 출력한다. 2. 풀이 이전의 N과 M(1)과 동일하게 풀면 되는데, 이번에는 그 숫자가 임의의 서로 다른 숫자로 주어지게 되므로 그 숫자들을 사전에 저장하고 출력 시에 저장된 숫자의 index를 기반으로 출..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 2. 6. 13:51

알고리즘 풀이 - 백준 15652(N과 M(4), 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 백트래킹 관련 포스팅은 여기를 참조 관련 문제인 N과 M(1)은 여기를 참조 관련 문제인 N과 M(2)는 여기를 참조 관련 문제인 N과 M(3)은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 이전 문제인 N과 M(2)와 비슷한데, 중복이 허용되며, 비 내림차순이라는 것이 추가되었다. 2. 풀이 이 문제는 백트래킹 관련 문제이다.(백트래킹은 상단 링크 포스팅 참조) N, M이 주어질 때, M개의 수를 중복 허용하에 수를 고르되 비 내림차순으로 출력하고 전체 수열은 사전 순으로 고르므로 아래와 같이 우선 파악하자. ① 숫자를 M개 골랐다면 그 숫자를 출력해야 한다. ② 이미 고른 숫자를 다시 선택할 수 있지..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 2. 6. 13:21

알고리즘 풀이 - 백준 15651(N과 M(3), 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 백트래킹 관련 포스팅은 여기를 참조 관련 문제인 N과 M(1)은 여기를 참조 관련 문제인 N과 M(2)는 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 자연수 N, M이 주어질 때, 1 ~ N까지 자연수 중 중복 포함 M개를 고른 것 중 오름차순의 수열만 사전 순으로 모두 출력하는 문제 2. 풀이 이 문제는 백트래킹 관련 문제이다.(백트래킹은 상단 링크 포스팅 참조) 이전의 관련 문제(상단 링크 참조)들을 보면 이번에 바뀐 점은 같은 숫자를 여러 번 써도 된다는 것이다. 즉, 이전 처럼, 현재의 숫자가 이미 포함되었는지 아닌지를 알 필요가 없다. 다만, 그렇다보니 출력에 큰 시간이 소요될 수 있다. 실제로..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 2. 6. 12:39

알고리즘 풀이 - 백준 15650(N과 M(2), 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 백트래킹 관련 포스팅은 여기를 참조 관련 문제인 N과 M(1)은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 자연수 N, M이 주어질 때, 1 ~ N까지 자연수 중 중복 없이 M개를 고른 것 중 오름차순의 수열만 사전 순으로 모두 출력하는 문제 2. 풀이 이 문제는 백트래킹 관련 문제이다.(백트래킹은 상단 링크 포스팅 참조) N과 M(1)에서 살펴보았던 내용은 다음과 같다. N, M이 주어질 때, 중복하지 않도록 수를 고르고 사전 순으로 고른다는 것은 M개의 숫자로 이루어진 모든 부분 집합을 구하라는 의미이다. 여기서 몇 가지 해결을 위한 단서를 파악할 수 있다. ① 숫자를 M개 골랐다면 그 숫자를 출력..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 2. 5. 20:40

알고리즘 - 백트래킹(Backtracking)

1. 백트래킹이란? 백트래킹은 알고리즘 기법 중 하나로, 재귀적으로 문제를 하나씩 풀어나가되 현재 재귀를 통해 확인 중인 상태(노드)가 제한 조건에 위배되는지(유망하지 않은지) 판단하고 그러한 경우 해당 상태(노드)를 제외하고 다음 단계로 나아가는 방식이다. 여기서 알아둘 것은 특정 상태(노드)를 제외한다는 것이다. 백트래킹은 현재 상태(노드)에서 다음 상태(노드)로 나아갈 수 있는 모든 경우를 찾되, 그 중 유망하지 않다면 현재에서 더 이상 나아가지 않고 이전의 상태(노드)로 돌아가 다음 상태(노드)를 검사한다. 여기서 더 이상 탐색할 필요가 없는(유망하지 않은) 상태(노드)를 제외하는 것을 가지치기(pruning)라고도 한다. 즉, 이 방법을 통해 우리는 모든 경우의 수를 체크 하지 않고 필요한 것만..
자바 프로그래밍/알고리즘(Algorithm) 2021. 2. 3. 23:36

알고리즘 풀이 - 백준 15649(N과 M(1), 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 백트래킹 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 자연수 N, M이 주어질 때, 1 ~ N까지 자연수 중 중복 없이 M개를 고른 것을 사전 순으로 모두 출력하는 문제 2. 풀이 이 문제는 백트래킹 관련 문제이다.(백트래킹은 상단 링크 포스팅 참조) N, M이 주어질 때, 중복하지 않도록 수를 고르고 사전 순으로 고른다는 것은 M개의 숫자로 이루어진 모든 부분 집합을 구하라는 의미이다. 여기서 몇 가지 해결을 위한 단서를 파악할 수 있다. ① 숫자를 M개 골랐다면 그 숫자를 출력해야 한다. ② 이미 고른 숫자를 다시 선택하지 않도록 구현해야 한다. ③ 사전 순으로 출력해야 하므로 1부터 ..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 2. 1. 20:57