DFS21 [BOJ] 2529. 부등호(Python) / DFS www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제 www.acmicpc.net 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾는 문제 사용 알고리즘 : DFS 재귀로 순열 구현하기 간단한 DFS 문제로 순열을 구하고 들어오는 각 숫자가 부등호에 부합하는 경우에만 재귀로 수를 더하며 넘기고, 부등호에 맞지 않다면 그냥 넘어간다.(isSatisfy 함수에서 확인) 가능한 경우일 때마다 최솟값, 최댓값을 갱신한다. 출력 시, 최댓값은 그대로 출력, 최솟값은 맨 앞 자리.. 2021. 4. 5. [BOJ] 1937. 욕심쟁이 판다(Python) / DFS + DP 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 처음 이 문제를 DFS 각 위치별 완전탐색으로 접근했더니 답은 금방 구했지만, 바로.. 시간초과가 떴다.. 아니나 다를까 DFS + DP의 콜라보로 풀어야 하는 문제였다. 즉, Memoization을 해야한다는 것! Memoization은 이미 한 번 탐색한 위치에 대해서는 재귀로 더 탐색할 필요 없이 그냥 그 값을 가져다 사용할 수 있도록 해당 위치별 값을 미리 저장한 DP Table을 만들어두는 것이 포인트다! 즉, 불필요한 반복 연산 없이 한 번 .. 2021. 4. 1. [SWEA] 2112. 보호필름(Python) / DFS swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 1시간 1분 소요 많이 풀어본 유형이라 큰 고민 없이 풀어낸 문제다. 사용 알고리즘 : DFS 조합 우선, 약품을 투입하지 않고도 성능검사를 통과하는 경우에는 0을 출력한다. 고 했으니, 성능검사 함수를 만들어줬다.(testPerformance()) 동일한 특성의 셀들이 K개 이상 연속으로 있는 경우에만 성능검사 통과 한 열의 동일 셀이 K 미만이면 즉시 False 리턴 이중 포문 통과하면 True 리턴하여 .. 2021. 3. 28. [BOJ] 1038. 감소하는 수(Python) / DFS 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. 사용 알고리즘 : DFS 10보다 작은 수에 대해서는 input값 그대로 출력 depth를 최대 1.. 2021. 3. 26. [BOJ] 13023. ABCDE(Python) / DFS www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 깔끔한 DFS 문제였다. input 받으면서 정점별로 갈 수 있는 정점의 정보를 딕셔너리에 담는다. 전역변수 flag를 두어 depth가 4이상 되면 1로 바꿔주며 return하여 더이상 진행하지 않는다. 모든 정점에서 start할 수 있다. visited로 아직 방문하지 않는 곳에 방문체크하며 다음 재귀로 넘어간다. 재귀 풀려 나올 땐 방문체크한 것을 0으로 돌려 놓는다. flag가 1이면 1, 0이면 0을 출력한다. 파이썬 코드는 다음과 같다. import sys input = sys.stdin.readline .. 2021. 3. 23. [BOJ] 1149. RGB거리(Python) / DP www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 실버 1 문제라 간단한 DFS로 Brute Force(완전탐색)으로 풀릴 줄 알았는데, 47%에서 시간초과 나더라.. # 소요시간 20분 DFS 완전탐색으로 접근한 파이썬 코드는 다음과 같다.(47%에서 실패한 코드) from sys import stdin input = stdin.readline def dfs(depth, temp): global MIN if temp > MIN: # 가지.. 2021. 3. 17. 이전 1 2 3 4 다음
