welcome!

n 팩토리얼의 값에 5와 2가 몇 개가 들어가있는지 질의하는 문제이다. 그럼 n 팩토리얼에 5, 2가 몇 개 들어가있을 까를 알아야한다. 2를 기준으로, 24! 는 2는 모든 짝수에 들어가있다. 12개 그리고, 4, 8, 12, 16, 20, 24 에 추가적으로 2가 들어가있다. (4 = 22, 8= 222, 12 = 223, 16=224, 20 = 225, 24 = 226) 이 때, 8, 16, 24는 추가적으로 들어가있다. 문제전략은 계속 base를 나눠가면서 몇 개의 2가 남아있는지 세는 것이다. 24 / 2 = 12 (21, .... 212) 12 / 2 = 6 ( 221, .... 226) 6 / 2 = 3 ( 2221, ... 2223) 3 / 2 = 1 ( 2222*1 ) ^^.. def g..

백준 2133 타일채우기 해설 흥미로운 문제이다. 정답을 미리 알거나 스포일링 당하는건 괴롭지만, ... 생각해나갈 때는 알쏭달쏭한 즐거운 문제였을 것이다.(구현문제보단 재밌는듯) 가로 길이 2 인 것을 만드는 경우의 수는 3가지이다. ( ||_ ),( _|| ), ( _ _ _ )이다. 임의의 길이 i를 만드는 데에는 i-2 길이를 만드는 경우의 수에 3가지 경우의 수를 조합하는 것이므로, f(i) = f(i-2)*2 이다. 그리고, 길이 4 이상부터 다음과 같은 형태를 만들 수 있다. 이러한 형태는 4, 6, 8, ... i 길이 만큼 만들 수 있고, 뒤집은 형태도 있기 때문에 각 길이마다 2가지의 경우의 수가 있다. 이를 종합하면 i를 만드는 경우의 수는 다음과 같다. f(i) = f(i-2)*2 ..

백준 14494 다이나믹이 뭐에요? 해설 n*n의 2차원 공간에서 오른쪽, 아래쪽, 우아래 대각 세 방법만 이용하여 이동한다고 하자. 이때 임의의 점 (x, y)에 도달 할 수 있는 경우의 수 f(x, y)는 f(x-1,y) + f(x, y-1) + f(x-1, y-1)이다. d배열을 1칸 크게 잡는다면 특별히 배열 range-exception 처리를 할 필요 없이 온전하게 연산에만 집중할 수 있다. #include #define MOD ((int)1e9+7) using namespace std; int d[(int)1e3+1][(int)1e3+1]; int main() { int n, m; cin >> n >> m; d[0][0] = 1; for (int i=1; i

백준 2037 문자메세지 해설 ABC, DEF, GHI, JKL, MNO, PQRS, TUV, WXYZ 가 각각 같은 번호를 눌러 입력해야하므로 이전에 동일한 번호를 눌렀다면 추가로 대기시간 W시간을 요구한다. 공백에 대해선 대기시간 W 이 필요하지 않다. BC, EF, HI .. 등에 대해선 여러번 눌러야하므로 P*required[알파벳]을 이용해 구할 수 있게 하였음. 입력 받는 것이 조금 까다로울 수 있다. ````C++ #include #include #include using namespace std; int a[26] = { 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9 }; int required[26..

백준 1463 1로 만들기 해설 Queue를 이용하여, 임의의 n 에서 1 까지의 이동하는 것을 구현하여서 최단경로 길이를 구할 수 있다. (BFS) 하지만 문제를 뒤집어서 생각해보면, n에서 1까지의 최단경로 길이는 다음 세개 중 하나이다. n/2 에서 1까지 가는 최단경로 길이 + 1 n/3 에서 1까지 가는 최단경로 길이 +1 n-1 에서 1까지 가는 최단경로 길이 + 1 아래는 memoization을 이용하여 문제를 해결한 소스코드이다. ````C++ #include #include #include using namespace std; int d[(int)1e6+1]; int go(int cur) { if ( cur = 0) return d[cur]; d[cur] = 1e9; if ( cur%2 ..

이 문제는 비교적 구현의 성격이 강한 문제이다. 해당 문제에 대해 포스팅을 남긴 이유는 삼성 B형과 성격이 비슷하기에 골랐다. 입력으로 들어온 단어들을 내 사전 (Trie) 로 저장해놓고, 4*4 배열을 규칙에 따라 순회하면서 생성된 단어를 Trie에서 탐색하는 것이 해당 문제의 풀이이다. 이 풀이 서술은 조금은 일반적인 서술로써, 구현에 대해 조금 구체적으로 이야기 해보려 한다. 1 트라이 with memory allocation 대부분이 알고있는 Trie 의 형태로써 Trie 노드가 자식 노드의 주소를 가지고 있는 것이다. 그리고 동적으로 관리하기 때문에 new, delete를 동반한다. 아래는 해당 문제에 대한 Trie 풀이 소스이다. 해당 문제 자체가 올림피아드 성격의 대회 문제이기에 구현성이 강..

문제보기https://www.acmicpc.net/problem/2447분할정복 문제 재귀에 대해 능숙하다면 금방 해결 할 수 있는 문제이다. 10~20분 소요. 나는 알고리즘을 처음 시작할 때가 작년 7월 정도였으니, 한 9개월 정도 공부한 것이다. 내가 별찍기 11을 작년 8월- 그러니까 한 알고리즘 시작한지 1개월 도 안되었을 때 도전했다가 실패했을 것이다. 그때 좀 우울했다. 그러니까 이 문제를 해결하고, 포스팅 하는거지만,.. 나에겐 의미가 있는 포스팅이다 ㅋ. 이런류의 또 이런 수준의 문제는 다른사람의 코드를 보고 이해하고 분석하고 왜 틀린 이유를 짚으려면 나에겐 아직 조금 난해하기도 하고, 어렵다 그런만큼 초보 수준에서 별찍기 마스터를 하겠다 해서 괜히 이런문제에 상처받질 않기를 원한다. 왜..

문제 보기https://www.acmicpc.net/problem/11657 벨만포드 알고리즘이다. 알고리즘 분류 기능을 이용해 풀수있는 가장 첫 문제이며, 벨만포드 알고리즘을 그대로 사용하면 된다.기존소스에 반례가 있었다. 출발점에서 도달 할 수 없는 정점 간에 음수 경로가 존재해도 음수사이클 존재를 판단했던 것이다. 그리고 INF 값이 너무 작았다. 500*10,000+1 이상되어야한다. 수정하였음. 등록일이 18년 2월이었으니... 1년 8개월만에 수정한거네요!` 소스보기https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/11657.cc

백준 5719 거의 최단경로 난이도 꽤 있다고 생각함.https://www.acmicpc.net/problem/5719 다익스트라를 이용하여 최단경로를 저장해나가는데 pred 벡터에 이전 경로를 갱신해준다.그리고 이전경로를 모두 탐색해 그 경로를 재귀적으로 접근하여 -~ 사용할 수 없는 간선으로 만든다.그리고 다시 다익스트라를 활용한다. 그러면 거의 최단경로가 나온다. 개념적으로 와닿지만, pred 를 어떻게 벡터로 만들고, ... 그리고 어떻게 삭제하는가... 에 대해서 생각하는데 시간이 많이 걸린 문제였다. 여기서 아마 구현능력과 논리력이 갈리었을거라 생각한ㄷㅏ 리저널,, 문제였는데 어렵긴 어려운것 같다. 난 제한 시간내에 못풀었다 100% ㅋㅋㅋ. 이 문제로 인해 느낀점은, pred 벡터에 targ..

백준 1, 2, 3 더하기본문보기https://www.acmicpc.net/problem/9095 이번 문제는 경우의 수 구하는 문제이다. 해당문제는 n중 for문으로도 풀 수 있고, 재귀를 이용한 dfs 탐색(트리탐색) 으로도 풀 수 있다. 하지만 또 dp풀듯이도 풀 수 있다. dp 풀듯이라는 뜻은 어쨋든 굉장히 큰 길이 또는 크기를 구하는 문제이지만 서도 낮은 숫자부터 차근차근 sub-answer들을 구해내서 귀납적으로 큰 값에 대한 답 real-answer를 구하는 것이다.이게 바로 sub-problem , overlapping 이라는 개념인데 나는 아직 이 개념에 익숙치 않아서 이 블로그를 포스팅 하는 이유이기도 하다. 이번문제에서 숫자는 어떻게 완성될까? 우선 이전 dp 문제들의 접근법을 확인해..