C#/알고리즘 썸네일형 리스트형 [알고리즘] 쿼드 트리 이번에는 쿼드 트리의 작동 방식을 직접 알고리즘으로 제작하는 퀴즈를 풀어보았다.여담으로 쿼드 트리는 데이터 베이스 검색 , 이미지 용량 최적화 , 지형 내에서 충돌 처리 등에서 사용가능한 방법으로 기본적으로 재귀적으로 분할하는 구조를 가진다. https://school.programmers.co.kr/learn/courses/30/lessons/68936 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.당신이 압축하고자 .. 더보기 [알고리즘] DFS 문제 - 더하기 빼기 스스로가 생각했을 때 아직 DFS BFS관련 문제 해결능력이 부족하다고 생각했고, 관련 문제를 풀던중 문제가 직관적이진 않지만 재미있는 DFS의 활용 문제라고 생각해서 가져와 봤다. 해당 문제 에서는 각 경로를 끝까지 따라갔을 때의 총합이 target 값 과 동일하게 나오는 방법의 수를 원하였고 이때 index의 각 숫자들은 같은 수가 + 와 - 의 2가지 경우의 수로 매번 나뉘기 때문에 해당 + 와 - 로 갈리는 구간을 재귀함수로 나타내면 좋겠다고 생각하였다.그리고 target 값에 만족하는 경우를 1로 리턴하도록 하여 모든 경우의 수의 DFS값이 최종적으로 원하는 return값이 되도록 아래와 같이 코드를 만들었다. public int solution(int[] numbers, int target.. 더보기 [알고리즘] 이분 탐색 이분 탐색 문제의 특징은 아래와 같다. 최적화 문제에서 "최소" 또는 "최대"를 구하는 유형."가능한 최소 시간"을 찾는 문제는 이분 탐색으로 해결 가능할 때.완전 탐색(브루트 포스)으로 전체를 확인하기엔 너무 연산의 크기가 클 때. 위는 이분 탐색으로 풀 수있는 문제로, 최소한의 시간을 요구하는 문제이다.이를 이분 탐색으로 풀면 아래와 같이 나온다.public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) { long min = 0; long max = (long)1e14; // 최대 가능 시간 설정 long answer = max; while (min = t[i]) trips++;.. 더보기 [알고리즘] DFS 과 BFS + 다익스트라 , 길찾기 알고리즘 DFS: 너비 우선 탐색 BFS: 깊이 우선 탐색 은 그래프를 탐색할때 쓰이는 방법중 하나이다. 이때 말하는 그래프는 노드(node)와 선(edge)로 이루어진 자료구조이며 각 노드를 하나씩 방문하는것을 탐색한다고 말한다. 1. DFS (Depth-First Search) 는 먼저 한 방향으로 최대한 깊게 탐색한뒤 더이상 이동할 노드가 없을경우 옆 경로로 이도하는 방식으로 길이 갈리는 분기에서 다른 분기로 넘어가기전 먼저 해당 분기를 다 탐색한뒤 반대편 분기로 넘어가는 방식으로 BFS와 비교 했을때 연산횟수가 상대적으로 늘어나기에 검색 속도는 너비우선 탐색보다 느리고, 최단거리 검색에는 불리하다는 단점이 있다. 2.BFS (Breadth-First Search) 의 경우 최대한 넓게 두루두루 분기의 처음.. 더보기 이전 1 다음
