2024/01/15

안석환·2024년 1월 15일

오늘 배운 코드

🧐기본 공부 내용

Linq.OrderBy(s => s).ToArray

링큐를 통해 배열을 조건을 통해 정렬하기

💾 코드

using System;
using System.Linq;

public class Solution {
    public string[] solution(string[] strings, int n) {
        string[] answer = strings.OrderBy(s => s[n]).ThenBy(s => s).ToArray();
        //answer은 (=) strings배열을 정렬(문자열을 문자열의 [n] 번째 char 의 사전순으로)하여. 
        return answer;
    }
}

📖 참고

참고할 코드 내용

깊이 우선 탐색 (Depth-First Search, DFS)

DFS는 트리나 그래프를 탐색하는 알고리즘 중 하나로, 루트에서 시작하여 가능한 한 깊이 들어가서 노드를 탐색하고, 더 이상 방문할 노드가 없으면 이전 노드로 돌아가는 방식입니다.
시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)

너비 우선 탐색 (Breadth-First Search, BFS)

BFS는 트리나 그래프를 탐색하는 알고리즘 중 하나로, 루트에서 시작하여 가까운 노드부터 방문하고, 그 다음 레벨의 노드를 방문하는 방식입니다.
시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)

💾 코드

using System;
using System.Collections.Generic;

public class Graph
{
    private int V; // 그래프의 정점 개수
    private List<int>[] adj; // 인접 리스트

    public Graph(int v)
    {
        V = v;
        adj = new List<int>[V];
        for (int i = 0; i < V; i++)
        {
            adj[i] = new List<int>();
        }
        //초기값
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w)
        //List adj의 v번째에 w를 추가한다;
    }

    public void DFS(int v)
    {
        bool[] visited = new bool[V];
        //방문 했는지에 대한 참, 거짓 값 지정
        DFSUtil(v, visited);
        //첫번 째 값과(,) 불값을 DFSUtil에 매개변수로 참조시켜 실행한다
    }

    private void DFSUtil(int v, bool[] visited)
    {
        visited[v] = true;
        //첫번 째 값을 방문했다
        Console.Write($"{v} ");
        //어떤 칸인지 보여준다

        foreach (int n in adj[v])
        //adj의 첫번째 값과 연결된 숫자에 반복한다
        {
            if (!visited[n])
            //값이 방문 하지 않았을 경우
            {
                DFSUtil(n, visited);
                //해당 값읋 넣고 반복한다
            }
        }
    }

    public void BFS(int v)
    {
        bool[] visited = new bool[V];
        //방문했는지에 대한 참, 거짓 값 생성
        Queue<int> queue = new Queue<int>();
        //선입 선출 구조 생성

        visited[v] = true;
        //기본값은 방문 했다로 변경
        queue.Enqueue(v);
        //해당값 선입 선출에 저장

        while (queue.Count > 0)
        //큐에 아무것도 없을 때 까지 반복
        {
            int n = queue.Dequeue();
            //정수 n은(=) 큐에서 빼낸 값이다
            Console.Write($"{n} ");
            //해당 내용 출력

            foreach (int m in adj[n])
            //큐에서 빼낸 값 안에 있는 포함되어 있는 것에
            {
                if (!visited[m])
                //방문 하지 않았다면
                {
                    visited[m] = true;
                    //해당 값을 방문했다로 바꾸고
                    queue.Enqueue(m);
                    //해당 값을 큐에 넣는다
                }
            }
        }
    }
}

public class Program
{
    public static void Main()
    {
        Graph graph = new Graph(6);

        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(2, 3);
        graph.AddEdge(2, 4);
        graph.AddEdge(3, 4);
        graph.AddEdge(3, 5);
        graph.AddEdge(4, 5);

        Console.WriteLine("DFS traversal:");
        graph.DFS(0);
        Console.WriteLine();

        Console.WriteLine("BFS traversal:");
        graph.BFS(0);
        Console.WriteLine();
    }
}

Stack.Peek()

스택의 제일 마지막에 있는것을 참조한다

💾 코드

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int[] heights = { 2, 1, 5, 6, 2, 3 };
        int result = LargestRectangleArea(heights);

        Console.WriteLine($"Largest Rectangle Area: {result}");
    }

    // 히스토그램에서 가장 큰 직사각형의 면적을 계산하는 함수
    static int LargestRectangleArea(int[] heights)
    {
        // 스택을 사용하여 히스토그램을 탐색하면서 가장 큰 직사각형의 면적을 계산
        Stack<int> stack = new Stack<int>();
        int maxArea = 0;

        for (int i = 0; i < heights.Length; i++)
        {
            // 현재 높이가 스택의 맨 위에 있는 높이보다 작을 때
            while (stack.Count > 0 && heights[i] < heights[stack.Peek()])
            {
                // 스택의 맨 위에 있는 높이를 꺼내어 계산
                int height = heights[stack.Pop()];
                // 직사각형의 너비 계산
                int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
                // 최대 면적 업데이트
                maxArea = Math.Max(maxArea, height * width);
            }

            // 현재 인덱스를 스택에 추가
            stack.Push(i);
        }

        // 스택에 남아 있는 인덱스들에 대한 처리
        while (stack.Count > 0)
        {
            // 스택의 맨 위에 있는 높이를 꺼내어 계산
            int height = heights[stack.Pop()];
            // 직사각형의 너비 계산
            int width = stack.Count == 0 ? heights.Length : heights.Length - stack.Peek() - 1;
            // 최대 면적 업데이트
            maxArea = Math.Max(maxArea, height * width);
        }

        // 최종적으로 계산된 가장 큰 직사각형의 면적 반환
        return maxArea;
    }
}