블록체인하는 만두아빠

폰 노이만이 1945년 개발한 Merge Sort (합병 정렬)은 Divide and Conquer (분할 정복) 알고리즘의 하나입니다.

합병 정렬은 순서없이 뒤섞여 있는 배열(Array)을 길이가 1 이하가 될 때까지 분할하고 재귀적으로 정렬하고 다음 정렬된 부분을 병합하는 방법으로 진행합니다.

27, 10, 12, 20, 25, 13, 15, 22로 구성된 배열을 nondecreasing order(오름차순)로 정렬하는 Merge Sort는 다음과 같습니다.

각각 절반씩 Divide한 후에 길이가 1이하가 되면 정복(Conquer)을 통해 재귀적으로 정렬하고, Merge를 합니다. 최종적으로 Merge된 배열은 nondecreasing order로 정렬되어 있습니다.

위의 내용을 토대로 Input이 n, array s[1...n]이고 Output이 nondecreasing order로 정렬된 S[1...n]이 되는 Merge Sort 알고리즘을 다음과 같이 구성해볼 수 있을 것입니다.

void mergesort (int n, keytype S[]) {
	const int h = [n / 2], m = n - h;
	keytype U[1..h], V[1..m];
	
    if (n > 1) {
		copy S[1] through S[h] to U[1] through U[h];
		copy S[h+1] through S[n] to V[1] through V[m];
		mergesort(h,U);
		mergesort(m,V);
		merge(h,m,U,V,S);
	}
}

BOJ 2884번 알람 시계 Go Lang 문제풀이입니다.

45분인지 아닌지를 확인하기 위해 If문을 사용해서 45분 보다 많이 남았을 때, 딱 45분일 때, 45분 미만일 때로 분류해서 작성합니다.

시간은 h, 분은 m으로 입력값을 받아서 다음과 같이 나타낼 수 있습니다.

package main

import (
	"fmt"
)

func main() {
	var h int
	var m int
	fmt.Scan(&h, &m)

	if m-45 >= 0 {
		fmt.Printf("%d %d\n", h, m-45)
	} else if h == 0 {
		fmt.Printf("%d %d\n", 23, 15+m)
	} else {
		fmt.Printf("%d %d\n", h-1, 15+m)
	}
}

BOJ 14681번 사분면 고르기 Go Lang 문제풀이입니다.

x좌표와 0보다 큰 경우와 0보다 크지 않은 경우를 if 문을 통해 나누고, 그 안에서 다시 y좌표가 0보다 큰 경우와 크지 않은 경우에 따라 각각의 사분면이 표시될 수 있도록 Println합니다.

package main

import (
	"fmt"
)

func main() {
	var x, y int
	fmt.Scanln(&x)
	fmt.Scanln(&y)

	if x > 0 {
		if y > 0 {
			fmt.Println(1)
		} else {
			fmt.Println(4)
		}
	} else {
		if y > 0 {
			fmt.Println(2)
		} else {
			fmt.Println(3)
		}
	}
}

BOJ 2292번 벌집 Go Lang 문제풀이입니다.

해당 문제는 첫번째 벌집인 1번 벌집 주위에 6개의 벌집이 생기며, 그 주변으로 총 6의 배수만큼씩 벌집이 증가하는 형태를 나타냅니다. 1번 방에서 시작하기 때문에 첫번째 6의 배수 안에 숫자로 가기 위해서는 총 두 번, 두번째 6의 배수 안의 숫자로는 세 번 이동하면 갈 수 있습니다.

이를 Go Lang에서 반복문과 조건문을 통해 구성하면 됩니다.

package main

import "fmt"

func main() {
	var a int
	fmt.Scanln(&a)

	b := 1
	c := 1
	for {
		if b >= a {
			break
		}
		b += c * 6
		c++
	}
	fmt.Println(c)
}

BOJ 1712번 손익분기점 Go Lang 문제풀이입니다.

해당 문제는 '가격'이 주어졌을 때, '고정비용' + '가변비용'의 합이 '가격'을 넘지 않는 바로 직전의 지점을 구하는 문제입니다.

손익분기점을 BE Point라는 이름으로 별도 함수화하여 메인 함수에서 호출하는 방법으로 소스를 작성하였습니다.

package main

import "fmt"

func bepoint(a, b, c int) int {
	if b >= c {
		return -1
	}
	return a/(c-b) + 1
}

func main() {
	var a, b, c int
	fmt.Scanln(&a, &b, &c)
	fmt.Println(bepoint(a, b, c))
}