이동건의 이유있는 코드

[알고리즘] 백준 2178번문제https://www.acmicpc.net/problem/2178 풀이 알고리즘 공부를 하면서 자료구조도 간간히 복습하고 있습니다. 그리고 최근에 복습한 것이 바로 BFS와 DFS 알고리즘입니다. 단순히 자료구조를 공부하기 위해 구현을 하는 것은 그렇게 어렵지 않았고 실제 알고리즘에서 어떻게 활용될지가 궁금해 BFS 알고리즘 하나를 시도해봤습니다. 하지만 기본 BFS 알고리즘 조차 문제로써 나오니 쉽게 떠오르지 않는 부분도 있었고 새로 알게 된 점도 있었습니다. 다음은 저의 풀이과정입니다. DFS로 시도하였으나 최소의 칸 수이기 때문에 DFS로는 조금 까다로울 것 같아서 BFS를 선택했습니다. BFS로 어떻게 최소의 칸수를 구할까 고민하던 중 지금 문제는 최소 경로가 아닌 ..

[알고리즘] 백준 11722번 문제 https://www.acmicpc.net/problem/11722 풀이 오늘은 가장 긴 감소하는 부분 수열 문제를 풀어보았습니다. 유명한 dp 문제의 유형 중 하나이고 난이도 역시 쉽다고 하는데 저는..역시나 아직은 알고리즘이 약해서 그런지 여러 블로그에서 힌트를 얻어 풀었습니다. 주어진 수열에서 가장 긴 감소하는 부분 수열을 구하기 위해서는 수열의 각 요소를 기준점으로 이전의 요소들과 비교를 해서 본인보다 큰 요소가 존재한다면 자신의 길이를 1 추가하는 방식으로 접근하였습니다. 그렇게 되면 이전 요소들 또한 각각 부분 수열에 포함되어 있는데 해당 부분 수열에 속해서 더 긴 감소하는 부분 수열을 이룰수 있다면 그곳에 속하는 코드를 작성해주어야 합니다. 코드는 다음과 ..

[알고리즘] 백준 2193번 문제https://www.acmicpc.net/problem/2193 풀이 이 문제의 정답률은 35퍼센트였습니다! 알고리즘에 정말 약한 저에겐 넘볼 수 없는 존재 같았습니다. 하지만 정답률이 높은 문제를 찾던 도중 잘못 클릭하여 들어와서 문제를 읽어봤는데 "어? 이거 할만한데?" 라는 생각이 들었습니다. 왜냐하면 이런 비슷한 어려운 문제를 풀다가 포기를 한 적이 때문입니다...! 풀이를 보면서 코드를 하나하나 따라가도 전 풀지 못했었죠.. 그리고 그냥 포기했었던 기억이 있습니다. 근데 그때 잠깐 보았던 풀이의 원리 중 하나가 생각났습니다. 그리고 같은 원리를 적용해서 풀었더니 쉽게 풀렸습니다! 이게 알고리즘의 묘미인가 싶습니다...그냥 단순히 우연하게 기억이 났던 것일까..!..

[알고리즘] 백준 1149번 문제 https://www.acmicpc.net/problem/1149 풀이 먼저 Input을 약간 헷갈렸다. 첫번째 입력 N은 집의 갯수이고 두번째 부터는 집마다 칠하는 색의 비용을 입력해주는데 위의 문제처럼 26, 40, 83을 입력하면 첫번째 집을 빨간색으로 칠하는데 비용은 26, 초록색으로 칠하는데는 40 그리고 파란색으로 칠하는데는 83의 비용이 든다는 의미입니다. 또한 문제에 나와있듯이 이웃한 집은 같은 색으로 칠할 수 없습니다. 저는 아직 많이 부족하여 역시 잘하시는 분들의 블로그들에서 힌트를 얻어 풀었습니다. 그래도 조금은 문제를 풀어서 그런지 다이나믹 프로그래밍으로 풀어야한다는 것은 알았습니다! 제가 이해하고 만든 풀이와 제 의식의 흐름은 다음과 같습니다. 바..