IT's me

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

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

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

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

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

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

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

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

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

01. 변수 선언

02. 인큐, 디큐

03. 초기화

04. 체크 함수

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

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

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

05. BFS

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

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

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

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

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

05. 메인

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

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

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

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

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

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

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

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

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

01. 변수 선언 및 초기화

02. 다이나믹

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

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

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

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

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

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

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

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

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

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

[DFS 알고리즘] 빙산 (정올)

게임 만들랴 자소서쓰랴 정신 없는 7월이 지나가고

한 달만에 풀어보는 알고리즘..

이번에는 정답률 20%대의 DFS 알고리즘을 풀어보았습니다.

정답률이 낮은 문제의 특징은 정말 어렵거나.. 아니면 함정이 많은 문제인데

이 문제는 어려운 문제라기 보다는 함정이 많은 문제가 되겠습니다.

DFS 알고리즘 문제 - 빙산 (정올)

01. 변수 선언 및 초기화

02. 재귀 함수

03. 1년 후 빙산의 변화 예측 함수

함정 1 : 빙산의 모습을 1년 후로 바꿀 때, 녹아 없어질 빙하라도 바로 0으로 바꾸어준다면 인접한 빙하에 영향을 주게 됩니다.

그래서 저는 -9999라는 숫자로 일단 바꾸어주고, 모든 빙하를 다 둘러본 뒤 -9999의 값을 0으로 다시 바꾸어 주었습니다.

04. 메인

함정 2 : 빙하가 아예 없어질 때까지 반복문을 돌려야 합니다.

따라서 while문을 돌려주고 두 동강 났다면 답 출력하고 리턴

더 이상 체크할 빙하가 없다면 반복문 종료. 그리고 0 출력

20%대 문제 치고는 살짝 쉬운 감이 있지만, 문제를 꼼꼼히 읽지 않았다면 또 한참 헤맸을 법한 문제였습니다.

DFS 알고리즘 문제 - 안전 영역(백준)

DFS혹은 BFS의 기본 원리를 알고 있다면 쉽게 풀릴만한 문제이다.

완벽하게 풀었다 생각했지만 4번의 실패..

문제는 비가 안올 경우도 존재한다는 것이다..

백준 사이트는 문제가 많아서 좋지만.. 이런 경우 조금 짜증이 나기도한다.

어떤 부분이 틀렸는지 정올 처럼만 가르켜줘도 쓸데없는 시간이 단출될텐데 말이다..

(물론 오답을 찾는 과정이 쓸데없는 시간은 아니지만 이러한 부분은 쪼금...)

예를들어 

1 1

1 1

이 입력되었다면 모두 물에 잠겨버리기 때문에 답은 0일 것이다.

하지만 비가 오지 않는다면 1개의 지역이 남기 때문에 답은 1이 된다는 것이다.. 하...

안전 영역 - DFS 알고리즘 문제

01. 변수 선언, 초기화

02. DFS 알고리즘

03. 메인

풀 때까지만해도 기분좋게 풀었는데.. 틀린 부분을 찾다가 기분이 그닥..

문제를 몇번이나 읽어보았는데 비가 안올 경우는 정말 생각하지도 못했다..

반성하자.

다이나믹 프로그래밍 (동적 계획법) 알고리즘 문제 - 다리 놓기 (백준)

점화식을 찾는 과정이 상당히 어려웠다.

N의 수를 차례로 늘려보기도 하고, M의 수를 차례로 늘려보기도 했으나

도저히 감이 잡히지 않아 굉장히 어려운 문제였다.

하지만 다리가 크로스 될 수 없다는 조건을 떠올려서 간신히 점화식을 구할 수 있었다.

N의 가장 위에 점이 M의 가장 위의 점에다 다리를 놓게 된다면

dp[N-1][M-1]의 경우의 수를 얻을 수 있다.

거기에다 M에 하나의 점이 추가되기 전인 dp[N][M-1]의 경우의 수를 더해주면 점화식을 완성할 수 있다.

(N과 M은 1부터 차례대로 올라가면서 모든 경우의 수를 찾아 dp에 저장하였다.)

dp[N][M] = dp[N-1][M-1] + dp[N][M-1]

설명이 상당히 미흡한 부분이 많은데, 이해가 가지 않는 다면

기존에 구해 놓은 답을 통해 현재의 답을 찾는다 라는 동적 계획법의 기본 원리를 떠올려보고

몇 가지의 케이스를 노트에다 적으면서 점화식을 찾아내는 것도 좋은 방법일 것이다.

동적 계획법 문제 - 다리 놓기 (백준)

항상 느끼는 것이지만 수행 시간이 다른 사람보다 많이 나오는 것 같다.

시간 단축을 위해 dp[0][M]을 초기화하는 과정을 빼고 싶었으나 GG..

다이나믹 프로그래밍은 정말 많이 풀어봐야겠다는 생각이 든다..

다이나믹 프로그래밍(동적 계획법) 문제 - 2xn 타일링(백준)

동적 계획법의 가장 기본적인 문제가 아닌가 한다.

2xn 크기의 타일이 주어진다면 2x1, 1x2크기로 타일을 채울 수 있는 경우의 수를 모두 구하는 문제이다.

1. 2x1 크기 타일로 채우는 방법

2. 2x2(1x2 타일 두개)로 채우는 방법

위의 두가지 방법으로 분류하여 생각하면 쉽게 점화식을 찾을 수 있다.

동적 계획법의 기본 원리를 짚고 넘어가자면 차근차근 답을 찾아나가면서

그 답을 dp배열에 저장하고, 저장된 데이터를 통해 다음 답을 찾아나간다는 것이다.

n크기의 타일을 채울 수 있는 경우의 수는 

1. dp[n-1]의 경우의 수에 2x1 크기 타일을 하나씩 붙여주는 경우

2.  dp[n-2]의 경우의 수에 2x2 크기 타일을 하나씩 붙여주는 경우

dp[x]의 값에는 n이 x일 경우의 모든 경우의 수가 들어가 있다. 

따라서 dp[10]의 값을 찾는다 하면 

dp[9]에 2x1타일을 하나 붙여주는 경우 + dp[8]에 2x2타일을 하나 붙여주는 경우이다.

해당 인덱스의 dp에는 모든 경우의 수가 들어있다는 보장이 있기 떄문에

dp[n] = dp[n-1] + dp[n-2] 라는 점화식이 성립하게 된다.

다이나믹 프로그래밍 - 2xn 타일링(백준)

소스 코드

코드는 굉장히 짧지만 점화식을 생각해내는 시간이 꽤 오래 걸렸다.

BFS 알고리즘 문제 - 나이트의 이동 (백준)

전형적인 BFS문제이다. 체스판 위의 나이트를 이동시켜

목적지까지 도착하는 문제. 최단 거리를 찾아야 하기 때문에

DFS 알고리즘 보다는 BFS 알고리즘이 효율적일 것이다.

체스판의 범위에 있는지를 체크할 때 부등호 하나를 빼먹어서 틀린 이유를 찾느라 상당히 애를 먹었다.

항상 느끼는 거지만 문제를 꼼꼼히 잘 읽어야 겠다 ㅠ

나이트의 이동 (BFS 알고리즘 문졔)

시간이 12MS가 뜨는 사람은 도대체 어떻게 풀길래 그 시간이 나올 수 있는거지..

01. 변수 선언

02. BFS

03. 메인

BFS와 DFS는 어느정도 자신감이 붙었고, 이제 DP를 중심적으로 해야할 것 같다.

그리디 알고리즘도 간간히 풀어봐야겠다는 생각이 든다.

2차원 배열의 합 - 동적 계획법 문제 (백준)

이 문제를 처음 보고 이게 왜 동적 계획법인가 의아했다.

그냥 아무 생각 없이 2중 for문을 돌려서 답을 찾았다.

너무 쉬운 문제라고 생각했다. 하지만 수행시간이 상당히 맘에 걸렸다.

다른 분들은 16MS가 나오는데 836MS가 떠버린 것..

수행 시간을 위해서라도 동적 계획법으로 풀어봐야겠다는 생각이들어서

나름 DP배열을 선언하고 활용하면서 문제를 다시 풀어보았다.

2차원 배열의 합(동적 계획법)

836MS에 비하면 반으로 줄었지만 16MS에 비하면 어마어마한 수치가 떠버렸다..

어떻게 풀었을지 힌트라도 얻고 싶은데.. 코드 오픈을 아무도 해놓지 않았다 ㅠ

01. 초기화

초기화를 할 때 DP배열 또한 초기화를 해주었는데

이전의 모든 값의 합을 저장하는 것이 아니라 한 행마다 따로따로 합을 계산했다.

02. 동적 계획법(다이나믹) 알고리즘

때문에 DP배열 x행의 y열을 선택하면 그 행의 y열까지의 최대 합이 들어있다.

그 합을 모두 더한 것에서 필요 없는 부분을 빼버리면 답을 구할 수 있다.

딱 보고 문제가 너무 쉬웠기 때문에 빨리 풀고 다음 문제로 넘어가야지 했는데

수행 시간 때문에 한참을 고전했던 것 같다. 완벽하게 수행 시간을 줄이지는 못했지만

계속해서 연구해봐야 할 가치가 있는 문제라고 생각한다.

DFS 알고리즘 - 영역 구하기 (백준)

확실히 DFS가 BFS 알고리즘 보다는 손이 덜 가고 쉽게 풀리는 것 같다.

이번 문제는 입력을 받을 때, 모눈 종이 역할을 하는 2차원 배열에 색칠을 해나가면서 진행했다.

좌표를 구하는 부분에서 수학 문제를 푸는 것 같아 약간 주춤했지만 어려운 수준이 아니라 패스~

영역 구하기 문제 (DFS 알고리즘)

01. 변수 선언

02. 초기화

03. DFS 알고리즘

04. 메인

최근들어 BFS, DFS 문제를 많이 풀어보고 있는데, 확실히 동적 계획법보다는 푸는 재미가 있는 것 같다.

현재 만들고 있는 퍼즐 게임에서 유용하게 쓰일 알고리즘이라 한 동안 집중해서 공부할 예정이다.

BFS 알고리즘 문제 - 숨바꼭질 (백준)

처음에는 DFS로 풀어보았는데 시간초과를 극복 할만한 대안이 떠오르지 않았다.

문제 자체가 최단으로 도착하는 방법을 찾는 것이기 때문에 BFS가 더 적합한 것 같다.

숨바꼭질 (백준) - BFS

01. 초기화, 변수 선언 등

02. 함수들

03. BFS 알고리즘

04. 메인

이제 BFS, DFS 알고리즘을 활용하여 간단한 퍼즐 게임을 만들어 보려한다.

위의 두 알고리즘이 퍼즐게임의 핵심 알고리즘으로 활용될 수 있을 것 같아

예전부터 꾸준히 공부해왔는데, 이제 실제로 활용해 볼 때가 된 것같다.