본문 바로가기
반응형

알고리즘/백트래킹9

[백준][JAVA] 9742번 순열 9742번: 순열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전 www.acmicpc.net 문제 집합의 순열이란 집합의 서로 다른 원소를 모두 사용해 만들 수 있는 순서이다. 예를 들어, {2,3,5}의 순열은 다음과 같다. 2 3 5 2 5 3 3 2 5 3 5 2 5 2 3 5 3 2 각각의 순열은 숫자로 나타낼 수 있다. 위의 순열은 사전순으로 쓰여져 있으며, 등장하는 순서를 이용해 나타낸다. 즉, 3 5 2는 위치 4에 있고, 5 3 2는 마지막 위치인 6에 있다. {b,e,i,n}으로 만들 수 있는 순열은 다음과 같다. b e i n b e n i.. 2023. 3. 15.
[백준][Python] 1759번 암호 만들기 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 코드 def back(cnt,ind): if cnt == l: vo,co = 0,0 for i in word: if i in vowel: vo+=1 else: co+=1 if vo >= 1 and co >= 2: print("".join(word)) return for i in range(ind,c): if visit[i] == 0: word.append(alpha[i]) visit[i] = 1 back(cnt+1,i+1) visit[i] = 0 word.pop() .. 2022. 12. 2.
[백준][Python] 18429번 근손실 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 코드 n,k = map(int,input().split()) n_list = list(map(int,input().split())) visit = [False] * n cnt = 0 ans = 0 def dfs(weight): global cnt, ans if weight < 500: return if cnt == n: ans += 1 return for i in range(n): if visit[i] == False: visit[i] = True we.. 2022. 8. 8.
[백준][Python] 10974번 모든 순열 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 코드 n = int(input()) visit = [False] * (n+1) s = [] def dfs(): if len(s) == n: print(*s) return for i in range(1,n+1): if visit[i] == False: s.append(i) visit[i] = True dfs() s.pop() visit[i] = False dfs() 아래 문제와 거의 똑같다. [백준][Python] 15649번 N과 M (1) 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 .. 2022. 8. 4.
반응형

티스토리툴바