글을 작성하는 이유최근 문제를 풀면서 키워드 유추 -> 접근법 생각 -> 검증 -> 코드로 구현 순으로 풀이를 진행하는 연습을 하고 있습니다.이 과정에서 접근법에 대해 코드로 구현하는게 잘 되지 않는다고 느껴져서 이유를 생각해보고, 어떻게 개선해나갈지 정리하고자 글을 작성하게 되었습니다. 참고 문제https://school.programmers.co.kr/learn/courses/30/lessons/77886  키워드 유추0과 1로 이루어진 어떤 문자열 xx를 최대한 사전 순으로 앞에 오도록x에 있는 "110"을 뽑아서임의의 위치에 삽입접근법 생각문자열 x에서 "110"을 추출추출 후 남은 문자열에 대해서도 계속해서 추출최종적으로 남은 문자열에서 마지막 0의 위치를 탐색추출한 "110"을 순차적으로 마지..

문제https://www.acmicpc.net/problem/3109풀이그리디 + DFS접근법처음 접근은 완전탐색 방식으로 접근했습니다.문제를 해석해보면 왼쪽 열에서 오른쪽 열까지 벽(x)을 제외한 나머지 통로들에 파이프를 설치하여 연결할 수 있는 길의 개수를 구하는 문제입니다.주어진 조건에 의한 행동은 3가지로 다음과 같습니다.오른쪽 상단 대각선오른쪽오른쪽 하단 대각선또한 겹치게 설치 할 순 없다는 조건이 있습니다.탐색해야하는 경우의 수는 그럼 총 N개로 시작 열의 격자칸 개수만큼 탐색을 해야합니다.또한 백트래킹을 통해서 완성된 길에 대해서는 기록을 하고, 끝까지 도달하지 못하는 경우에는 원상복귀를 시켜야 한다고 생각했습니다.위와같은 로직을 구현하기 위해서 처음 0,0에서 탐색을 시작하여 길이 완성될 ..

H사 코딩테스트를 치고나서 생각했다.“내가 뭔가 잘못하고 있구나. 이대로는 안되겠다”간단한 복기180분 동안 총 2개의 문제를 풀면됐다.늘 그렇듯, 2개의 문제를 읽었다.둘 다 풀 수 있을거라 생각했다. (뭐 이정도면 3시간까지도 안들겠네..) 첫번째 문제를 풀기 시작했다.생각보다 쉽지않다. 풀다보니 애드혹 알고리즘 같았다. (모르면 못푸는..)시간이 2시간 지났다… 이대로는 안된다. 2번으로 가자.2번을 10분정도 봤을까? 매몰비용이 생긴 1번이 눈앞에 아른아른 거린다.“조금만 더하면 풀릴 것 같은데…”다시 1번으로 향했다. 규칙 찾으려고 A4 2장을 양면으로 빡지를 썻다.시간이 끝났다. “벌써?”“이대로는 오늘 잠을 못잘 것 같다. 끝을 봐야겠어.”이 후 30분 정도 인텔리제이에서 코드를 작성했다. ..

이번 글의 목적은 피보나치같은 대표적인 예시로 다이나믹 프로그래밍에 대해 뜯어보기 위함이 아닌저만의 접근(풀이)방식에 대해서 정리한 글입니다. 도움이 되셨다면 좋겠네요.도입부알고리즘 문제를 조금 풀어본 사람의 경우, 문제를 풀다보면 “DP로 풀어야하나?” 라는 감이 올 때가 있습니다.예를 들자면, 완전 탐색을 요구하는 문제인데 입력이 굉장히 클 경우, 일반적인 DFS, BFS로 풀 수가 없다고 느꼈을 때입니다. 아마 동전, 배낭문제와 같이 잘 알려진 문제들에 대해서는 곧바로 풀이를 할 수 있겠지만, 이러한 문제들은 코딩테스트에서 잘 나오지 않죠. 심지어 “DP로 풀어야하나?”라는 생각도 들지않게 나올 때도 있습니다.“DP로 풀어야겠다!”라고 생각을 해도 좀처럼 풀리지 않을텐데, 이유는 문제마다 공식이 제..