알고리즘/완전탐색7

• [swea] 1244번: 최대상금 - 파이썬(python) 완전탐색을 이용한 풀이. 갈피를 잡지 못해 다른 분들의 코드를 참고했다. 0번째 인덱스부터 탐색을 시작하는데, 현재인덱스값 이상인 값이 있다면, 현재 인덱스의 값과 교환한다. 그런다음,(현재 탐색중인 인덱스 (i) , 교환횟수+1) 을 dfs 인자로 주고 탐색한다. 만약 교환횟수를 모두 써버렸다면, 최댓값보다 현재 교환된 숫자결과가 더 크다면 갱신한다. 만약, 이미 내림차순 정렬이 되어있어 교환횟수가 남아있는 상태라면, 홀수라면 마지막 1,2번째 인덱스를 바꾸고, 짝수라면 그대로 둔다. 나의 풀이 def dfs(idx, n): global max_val if n == int(cnt): max_val = max(max_val, int(''.join(data))) return for i in range(id.. 알고리즘/완전탐색 2022. 11. 14.

• 

  [프로그래머스] 모음사전 - 파이썬(python) 나의 풀이 def dfs(x, dictionary, alpha): dictionary.append(x) for i in alpha : if len(x) != len(alpha) : dfs(x+i, dictionary, alpha) else : x[:-1] def solution(word): alpha = ['A','E','I','O','U'] dictionary = [] for i in range(len(alpha)) : dfs(alpha[i], dictionary, alpha) return dictionary.index(word) + 1 DFS 로 풀이한 문제이다. 먼저 dictionary 에 현재 나의 문자를 추가한다. 그리고, alpha 리스트를 반복문으로 돌면서, 문자열 x의 길이가 5 보다 작다.. 알고리즘/완전탐색 2022. 9. 7.

• 

  전력망을 둘로 나누기 - 파이썬(python) BFS 에 익숙치 않아 많은 시간이 소요된 문제... 아래 영상이 기본 개념 숙지에 많은 도움이 되었다. 나의 풀이 from collections import deque def bfs(start, visited, graph) : cnt = 1 visited[start] = True queue = deque([start]) while queue : v = queue.popleft() for i in graph[v] : if not visited[i] : queue.append(i) visited[i] = True cnt += 1 return cnt def solution(n, wires): graph = [[] for _ in range(n+1)] count = [] for a,b in wires : gr.. 알고리즘/완전탐색 2022. 9. 7.

• [프로그래머스] 피로도 - 파이썬(python) 문제 설명 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다. 이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들.. 알고리즘/완전탐색 2022. 9. 7.

• 

  [프로그래머스] 소수 찾기 - 파이썬(python) 나의 풀이 from itertools import permutations def solution(numbers): answer = [] s = [] for i in range(1,len(numbers)+1): s += (list(map(''.join, permutations(numbers, i)))) s = list(map(int, s)) s = list(set(s)) print(s) for i in s : if i < 2 : continue elif i == 2 : answer.append(i) continue for j in range(2, int(i**0.5) + 1) : if int(i) % j == 0 : break elif j == int(i**0.5) : answer.append(i) ret.. 알고리즘/완전탐색 2022. 9. 7.

• 

  [프로그래머스] 모의고사 - 파이썬(python) 나의 풀이 def solution(answers): answer = [] count = len(answers) one = ([1,2,3,4,5] * (count//5 + 1))[:count] two = ([2,1,2,3,2,4,2,5] * (count//8 + 1))[:count] three = ([3, 3, 1, 1, 2, 2, 4, 4, 5, 5] * (count//10 + 1))[:count] score = [0,0,0] print(one, two, three) for i in range(count) : if answers[i] == one[i] : score[0] += 1 if answers[i] == two[i] : score[1] += 1 if answers[i] == three[i] : sc.. 알고리즘/완전탐색 2022. 9. 6.

• 

  [프로그래머스] 최소직사각형 - 파이썬(python) 나의 풀이 def solution(sizes): for i in sizes : if i[0] < i[1] : tmp = i[1] i[1] = i[0] i[0] = tmp max_width = max(sizes)[0] max_height = max(sizes, key=lambda x:x[1])[1] return max_width * max_height 가로, 세로 길이 중 더 큰 값을 가로가 되도록 변경한다. 그런다음 가로 중에 가장 큰 값, 세로 중에 가장 큰 값을 곱한 값이 사이즈가 되도록 리턴한다. 다른 풀이 def solution(sizes): return max(max(x) for x in sizes) * max(min(x) for x in sizes) 가로, 세로 중에 큰 값을 고르고, 그 중 .. 알고리즘/완전탐색 2022. 9. 6.