[25.03.31] TIL(코테 - 완전탐색/DP, CS)

설민우·2025년 3월 31일

내일배움캠프 - Unity

목록 보기
11/85

< 프로그래머스 LV2 전력망을 둘로 나누기 >

키워드 : 완전탐색, BFS

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public int solution(int n, int[,] wires)
    {
        int answer = int.MaxValue;


        // 트리 생성
        Dictionary<int, HashSet<int>> dict = new Dictionary<int, HashSet<int>>();
        for (int i = 1; i <= n; i++)
        {
            dict.Add(i, new HashSet<int>());
        }

        // 노드 연결
        for (int i = 0; i < wires.GetLength(0); i++)
        {
            dict[wires[i, 0]].Add(wires[i, 1]);
            dict[wires[i, 1]].Add(wires[i, 0]);
        }

        for (int i = 0; i < wires.GetLength(0); i++)
        {
            // 끊고
            dict[wires[i, 0]].Remove(wires[i, 1]);
            dict[wires[i, 1]].Remove(wires[i, 0]);

            // 탐색하고
            var queue = new Queue<int>();
            bool[] visit = new bool[n + 1];
            queue.Enqueue(1);
            int count = 0;
            while (queue.Count > 0)
            {
                var now = queue.Dequeue();
                visit[now] = true;
                ++count;
                foreach (var value in dict[now])
                {
                    if (visit[value] == false)
                    {
                        queue.Enqueue(value);
                    }
                }
            }
            int checkAbs = Math.Abs((n - count) - count);
            if (answer > (checkAbs))
            {
                answer = checkAbs;
            }

            // 재연결
            dict[wires[i, 0]].Add(wires[i, 1]);
            dict[wires[i, 1]].Add(wires[i, 0]);

            //절대값 확인 후 갱신
        }

        return answer;
    }
}

처음에는 어떻게 최적화를 시켜 주어야 할까에 대해서 고민을 많이 했으나

위와 같은 제한 사항 특성상 완전 탐색으로도 문제를 풀이 할 수 있다는 것을 확인했습니다.
따라서, 아래와 같은 방식으로 문제를 풀었습니다.

  • Dictionary 형태로 트리 구조 생성
  • wires의 배열에서 순서대로 간선 제거
  • BFS 로 연결된 노드의 갯수 확인 및 해답 최적화
  • 간선 재연결 후 다음 배열 확인

이렇게 완전 탐색으로 문제를 풀때는 시간 복잡도에 대해서 확인해 보면 좋습니다. 이때 알아둬야 할 것이 Big_O 표기법 입니다

( BIG - O 표기법 )

BIG-O 표기법은 알고리즘으 ㅣ시간복잡도를 나타내는 방법으로, 입력 크기 n에 따라 실행 시간이 어떻게 증가하는지를 표현합니다.

주요 시간 복잡도 종류

표기의미예시
O(1)상수 시간배열에서 인덱스로 접근 arr[i]
O(log n)로그 시간이진 탐색(Binary Search)
O(n)선형 시간배열 순회(단순 반복문)
O(n log n)로그 선형 시간퀵 정렬, 병합 정렬
O(n²)이차 시간중첩 반복문(버블 정렬)
O(2ⁿ)지수 시간피보나치 재귀(비효율적)
O(n!)팩토리얼 시간브루트포스 순열 생성

핵심 정리

  • 가장 빨리 증가하는 항만 남기고, 상수는 무시한다.
    예: 3𝑛2+5𝑛+7⇒𝑂(𝑛2)3n 2+5n+7⇒O(n2)
  • 입력 크기 n이 커질수록 성능 차이가 극명해진다.
  • 최악의 경우(Worst Case)를 기준으로 측정하는 것이 일반적이다.

< 프로그래머스 LV3 - 연속 펄스 부분 수열의 합 >

키워드 : DP, 카데인 알고리즘

이 문제는 혼자서는 풀이 할 수 없어 결국 외부에서 해답을 찾아보았습니다.

문제의 제한 조건을 보고, 완전 탐색으로는 해당 문제를 풀 수 없다는 것을 알 수 있었습니다. 특정 배열에서의 합을 구해야 한다는 점에서 "누적합" 을 먼저 떠올렸으나, 곱해지는 값이 펄스로 구성 되어 있어 단순하게 풀어지지 않았습니다.

때문에, 이를 최적화 하며 풀어주기 위해서 DP(동적 프로그래밍)이 필요했습니다.

풀이 1번 : DP 이용

using System;

public class Solution
{
    public long solution(int[] sequence)
    {
        int n = sequence.Length;
        long[,] dp = new long[n, 2];
        long max = 0;

        // i, k => 0 = 양수 펄스, 1 = 음수 펄스 (i번째 원소)
        dp[0, 0] = sequence[0];
        dp[0, 1] = -1 * sequence[0];
        max = Math.Max(dp[0, 0], dp[0, 1]);

        for (int i = 1; i < n; i++)
        {
            dp[i, 0] = Math.Max(sequence[i], dp[i - 1, 1] + sequence[i]);
            dp[i, 1] = Math.Max(-1 * sequence[i], dp[i - 1, 0] - sequence[i]);
            max = Math.Max(dp[i, 0], max);
            max = Math.Max(dp[i, 1], max);
        }

        return max;
    }
}
  • 먼저 dp는 int[,] 배열을 사용하는데, 두번째 배열의 0은 양의 펄스를, 1은 음의 펄스를 넣는 dp 입니다.
  • 최초의 초기화를 진행한 이후에는 for문을 돌면서 dp와 max를 갱신합니다.
  • 이때의 갱신시, dp[i,0]은, 새로 들어온 sequnce와, 이전 dp[i-1,1]과 현재의 값을 더한 것을 체크합니다.
  • 중요한 점은 펄스 입력이 들어오기 때문에 dp의[?,0] 은 dp[?,1] 과 관련되어 비교를 진행해 주어야 합니다.

풀이 2번 : 카데인 알고리즘 사용

using System;

public class Solution
{
    public long solution(int[] sequence)
    {
        long oddnowMax = 0;
        long oddMax = long.MinValue;
        for(int i =0; i < sequence.Length; i++)
        {
            int oddSeq = (i % 2 == 0 ? -1 : 1) * sequence[i];
            oddnowMax = Math.Max(oddSeq, oddSeq + oddnowMax);
            oddMax = Math.Max(oddMax, oddnowMax);
        }
        long evennowMax = 0;
        long evenMax = long.MinValue;
        for (int i = 0; i < sequence.Length; i++)
        {
            int evenSeq = (i % 2 == 0 ? 1 : -1) * sequence[i];
            evennowMax = Math.Max(evenSeq, evenSeq + evennowMax);
            evenMax = Math.Max(evenMax, evennowMax);
        }

        return Math.Max(evenMax, oddMax);
    }
}
  • 카데인 알고리즘은 연속된 부분수열의 최대합을 빠르게 찾는 알고리즘으로 이 또한 DP 를 이용합니다.
  • 핵심 개념 : 현재까지의 부분합을 유지하면서 최댓값 갱신
  • 아래와 같은 방식으로 동작합니다
public int Kadane(int[] arr)
{
    int currentMax = arr[0]; // 현재까지의 최대 부분합
    int globalMax = arr[0];  // 전체 배열에서의 최대값

    for (int i = 1; i < arr.Length; i++)
    {
        currentMax = Math.Max(arr[i], currentMax + arr[i]);
        globalMax = Math.Max(globalMax, currentMax);
    }

    return globalMax;
}

현재 최대와 전체 최대를 갱신하는 방식입니다.

( 정리 )

두 풀이 모두 DP 를 이용하지만 첫번 째 풀이는 dp 배열로 인한 메모리 사용이 추가적으로 필요하지만 시간 복잡도에서 앞서고, 카데인 알고리즘은 직관적이지만 중복 계산이 발생합니다.

결국 동적 프로그래밍으로 풀어야 하는 문제였는데, 아직까지도 가장 어려운 카테고리인 만큼 더 많은 공부와 예제 풀이가 필요해 보입니다.

< CS 공부 >

( GC - 가비지 컬렉터 )

가비지 컬렉터란 더이상 사용하지 않는 객체를 자동으로 식별하고 해제하는 메커니즘. C#에서의 가비지 컬렉터는 .NET 네트워크의 일부로 Heap 영역에서 동작합니다.

( 1. 동작 원리 )

C# 의 가비지 컬렉터는 Mark and Sweep 알고리즘을 사용하는 세대별 가비지 컬렉터 입니다. 이는 다음과 같은 단계로 이루어집니다.

    1. 마킹 : GC는 루트 오브젝트 부터 시작하여 모든 접근 가능한 객체들을 마킹합니다. 루트 오브젝트는 스택 변수, 정적 변수등을 포함합니다. 이때 83KB 보다 크면 LOH 작으면 SOH에 저장합니다.
    1. 스위핑 : 마킹 되지 않은 객체들을 힙에서 제거하여 메모리를 회수합니다.
    1. 컵펙션 : 남아있는 객체들을 힙의 시작부분으로 이동시켜 메모리 단편화를 줄입니다.

또한 세대별 가비지 컬렉션의 세부적인 내용은 아래와 같습니다.

( 2. 가비지 컬렉션은 언제 작동하는가 )

    1. 할당된 메모리보다 메모리를 더 쓸때, 메모리 부족을 방지하기 위해 동작
    1. 일시 중지 또는 게임 상태 전환. 유니티 게임에서 해당 상황에서 실행되어 사용되지 않는 객체를 정리한다.
    1. 각제 호출, 이는 성능 소모를 불러오기 때문에 자주 사용하지 않는것이 좋다

( 3. 세대별 가비지 컬렉션 )

각 세대애 대한 설명은 아래와 같습니다.

  • 0세대 : gc를 한번도 겪지 않는 객체
  • 1세대 : gc를 한번 겪은 객체
  • 2세대 : gc를 2회 이상 겪은 객체

단, 이때 gc는 이전 세대까지 모두 부르기 때문에, 2세대 에서의 GC는 사실상 전체를 의미합니다.

이 세대를 나누는 근거는 아래와 같습니다.

  • 최근에 생성된 객체일수록 생명주기가 짧을 가능성이 높고, 오래된 객체일수록 생명 주기가 길 가능성이 높다.
  • 최근에 생성된 객체들 끼리는 서로 연관성이 높을 가능성이 높고, 비슷한 시점에서 자주 액세스 된다.
  • 일부분 Heap에 대해서 GC를 하는 것이 전체 대상 보다 빠르다.

< 추가 설명 >

  • 메모리 할당 단계에서 SOH 에 할당된 메모리는 0세대, LOH 에 할당된 메모리는 2세대로 정ㅎ나다.
  • 가비지 컬렉터가 동작하면 0세대 부터 동작하고, 0세대에서 살아남은 메모리는 1세대, 1세대에서 살아남은 메모리는 2세대로 옮겨진다.
  • 0세대 -> 2세대로 동작하되, 아래 세대에서 메모리 공간이 여류오뤄지면 위 세대로 넘어가지 않고 종료 한다.
  • 2세대 가비지 컬렉션을 동작한 후에는 메모리 재배치를 하지 않는데, 이는 너무 큰 녀석들은 재배치하는것이 비효율 적일 수 있기 떄문이다.

( 4. GC의 장단점 )

장점

  • 자동 메모리 관리 : GC는 자동으로 메모를 해제하기 때문에 안정적인 시스템을 개발하는데 도움을 줍니다
  • 메모리 누수 방지 : 개발자가 메모리를 명시적으로 해제 하지 않아도 되기 떄문에 누수가 발생할 가능성이 적습니다
  • 안전성 향상 : 객체가 더이상 참조되지 않을때 삭제하므로, 잘못된 접근을 방지할 수 있습니다.
  • 메모리 단편화 감소 : 힙 메모리를 재배치 하기 떄문에 단편화를 줄입니다.

단점

  • 성능 오버헤드 : GC는 주기적으로 실행되는데, 이때 앱이 일시적으로 중단될 수 있습니다.
  • 예측 불가능한 중단 : GC의 발생 시점을 예측 할 수 없습니다.
  • 메모리 사용량 증가 : GC를 위해서는 추가적인 메모리가 필요합니다.

( 5. GC를 줄이기 위한 방법 )

  • 객체 재사용 : 오브젝트 풀링등을 이용해 빈번하게 생성되고 파괴되는 객체를 줄인다.
  • 구조체 사용 : 값 타입 Struct를 이용해서 힙 할당값을 줄인다.
  • 큰 객체 관리 : 큰 객체는 LOH에 할당되므로 이를 최소화 하고 가능하다면 분할해서 사용합니다.

( 6. 유니티의 가비지 컬렉션 )

  • 유니티 에서는 Boehm–Demers–Weiser 가비지 컬렉터를 사용합니다. 이 또한 마크 스윕 방식을 사용하는 것은 똑같으나 세대를 구분하지는 않습니다.
  • 이는 비 세대적 가비지 컬렉터로 모든 객체를 동일하게 취급 하고, 세대별로 관리하지 않습니다. 세대별 가비지 컬렉션과 달리 오버헤드가 적고 성능을 안정적으로 유지할 수 있기 때문입니다.
  • 또한 유니티 에서는 점진적 GC 옵션을 도입하여 여러 프레임에 걸쳐 GC를 분산시켜 프레임 드랍을 줄이는 개선도 이루어지고 있습니다.
profile
설민우
클라이언트 개발자를 지망하고 있습니다.
이전 포스트

[25.03.28] TIL(코테 - Stack, 투포인터 , CS)

다음 포스트

[25.04.01] TIL(오브젝트 풀링)

0개의 댓글