FE개발자

그래픽 탐색이란? 하나의 정점으로 부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것 EX) 특정 도시에서 다른 도시로 갈 수 있는지 없는지 너비 우선 탐색 (BFS, Bredth-First-Search) 정의 루트 노드(혹은 임의의 다른 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점부터 가까운 정점을 먼저 방문하고 먼 정점을 나중에 방문하는 방법 즉, 깊게 탐색하기 전에 넓게 탐색하는 것이다. 사용하는 곳 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때. 특징 1) 직관적이지 않은 점 - BFS는 시작 노드에서 거리에 따라 단계별로 탐색한다고 본다. 2) 재귀적인 동작을 하지 않는다. 3) 어떤 노드를 방문했는지 여부를 기록하여 무한루프에 빠질 위험을 제거 4) 방문..

문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한 사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers..

문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한 사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이하인 자연수입니다. 문제 풀이 방법 DFS를 처리할 함수를 생성한다. 함수는 노드를 방문 여부를 기록하는 count와 numbe..

깊이 우선 탐색 (DFS, Depth-First-Search) 정의 루트 노드 (혹은 임의의 다른 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 넓게 탐색하기 전에 깊게 탐색하는 것이다. 특징 1) 깊이 우선이 너비 우선(BFS)보다 간단하지만 느리다. 2) 자기 자신을 호출하는 순환 알고리즘의 형태를 갖는다. 3) 전위 순회(Pre-Order Traversals) 를 포함한 다른 형태의 순회는 모두 DFS의 한 종류이다. 주의점 그래프 탐색의 경우 어떤 노드를 방문했는지 검사해야 무한루프에 빠질 위험이 없다. 동작원리 a노드(시작노드) 방문 - 방문을 표시한다 a와 인접한 노드들을 차례로 순회 - 인접한 노드가 없다면 종료 a와 이웃된 노드b를 방문했다..

문제 설명 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다. solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요. 제한 사항 bridge_length는 1 이상 10,000 이하입니다...

문제 설명 현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요. 제한 사항 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다. 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다. location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다. 문제 풀이 방법 중요도에 따라 각 문서의 인덱스와 중요도를 map()으로 배열화 시켜 준다. 각 ..