본문 바로가기

코딩일기/알고리즘75

[프로그래머스 : 레벨 3] 단어변환 : BFS(Java) 이번문제는 내가 DFS 알고리즘으로 문제를 풀려다가 중복되는 단어에서 어딜 먼저 접근해야하나라는 부분에서 막혀 답지를 봤다. 일단 문제부터 보자. 문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다... 2021. 6. 21.
[프로그래머스 : 레벨 3] 네트워크 : DFS(Java) 이번 문제는 생각외로 쉬웠다. 어떤 알고리즘으로 문제를 풀어야 할지를 먼저 생각하니 금방 풀렸던것 같다. 문제부터 살펴보자. 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 .. 2021. 6. 21.
[프로그래머스 : 레벨 2] 타겟 넘버 : DFS(Java) 이번 문제는 내가 풀어보려다가 시간이 오래 지체할거같아 답지를 봤다. 이번 문제는 DFS로 풀어야 겠다는것도 알겠고 했는데 해당 문제를 어떻게 구현해야할지 몰랐다. 왜냐면 더하기와 빼기 했을때의 경우의수를 어떻게 구하지 했는데 답에서는 더하기 했을때와 빼기 했을때를 더한것으로 처리했다. 일단 문제를 자세히 살펴보자. 문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 .. 2021. 6. 21.
[자료구조] BFS(Breadth First Search) Java 구현 BFS는 Breadth First Search로 너비우선 탐색이란 뜻을 가진다. 너비 우선 탐색을 아래와 같은 과정으로 그래프를 모두 순회하는것이다. 자식노드와 그 형제노드를 모두 검색한뒤 그 다음에 있는 자식의 자식 노드와 그 형제들을 순회하는 방법이다. 해당 그림처럼 노드를 넓게 탐색한다. 그래서 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을때 이방법을 사용한다. BFS의 장점 1. 노드의 수가 적고 깊이가 얕은경우 빠르게 동작한다. 2. 단순 검색 속도가 DFS보다 빠르다. 3. 너비를 우선 탐색하기 때문에 답이 되는 경로가 여러개인 경우 최단경로를 보장한다. 4. 최단 경로가 존재한다면 경로가 무한대로 깊어져도 최단경로를 반드시 찾을수 있다. BFS의 단점 1. 재귀호출의 DFS와.. 2021. 6. 20.

티스토리툴바