용용코딩

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

• 문제

• 문제풀이

백트래킹 문제이다. 깊이 탐색을 활용해서 풀어준다.

• 코드 1

using System.ComponentModel.Design;
using System.Text;

namespace ConsoleApp2
{
    internal class Program
    {
        static public StringBuilder sb = new StringBuilder();
        static public bool[] visited;
        static public int[] result;
        static void Main(string[] args)
        {
            
            
            string[] input = Console.ReadLine().Split();
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);
            result= new int[N];
            visited= new bool[N];
            
            
            dfs(N, M, 0, 1);
            Console.WriteLine(sb.ToString());
        }
        static void dfs(int N, int M, int cnt, int num)
        {
            if (cnt == M)
            {
                for(int i=0;i<M;i++)
                {
                    sb.Append(result[i]+" ");
                }
                sb.AppendLine();
                return;
            }
            for(int i=num;i<=N;i++)
            {
                //if (!visited[i])
                //{
                    //visited[i]=true;
                    result[cnt] = i;
                    dfs(N, M, cnt+1, i+1);
                    //visited[i] = false;
                //}
            }
        }
    }
}

• 후기

DFS를 활용한 백트래킹 문제이다.

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

• 문제

• 문제풀이

백트래킹 문제이다. 깊이 탐색을 활용해서 풀어준다.

• 코드 1

using System.ComponentModel.Design;
using System.Text;

namespace ConsoleApp2
{
    internal class Program
    {
        static public StringBuilder sb = new StringBuilder();
        static public bool[] visited;
        static public int[] result;
        static void Main(string[] args)
        {
            
            
            string[] input = Console.ReadLine().Split();
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);
            result= new int[N];
            visited= new bool[N];
            
            
            dfs(N, M, 0);
            Console.WriteLine(sb.ToString());
        }
        static void dfs(int N, int M, int cnt)
        {
            if (cnt == M)
            {
                for(int i=0;i<M;i++)
                {
                    sb.Append(result[i]+" ");
                }
                sb.AppendLine();
                
            }
            for(int i=0;i<N;i++)
            {
                if (!visited[i])
                {
                    visited[i]=true;
                    result[cnt] = i + 1;
                    dfs(N, M, cnt+1);
                    visited[i] = false;
                }
            }
        }
    }
}

• 후기

DFS를 활용한 백트래킹 문제이다.

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

• 문제

• 문제풀이

-앞을 잘라서 뒤의 수를 크게 만들어 준다.

• 코드 1

using System.Diagnostics.Tracing;
using System.Text;
using System.Text.RegularExpressions;

namespace ConsoleApp1
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string sentence = Console.ReadLine();
            string[] cal = sentence.Split('-');//'-'기준으로 자름
            int sum = 0;
            foreach(string item in cal[0].Split('+'))//-기준 앞부분을 +로 잘라서 더함
            {
                sum += int.Parse(item);
            }
            if (cal.Length == 0)//-가 안나온 경우고
            {
                Console.WriteLine(0);
            }
            else
            {
                for(int i=1;i<cal.Length;i++)
                {
                    string[] cal2 = cal[i].Split('+');
                    foreach(string item in cal2)
                    {
                        sum-=int.Parse(item);
                    }
                }
            }
            Console.WriteLine(sum);
        }
    }
}

• 후기

생각보다 많은 문제가 그리디 알고리즘이다.

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

• 문제

• 문제풀이

큰 단위로 뒤집어서 큰것부터 빼주었다.

• 코드 1

using System.Text;

namespace ConsoleApp1
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();
            int N = int.Parse(input[0]);
            int K = int.Parse(input[1]);
            int count = 0;
            int coincnt = 0;
            int[] arr=new int[N];
            for(int i = 0; i < N; i++)
            {
                arr[i] = int.Parse(Console.ReadLine());
            }
            Array.Reverse(arr);
            for(int i=0;i<N;i++)
            {
                if (K / arr[i] >= 1&&K!=0)
                {
                    coincnt= K / arr[i];
                  
                    count += coincnt;
                    K = K % arr[i];
                }
                else if (K == 0)
                {
                    break;
                }
            }
            Console.WriteLine(count);
        }
    }
}

• 후기

동전문제는 이제 그리디로 쉽게 하는 것 같다.

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

• 문제

• 문제풀이

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp4
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] road_data = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            long[] cost_data = Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
            
            long cost = 0;
            long minprice=cost_data[0];
            for(int i = 0; i < N - 1; i++)
            {
                if(cost_data[i] < minprice)
                {
                    minprice = road_data[i];
                }
                cost+=minprice*road_data[i];
            }
            Console.WriteLine(cost);
        }
    }
}

첫 번째 주유소부터 시작하여, 현재까지 최소 가격을 계속 갱신하며 각 도시까지 이동하는 데 필요한 비용을 계산하고
현재 도시에서 주유할 때 가격이 현재까지 최소 가격보다 작다면, 그 가격으로 최소 가격을 바꿔서 계산된 비용을 cost에 누적한뒤 출력했다.

그리고 17점이 나왔다.

• 코드 1

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp4
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] road_data = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            long[] cost_data = Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
            
            long cost = 0;
            long minprice=cost_data[0];
            for(int i = 0; i < N - 1; i++)
            {
                if(cost_data[i] < minprice)
                {
                    minprice = cost_data[i];
                }
                cost+=minprice*road_data[i];
            }
            Console.WriteLine(cost);
        }
    }
}

road_data가 아닌 cost_data로 바꾸고 100점을 받았다.

• 후기

헷갈린다..

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

• 문제

• 문제풀이

입력받은 시간값을 정렬하고 시간값을 누적하여 합한 후 출력한다.

• 코드 1

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp4
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int sum = 0;
            string[] input=Console.ReadLine().Split();
            
            int[] arr=new int[N];
            for(int i=0; i < N; i++)
            {
                int time=int.Parse(input[i]);
                arr[i]=time;
            }
            Array.Sort(arr);
            for(int j=1; j < N; j++)
            {
                arr[j]=arr[j-1]+arr[j];
                sum+=arr[j];
            }
            Console.WriteLine(sum+arr[0]);
        }
    }
}

• 후기

그리디 알고리즘을 활용해 컴퓨터에게 노가다를 시킨다.

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

• 문제

• 문제풀이

입력받은 활동들을 종료시간을 기준으로 오름차순으로 정렬한다. 반복문을 사용하여 정렬된 리스트를 순회하며, 각 활동의 시작 시간과 현재까지 선택된 활동들 중 마지막으로 종료된 활동의 종료 시간을 비교한다. 만약 시작 시간이 현재까지 선택된 활동들 중 마지막으로 종료된 활동의 종료 시간보다 크거나 같다면, 해당 활동을 선택하고 count를 증가시키며, time 변수를 해당 활동의 종료 시간으로 업데이트한다.

• 코드 1

using System.Text;

namespace ConsoleApp1
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StringBuilder stringBuilder= new StringBuilder();
            int N = int.Parse(Console.ReadLine());

            List<(int,int)> list=new List<(int,int)>();
 
            for(int i=0; i<N; i++)
            {
                string[] zoom = Console.ReadLine().Split();
                int a = int.Parse(zoom[0]);
                int b = int.Parse(zoom[1]);
                list.Add((a,b));
            }
            list = list.OrderBy(b => b.Item2).ThenBy(b => b.Item1).ToList();
            int count = 0;
            int time = 0;
            for (int i = 0; i < N; i++)
            {
                if (time <= list[i].Item1)
                {
                    count++;
                    time = list[i].Item2;
                }
            }
            Console.WriteLine(count);
        }
    }
}

• 후기

그리디 알고리즘을 활용해 컴퓨터에게 노가다를 시킨다.

빅오 표기법(Big-O notation)은 알고리즘의 시간 복잡도(Time Complexity)를 표현하는 데 사용되는 수학적인 표기법입니다. 알고리즘의 시간 복잡도란 입력 데이터의 크기에 따라 알고리즘이 소요하는 시간의 증가율을 의미합니다. 빅오 표기법은 이러한 시간 복잡도를 수학적으로 표현함으로써 알고리즘의 성능을 쉽게 비교하고 분석할 수 있습니다.

빅오 표기법의 표기 방법

빅오 표기법은 O(입력 데이터의 크기에 따른 알고리즘의 시간 복잡도)의 형태로 표기합니다. 예를 들어, 입력 데이터의 크기가 n일 때 알고리즘의 시간 복잡도가 O(n)이라면, 입력 데이터의 크기에 비례하여 알고리즘이 수행하는 시간이 증가한다는 것을 의미합니다. 다른 예로, O(n^2)는 입력 데이터의 크기의 제곱에 비례하여 알고리즘이 수행하는 시간이 증가한다는 것을 의미합니다.

빅오 표기법의 예시

빅오 표기법을 사용하여 다양한 알고리즘의 시간 복잡도를 분석할 수 있습니다. 아래는 몇 가지 대표적인 예시입니다.

O(1)

O(1)은 입력 데이터의 크기와 무관하게 항상 일정한 시간이 소요되는 알고리즘입니다. 예를 들어, 배열에서 인덱스를 이용하여 데이터에 접근하는 것은 O(1)입니다.

O(n)

O(n)은 입력 데이터의 크기에 비례하여 알고리즘이 소요되는 시간이 증가하는 알고리즘입니다. 예를 들어, 배열에서 데이터를 찾는 것은 O(n)입니다.

O(n^2)

O(n^2)는 입력 데이터의 크기의 제곱에 비례하여 알고리즘이 소요되는 시간이 증가하는 알고리즘입니다. 예를 들어, 이중 반복문을 사용하여 배열의 모든 요소를 탐색하는 것은 O(n^2)입니다.

O(log n)

O(log n)은 입력 데이터의 크기의 로그에 비례하여 알고리즘이 소요되는 시간이 증가하는 알고리즘입니다. 이진 검색 알고리즘은 O(log n)입니다.

결론

빅오 표기법은 알고리즘의 시간 복잡도를 표현하는 중요한 수학적인 표기법입니다. O(log n)는 입력 데이터의 크기가 증가해도 알고리즘의 소요 시간이 빠르게 증가하지 않는다는 특징을 가지고 있습니다. 따라서 O(log n) 알고리즘은 매우 빠르게 동작하며, 대표적으로 이진 검색 알고리즘이 있습니다.

이진 검색 알고리즘은 정렬된 배열에서 특정 값을 찾는 알고리즘으로, 입력 데이터의 크기가 n일 때 최대 n번의 비교 연산을 수행하며, 이는 O(n)의 시간 복잡도를 가집니다. 그러나 이진 검색 알고리즘은 배열을 매번 반으로 나누어 탐색을 수행하기 때문에, 입력 데이터의 크기가 증가해도 시간 복잡도가 느리게 증가합니다. 따라서 이진 검색 알고리즘의 시간 복잡도는 O(log n)입니다.

O(log n) 알고리즘은 대부분의 경우 매우 빠르게 동작하기 때문에, 데이터를 탐색하거나 정렬하는 등의 문제를 해결할 때 많이 활용됩니다. 이러한 알고리즘을 잘 이해하고 활용한다면, 효율적인 알고리즘을 설계하는 데 큰 도움이 될 것입니다.