hw.dev

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 📌 해결순서 이 문제는 bfs 보다는 dfs가 더 깔끔한 풀이가 나오는듯 싶다 dfs는 재귀함수 구조이기 때문에 파이썬으로 백준 문제를 푸는데 dfs로 해결해야겠다 싶으면 대부분 sys.setrecursionlimit(10000) 이 코드를 추가 해줘야한다. 파이썬은 기본적으로 재귀함수 호출제한을 1000으로 두는데 백준에서 테스트 케이스 검사를 받다보면 1000번 넘게 dfs를 호출해야 하는 경우가 있다. ..

https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 📌 해결순서 "인접한 두 부분수열"의 의미를 이해하는게 가장 중요한 문제였다. 인접한 이라는 말에 집중하지 않고 이런 풀이 과정을 생각했다. 1. 추가하려는 숫자 앞에 같은 숫자가 있으면 더이상 탐색하지 않고 return 2. 길이가 2부터 현재 길이까지의 부분수열을 만들어서 중복되는 부분수열이 있으면 더이상 탐색하지 않고 return 3. 백트래킹으로 완탐.. 이렇게 생각하고 길이에 맞는 부분수열을 백트래킹..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 📌 해결순서 1. 백트래킹 dfs 완탐으로 암호를 일단 생성한다 2. 모음 갯수가 자음에 비해서 굉장히 적기 때문에, 모음 알파벳으로만 이루어진 배열을 만든다 3. 암호의 길이가 l 과 같은 경우에, 모음 자음의 갯수가 문제의 조건과 일치 하는지 확인한다 4. 암호의 각 단어가 모음인지 자음인지 판단하고 모음 갯수 >= 1 , 자음 갯수 >= 2 인 경우만 출력한다 📌 코드 import sys inpu..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 📌 해결순서 모든 부분수열의 합을 구해야 하므로, 완탐으로 구해야함을 알수 있고 더하는 숫자들의 중복이 있으므로 백트래킹으로 하나씩 제거하고 다음 수를 추가해주는 식으로 풀어야한다고 생각했다. 1. 부분수열의 크기가 양수여야 하므로 부분수열을 담는 배열의 길이가 1 이상인 경우에만 합을 구한다 2. 항상 부분수열을 담는 배열에 저장되는 숫자들의 원래 인덱스 값은..