백트래킹
-
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가능한 문자열을 구성하기 위한 방법으로는 순열, 백트래킹을 활용한 DFS가 있다. DFS 과정에서 각 종이(숫자)가 한 번만 활용돼야 하기 때문에 is_used 라는 변수를 활용했다. # 가능한 문자열 구성하기 def dfs(numbers, n_len, num): global cnt, is_used, num_uniq # 문자열 길이 최대일 경우 if n_len == len(numbers): return for i in range(len(numbers)): if not is_used[i]:..
[Python] 프로그래머스 소수 찾기 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가능한 문자열을 구성하기 위한 방법으로는 순열, 백트래킹을 활용한 DFS가 있다. DFS 과정에서 각 종이(숫자)가 한 번만 활용돼야 하기 때문에 is_used 라는 변수를 활용했다. # 가능한 문자열 구성하기 def dfs(numbers, n_len, num): global cnt, is_used, num_uniq # 문자열 길이 최대일 경우 if n_len == len(numbers): return for i in range(len(numbers)): if not is_used[i]:..
2023.03.06 -
14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 나의 풀이 +, -,*, / 연산자 각 원소의 개수에 맞춰서 인덱스 리스트를 만들어서 저장했다. 이후 인덱스 리스트로 순열을 만들어서 완전 탐색을 진행해서 풀었다. 순열을 직접 구현하고 사용해보려고 이런 방식으로 풀었는데, itertools의 permutations 함수를 사용하면 통과가 되지만 구현한 수열 함수로는 시간 초과가 발생한다. def get_perm(arr, n): perm_list = [] # ..
[파이썬] 백준 연산자 끼워넣기14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 나의 풀이 +, -,*, / 연산자 각 원소의 개수에 맞춰서 인덱스 리스트를 만들어서 저장했다. 이후 인덱스 리스트로 순열을 만들어서 완전 탐색을 진행해서 풀었다. 순열을 직접 구현하고 사용해보려고 이런 방식으로 풀었는데, itertools의 permutations 함수를 사용하면 통과가 되지만 구현한 수열 함수로는 시간 초과가 발생한다. def get_perm(arr, n): perm_list = [] # ..
2022.11.11 -
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가능한 여러 경로를 얻고, 이 중에서 가장 앞서는 경로를 찾는 것이 핵심이다. 이중에서 가장 앞서는 경로를 처리하는데 어려움을 느껴 다른 사람의 풀이를 참고했다. 백트래킹 활용 현재 위치 정보를 전달해서 중복된 방문을 제한했다. [ic]path[/ic] 들을 저장해둔 [ic]answer[/ic]를 정렬하면서 가장 앞서는 경로를 얻을 수 있었다. from collections import defaultdict def solution(tickets): # 방문 여부 visited = defaultdic..
[파이썬] 프로그래머스 여행경로프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가능한 여러 경로를 얻고, 이 중에서 가장 앞서는 경로를 찾는 것이 핵심이다. 이중에서 가장 앞서는 경로를 처리하는데 어려움을 느껴 다른 사람의 풀이를 참고했다. 백트래킹 활용 현재 위치 정보를 전달해서 중복된 방문을 제한했다. [ic]path[/ic] 들을 저장해둔 [ic]answer[/ic]를 정렬하면서 가장 앞서는 경로를 얻을 수 있었다. from collections import defaultdict def solution(tickets): # 방문 여부 visited = defaultdic..
2022.10.31 -
15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 나의 풀이 수열이 오름차순인지 확인하기 위해서, 정렬 전후가 같은지 체크하는 방식으로 풀었다. 답은 맞았지만, 가능성이 없는 수열도 불필요하게 계산된다는 단점이 있다. def get_num(k): # 수열이 완성된 경우 if k == m: if sorted(num_list) == num_list: print(*num_list) return # 수열에 원소 저장 for i in range(1, n + 1): if not isused[i]: num_list[k] =..
[파이썬] 백준 N과 M (2)15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 나의 풀이 수열이 오름차순인지 확인하기 위해서, 정렬 전후가 같은지 체크하는 방식으로 풀었다. 답은 맞았지만, 가능성이 없는 수열도 불필요하게 계산된다는 단점이 있다. def get_num(k): # 수열이 완성된 경우 if k == m: if sorted(num_list) == num_list: print(*num_list) return # 수열에 원소 저장 for i in range(1, n + 1): if not isused[i]: num_list[k] =..
2022.10.21 -
15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 나의 풀이 백트래킹 유형 기본 문제라고 하는데, 어려워서 풀이를 참고하면서 풀었다. 원소 사용 여부를 저장하는 것이 핵심이었다. def get_num(k): # 수열이 완성된 경우 if k == m: print(*num_list) return # 수열에 원소 저장 for i in range(1, n + 1): if not isused[i]: num_list[k] = i isused[i] = 1 get_num(k + 1) # 사용 후 제거 isused[i] = 0..
[파이썬] 백준 N과 M (1)15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 나의 풀이 백트래킹 유형 기본 문제라고 하는데, 어려워서 풀이를 참고하면서 풀었다. 원소 사용 여부를 저장하는 것이 핵심이었다. def get_num(k): # 수열이 완성된 경우 if k == m: print(*num_list) return # 수열에 원소 저장 for i in range(1, n + 1): if not isused[i]: num_list[k] = i isused[i] = 1 get_num(k + 1) # 사용 후 제거 isused[i] = 0..
2022.10.21