IT's me

동적 계획법 (다이나믹) 알고리즘 기초 문제 - 포도주 시식 (백준)

오랜만에 동적 계획법 문제를 풀어보았다.

오랜만이라 그런지 또 감을 잃은 느낌이 든다..

저번에 풀어보았던 계단 오르기 문제와 비슷한 문제지만,

계단 오르기는 무조건 밟는 것이었고, 이번 문제는 포도주를 마실지 마시지 않을지

선택하는 과정이 포함되어 있기 때문에 꽤 생각을 해봐야 했던 문제였다.

동적 계획법 (다이나믹) 알고리즘 문제 - 포도주 시식 (백준)

항상 강조하지만

1. DP배열을 통해 답을 차근 차근 저장해 나갈 것!

2. 기존에 저장된 데이터를 통해 현재의 답을 찾아 나갈 것!

이 두가지만 기억한다면 동적 계획법은 끝났다고 볼 수 있다. (점화식 세우는 것이 문제이긴 하지만..)

완벽하게 이해했다 생각한 동적 계획법이었지만

오랫동안 머리를 안쓰다보니 상당히 낮설게 느껴진다.

상당히 오랫동안 고민을 했던 것 같다. 꾸준히 머리를 써줘야겠다는 생각이 든다..

BFS 알고리즘 문제 : 미로 탐색 (백준)

약 2주전 이 문제를 DFS 알고리즘으로 풀어본 적이 있다.

하지만 시간초과가 떠서 상당히 난감한 적이 있었는데

이를 BFS 알고리즘으로 풀어보니 상당히 쉽게 풀렸다.

해가 없는 경로로도 쭉쭉 들어가서 수행시간을 폭발 시키는 DFS 알고리즘의 단점을 실감할 수 있었고,

DFS 알고리즘에 비해 BFS 알고리즘은 공간 복잡도는 상당하지만 항상 최단 경로를 보장한다는 장점을 체험할 수 있었다.

미로 탐색이라는 알고리즘은 DFS, BFS 알고리즘으로 풀어봄으로써

약간씩 헷갈렸던 두 알고리즘의 장단점을 명확하게 할 수 있었다.

미로 탐색 (백준)

1. 필요한 변수 선언

2. 초기화

3. 인큐, 디큐, 비었는지 확인, 가능한 경로인지 확인

4. BFS 알고리즘

5. 메인

6. 참고

DFS 알고리즘과 BFS 알고리즘의 장단점을 잘 정리해놓은 것 같아 링크를 가져왔다.

http://blog.naver.com/jjuncoder/220797012420

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

동적 계획법에도 어느정도 익숙해져 가는 것 같다.

매번 강조하는 내용이지만 그 전에 찾아 놓은 답을 활용할 것!

그리고 그 전에 찾아 놓은 답을 저장할 DP배열을 꼭 만들 것!

이 둘만 기억한다면 동적 계획법 알고리즘은 쉽게 풀 수 있을 것이다.

늘 그렇듯 이번 문제에도 함정이 있었는데.. 나만 그렇게 생각하는 것일 수 있지만

2로 나누어 떨어지는 숫자라도 -1을 해준 뒤 계산할 경우 더 작은 숫자가 나올 수 있다는 것이다.

(3으로 나누어 떨어지는 숫자는 무조건 가장 작은 수이기 때문에 -1한 값과 비교할 필요가 없다.)

10을 예로 들어보자.

2로 나눈다면 5가될 것이고 DP[5]에는 3이 저장되어 있을 것이다.

따라서 총 연산 횟수는 4번.

하지만 -1을 해주고 시작한다면 9가되고 DP[9]에는 2가 저장되어 있을 것이다.

따라서 총 연산 횟수는 3번.

이 부분을 생각하는 데 시간이 좀 걸렸으나, 전체적으로 쉬운 동적 계획법(다이나믹) 문제이다.

01. 변수 선언 그리고 초기화

02. 동적 계획법(다이나믹) 알고리즘을 수행할 함수

03. 메인 함수

동적 계획법(다이나믹) 알고리즘의 기본 문제를 풀어 보았다.

요즘 동적 계획법 문제만 풀어보는 것 같은데 다음 포스팅에서는 DFS, BFS문제를 풀어보도록 하겠다.

DFS 알고리즘, 다이나믹(동적 계획법) 알고리즘 문제 - 점프 (백준)

DFS와 동적 계획법을 동시에 써서 풀어야 했다.

문제가 쉬워서 금방 금방 푸나 싶었는데..

정말 함정이 많은 문제였다..

첫 번째 함정.. 0이 종착점 말고도 존재할 수 있다는 것..

두 번째 함정.. 경로의 수가 겁나 크게 나올 수 있기 때문에

int로는 답을 담을 수가 없어 long long로 선언해야 한다는 것..

문제를 꼼꼼히 읽지 않아서 정말 고생할 뻔 했다..

DFS 알고리즘, 다이나믹(동적 계획법) 알고리즘 문제 - 점프 (백준)

DFS와 동적 계획법의 개념이 동시에 들어가 있다.

이번 문제는 알고리즘이 어려웠다기 보다

문제를 꼼꼼히 읽지 않아서 소요된 시간이 더 많았다.

문제를 꼼꼼히 읽는 습관을 들여야겠다.

아무튼 문제는 DFS와 동적 계획법을

연습하기에는 정말 좋은 문제인 것 같다.

DFS 알고리즘 - 점프 문제 (백준)

DFS , BFS 알고리즘 항목에 있길래

DFS 알고리즘으로 풀어 보았다..

답이 맞는지 안맞는지는 모르겠지만

일단은 예제는 맞고.. 10분 컷 했으나 시간초과..

예전에 DFS 알고리즘 문제를 풀다가

시간 초과가 계속 떠서 몇 시간을 씨름하다

나중에 검색해보니 DP 문제였던 기억이 있어서

이번에도 뭔가 느낌이 싸해서 바로 검색을 해보니

아니나 다를까 DP문제...

사실 문제를 풀 때, 쓸데없는 동작들이 있어서

(이미 DFS를 수행한 곳을 또 다시 들렸을 경우, 똑같은 작업을 반복)

사실 DP문제가 아닌가 생각도 했지만, 일단은 DFS로 풀어보았다.

DFS 알고리즘 문제 - 점프 (백준)

DFS에 DP 배열을 넣어서 풀어보면 어떻까 하고 풀었지만

DP 배열을 넣는 순간 코드가 DP로 서서히 바뀌어 나가더라..

DP로 다시 풀어서 올려야 겠다고 생각해서 일단 오답 코드를 올려본다.

음.. DFS 알고리즘으로 한번 풀어 보았으니

DP로 풀어서 다시 올리도록 하겠다.

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

이번 문제를 풀면서 느낀 점은

다이나믹(동적 계획법) 알고리즘을 풀 때에는

답을 저장하는 DP배열이 꼭 필요하다는 것이다.

답을 담을 변수를 하나만 선언해서 이리저리 굴려보다가 결국 제시간에 풀지 못했다.

동적 계획법은

첫 째, 그 전에 구해놓은 답을 사용하여 현재의 답을 찾는 것!

둘 째, 구한 답을 저장할 DP배열을 사용할 것!

셋 째, 문제를 잘 읽고 규칙을 찾아 내는 것!

지금까지 다이나믹(동적 계획법) 알고리즘을 풀면서 중요하다고 느낀 부분이다.

익숙해질 때까지 반복적으로 문제를 풀어보는 것이 중요할 듯 하다.

계단 오르기 (백준)

문제를 처음 딱 접했는 때에는

DFS 알고리즘으로도 풀 수 있겠다 생각했지만,

동적 계획법으로 푸니 정말 간단하게 답이 나왔다.

짧은 코드로 많은 것을 해내는 코드는 그 만큼 어렵다고 했다.

위의 코드는 매우 간단해보이지만, 이 문제를 DFS 알고리즘으로

푼다고 생각했을 때는, 이렇게 간단한 코드로 끝나지 않을 것이다.

(물론 DFS도 그리 긴 코드는 나오지 않을 것이다.)

다이나믹 (동적 계획법) 알고리즘 기초 문제 : 숫자 삼각형 (백준)

첫 문제를 풀고나서 푸니까 확실히 시간이 단축된다.

원리에 좀 더 익숙해진다면 점점 더 단축되리라 믿는다.

다이나믹(동적 계획법) 알고리즘 기초 : 숫자 삼각형

RGB 거리라는 비슷한 문제를 풀고

바로 풀어서 그런지 시간이 15분 밖에 안걸렸다.

RGB와 같은 원리지만 위에서 아래로 향했던 것과 달리

이 문제는 아래에서 위로 계산하며 올라가야 한다.

다시한번 말하지만 다이나믹(동적 계획법) 알고리즘의 핵심은

구해놓은 답을 활용하여 현재의 답을 차근차근 찾아 나가는 것!!

꼭 기억하고 문제를 푼다면 더욱 이해하기 쉬울 것이다.

가장 밑의 바로 위층 부터 시작해서

(가장 밑 층의 데이터를 이용하여 밑의 바로 위층을 갱신하기 때문에 여기부터 시작한다.)

최대 값만을 골라 그 위치에 더하면서 갱신한다.

그렇다면 현재층의 모든 숫자는 아래층으로부터 올라온 최대값을 골라서 더하게 되며,

결국 꼭대기에서는 가장 최대값만을 골라서 더한 값이 저장되게 된다.

다이나믹(동적 계획법) 알고리즘은 코드의 크기는

DFS, BFS보다 훨씬 간결하다. 하지만 두 알고리즘 보다

훨씬 많은 고민을 해야하는 것은 분명한 사실인듯 하다.

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

다이나믹 (동적 계획법) 알고리즘의 기초 문제를 풀어 보았다.

핵심은!! 그 전에 저장되었던 답을 끌어다가 현재의 답을 도출한다는 점!!

딱 저거 하나만 알면되는데.. 그 과정을 생각하기가 정말 쉽지 않다.

동적 계획법 기초 문제 : RGB 거리

몇줄 안되는 코드이지만 푸는 데 시간이 꽤 걸렸다..

잊지 말자!

처음 부터 차근차근 답을 구해서

구한 답을 바탕으로 계속해서 답을 찾아 나가는 것!

이번 문제는 기준을 잡는 것이 중요해 보였다.

처음에 집을 어떤 색으로 칠할 것이냐?

빨강, 초록, 파랑으로 모두 칠하면서 답을 찾아가봄

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

항상 풀 때마다 많은 고민을 하게 하는 것 같다.

꾸준히 풀어나가야 겠다는 생각이 든다.

[알고리즘 기초][구현] X보다 작은 수, 윷 놀이 (백준)

백준 사이트에서 단계별로 풀어보기를 하다가

구현이라는 단계의 몇 문제를 풀어 보았다.

알고리즘 기초 중의 기초 문제인 듯 하다.

01. X보다 작은 수

02. 윷놀이

간단 알고리즘 기초 문제를 풀어 보았다.

오랜만에 알고리즘 문제를 풀어서 쉬운 문제를 골랐는데

음.. 너무 쉬운 문제를 골랐나..?

DFS 알고리즘 백준의 미로 탐색 문제

백준 알고리즘 사이트의 미로 탐색 문제를 풀어보았다.

DFS 알고리즘, BFS 알고리즘 모두 가능 하지만

DFS 알고리즘을 이용하여 풀어 보았다.

결과는...

내가 생각하기에도 너무 쓸데없는 탐색이 많이 들어가있다.

한 지점에 들렀을 때 이 지점을 경유하면 최소값이

나올 수 없다는 것을 판단하는 부분을 넣어서 

아예 그 지점에 대한 DFS 알고리즘을 수행하지 않는

방법으로 가보는 것이 좋을 것 같다.

01. 초기화 , 체크 함수

02. DFS 알고리즘

03. 메인 함수

DFS 알고리즘은 항상 풀기는 쉬운데

시간 초과가 많이 뜨는 것 같다.

이 문제는 정답을 맞춘 후에

위의 포스팅과 비교하여 어떤 부분에서

시간초과가 났는지 분석해서 올리도록 하겠다.