Dev Note

1. 완전탐색 : '친구관계' 문제 A 로부터 시작해서 한 명의 친구에게만 소식을 전달할 수 있다면, 최대 몇 명의 친구가 소식을 전달받을 수 있을까? (단, 소식을 전달 받은 친구한테는 소식을 재전달 할 수 없다.) A로부터 시작해서 친구들에게 동시에 소식을 전달할 수 있다고 할 때, 가장 늦게 전달받는 사람은 누구인가? (단, 친구에게 소식을 전달하는 속도는 동일하다.) 그래프 순회란? : 비선형구조인 그래프로 표현된 모든 자료(정점)을 빠짐없이 탐색하는 것 깊이 우선 탐색(Depth First Search, DFS) 너비 우선 탐색(Breath First Search, BFS) DFS 깊이 우선 탐색 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게..

Vertex 노드의 갯수와 Edge 간선의 갯수, 그리고 출발점과 연결점이 한 쌍으로 연결된 정보가 주어진다. 이때 인접행렬 또는 인접리스트로 정보를 받는다. 언제 인접행렬 / 인접리스트를 사용하나? 주어진 문제 상황에 따라 다르며 무엇이 더 좋고나쁘고, 어렵고 쉽고는 없다. 일반적으로는 노드 수가 1000개를 넘어가면 인접행렬보다는 인접리스트를 사용한다고 한다. 또한 유향그래프인지, 무향그래프인지 문제에 따라 다르므로 확인하자! # 6 8 # 0 1 0 2 0 5 0 6 4 3 5 3 5 4 6 4 V, E = map(int, input().split()) edge = list(map(int, input().split())) 인접행렬로 받기 노드 수 + 1만큼의 행렬, 0으로 구성된 이차원 리스트를 만..

이해도 ★☆☆☆☆ 지못미.. 소감 DFS, 백트래킹을 사용하는 문제로 난이도 높게 느껴졌다. 위의 알고리즘을 사용하지 않고 푸는 것도 가능하다. 왼쪽과 오른쪽 갈 수 있는 거리를 구해 조건을 걸어주는 식이다. DFS, 백트래킹 이해 후 다시 도전하는 것이 좋겠다. 접근방식 유형1 방향은 한쪽 방향으로만 돌아도 괜찮다. 백트래킹으로 분기처리를 하기 => d, d+1인 이유는 두 방향(우-하 방향으로 진행중이었다면 우-하 와 좌-하) 으로 가면 되기 때문이다. map 함수를 사용하여 이중리스트 내에 있는 리스트들의 길이를 routes에 담는다. DFS 처럼 끝까지 갔다가 돌아오는건 아니고, 함수 리턴값 없이 가지치기 하며 뻗어나가는 구조이다. import sys sys.stdin = open('input.t..

소감 [업데이트] 변수명 구체적으로 변경 : food_combination -> ingredient_combination 문제가 구체적이지 않아서 애를 먹었다. 디버깅과 문제의 문제점..! 을 짚어준 댓글이 없었다면 풀기 힘들었을 것 같다. 재료 2개를 구할 경우 (1, 2) (2, 1) 조합으로 풀면 되는데 재료가 3개일 경우 2개를 선택하는 건지, 아니면 재료 3개를 모두 선택하는건지 등에 대한 정보가 없었다. 이차원 리스트 벽 세우는걸 좀 더 깔끔하게 구현할 수 없을까..? 접근법 이차원리스트를 받아온다. 이 때 재료와 인덱스 순서를 맞추기 위해 좌측, 상단에 벽을 세운다. 전체 리스트에서 조합으로 2개 선택한다. 반복문을 돌며 음식별 맛의 합계를 구한다. 이 때, 재료를 순열로 다시 구해서 음식1..

다이나믹 프로그래밍 재귀적 호출을 power(x, y - 1) 대신 power(x, y // 2) 로 바꿔줌으로써 시간복잡도를 O(n)에서 O(lgn) 으로 줄일 수 있다. 홀수와 짝수를 나누어서 계산한다. # 시간복잡도 O(n) def power(x, y): if y == 0: return 1 return power(x, y - 1) * x # 시간복잡도 O(lgn) def power(x, y): if y == 0: return 1 # 계산을 한 번만 하기 위해서 변수에 저장 subresult = power(x, y // 2) # 문제를 최대한 똑같은 크기의 문제 두 개로 나눈다. if y % 2 == 0: return subresult * subresult else: return x * subresu..

문제 특정 기간 중 수익이 가장 큰 기간을 찾기 # 테스트 print(sublist_max([4, 3, 8, -2, -5, -3, -5, -3])) print(sublist_max([2, 3, 1, -1, -2, 5, -1, -1])) print(sublist_max([7, -3, 14, -8, -5, 6, 8, -5, -4, 10, -1, 8])) 내 풀이 모든 경우의 수를 리스트에 추가해서 최댓값을 구함 def sublist_max(profits): profit_list = [] for i in range(len(profits)): for j in range(i, len(profits)): profit_list.append(sum(profits[i:j+1])) return max(profit_list..

문제 n번째 피보나치 수를 찾아주는 함수 fib_memo을 작성하기. fib_memo는 memoization 방식으로 구현한다. 내 코드(통과) 엄밀히 얘기하면, 재귀가 아니라 for문을 사용한 것. 예를 들어 n 이 8이면 그 전까지의 수들을 계산해서 하나하나 딕셔너리에 넣어준 것이다. 이를 재귀함수로 구현할 수 있다. 수정하면 좋을 부분 def fib(n) 을 수정하는 것이 아니라, fib_memo 함수만 수정해야 한다. 사전에 n 이 있으면 그대로 출력하고, 없다면 만들어내는 형식으로 작성한다. def fib_memo(n, cache): # 코드를 작성하세요. if n == 1 or n == 2: return cache[1] else: return cache[n-2] + cache[n-1] def ..

소감 for문으로 풀려고 했으나 구현이 쉽지 않았다. 어느 시점에 result에 배포갯수를 추가할지 정하기 어려웠다. stack의 경우는 stack_list.pop(), queue의 경우는 FIFO 성질을 이용, queue_list.pop(0) 을 활용하는 문제가 많다고 한다. 이런 식의 사고과정에 익숙해져야 할 것 같다. 문제 접근하기 스택과 큐를 활용하면 보다 쉽게 풀 수 있다. 주어진 리스트에서 pop(0) 하여 큐의 성질을 활용한다. while문을 돌리며 pop(0) 하면 for문을 대체할 수 있다. 각 기능이 언제 배포되는지, 몇 개의 기능이 배포되는지를 계산하기 위해 변수 time 과 count를 설정한다. 언제 count를 초기화할지 정한다. => 기존의 time 값으로 일처리를 계산했는데 ..