Retry

package main

import (
	"fmt"
	"os"
)

type MazeNode2 struct {
	x, y     int
	distance int
}

func put2(maze *[]MazeNode2, m MazeNode2) {
	*maze = append(*maze, m)
}

func pop6(maze *[]MazeNode2) MazeNode2 {
	data := (*maze)[0]
	*maze = (*maze)[1:]
	return data
}
func mazeBFS2(maze [][]int, x, y int, distance int) {
	queue := []MazeNode2{{x, y, distance}}
	put2(&queue, MazeNode2{x, y, distance})

	for len(queue) > 0 {
		//ogQueue := queue[0]
		//queue = queue[1:]

		ogQueue := pop6(&queue)

		if ogQueue.x == 8 && ogQueue.y == 8 {
			fmt.Println(ogQueue.x, ogQueue.y)
			for i := 0; i < len(maze); i++ {
				fmt.Println(maze[i])
			}
			fmt.Println(ogQueue.distance)
			fmt.Println("!!!Yeah!!!")
			os.Exit(0)
		}

		maze[ogQueue.y][ogQueue.x] = 2
		//fmt.Println(ogQueue.y, ogQueue.x)

		dir := [][]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}

		for _, dir := range dir {
			nx, ny := ogQueue.x+dir[0], ogQueue.y+dir[1]
			if nx == -1 || ny == -1 || nx == len(maze) || ny == len(maze[0]) {
				continue
			}
			if maze[ny][nx] != 0 {
				continue
			}
			// 재귀함수 콜을 하면 무한루프에 빠질수있음. 그 이유는 "queue"에 계속해서 추가되기 때문
			// mazeBFS(maze, nx, ny)
			//queue = append(queue, &MazeNode2{nx, ny, distance})
			//fmt.Println(queue[x], queue[y])
			put2(&queue, MazeNode2{nx, ny, ogQueue.distance + 1})
		}

	}

}

func main() {
	maze := [][]int{
		{0, 1, 0, 1, 0, 0, 0, 0, 1},
		{0, 0, 0, 1, 0, 1, 0, 1, 1},
		{1, 0, 1, 0, 0, 1, 1, 0, 0},
		{0, 0, 0, 0, 1, 0, 0, 0, 1},
		{0, 1, 1, 0, 0, 0, 1, 1, 0},
		{0, 0, 1, 0, 1, 0, 1, 0, 0},
		{0, 1, 0, 0, 1, 1, 0, 0, 1},
		{0, 1, 0, 1, 0, 0, 0, 1, 1},
		{1, 1, 0, 0, 0, 1, 0, 0, 0},
	}
	mazeBFS2(maze, 0, 0, 0)
}

package main

import (
	"fmt"
	"os"
)

type MazeNode struct {
	x, y int
}

func mazeBFS(maze [][]int, x, y int) {
	queue := []*MazeNode{{x, y}}

	for len(queue) > 0 {
		ogQueue := queue[0]
		queue = queue[1:]

		// length로 바꾸기
		if ogQueue.x == 8 && ogQueue.y == 8 {
			fmt.Println(ogQueue.x, ogQueue.y)
			fmt.Println(maze)
			fmt.Println("!!!Yeah!!!")
			os.Exit(0)
		}

		maze[ogQueue.y][ogQueue.x] = 2
		//fmt.Println(ogQueue.y, ogQueue.x)

		dir := [][]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}

		for _, dir := range dir {
			nx, ny := ogQueue.x+dir[0], ogQueue.y+dir[1]
			if nx == -1 || ny == -1 || nx == len(maze) || ny == len(maze[0]) {
				continue
			}
			if maze[ny][nx] != 0 {
				continue
			}
			// 재귀함수 콜을 하면 무한루프에 빠질수있음. 그 이유는 "queue"에 계속해서 추가되기 때문
			// mazeBFS(maze, nx, ny)
			queue = append(queue, &MazeNode{nx, ny})
			//fmt.Println(queue[x], queue[y])
		}

	}

}

func main() {
	maze := [][]int{
		{0, 1, 0, 1, 0, 0, 0, 0, 1},
		{0, 0, 0, 1, 0, 1, 0, 1, 1},
		{1, 0, 1, 0, 0, 1, 1, 0, 0},
		{0, 0, 0, 0, 1, 0, 0, 0, 1},
		{0, 1, 1, 0, 0, 0, 1, 1, 0},
		{0, 0, 1, 0, 1, 0, 1, 0, 0},
		{0, 1, 0, 0, 1, 1, 0, 0, 1},
		{0, 1, 0, 1, 0, 0, 0, 1, 1},
		{1, 1, 0, 0, 0, 1, 0, 0, 0},
	}
	mazeBFS(maze, 0, 0)
}

- 위와 같은 배열이 있다고 하자. 이 배열을 3개의 작은 배열로 자르려고 한다. (순서를 바꾸지는 않는다)

자른 배열의 평균이 가장 비슷하게 자르는 방법은 무엇일까?



이론: mean-squared-error 라는 값이 있다. 전체 평균을 각 자른 slice의 평균과의 차이를 제곱한 값을 구해서 모두 더한 값이다.

만약 전체 평균이 10이고, 3개의 부분 배열의 평균값이 각각 8, 11, 9 라고 가정한다면 (8-10)^2 + (11-10)^2 + (9-10)^2 = 4 + 1 + 4 = 9가 된다.

배열을 어떻게 slice로 자르냐에 따라서 이 값은 변화하는데, mean-squared-error가 가장 작을 때 3개의 배열이 가장 고르게 분리되었다고 말할 수 있다.

package main

import "fmt"

func average2(slice []int) float64 {
	sliceSum := 0.0
	for _, v := range slice {
		sliceSum += float64(v)
	}
	sliceAverage := sliceSum / float64(len(slice))

	return sliceAverage
}

func main() {
	a := []int{4, 7, 4, 2, 9, 3, 7, 4, 1, 5, 3, 1, 10, 3, 6, 5, 2}

	sum := 0
	for _, num := range a {
		sum += num
	}
	average := float64(sum) / float64(len(a))
	fmt.Println(average) // ==> 4

	left2, right2 := 0, 0
	min := 20.0
	for i := 1; i < len(a)-1; i++ {
		for j := i + 1; j < len(a); j++ {
			slice1 := a[:i]
			slice2 := a[i:j]
			slice3 := a[j:]
			aver1 := average2(slice1)
			aver2 := average2(slice2)
			aver3 := average2(slice3)
			mse := (aver1-average)*(aver1-average) + (aver2-average)*(aver2-average) + (aver3-average)*(aver3-average)
			fmt.Println(mse)
			if mse < min {
				min = mse
				left2 = i
				right2 = j
			}
		}
	}
	fmt.Println(a[:left2], a[left2:right2], a[right2:])

}

- 다음과 같은 10x10 땅이 있다. 이 땅에서 3x3의 땅으로 분리해서 찾아볼 때 3x3 내부의 값의 합이 가장 큰 금싸라기 땅은 어디인가?

7-3) 합이 10인 곳은 몇군데나 있을까?

7-4) 7-3에 있는 배열에서 가로로 4칸의 블럭의 합이 10이거나 세로로 4칸의 블럭의 합이 10인 곳이 몇군데가 있을까?

package main

import "fmt"

func main() {
	a := [][]int{
		{1, 3, 2, 5, 3, 2, 7, 3, 2, 1},
		{4, 7, 4, 2, 2, 3, 1, 4, 1, 5},
		{3, 1, 2, 3, 6, 5, 2, 2, 8, 2},
		{6, 2, 3, 1, 4, 2, 1, 4, 1, 4},
		{1, 5, 4, 2, 3, 8, 4, 2, 1, 3},
		{1, 6, 3, 4, 2, 4, 3, 2, 6, 1},
		{1, 2, 1, 1, 2, 1, 1, 2, 3, 1},
		{5, 3, 7, 1, 2, 3, 2, 1, 5, 2},
		{3, 3, 4, 8, 1, 2, 5, 1, 3, 9},
		{7, 1, 2, 2, 3, 1, 6, 3, 2, 3},
	}

	// 7-3번 답
	//var maxSum, x, y int
	//for i := 0; i <= len(a)-3; i++ {
	//	for j := 0; j < len(a[i])-3; j++ {
	//		var sum int
	//		for k := i; k < i+3; k++ {
	//			for l := j; l < j+3; l++ {
	//				sum += a[k][l]
	//			}
	//		}
	//		if sum > maxSum {
	//			maxSum = sum
	//			x = i
	//			y = j
	//		}
	//	}
	//}
	//fmt.Println(maxSum, x, y)

	// 7-4번 답
	cnt := 0
	for i := 0; i < len(a); i++ {
		for j := 0; j < len(a[0]); j++ {
			// 세로 x4
			if j+3 < len(a[0]) {
				sumCol := a[i][j] + a[i][j+1] + a[i][j+2] + a[i][j+3]
				if sumCol == 10 {
					cnt++
				}
			}
			// 가로 x4
			if i+3 < len(a) {
				sumRow := a[i][j] + a[i+1][j] + a[i+2][j] + a[i+3][j]
				if sumRow == 10 {
					cnt++
				}
			}
		}
	}
	fmt.Println(cnt)
}

- 토끼는 전진할 때에는 무조건 7칸을 간다. 뒤로 갈 때는 무조건 3칸을 간다.

거리 n 이 주어진 경우 토끼가 목적지에 다다를 때까지 몇 번을 움직여야 하는지 횟수를 얻어내시오.

(예: 거리가 11인 경우... 앞으로 1번 전진 후 뒤로 1번 후진하고 다시 앞으로 한번 전진하면 7, 4, 11 이런 순으로 3번 만에 도착할 수 있다. 목적지를 지나치거나 출발지 뒤로 넘어갈 수는 없다.)

package main

import (
	"fmt"
	"os"
)

func rabbitMove(now int, distance int, cnt int) int {
	if now == distance {
		fmt.Println(cnt)
		os.Exit(0)
	}
	if now > distance || now < 0 {
		return -1
	}

	return rabbitMove(now+7, distance, cnt+1) + rabbitMove(now-3, distance, cnt+1)
}

func main() {
	distance := 10
	rabbitMove(0, distance, 0)
}

package main

import "fmt"

type SimpleNode2 struct {
	value   int
	visited bool
}

func bfs2(id int, nodes map[int]*SimpleNode2, edges [][]int) {
	queue := make([]int, 0)
	queue = append(queue, id)

	if !nodes[id].visited {
		nodes[id].visited = true
	}

	for len(queue) > 0 {
		ogQueue := queue[0]

		queue = queue[1:]

		//fmt.Println(nodes[ogQueue].value)

		for _, e := range edges {
			fmt.Println(e[0], ogQueue, e[1])
			if e[0] == ogQueue && !nodes[e[1]].visited {
				nodes[e[1]].visited = true
				queue = append(queue, e[1])
				//fmt.Println(queue, "===")
			} else if e[1] == ogQueue && !nodes[e[0]].visited {
				nodes[e[0]].visited = true
				queue = append(queue, e[0])
				//fmt.Println(queue, "++++")
			}
		}
	}
}

func main() {
	nodes := make(map[int]*SimpleNode2)
	edges := [][]int{
		{1, 2},
		{2, 4},
		{2, 3},
		{4, 5},
		{4, 6},
		{5, 8},
		{6, 8},
		{8, 10},
		{6, 7},
		{5, 9},
	}
	for i := 1; i <= 10; i++ {
		nodes[i] = &SimpleNode2{value: i, visited: false}
	}

	bfs2(1, nodes, edges)
}