본문 바로가기

156492

백준 알고리즘 15649 (N과 M(1)) - python (재풀이) 백준 알고리즘 15649 (N과 M(1)) - python > https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹의 기본 문제. 1~N까지 자연수 중 길이가 M인 중복되지 않는 수열 출력 [문제 풀이] 1. depth가 늘어날 때마다 배열을 저장해 줄 result 생성 2. 알아보기 쉽게 (N+1) size로 하여 자연수 값 그대로 적용되게 함 3. DFS 탈출 조건 : 길이(이 문제는 depth로 생각해도 됨)가 M을 만족 4. 저장된.. 2022. 5. 7.
백준 알고리즘 15649 (N과 M(1)) - python [문제] 백준 알고리즘 15649 (N과 M(1)) - python > https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 1~N을 이용해서 M개 요소의 조합을 순서대로 만드는 문제. (중복 제거) DFS(Depth First Search), 백트래킹 구현하는 법을 정확하게 모르는 상태라 한참을 고전했다. 그래서 이번 구현 시에 쓰일 사항들을 간단히 정리해야겠다. 1. visited (탐사 했는지 여부) 2. out (탐사 내용) 3. .. 2019. 10. 15.
728x90