요격 시스템 (ver. golang)

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

 

문제풀이

이 문제는 최소한의 요격으로 모든 미사일을 격추시키는 것이 요구사항임을 알 수 있습니다.

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/181188

 

 

A나라의 미사일이 X축과 평행하게 발사되면, B나라에서는 Y축으로 발사하여 모든 미사일을 요격합니다. 따라서 X 구간의 범위가 겹치지 않는 선에서 최소한의 미사일을 발사하는 것이 중요합니다.

 

이를 위해서는 A 나라의 미사일 좌표를 정렬하고, start 와 end 값을 확인하고 끊겨지는 구간이 발생하는 경우 미사일을 한발 더 쏘게 하면 될 것입니다.

 

좌표의 끝점과 동일한 곳에서 미사일을 발사하면 안되는 제한조건이 있기 때문에 끝점과 일치하지 않는 경우만 미사일이 격추할 수 있도록 조건문을 작성하였습니다.

 

func main() {
	fmt.Println(solution([][]int{{4, 5}, {4, 8}, {10, 14}, {11, 13}, {5, 12}, {3, 7}, {1, 4}}))
}

func solution(targets [][]int) int {
	cnt := 0

	fmt.Println(targets)
	// 한 발 맞출 때 최대한 많은 미사일을 맞추면 된다.
	// start 와 end 값을 확인하고 끊겨지는 구간을 확인하면 된다.
	// 값을 비교하기 위해서는 정렬이 필요하다.
	sort.Slice(targets[:], func(i, j int) bool {
		return targets[i][1] < targets[j][1]
	})

	fmt.Println(targets)

	// 끝점을 저장
	endPoint := 0
	for _, target := range targets {
		// 시작점이 endpoint 보다 작다면 이전 미사일로 격추할 수 있음
		if target[0] < endPoint {
			continue
		} else {
			cnt++
			endPoint = target[1]
		}
	}

	return cnt
}

 

문제는 위와 같이 풀어보았고, 문제를 통해 정리할 수 있는 내용에 대해 정리하겠습니다.

 

Golang 에서 2차원 배열에 대한 정렬

ASIS : [[4 5] [4 8] [10 14] [11 13] [5 12] [3 7] [1 4]]

sort.Slice(targets[:], func(i, j int) bool {
		return targets[i][1] < targets[j][1]
})

TOBE : [[1 4] [4 5] [3 7] [4 8] [5 12] [11 13] [10 14]]

 

sort.Slice 함수는 첫번째 인수로는 대상 배열, 두번째 인수로는 비교 함수를 받고 있습니다.

 

두번째 인수로 쓰이는 비교함수는 우리가 정렬을 할때 기준이 되는 조건식을 의미합니다.

 

그리고 비교함수의 i 와 j 는 인덱스를 의미하며 이는 순차적으로 증가됩니다.

 

우리는 위에서 끝점(end point) 의 값에 따라 요격할 수 있는 범위가 달라지다보니, targets 의 배열의 첫 번째 요소의 끝점과 두 번째 요소의 끝점을 비교하여 오름차순(<) 정렬을 진행하게 됩니다.

 

Greedy Algorithm

탐욕알고리즘(Greedy Algorithm) 은 최적해를 구하는 알고리즘입니다. 각 단계에서 최적이라고 생각되는 것을 선택해나가 최종적인 해답에 도달하는 알고리즘입니다.

 

주의해야할 점은 탐욕알고리즘이 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 근사한 값을 목표로 합니다.

 

탐욕 알고리즘의 필요 조건

탐욕 선택 속성 (Greedy Choice Property)

• 앞의 선택이 이후의 선택에 영향을 주지 않는 것

최적 부분 구조 (Optimal Substructure)

• 문제에 대한 최적 해가 부분문제에 대해서도 역시 최적해가 되어야 한다는 점

탐욕 알고리즘의 단계

• 선택 절차(Selection Procedure) : 이 단계에서는 현재 상태에서 최적인 선택을 합니다. 이 선택은 이후에는 바뀌지 않습니다.
• 적절성 검사(Feasibility Check) : 이 단계에서는 선택한 항목이 문제의 조건을 만족시키는지 확인합니다. 조건을 만족시키지 않으면 해당 항목은 제외됩니다.
• 해답 검사(Solution Check) : 이 단계에서는 모든 선택이 완료되면 최종 선택이 문제의 조건을 만족시키는지 확인합니다. 조건을 만족시키면 해답으로 인정됩니다.

탐욕 알고리즘 문제풀이 절차

그리디 알고리즘의 단계는 매 단계마다 최적이라고 생각되는 선택을 하면서 최종적으로 전체적인 최적인 해답을 찾아내는 과정을 의미

1. 문제의 최적해 구조를 결정합니다.
2. 문제의 구조에 맞게 선택 절차를 정의합니다. : 선택 절차 (Selection Procedure)
3. 선택 절차에 따라 선택을 수행합니다.
4. 선택된 해가 문제의 조건을 만족하는지 검사합니다. : 적절성 검사 (Feasibility Check)
5. 조건을 만족하지 않으면 해당 해를 제외합니다.
6. 모든 선택이 완료되면 해답을 검사합니다.
7. 조건을 만족하지 않으면 해답으로 인정되지 않습니다.

요격시스템을 탐욕 알고리즘에 적용

위에서 탐욕 알고리즘의 개념을 다져봤습니다. 우리가 문제를 풀 때 정렬을 적용한 배열을 순환을 통해서 어떤 조건을 판별하거나, 이전 단계에서의 결과가 다음 단계에서의 결과와 무관할 때 우리는 탐욕 알고리즘을 적용시킬 수 있는 점을 알 수 있습니다.

 

그리고 탐욕 알고리즘으로 문제를 풀고자 할 때 우리는 선택절차, 적절성 검사, 해답 검사를 로직으로 구현하면 문제를 풀어낼 수 있습니다.

 

3가지 단계를 쉽게 풀어내면, 하나의 단계를 어떤 단계부터 풀어낼 것인지 정하기 위해 배열을 정렬하여 단계를 설정합니다. 그리고 그 단계가 주어진 조건에 맞는지 적절성 검사를 진행합니다. 모든 검사가 완료되면 전체 해가 조건을 만족하는지 해답을 검사합니다.

 

요격시스템 문제풀이

func solution(targets [][]int) int {
	cnt := 0

	fmt.Println(targets)
	// 한 발 맞출 때 최대한 많은 미사일을 맞추면 된다.
	// start 와 end 값을 확인하고 끊겨지는 구간을 확인하면 된다.
	// 값을 비교하기 위해서는 정렬이 필요하다.
	sort.Slice(targets[:], func(i, j int) bool {
		return targets[i][1] < targets[j][1]
	})

	fmt.Println(targets)

	// 끝점을 저장
	endPoint := 0
	for _, target := range targets {
		// 시작점이 endpoint 보다 작다면 이전 미사일로 격추할 수 있음
		if target[0] < endPoint {
			continue
		} else {
			cnt++
			endPoint = target[1]
		}
	}

	return cnt
}

선택절차

요격시스템에서는 A나라가 발사한 미사일의 좌표 배열 targets 배열을 좌표의 끝점을 기준으로 정렬을 하였습니다. 우리는 targets 를 순회하면서 조건을 검사할 수 있는 단계들을 설정하였습니다.

적절성 검사

요격시스템의 끝점을 endPoint 에 저장합니다. 그리고 이전 단계에서 발사했던 미사일의 타격범위에 포함되는지 적절성을 검사합니다. 미사일의 타격범위에 포함되지 않는 경우에는 새로운 미사일을 발사하고, 새로운 미사일의 endPoint 를 다시 저장하여 미사일 발사횟수를 count 합니다.

해답 검사

미사일 발사횟수 cnt 가 A 나라가 발사한 미사일들을 모두 격추할 수 있는지 검사하고, 답을 반환합니다.

 

Reference

https://adjh54.tistory.com/212