용용코딩

https://www.acmicpc.net/problem/1149

• 문제

• 문제풀이

for문을 사용하여 math.min을 구해 최소거리를 구했다.

• 코드 1

using System;

class RGBHouse
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());

        int[,] cost = new int[n, 3];
        for (int i = 0; i < n; i++)
        {
            string[] input = Console.ReadLine().Split();
            cost[i, 0] = int.Parse(input[0]);
            cost[i, 1] = int.Parse(input[1]);
            cost[i, 2] = int.Parse(input[2]);
        }

        int[,] ans = new int[n, 3];
        ans[0, 0] = cost[0, 0];
        ans[0, 1] = cost[0, 1];
        ans[0, 2] = cost[0, 2];

        for (int i = 1; i < n; i++)
        {
            ans[i, 0] = cost[i, 0] + Math.Min(ans[i - 1, 1], ans[i - 1, 2]);
            ans[i, 1] = cost[i, 1] + Math.Min(ans[i - 1, 0], ans[i - 1, 2]);
            ans[i, 2] = cost[i, 2] + Math.Min(ans[i - 1, 0], ans[i - 1, 1]);
        }

        int minCost = Math.Min(ans[n - 1, 0], Math.Min(ans[n - 1, 1], ans[n - 1, 2]));
        Console.WriteLine(minCost);
    }
}

• 후기

다이나믹 프로그래밍은 항상 접근하기 어렵다. 많이 노력해야겠다.

https://www.acmicpc.net/problem/1912

• 문제

• 문제풀이

첫번째 숫자를 output에 넣어주고 그다음 숫자를 더했을 때와 아닐때를 비교하여 max값을 찾는 방식으로 코드를 작성하였다.

• 코드 1

using System;

class MainClass
{
    public static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        int[] output = new int[n];
        output[0] = input[0]; 
        int max = output[0];

        for (int i = 1; i < n; i++)
        {

            output[i] = Math.Max(input[i], input[i] + output[i - 1]);
            max = Math.Max(max, output[i]);
        }

        Console.WriteLine(max);
    }
}

• 후기

다이나믹 프로그래밍은 항상 접근하기 어렵다. 많이 노력해야겠다.

https://www.acmicpc.net/problem/11053

• 문제

• 문제풀이

반복문을 사용해서 큰 수가 나올때마다 카운팅해주어 MAX값을 찾아내었다.

• 코드 1

using System;

class MainClass
{
    public static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        int[] output = new int[n];
        int max = 1;

        for (int i = 0; i < n; i++)
        {
            output[i] = 1;
            for (int j = 0; j < i; j++)
            {
                if (input[j] < input[i] && output[i] < output[j] + 1)
                {
                    output[i] = output[j] + 1;
                }
            }
            max = Math.Max(max, output[i]);
        }

        Console.WriteLine(max);
    }
}

• 후기

다이나믹 프로그래밍은 항상 접근하기 어렵다. 많이 노력해야겠다.

https://www.acmicpc.net/problem/1463

• 문제

• 문제풀이

다이나믹 프로그래밍을 사용하였다. 재귀 방식을 사용하여 문제를 풀었다.

• 코드 1

using System;

class MainClass
{
    public static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());

        int[] dp = new int[n + 1];
        int count = FindMinOperations(n, dp);

        Console.WriteLine(count);
    }

    public static int FindMinOperations(int n, int[] dp)
    {
        if (n == 1)
        {
            return 0;
        }

        if (dp[n] > 0) // 이미 계산한 값이 있다면 그 값을 사용
        {
            return dp[n];
        }

        int minOperations = FindMinOperations(n - 1, dp) + 1; // n에서 1을 빼는 경우
        if (n % 2 == 0)
        {
            minOperations = Math.Min(minOperations, FindMinOperations(n / 2, dp) + 1); // n을 2로 나누는 경우
        }
        if (n % 3 == 0)
        {
            minOperations = Math.Min(minOperations, FindMinOperations(n / 3, dp) + 1); // n을 3으로 나누는 경우
        }

        dp[n] = minOperations; // 최소 연산 횟수를 저장
        return minOperations;
    }
}

• 후기

다이나믹 프로그래밍은 항상 접근하기 어렵다. 많이 노력해야겠다.

Detectron 2를 사용해야하기 때문에 test set, train set을 만들기 위해 labelme를 사용해야했다.

anaconda prompt를 관리자권한으로 실행시켜야 한다. 그렇지 않으면 왜인지 모르겠지만 pip install을 할 때 오류가 생긴다.

명령 프롬프트에서

conda create --name=labelme python=3.6
conda activate labelme
pip install labelme
labelme

4줄을 이어서 쓰면 labelme가 설치가 된다.

이런식으로 쓰면

이런식으로 화면이 뜨게 된다.

Open을 통해 사진 파일을 읽고 Create Polygons로 사진을 라벨링 해줄 수 있다.

이런식으로 사람도 라벨링 할 수 있다.

https://www.acmicpc.net/problem/1697

• 문제

• 문제풀이

move는 a+1, a-1, a*2 3개로 나누어 BFS를 확인한다.

• 코드 1

using System;
using System.Collections.Generic;

namespace ConsoleApp2
{
    internal class Program
    {
        public static int[] graph = new int[100001];
        public static bool[] visit = new bool[100001];
        public static int[] move = new int[3];
        public static int num;

        static void Main(string[] args)
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int N = input[0];
            int K = input[1];

            bfs(N, K);

            Console.WriteLine(num);
        }

        public static void bfs(int startX, int targetX)
        {
            Queue<int> queue = new Queue<int>();
            queue.Enqueue(startX);
            visit[startX] = true;

            while (queue.Count > 0)
            {
                int a = queue.Dequeue();

                move[0] = a - 1;
                move[1] = a + 1;
                move[2] = a * 2;

                for (int k = 0; k < move.Length; k++)
                {
                    int x = move[k];

                    if (x >= 0 && x <= 100000 && !visit[x])
                    {
                        graph[x] = graph[a] + 1;
                        queue.Enqueue(x);
                        visit[x] = true;

                        if (x == targetX)
                        {
                            num = graph[x];
                            return;
                        }
                    }
                }
            }
        }
    }
}

• 후기

예전에 좀비에 전염된다는 문제를 풀었던 코드가 있어 일부 수정했다.

https://www.acmicpc.net/problem/7576

• 문제

• 문제풀이

visit을 만들어주어서 방문처리 후 숫자를 1로 바꿔준다. BFS를 마친 뒤 0이 있다면 -1을 출력해준다.

• 코드 1

using System;
using System.Collections.Generic;

namespace ConsoleApp2
{
    internal class Program
    {
        public static int[,] graph;
        public static int N, M;
        public static bool[,] visit;
        public static int[] dx = { -1, 1, 0, 0 };
        public static int[] dy = { 0, 0, 1, -1 };
        public static Queue<(int, int)> queue = new Queue<(int, int)>();

        static void Main(string[] args)
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            M = input[0];
            N = input[1];
            graph = new int[N, M];
            visit = new bool[N, M];

            for (int i = 0; i < N; i++)
            {
                string[] str = Console.ReadLine().Split();
                for (int j = 0; j < M; j++)
                {
                    graph[i, j] = int.Parse(str[j]);
                    visit[i, j] = false;
                }
            }

            int days = bfs();

            
            bool all = true;
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    if (graph[i, j] == 0)
                    {
                        all = false;
                        break;
                    }
                }
            }

            if (all)
                Console.WriteLine(days - 1);
            else
                Console.WriteLine(-1);
        }

        public static int bfs()
        {
            int days = 0;

          
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    if (graph[i, j] == 1)
                    {
                        queue.Enqueue((i, j));
                        visit[i, j] = true;
                    }
                }
            }

            while (queue.Count > 0)
            {
                int size = queue.Count;

                for (int i = 0; i < size; i++)
                {
                    (int a, int b) = queue.Dequeue();

                    for (int k = 0; k < 4; k++)
                    {
                        int x = a + dx[k];
                        int y = b + dy[k];
                        if (x >= 0 && x < N && y >= 0 && y < M)
                        {
                            if (!visit[x, y] && graph[x, y] == 0)
                            {
                                visit[x, y] = true;
                                graph[x, y] = 1; 
                                queue.Enqueue((x, y));
                            }
                        }
                    }
                }

                days++;
            }

            return days;
        }
    }
}

• 후기

예전에 좀비에 전염된다는 문제를 풀었던 코드가 있어 일부 수정했다.

https://www.acmicpc.net/problem/7562

• 문제

• 문제풀이

BFS를 사용하여 만든다. dx와 dy를 나이트가 움직이는 좌표로 설정해주어야한다.

• 코드 1

using System;
using System.Collections.Generic;

namespace YONGYONG2
{
    class Program
    {
        public static int[] dx = { -2, -1, 1, 2, 2, 1, -1, -2 };
        public static int[] dy = { 1, 2, 2, 1, -1, -2, -2, -1 };
        public static int[,] chessBoard;
        public static int size;

        static void Main(string[] args)
        {
            int T = int.Parse(Console.ReadLine());

            for (int t = 0; t < T; t++)
            {
                size = int.Parse(Console.ReadLine());
                chessBoard = new int[size, size];

                int[] start = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                int[] target = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

                int result = bfs(start[0], start[1], target[0], target[1]);
                Console.WriteLine(result);
            }
        }

        public static int bfs(int startX, int startY, int targetX, int targetY)
        {
            Queue<(int, int)> queue = new Queue<(int, int)>();
            queue.Enqueue((startX, startY));
            chessBoard[startX, startY] = 1;

            while (queue.Count > 0)
            {
                (int x, int y) = queue.Dequeue();

                if (x == targetX && y == targetY)
                    return chessBoard[x, y] - 1;

                for (int k = 0; k < 8; k++)
                {
                    int nx = x + dx[k];
                    int ny = y + dy[k];

                    if (nx >= 0 && nx < size && ny >= 0 && ny < size && chessBoard[nx, ny] == 0)
                    {
                        queue.Enqueue((nx, ny));
                        chessBoard[nx, ny] = chessBoard[x, y] + 1;
                    }
                }
            }

            return -1; 
        }
    }
}

• 후기

공학수학으로 선형방정식의 행렬계산법을 배웠는데 이게 이렇게 쓰일 줄 몰랐다.