개발 블로그

오늘도 N과 M 시리즈를 복습 차원에서 다시 풀어보았습니다. 유형마다 조금씩 차이도 있고, 함수 구현하는데 있어 도움이 많이 될 것 같아서 다시 풀어보았습니다. 6 ~ 12번 까지 문제 설명 드리겠습니다. 6번 : N개의 자연수 중에서 M개를 고른 수열, 고른 수열은 오름차순이어야 한다. 7번 : N개의 자연수 중에서 M개를 고른 수열, 같은 수를 여러 번 골라도 된다.(사전 순으로 증가하는 순서로 출력) 8번 : N개의 자연수 중에서 M개를 고른 수열, 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 9번 : N개의 자연수 중에서 M개를 고른 수열(중복 수열 제거, set 사용..

오늘은 N과 M 시리즈를 다시 풀어보았습니다. 백트래킹(완전탐색)은 BFS, DFS에서도 굉장히 많이 응용되어서 나오기 때문에 잘 알아둬야 할 것 같습니다. 문제마다 조금씩 다른 유형이지만, 조건을 잘 보고 로직을 조금씩 다듬으면 수월하게 풀 수 있을 것 같다고 생각합니다. 1번부터 5번까지 문제 설명 드리겠습니다. (공통) 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1 : 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 2: 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열, 고른 수열은 오름차순이어야 한다. 3: 1부터 N까지 자연수 중에서 M개를 고른 수열, 같은 수를 여러 번 골라도 된다. 4: 1부터 N까지 자연수..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 이 문제는 주어진 배열의 해당하는 값 4개를 더한 값들 중 최댓값을 구해야 하는 문제입니다. 그렇지만, 예외처리 해줘야 하는 부분이 있습니다. ㅗ,ㅜ,ㅏ,ㅓ와 같은 테트로미노 모양은 DFS탐색이 불가능 합니다. 그래서 따로 함수를 만들어서 처리해줘야 하는 번거로움이 있습니다. 그 외에는 백트래킹으로 접근해서 테트로미노의 칸에 놓은 수들의 합의 최댓값을 구해주면 됩니다. 더불어, 이 문제는 DFS ..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 로또의 당첨 번호는 6개입니다. 입력받은 숫자들 중 6개의 순서쌍을 오름차순으로 모든 경우의 수를 출력해 주는 문제입니다. 백트래킹으로 접근할 수 있습니다. 만약 해당 인덱스의 숫자를 사용한다면 함수는 다음과 같이 정의 할 수 있습니다. solve(a, index+1, cnt+1) 해당 인덱스의 숫자를 사용하지 않는다면, 개수는 늘려주지 않고, 해당 인덱스만 1 늘려주면 끝입니다. so..

백트래킹이란 ? 현재 상태에서 가능한 모든 후보를 따라 들어가며 탐색하는 알고리즘 ex) 오목을 예시로 둘 수 있다. 오목을 둘 때 상대방의 바둑알을 어디에 두눈가에 따라 다양한 후보들이 생긴다. 즉 가능한 모든 경우를 생각해볼 수 있기에 이를 백트래킹 알고리즘이라고 할 수 있다. 알고리즘 예시1) N과 M(1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M은 전형적인 백트래킹 문제이다. 이는 1~N까지 중복 없이 M개를 선택하여 ..