개발자 준비중인 블로그

더럽게 고생한 문제 중 하나다. 보통 가장 짧은 거리를 구하는 문제가 많으나 경우의 수를 붙여서 DP문제가 되었다. 우선 경로 자체를 DFS로 탐색하는 것이 맞다. DFS에서는 1. 해당 경로를 탐색하면 중복체크를 남긴다. 2. 해당 경로가 접근 가능하거나, 기존의 방법보다 이동거리가 짧다면, 누적거리를 기록하고 stack에 삽입한다. 3. 경로가 막히거나, 이미 탐색한 경로이며, 이동거리가 더 길다면 stack를 반환하여 다시 돌아간다. 이 3가지의 규칙을 따른다. 그리고 도착했다면 도착지점에 남겨진 누적거리를 체크하면 가장 빠른 길을 확인이 가능하다. 하지만 여기서는 가는 모든 경우의 수를 찾아야 한다. 그렇다면 여기서 DFS를 조금 변경하면 된다. 1. 해당 경로를 최초 탐색하면 중복체크를 남긴다...

경우의 수의 문제이다. 이런 경우의 수의 경우, 처음부터 마지막 값까지 가면서 누적되는 경우의 수를 더해가며 구하게 된다. 왜냐하면 1. 목표값까지의 경로값의 경우의 수는 불변하며, 2. 다음 목표값은 이전의 경로값과 중복되기 때문이다. 예를 들어보자 동전 1, 2, 5,가 있고 무한하게 주어진다고 가정하자 여기서 총합 2COIN을 만든다면 1+1, 2 이렇게 2개의 경우의 수가 나오게 되며 이는 COIN의 종류가 변하지 않는 이상 불변한다. (1) 여기서 COIN을 만든다면 1+1+1, 2+1 이렇게 2개의 경우의 수가 된다. 여기서 3COIN의 경우의 수를 자세히 보게 되면 2COIN을 만드는 경우의 수에 1COIN을 더한 값이 나온다. 즉 기존의 경우의 값을 참조하여 새로운 경우의 값을 구하는 것이..

정리는 정말 나에게 너무 먼 행동이다. 그 동안 "머리속에 들어있으니깐 문제없어!" 하면서 과거의 대뇌피질의 존재를 믿어 의심치 않았다. 실제로 대학시절에 모든 전공과목은 술술 꿰뚫고 있었다. 대부분의 점수들은 A+이었고, 1년전 과목을 후배들에게 다시 가르켜 주기도 했었다. 그렇게 자신있게 대학을 졸업하고, 1년 반동안 반도체검사 회사에서 신개발팀으로 다니다가 혼자 다니는 잦은 출장, 잦은 야근, 무리한 스케줄 요구에 지쳐서 회사를 그만두었고, 테스터가 아닌 개발을 하고 싶다는 생각에 백앤드 개발자로 목표를 잡고 다시 공부를 시작했다. 그리고 현재. 대학생활때의 자신감으로 취준생이였던 내가 첫 알고리즘 문제를 풀었을때는 정말... 그야말로 첫시험은 맨붕의 연속이였다. 그리고 5개의 문제중 1개만 풀어낸..