알고리즘 (37) 썸네일형 리스트형 [완전탐색] 프로그래머스 - 카펫 python from math import ceil, floor, sqrt def solution(brown, yellow): answer = [] height = 0 width = 0 area = brown + yellow sqrt_area = (ceil(sqrt(area))) for i in range(3, sqrt_area+1): if area % i == 0: if (area/i - 2)*(i-2) == yellow: height = i width = area/i answer.append(int(max(height, width))) answer.append(int(min(height, width))) return answer [DPS] 프로그래머스 - 단어 변환 DFS def solution(begin, target, words): if target not in words : return 0 visited = [] answer = 0 dfs_flag = True #답을 찾으면 False, 모든 DFS 종료 def dfs(begin, point): visited.append(begin) point += 1 #탈출 조건 cnt = 0 for i in range(len(begin)): if begin[i] != target[i]: cnt+=1 if cnt == 1: nonlocal answer answer = point nonlocal dfs_flag dfs_flag = False return #실행문 for word in words: flag = 0 if word .. [DFS] 프로그래머스 - 네트워크 DFS def solution(n, computers): answer = 0 visited = [False] * n def dfs (graph, start, visited): visited[start] = True for node in range(len(graph[start])): if visited[node] == False and node != start and graph[start][node] == 1: dfs(computers, node, visited) for i in range(n): if visited[i] == False : dfs(computers, i, visited) answer+=1 return answer [DFS] 프로그래머스 - 타겟 넘버 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43165 DFS로 풀기 nbs = list tg = int answer = 0 def solution(numbers, target): global nbs, tg, answer nbs = numbers tg = target dfs(0, 0) return answer def dfs(index, sum): global answer # 탈출 조건 if(index == len(nbs)): if(sum == tg): answer += 1 return # 실행문 dfs(index+1, sum+nbs[index]) dfs(index+1, sum-nbs[index]) 참고 https://www.youtube.com/.. [DFS][BFS] DFS와 BFS 개념정리 DFS / BFS 깊이 / 너비 우선 우선탐색 알고리즘 => 모든 개체들 중 특정 개체를 찾기 위한 알고리즘 경로탐색 유형 (최단거리 / 시간) 네트워크 유형 (연결) 조합 유형 (모든 조합 만들기) DFS, BFS 중 익숙한 것을 사용하면 된다. 단, 연습할 때는 DFS, BFS 모두 활용해보기 DFS 재귀로 구현 내가 짠 알고리즘의 검증이 쉽다. 시간 복잡도는 복불복 BFS Queue, LinkedList로 구현 시간복잡도가 낮다. 참고 : https://www.youtube.com/watch?v=BsYbdUnKZ-Y 이전 1 2 3 4 5 다음