이동건의 이유있는 코드

[알고리즘] 백준 9095번 문제 1,2,3 더하기 풀이 N을 1,2,3의 조합으로 만들 수 있는 개수를 구하는 문제다. 그렇기 때문에 N이 3일 때까지는 Default 값으로 배열을 채워주었다. 만약 N이 4라면 3을 만든 조합들에 1을 추가해주는 방법으로 4를 만들 수 있고, 2를 만든 조합들에 2를 추가해서 4를 만들 수 있고, 1을 만든 조합에 3을 추가하여 4를 만들 수 있다. 즉 이전에 만든 값을 통해 현재의 값을 구할 수 있는 것. 그렇기 때문에 점화식은 다음과 같이 나온다. dp[N] = dp[N-1] + dp[N-2] + dp[N-3] 코드

[알고리즘] Longest Common Subsequence - Length 안녕하세요. 오늘은 학교 수업 중 알고리즘 강의를 굉장히 재밌게 들었고 내용을 보다 확실히 이해하기 위해 기록을 통해 다시 한번 생각해보려 글을 작성하게 되었습니다. 오늘 배운 알고리즘 다이나믹 프로그래밍 (DP) 중 유명한 알고리즘 문제중 하나인 Longest Common Subsequence, 줄여서 LCS 문제를 분석해보는 시간이였습니다. 그 중에서도 문자열의 LCS에 대해 공부를 해보았습니다. LCS란 두 문자열에서 서로 공통되는 가장 긴 부분 문자열을 말합니다. LCS 문제는 이 부분 문자열을 구하는 문제가 되는 것입니다. 그럼 바로 시작해보도록 하겠습니다. LCS 먼저 단순히 뜻만으로는 와닿지 않을 수 있으니 몇 가지..

[알고리즘] 정렬 알고리즘 - 선택,버블,삽입 안녕하세요. 오늘은 정렬 알고리즘에 대해 공부를 해보았는데요. 기초적인 알고리즘에 속하지만 최근들어 알고리즘을 제대로 다시 시작하기 위해 시간복잡도를 바탕으로 다시 공부해보는 시간을 가졌습니다. 오늘은 기본적으로 시간 복잡도가 O(N^2)인 알고리즘부터 알아보도록 하겠습니다. (모든 다이어그램은 제가 키노트를 활용하여 제작하였습니다! 조금은 부족하더라도 너그러히 이해부탁드리며 틀린 부분이 있다면 피드백 부탁드리겠습니다.) 1. 선택 정렬 선택 정렬을 간단히 설명해드리자면 오름차순으로 정렬한다고 가정을 하였을 때 정렬되지 않은 배열 중 가장 작은 배열을 선택하여 앞에서부터 채워나가는 방식입니다. 파란색 화살표는 현재 채워야 할 위치의 인덱스를 가리킵니다. 빨간..

[알고리즘] 백준 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은 ..