이동건의 이유있는 코드

[알고리즘] 백준 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. 선택 정렬 선택 정렬을 간단히 설명해드리자면 오름차순으로 정렬한다고 가정을 하였을 때 정렬되지 않은 배열 중 가장 작은 배열을 선택하여 앞에서부터 채워나가는 방식입니다. 파란색 화살표는 현재 채워야 할 위치의 인덱스를 가리킵니다. 빨간..

[알고리즘] 백준 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로 찾아가며 방문..