Sangil's blog

https://github.com/ChoiSangIl Admin

프로그래머스 코팅테스트 DFS/BFS 단어 변환 JAVA DEV / ALGORITHM

2021-09-08 posted by sang12


어떤문제

일까? (출처:https://programmers.co.kr/learn/courses/30/lessons/43163)

해당 문제는 begin과 target 단어가 주어지고, 주어진 단어 배열을 이용하여 한개의 알파뱃씩을 변경하여 begin에서 target으로 변환 할 수 있는 최소 단계를 찾는 문제이다.

어떻게

풀었을까?

begin으로 부터 시작되는 트리를 만들어, 탐색할수 있는 노드들( 1개의 단어로 변환 가능한 )을 깊이 우선 탐색을 하여, target에 도달 했을 때의 depth를 반환 하면 답을 구할 수 있지 않을까 생각했다.

target 단어인 hit를 시작으로 변환 가능한 노드들을 따라서 깊이 탐색을 한다. 이때, stack이란 배열을 이용하여 탐색을 한 노드들을 제외하고 시작단어 + 단어의 개수인 최대 depth까지 탐색 하도록 한다. 이때, 탐색 노드와 target단어가 같으면 해당 depth를 리턴한다. 그러면 최종적으로 모든 노드들을 탐색하게 되고, 이때 리턴되는 최소값이 최소 변환 횟수가 된다.

코드

(https://github.com/ChoiSangIl/algorithm/tree/master/BFS%2CDFS/programmers_C30_L43163_words)

import java.util.ArrayList;
import java.util.Arrays;

public class A20210907 {

	public static void main(String[] args) {
		String begin = "hit"; 
		String target  = "cog";
		String[] words = {"hot", "dot", "dog", "lot", "log", "cog"};
		
		ArrayList<String> stack = new ArrayList<String>();
		int result = dfs(begin, target, words, stack, 0);
		System.out.println(result);
	}
	
	public static int dfs (String begin, String target, String[] words, ArrayList<String> stack, int depth) {
		stack.add(begin);
		System.out.println(stack);
		
		if(begin.equals(target)) {
			stack.remove(begin);
			return depth;
		}
		
		int result = 0;
		
		for(int i=0; i<words.length; i++) {
			int wordCheck = 0;
			
			//변환 가능한지 체크
			for(int j=0; j<words[i].length(); j++) {
				if(begin.charAt(j) == words[i].charAt(j)) {
					wordCheck = wordCheck + 1;
				}
			}
			
			//단어 변환이 가능하면, 해당 노드를 깊이 탐색한다.
			if(wordCheck == words[i].length()-1 && !stack.contains(words[i])) {
				int particleResult = dfs(words[i], target, words, stack, depth+1);
				if(result == 0) {
					result = particleResult;
				}else {
					if(particleResult != 0) {
						result = Math.min(result, particleResult);
					}
				}
			}
		}
		stack.remove(begin);
		return result;
	}
}

어떤게

어려웠을까?

단어가 변환 가능한지 체크 하는 부분을 처음엔 replace 하는 방법으로 구현을 하였는데, aaa -> aab와 같은 경우를 생각 하지 못했다. 그래서 words의 크기 -1개의 단어가 똑같은 단어가 있으면 통과되게 변경 하였다. (해당 체크로직을 사소하다고 생각하고 쉽게 넘어갔다, 다양한 케이스를 생각 못함)

개선할점

은 없을까?

해당 접근방법으로 문제를 풀때, DFS보다 BFS방식으로 탐색을 하면 더욱 좋은 퍼포먼스가 나올 수 있겠다라는 생각이 들었다. DFS방식으로 풀면 최소값을 찾아야 하기 때문에 전체 노드들을 순회해야 하지만, BFS방식으로 풀면 target값을 처음 찾는 순간이 최소값이기 때문이다. 물론 최악의 경우는 비슷하겠지만... 다음엔 BFS방식으로 풀어봐야겠다.

#알고리즘
REPLY

프로그래머스 코딩테스트 연습(BFS/DFS) 네트워크 JAVA DEV / ALGORITHM

2021-08-30 posted by sang12


왜? (문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43162)

못 풀었을까?

1. DFS를 사용할 방법은 생각 했지만, 활용을 하지 못했다. 
-> 모든 노드에서 DFS 탐색을 하지 않아도 된다. 연결이 되어 있다면 연결된 노드는 패스하고 연결되지 않은 노드부터 탐색해야 하는데 해당 부분을 생각하지 못했다.

어떻게 풀면 될까?


1. STACK ( 1->2->3 )
2. STACK ( 1->2 )
3. STACK ( 1->2->4 )
4. STACK ( 1->2->4->7 )
5. STACK ( 1->2->4 )
6. STACK ( 1->2 )
7. STACK ( 1->2-> 5)
8. STACK ( 1->2 )
9. STACK ( 1-> 6 )
10. STACK ( 1 )
11. STACK () 
위의 노드를 다 순회하고 나면, 순회한 노드들은 다 연결 되어 있다는 것을 알 수 있다.
그러므로 해당 노드들은 다시 탐색할 필요가 없다. 이를 PATH[] 배열을 이용하여 연결되었음을 TRUE값으로 넣어주고, 해당 순회가 끝나면 PATH 배열에 연결되어 있지 않은 노드들부터 다시 순회하면 해당 문제를 풀 수 있다.


-JAVA 소스 : https://github.com/ChoiSangIl/algorithm/tree/master/BFS%2CDFS/progrmmers_C30_L43162_networks
DFS로 생각 할때는 STACK으로 생각하는게 쉬워서 STACK을 사용했지만, 구현은 재귀 함수로 구현했다. 처음엔 재귀함수로 짜는것도 이해가 안되었는데, 프로그래머스 연습문제 타겟넘버가 많은 도움이 됐다(https://programmers.co.kr/learn/courses/30/lessons/43165)

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] path = new boolean[n];
		
		for(int i=0; i<n; i++) {
			path[i] = false;
		}
		
		for(int j=0; j<n; j++) {
			if(!path[j]) {
				answer ++;
				dfs(j, computers, path);
			}
		}
        
        return answer;
    }
    
    public static void dfs(int index, int[][] computers, boolean[] path) {
		path[index] = true;
		
		for(int i=0; i<computers.length; i++) {
			if(path[i] == false && computers[index][i] == 1) {
				dfs(i, computers, path);
			}
		}
	}
}

REPLY

이동평균 알고리즘 JAVA DEV / ALGORITHM

2021-05-10 posted by sang12


이동평균이란

주식에 발을 들이민 사람이라면 이평선이란 용어를 많이 들어 봤을 것이다. 3일 이동평균선이란 오늘을 포함한 3일동안의 평균값을 나타낸다. 예를들면 아래와 같다.


1일2일3일4일5일6일7일
주식가격100040007000550090001000015000
이동평균 (3일)

400055007166816611333
이동평균 (4일)


4375637578759875

내 주식도 저렇게 오르면 좋으련만... 3일의 이동평균값을 보면 1000+4000+7000/3 이란거를 볼 수 있다. 해당 알고리즘을 자바로 표현하면 아래와 같다.

이동평균 알고리즘(JAVA)

public class moving {
	public static void main(String[] args) {
		int m=4;
		int[] list = {1000, 4000, 7000, 5500, 9000, 10000, 15000};
                int n= list.length;
		List<Integer> result = new ArrayList<Integer>();
		
		for(int i=m-1; i<n; i++) {
			int sum = 0;
			for(int j=0; j<m; j++) {
				sum = sum + list[i-j];
			}
			result.add(sum/m);
		}
		System.out.println(result);
	}
}

알고리즘 개선

다시 7일간의 주식 가격을 확인해봅시다. 3일의 이평선값을 구하는 공식은 아래와 같습니다.

1일2일3일4일5일6일7일
주식가격100040007000550090001000015000
이동평균(3일)

400055007166816611333

3일 이동평균의 값 : (1000+4000+7000)/3
4일 이동평균의 값 : (4000+7000+5500)/3
5일 이동평균의 값 : (7000+5500+9000)/3

여기서 공통점이 보이시나요? 4일의 이동평균을 구하기 위해서는 3일의 이동평균값을 구하기위한 전체 값에서 1일 주식가격을 빼고 4일의 주식가격을 더해주면 됩니다. 5일의 이동평균값도 마찬가지로 4일의 이동평균값을 구하기위한 전체 가격에서 2일의 주식가격을빼고 5일의 주식가격을 더한뒤 3으로 나눠주면 됩니다. 그럼 이제 해당 공식을 코드로 구현해 봅시다.

개선된 이동평균 알고리즘(JAVA)

public class moving {
	public static void main(String[] args) {
		int m=3;
		int[] list = {1000, 4000, 7000, 5500, 9000, 10000, 15000};
                int n= list.length;
		List<Integer> result = new ArrayList<Integer>();
		
		int sum = 0;
		
		for(int i=0; i<m-1; i++) {
			sum = sum+list[i];	//m-1까지의 부분sum
		}
		
		for(int i=m-1; i<n; i++) {
			sum = sum + list[i];
			result.add(sum/m);
			sum = sum - list[i-m+1];  
		}
		
		System.out.println(result);
	}
}

여기서 우리는 중복되는 부분을 활용하여 이중 for문으로 구현한 알고리즘에서 for문 2개로 구성된 코드로 개선할 수 있었습니다. 이때 for문이 반복 되는 횟수는 n의 정비례하여 증가 하게 됩니다. 하여 해당 알고리즘을 선형 시간 알고리즘이라고 부릅니다 :)


#선형시간알고리즘
REPLY