개발자 퉁이리

https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 문제의 세 번째 제한조건을 보자. 고른 수열은 비내림차순이어야 한다. 이 조건을 보고 나는 의아했다. 오름차순과 내림차순, 서로 반대말 아닌가? 그렇다는 건 비내림차순으로 나타내라면 그에 반대인 오름차순으로 나타내라는 건가? 그리고 예제 입출력을 봤다. 오름차순이다. 내 생각이 어느 정도 맞았다는 것..

https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 방문 여부를 체크하지 않고, 기존의 값들을 배열에 저장해 정렬했다. 그그다음 백트래킹을 통해 값을 출력해줬다. ⊙ 문제 풀이 #include #include using namespace std; #define MAX 9 int N,M; int first[MAX]; int arr[MAX]; void d..

https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 이전 문제에서 18번째 줄을 오름차순으로만 바꿔줬다. 풀이 방법은 전 시리즈와 같다. ⊙ 문제 풀이 #include #include using namespace std; #define MAX 9 int N,M; int first[MAX]; int arr[MAX]; bool visited[MAX]; v..

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 18번째 줄만 계속 수정해주면 N과 M 시리즈가 풀린다! 다음 문제가 그렇다. 해당 줄을 코드에 주석으로 ★ 표시해놨다. 값을 입력받고 정렬한다. 그 값을 새로운 배열에 저장하고, dfs를 반복한다. 그러다가 M값에 도착하면 새로운 배열에 넣은 값을 출력해준다. 자세한 건 코드를 통해 확인하자!! ⊙..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 list와 dfs를 이용하였다. ⊙ 문제 풀이 N, M = map(int, input().split()) #값 입력 받기 S = [] #리스트 def dfs(): #dfs 함수 생성 if len(S) == M: print(' '.join(map(str, S))) return for i in range(1,N..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 DFS를 이용하여 백트래킹을 했다. 재귀를 통해 순열을 구하기 위해 DFS를 통해 문제를 접근했는데 방법과 개념만 잡혀있으면 구현하기가 비교적 간단하다고 생각한다. 어렵다. 어려워( + 2021.08.10 내용 추가 ) 무슨 오만인지 예전에 적었을 때, 쉽다고 적었을까. 다시 백트래킹을 보는데 생각보다 더 ..