C++ STL, 알고리즘12 c++ 복습을 위한 링크 https://www.tcpschool.com/cpp/cpp_intro_program 코딩교육 티씨피스쿨4차산업혁명, 코딩교육, 소프트웨어교육, 코딩기초, SW코딩, 기초코딩부터 자바 파이썬 등tcpschool.com 2024. 8. 30. DP 다이나믹 프로그래밍 Dynamic Programming Dynamic Programming이란? 큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말. Dynamic Programming이란 말 때문에 어떤 부분에서 동적으로 프로그래밍이 이루어지는 찾아볼 필요는 없다. 바로 동적프로그래밍이란 말을 창조한 사람도 이것이 단지 멋있어서 부여한 이름이라고 한다. 메모이제이션 기법을 사용한다. 그것이 핵심이다. Dynamic Programming 방법 모든 작은 문제들은 한번만 풀어야 한다. 따라서 정답을 구한 작은 문제를 어딘가에 저장해 두어야 한다. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 저장한 작은 문제의 결과값을 이용한다. Dynamic Programming의 조건 작은 문제가 반복이 일어나는 경우. 같은 문제는 구할 때마다 정답.. 2023. 11. 22. Greedy와 DP 알고리즘에 대한 고찰 문제를 풀면서, 깨닫는게 많아지면서 변화할 생각을 적어보고자 한다. 결국 DP의 미학은 계산한걸 또 계산하지 않겠다는 것이다. 그래서 메모이제이션이 필요한 것이다. 점화식을 구하는 것이 핵심인데, 점화식이라는 어려운 말보다 다음 껀 어떻게 구할래? 이렇게 생각하면 편할것이다. DP의 경우 N번째가 모두 정답이다. 곧, 정답만 저장된다는 것도 그 정답을 이용해 다음 정답을 이끌어내야하는 과제가 있다. 실버문제의 경우 초기식을 세우고 dp[0] 처럼 하드코딩으로 내가 정의할 수 있는 경우가 많다. 그 후, 문제를 풀때 dp[1], dp[2]는 어떻게 될지 나열하다보면, 결국 문제는 풀리기 마련이다. 골드문제의 경우 dp의 자료구조를 어떻게 정할지에 대해 고민스러웠던 경험이 있었다. dp자체에 어떤 정답을 담.. 2023. 11. 22. BFS, DFS 활용 문제 고찰 BFS 문제를 많이 접하다 보니, BFS 문제 유형에 대해서 생각해보게 되었다. 나는 문제를 일반화 시키는 것을 선호한다. 만능은 없지만 정답에 가까워지기 편하기 때문이다. 먼저 그래프를 사용해야할 것 같다는 감이 올 때, 그 감에 대해서 정의해보려고한다. 그래프 문제의 경우 1. 어디부터 어디까지 도달한다 2. 가는 길을 묻는다 3. 가는 길의 횟수를 묻는다 4. 영역을 나눈다 5. 전염? 된다 이런 식의 힌트를 문제에서 제공한다. 의심의 여지없이 그래프를 사용해야하고, 그래프 탐색 알고리즘을 사용해야하는 경우가 많다. 그래프 탐색 알고리즘 중 bfs를 사용해야할 때와 dfs를 사용해야할 때는 명확한데, 각각의 특성을 고려했을때 그 문제가 어느 알고리즘으로 해결해야할지 더욱 명확해진다. - 결국 bfs.. 2023. 11. 1. 이전 1 2 3 다음
