본문 바로가기

알고리즘26

섬 연결하기(프로그래머스, Java) 문제링크: https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 | 프로그래머스 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 알고리즘 설명: 가장 cost가 싼 간선으로 모든 노드를 연결하는 알고리즘이다. 양 방향으로 간선의 cost값을 알기 위해서 배열을 사용하여 두 방향 (A -> B, B -> A)의 cost를 넣어놓았다. 노드 0부터 탐색을 시작한다. 0부터 시작하므로 visited[0] = true 메서드 재귀호출하여 탐색한다. 재귀호출은 노드(섬)의 개수만큼 호출을 하고 변수 count를 만들어 재귀 호출한 횟수를 체크한다. 이중 for문으로 탐.. 2019. 10. 16.
깊이 우선 탐색(depth-first search, DFS) 깊이 우선 탐색이란? 트리에서는 왼쪽 노드부터 확인하여 탐색하지 않은 경우에 왼쪽노드에 넘어가고를 반복하여 마지막 깊이까지 들어간 뒤 마지막 노드의 인접 노드들을 전부 탐색한 뒤 백트래킹을 하며 탐색하지 않은 노드들을 탐색한다. 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색. 얻어진 해가 최단 경로가 된다는 보장이 없다. 탐색 지점에서 일직선으로 탐색을 해나가는 느낌 설명 방문을 체크하는 배열 존재 시작 노드를 설정한 뒤 DFS메서드를 불러오고 시작노드의 방문체크를 true로 바꾼다. DFS메서드에서는 설정한 시작노.. 2019. 10. 10.
네트워크(프로그래머스, Java) 문제링크: https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 | 프로그래머스 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크 programmers.co.kr 알고리즘 설명: 이미지 영역을 찾는 문제는 좌표에서 상하좌우로 .. 2019. 10. 9.
N으로 표현(프로그래머스, Java) 문제링크: https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 | 프로그래머스 programmers.co.kr 알고리즘 설명: 모든 노드의 경우를 확인하여 가장 적은 count 수를 찾기 위해 DFS 탐색방법을 사용하였다. 재귀함수를 이용하여 DFS를 구현하였다. 재귀함수로 값을 찾다가 찾는 경우 return으로 돌아가기보다는 전역변수로 answer를 만들어 바로 값을 넣어주고 함수를 return하여 종료해버린다. 숫자 사용 개수가 8개가 넘는 경우 (사용 개수는 count로 체크) answer는 -1 재귀함수를 돌다가 값을 처음 찾은 경우에는 answer에 count 값을 넣어준다. 또 함수에서 값을 찾았지만 다른 재귀함.. 2019. 10. 8.
너비 우선 탐색(Breadth-first search, BFS) 너비 우선 탐색이란? 시작 정점에서 인접한 모든 정점들을 우선 탐색하는 방법 OPEN List(검색 가능성이 있는 노드의 집합)는 큐(Queue)를 사용해야지만 레벨 순서대로 접근 가능 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다. 경로가 매우 길 경우, 탐색 가지가 급격히 증가하여 보다 많은 기억 공간이 필요하다. 탐색 지점에서 둥그렇게 탐색을 해나가는 느낌 설명 방문을 체크하는 배열존재 시작노드를 큐에 넣고 탐색시작 이중 반복문을 사용! - 큐 안에 있는 값을 pop하고 pop해서 나온 값의 인접한 노드에 대해서 가져오고 방문한 적 없는 노드에 경우 방문체크해주고 큐안에 노드를 넣어준다. 예시 코드(Java) import java.io.*; import java.util.*; /* 인접 리스.. 2019. 10. 6.
카카오 프렌즈 컬러링북(프로그래머스, Java) 문제링크: https://programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 | 프로그래머스 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 알고리즘 설명: 먼저 그림의 영역을 탐색하는 문제이므로 어떤 탐색방법을 선택할지 고민하였다. BFS와 DFS 방법중에 BFS가 주변탐색과 속도에서 더 용의하므로 BFS 탐색방법을 사용하였다. 문제에서 그림의 크기가 그렇게 크지않아서 큐 or 스택 둘중 아무거나 사용해도 될 것이라 판단하여 큐를 사용하였다. X 위치가 들어갈 큐, Y 위치가.. 2019. 10. 6.

티스토리툴바