이동건의 이유있는 코드

[알고리즘] 백준 1890번 문제 https://www.acmicpc.net/problem/1890 풀이 오늘도 역시 BFS/DFS 문제를 풀어보았습니다. 이 문제를 처음 봤을 때 여타 다른 문제와 다를 것이 없다고 생각했고 BFS를 이용해서 풀면 쉽게 풀릴 것이라고 생각했습니다. 그리고 BFS로 코드를 작성하고 실행시켜보니 역시 원하는 출력 결과물이 나왔습니다. 하지만 사이트에 제출하니 시간 초과라는 문구가 떴습니다. 그제서야 깨달았죠! 단순히 BFS/DFS로 풀면 안되겠구나! N이 100이 된다면 상당히 많은 칸을 점프할 것이고 그 중 중복 탐색이 생길 수 있다는 것을 알게되었습니다. 그렇기 때문에 BFS/DFS와 DP를 같이 사용해야하는 다소 복잡한 문제였습니다. 다음은 저의 풀이 과정입니다. 처음..

[알고리즘] 백준 2606번 문제https://www.acmicpc.net/problem/2606 풀이 오늘도 BFS/DFS 문제를 풀어보았습니다. 사실 지금까지 BFS로만 풀어서 DFS에 대한 감을 잃을까봐 이번 문제는 DFS로 풀어보았습니다. 재귀를 이용하여 풀었는데 간만에 DFS로 시도했더니 머리가 잘 돌아가지 않는 것을 느꼈습니다. 그래서 실수도 많았고 시간도 오래걸렸습니다. 사실 로직 자체는 크게 어렵지 않았습니다. 하지만 사소한 문제들과 제가 생각하지 못한 반례가 있어서 그 부분에 대해 언급하고자 합니다. 제가 생각한 풀이 과정은 다음과 같습니다. 시작점(1)을 시작으로 재귀를 이용한 DFS를 사용해야겠다고 생각했습니다. 배열을 사용하자니 낭비되는 메모리가 많은 것 같아서 List와 Array..

[알고리즘] 백준 7576번 문제 https://www.acmicpc.net/problem/7576 풀이 오늘도 역시 BFS 문제를 풀어보았습니다. 사실 BFS 문제가 DP보다 잘 풀려서 BFS에 더욱 손이 가더라구요. DP를 연습해야하는데 말이죠...하여튼! 오늘 풀어본 BFS 문제 역시 제가 지금까지 풀어온 BFS 문제와 크게 다를 것이 없습니다. 하지만 제가 생각하지 못한 반례가 존재하였기 때문에 약간은 시간을 소비했는데 정답률에 비해 그렇게 어렵지 않은 문제였습니다. 다음은 저의 풀이 과정입니다. BFS를 통해 전체를 탐색하는데 레벨이 곧 구해야하는 최소 날짜이기 때문에 이 부분은 이전에 풀어보았던 2178번과 같은 방법을 사용해주었습니다. 처음에는 단순히 위에 것만 생각하고 반례를 생각하지 않았..

[알고리즘] 백준 2667번 문제 https://www.acmicpc.net/problem/2667 풀이 안녕하세요. 오늘도 역시 비교적 쉬운 BFS 문제를 풀어보았습니다. 정답률이 39%이지만 BFS, DFS 문제들 중에서 유명한 문제에 속하기 때문에 정답률은 중요하지 않다고 생각합니다. 기본적으로 저는 로컬에서 풀었을 때는 맞췄으나 사이트에서 채점을 하면 런타임 에러가 몇번 나왔습니다. 이유를 몰랐으나 질문 게시판에서 답글을 보고 무엇이 틀렸는지 이해했으며 초반 코드는 메모리 낭비도 심했기에 이를 보완하기 위해 코드를 약간 개선하였습니다. 저의 풀이 과정은 다음과 같습니다. 먼저 여타 다른 BFS문제와 마찬가지로 방문을 했냐와 안했냐가 기본으로 들어갔습니다. 인접한 1들의 값을 BFS로 찾아가며 방문..

[알고리즘] 백준 11403번 문제https://www.acmicpc.net/problem/11403 풀이 사실 이 문제의 제목만 보고 풀만하겠다는 생각을 했습니다. 이미 정답률 39퍼센트의 BFS문제도 풀었기 때문에 자신감이 넘쳤습니다. 하지만 역시 쉽게 풀지는 못했습니다. 그래도!! 어떻게 보면 제가 처음부터 끝까지 힌트도 얻지 않고 스스로 푼 문제는 이것이 처음인 것 같습니다! 그래서 상당히 뿌듯했고 답을 제출할 때는 모니터 앞에서 맞췄습니다! 라는 문구가 뜨기까지 굉장히 초조하게 지켜보았습니다. 저의 풀이과정은 다음과 같습니다. 저는 먼저 그래프를 그려서 확인해보았습니다. 먼저 출발점에서 갈 수 있는 모든 점을 찾아야 하기 때문입니다. 예제 입력에서 볼 수 있다시피 0은 1로 연결되어 있고 1은 ..

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