염딩코

문제 풀이 처음에는 가장 많이 겹치는 순으로 제거하면서 겹치지 않는 선들만 남기려고 헀다. 하지만, 이 접근 방식은 DP와 거리가 있다고 생각을 했고 오히려 Greedy 알고리즘에 가깝다는 생각이 들었다. DP의 가장 중요한 특성 중 하나인 bottom-up을 고려하여 다시 생각을 해보는 시간을 가졌다. ⇒ 결과적으로 겹치지 않는 경우를 카운트 첫 번째 줄부터 마지막 줄까지 순차적으로 보면서 겹치는 경우를 고려하려고 했으나 쉽지 않았다. 처음에 입력을 받을 때, 랜덤한 순서로 받기 때문에 오름차순으로 정렬하여 우선 조금 더 쉽게 판단할 수 있도록 했다. (왼쪽을 기준으로 오름차순 정렬) 오름차순으로 정렬하여 가장 긴 수열(경우)를 찾는 것 = 가장 많이 겹치지 않는 경우

풀이를 생각해낸 과정 이 문제는 예전에 알고리즘 과제와 유사하다는 느낌을 받았다. (그래서 예전 알고리즘 수업 자료도 보면서 다시 공부를 했다.) 목적지에 도달을 하면 경우의 수에 1을 더하는 방식을 생각을 했었고, 그 과정에서 지나온 경로들을 모두 처리해줘야 했었다. 지나온 경로는 상하좌우를 따지면서 내리막길인 경우에 다른 표기를 해야한다고 생각했다. 그렇게 목적지에 도달하면 해당 경우의 수를 1씩 증가시키면서 답을 구하려고 했다. 오렌지 부분에서 고민을 많이 했고, 시간이 너무 지체되어서 참고를 하면서 구현을 했다. 풀이에 대한 설명 세부적인 내용은 주석을 통해서 간단하게 설명을 했고 핵심적인 내용 위주로 설명을 하면 각각의 노드에 왔을 때, 상하좌우를 따지면서 범위를 벗어났다면 continue를 하..

DP 점령 2일차. 지난 포스팅에 간단하게 DP에 대한 특징을 정리했습니다. 그것을 기억하면서 이 문제를 풀어봅시다. 2023.09.13 - [알고리즘 PS/Javascript] - [JavaScript] 백준 1463번 문제 [JavaScript] 백준 1463번 문제 이 문제는 DP(Dynamic Programming)를 연습하기 좋은 문제입니다. DP(동적 계획법)에 대한 자세한 설명은 추후에 글을 올리겠습니다. DP에 대해서 간단하게 말씀드리면 DP는 하나의 큰 문제를 여러 개의 yeomyeom.tistory.com 처음에 주어진 것은 1인 경우에는 1가지이고, 2인 경우에는 3가지가 나오는 구나. DP의 가장 큰 특징 중 하나는 작은 단위로부터 문제를 해결하려는 것입니다. 그래서 작은 단위에서부..

이 문제는 DP(Dynamic Programming)를 연습하기 좋은 문제입니다. DP(동적 계획법)에 대한 자세한 설명은 추후에 글을 올리겠습니다. DP에 대해서 간단하게 말씀드리면 DP는 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용합니다. DP는 재귀와 매우 유사합니다. 하지만, 가장 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 점입니다. DP를 사용하기 위한 조건으로는 크게 두 가지가 있습니다. 1. Overlapping Subproblems(겹치는 부분 문제) 동일한 작은 문제들이 반복하여 나타나는 경우 2. Optimal Substructure(최적 부분 구조) 부분 문..