IT's me

BFS 알고리즘 문제 : 탈출(백준)

정답률 25%의 살짝 난이도가 있는 문제입니다.

처음 문제를 읽고 정답률에 비해 쉬울 것 같다는 생각이 들기도 했습니다.

어딘가 함정이 있겠지 생각하고 조심스레 풀어보았는데

BFS 알고리즘 문제를 상당히 오랜만에 풀어보아서인지

기본적인 개념에서 문제가 생겨 상당히 고전했습니다.

문제 자체를 그리 어려운 문제가 아닌 듯 합니다.

필자는 고슴도치와 물을 두 개의 큐로 따로 담는 방법으로 풀어보았습니다.

BFS 알고리즘 문제 : 탈출(백준)

01. 변수 선언

02. 인큐, 디큐

03. 초기화

04. 체크 함수

고슴도치든 물이든 바위는 피하고 이미 지나온 포인트는 다시 가지 않으며

배열의 범위를 벗어나지 않아야 한다는 공통점을 가지고 있습니다.

체크된 곳은 물, 바위, 이미 지나온 곳이라는 것을 의미하기도 합니다.

05. BFS

문제를 풀다가 이 부분에서 실수를 하여 상당히 고전했습니다.

실수 내용은 현재 water 큐에 있는 모든 물들을 상하좌우 이동시킨 뒤

Player 큐로 넘어갔어야 했는데, water 큐에 있는 단 하나의 물에 대해

이동처리를 한 뒤 Player 큐로 넘어가버린 것입니다.

한 마디로 BFS에 대한 개념이 흔들린 것.

05. 메인

상당히 오랜만에 풀어보아서 그런지 조금 고전 했던것 같습니다.

감을 잃지 않게 꾸준히 풀어야 할 것 같습니다.

[C#] 세대별 가비지 컬렉션 알고리즘

얼마 전 포스팅에서 가비지 컬렉션의 동작원리에 대해 알아보았습니다.

그렇다면 오늘은 가비지 컬렉션의 성능을 높이기 위한

세대별 가비지 컬렉션 알고리즘에 대해 알아보도록 하겠습니다.

가비지 컬렉션에 대해 공부를 하는 이유는 유니티에서 게임오브젝트를

동적 생성/삭제 하는 과정에서 가비지 컬렉터의 활동 빈도를 높이게 된다고 합니다. 

가비지 컬렉터의 비용은 공짜가 아니기 때문에 이 또한 신중하게 관리되어야 할 메모리입니다.

때문에 메모리 풀을 이용하여 필요한 오브젝트를 미리 생성해놓고 사용하게 되는데

이 또한 가비지 컬렉터의 원리를 제대로 이해해야만 최대 효율로 이용할 수 있겠다는 생각이 들어서 입니다.

세대별 가비지 컬렉션 알고리즘

들어가기전에 이 알고리즘의 핵심만 간단하게 짚어보자면

오래 살아남을 것 같은 객체를 모아놓고 비교적 관심을 덜 주자는 것입니다.

그렇게 된다면 모든 객체에 관심을 주는 것보다 효율적인 관리방식이 될 수 있겠지요.

그렇다면 객체의 수명을 어떻게 예측해야 할까요?

01.   새로 할당된 객체들 모두 0세대에 포함됩니다.

0세대가 임계치에 도달하게되면 가비지 컬렉터는 0세대에 대해 가비지 컬렉션을 수행하게 됩니다.

02.   가비지 컬렉션 수행 후 살아남은 객체들을 1세대로 옮겨지게 됩니다.

03.   이후 또다른 객체가 할당되어 들어온다면 그 객체들은 당연히 0세대에 포함됩니다.

0세대가 또 다시 임계치에 도달하게 되면 가비지 컬렉터는 0세대에 대해 가비지 컬렉션을 수행합니다.

04.   이번에는 1세대가 임계치에 도달하게 되었습니다.

마찬가지로 가비지 컬렉션을 수행합니다.

05.   1세대의 가비지 컬렉션에서 살아남은 객체는 2세대로 옮겨지게 됩니다.

객체의 수명은 이런식으로 가비지 컬렉터에서 오래 살아남았다는 기준으로 정해지게 됩니다.

06.   이러한 방식으로 0세대, 1세대, 2세대를 구분하여 각각의 임계치에 도달하면 해당 세대에 대해 가비지 컬렉션을 수행하게 됩니다.

-->  0세대가 포화된다면 오로지 0세대만 가비지 컬렉션을 수행 한 후 1세대로 이동

1세대가 포화된다면 0세대와 1세대만 가비지 컬렉션을 수행 한 수 각각 1세대, 2세대로 이동

2세대 또한 똑같은 메커니즘으로 가비지 컬렉션을 수행할까요?

-->  2세대가 포화되게 된다면 더 이상 다른 곳으로 옮겨지지 않기 때문에, 전체 가비지 컬렉션을 수행하게 됩니다.

위의 세대별 가비지 컬렉션 알고리즘으로 인해 생성과 삭제가 빈번한 객체에 대해서만

가비지 컬렉터가 신경을 쓸 수있게 하는 메커니즘이 완성되었습니다.

하지만 2세대가 포화되게 된다면 전체 가비지 컬렉션이 수행된다는 항목에 주의를 기울여야 합니다.

전체 가비지 컬렉션이 수행되면 CLR은 앱의 실행을 잠시 멈추고 전체 가비지 컬렉션을 수행함으로써

여유 메모리를 확보하려 듭니다. 앱이 차지하고 있던 메모리가 크면 클수록 전체 가비지 컬렉션의

시간이 길어지므로 앱이 정지하는 시간도 그만큼 늘어나겠지요.

이것이 바로 우리가 가비지 컬렉션을 이해해야하는 중요한 이유입니다.

다이나믹(동적 계획법) 알고리즘 문제 : 이동하기 (백준)

다른 알고리즘에 비해 동적 계획법이 상당히 어렵게 느껴집니다.

그만큼 공부량이 적었다는 반증이기도 하지만, 알고리즘 자체가 어려운 것도 사실입니다.

때문에 항상 다이나믹 알고리즘은 쉬운 문제를 골라서 풀어보았는데

이번에도 그리 난이도가 높은 문제는 아닙니다. 

동적 계획법의 기초중의 기초라 말할 수 있는 문제입니다.

동적 계획법 문제 : 이동하기 (백준)

01. 변수 선언 및 초기화

02. 다이나믹

다이나믹 (동적 계획법) 알고리즘의 핵심은

1. 처음부터 차곡차곡 답을 쌓아 나간다.

2. 저장한 답을 바탕으로 현재의 답을 찾아 나간다.

위의 두가지 핵심을 잘 기억하고 있다면 이 문제는 상당히 쉽게 풀릴 것입니다.

--> 현재의 위치에서 바로 전에 들릴 수 있는 3개의 지점에서의 최대값을 비교합니다.

--> 바로 전에 들릴 수 있는 3개의 지점은 지금까지의 최대값을 저장해왔기 때문에 비교만 해준다면 답을 구할 수 있습니다.

--> 이동 방향은 오른쪽, 밑, 대각 이 세가지 뿐이기 때문에 바로 전에 거쳐온 지점은 현재 지점에서 왼쪽, 위쪽, 10시방향 대각선 위가 될 수 있겠네요.

다른 알고리즘 문제와는 다르게 동적 계획법은 꾸준히 풀지않으면 감이 떨어지는 듯한 느낌이 듭니다.

앞서 말씀드렸듯이 그만큼 동적 계획법의 공부량이 비교적 적었기 때문이기도 하겠지요.

좀 더 분발해야 할 것 같습니다.