개발 블로그

오늘도 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..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 이 문제는 DFS + 백트래킹 문제입니다. 보자마자, DFS보다 백트래킹 먼저 생각했습니다. 왜냐하면, 모든 말이 지날 수 있는 최대 칸수를 구해야 하기 때문입니다. 그래서 DFS로 탐색하면서, 조사한 모든 경우의 수(말이 지날수 있는 모든 경우의 수)들 중 최댓값을 구해주면 됩니다. #include #include using namespace std; char board[21][21]; ..