Sangil's blog

https://github.com/ChoiSangIl Admin

이동평균 알고리즘 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

프로그래머스 코딩 테스트 탑 JAVA(자바) DEV / ALGORITHM

2020-07-25 posted by sang12


이 문제가..왜 스택분류에 있는지 잘 모르겠다.. 스택으로 푸신분들도 존재. 이중 FOR문을 이용하면 간단히 해결 할 수 있다.

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42588

class Solution {
    public int[] solution(int[] heights) {
        int[] answer = new int[heights.length];
		
		for(int i=0; i<heights.length; i++) {
			if(i==0) {
				answer[i] = 0;
			}else {
				for(int j=i-1; j>=0; j--) {
					if(heights[i] < heights[j]) {
						answer[i] = j+1;
						break;
					}
					if(j==0) {
						answer[i]= 0;
					}
				}	
			}
		}
        
        return answer;
    }
}

REPLY

프로그래머스 코딩테스트 다리를 지나는 트럭 자바(JAVA) DEV / ALGORITHM

2020-07-25 posted by sang12


각각의 무게를 가진 트럭이 K만큼의 길이를 가지고있고 N만큼의 무게를 견딜 수 있는 다리를 건너는데 걸리는 시간을 구하는 문제입니다. 트럭은 1초마다 1만큼 이동 할 수 있습니다. (문제: https://programmers.co.kr/learn/courses/30/lessons/42583?language=java). 이미 문제 유형 자체가 스택이나 큐를 이용하는 문제여서 스포를당해버린...

링크드리스트를 이용해서 trucks과 bridge 객체를 생성했습니다. 그리고 다리의 길이만큼 이동하기위해 int배열을 이용해서 0번째에는 무게를 1번째에는 이동 할 수 있는 다리의 길이를 넣어줬습니다. 그리고 currentBridgeWeight는 다리위에 올라와있는 트럭의 무게이고, 이를 이용해서 다리에 올라 갈 수 있는 무게만 올가가게 해줬습니다. 그리고 트럭과 다리의 큐가 비어 있으면! 끝..!

import java.util.LinkedList;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
       int currentBridgeWeigh = 0;
		LinkedList<Integer> trucks = new LinkedList<Integer>(); 
		LinkedList<int[]> bridge = new LinkedList<int[]>(); 
		
		for(int truck : truck_weights) {
			trucks.add(truck);
		}
		
		int result = 1;
		
		while(!trucks.isEmpty() || !bridge.isEmpty()) {
			for(int j=0; j<bridge.size(); j++){
				int[] tructCheck = bridge.get(j);
				if(tructCheck[1] == 0) {
					bridge.poll();
					currentBridgeWeigh = currentBridgeWeigh-tructCheck[0];
				}
			}
			
			if(!trucks.isEmpty()) {
				int[] truck = {trucks.peek(), bridge_length};
				if(currentBridgeWeigh + truck[0]<= weight) {
					bridge.add(truck);
					currentBridgeWeigh = currentBridgeWeigh+truck[0];
					trucks.poll();
				}
			}
			
			for(int j=0; j<bridge.size(); j++){
				int[] tructCheck = bridge.get(j);
				tructCheck[1]--;
				bridge.set(j, tructCheck);
			}
			
			if(trucks.isEmpty() && bridge.isEmpty()) {
				break;
			}
			result++;
		}
		
		return result;
		
    }
}

하고 나서 다른사람들의 소스를 참고하니, 제가 int배열로 처리했던 부분 0번쨰에는 무게, 1에는 갈 수 있는거리를 Class Truck으로 만들어서 처리한 부분이 인상적이였습니다. 

REPLY