분류 전체보기

[Algorithm] Dynamic Programming(4) - 벨만포드(Bellman-Ford)

🤔Dynamic Programming 다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다. 다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다. 이번 포스팅에서는 최단 경로 문제중 하나인 벨만포드 알고리즘에 대해 알아보도록 하겠습니다. 🔎 최단 경로 문제(Shortest Path Problem) ✍️ 최단 경로 문제란? 그래프 G = (V, E)의 상에서 정점 u에서 v로의 가장 짧은 경로의 길이를 구하는 문제를 최단 경로 문제라고 합니다. 우리는 edge-weighted graph의 경우만을 생각하도록 하겠습니다. ( 이때 |V| = n, |E| = m ) ✍️ Edge-weighted graph 그래프 G의 edge(a, b)에 가중치 w(a, ..

[TW] 2022-11-18

😊 오늘의 하루 바르미 샤브샤브를 갔는데 고등학교 친구를 만났다. 엄청나게 친한 친구는 아니지만 매우 반가웠다. 5인분을 시켰는데 10인분은 넘게 고기를 먹은 듯하다. 샐러드바도 있어서 다양한 음식을 먹을 수 있는데 배가 터지도록 먹었다. 맛은 말 할 것도 없다. Algorithm을 하기 위해서 공부를 하고있었는데 피곤이 쏟아졌다. 10분만 자려고 했지만 잠깐 자서 해결 될 피곤함이 아니였다. 동아리방에서 결국 아침까지 잤는데 레전드레전드.. ✅ TO DO LIST → 11월 14일 컴퓨터 구조 과제 완료 → 11월 14일 객체지향설계 과제 완료 → 11월 15일 알고리즘 수업듣고 정리 급함! → 11월 15일 알고리즘 복습 완료 → 11월 15일 시스템 프로그래밍 과제 완료 → 11월 ~20일 기계학습..

[Algorithm] Dynamic Programming(3) - Edit Distance(편집거리)

🤔 Dynamic Programming 다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다. 다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다. 이번 포스팅에서는 Edit Distance 문제를 해결하기 위해 Dynamic Programming을 사용하여 해결하는 과정을 정리했습니다. Edit Distance 문제는 어떤 단어와 비슷한 단어는 어떤 방식으로 정의할 수 있을까? 라는 의구심에서 시작되었습니다. 아래의 그림과 같이 Microsoft Word spell check 기능을 사용하면 비슷한 단어를 자동으로 추천해줍니다. 우리도 이를 Edit Distance를 통해 해결해보겠습니다. 🔎 Edit Distance 위에서 어떤 단어와 비슷한 단어..

[TW] 2022-11-17

😊 오늘의 하루 창업 아이디어 경진대회로 인해 학교 공부는... ㅎㅎ 하고싶은 일을 하니 매우매우 재미있다. 그렇지만 해야할 일이 밀린다는 너무 큰 단점. 너무 늦게 공부하고 자료를 만들다 보니 다래끼가 생겨버렸다. 내일은 인생 첫 예비군.. 군대를 다시 가야한다니 슬프구만 ✅ TO DO LIST → 11월 14일 컴퓨터 구조 과제 완료 → 11월 14일 객체지향설계 과제 완료 → 11월 15일 알고리즘 수업듣고 정리 → 11월 15일 알고리즘 복습 완료 → 11월 15일 시스템 프로그래밍 과제 완료 → 11월 ~ 19일 기계학습 정리 Model Evaluation, DecisionTree, Ensemble Method, Neural Networks 정리 → 11월 ~19일 시스템 프로그래밍 복습 → 1..

[Algorithm] Dynamic Programming(2) - LIS(Longest Increasing Subsequence)

🤔 Dynamic Programming 다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다. 다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다. 이번 포스팅에서는 LIS문제를 해결하기 위해 Dynamic Programming을 사용하여 해결하는 과정을 정리했습니다. 🔎 LIS(Longest Increasing Subsequence) ✍️Subsequence 길이 n 인 sequence (ordered list) $S = a_1, a_2, …, a_n$ 이 주어졌을 때, sequence $S’ = a_{i1}, a_{i2}, .., a_{ik} 가 1≤ i1 < i2 < … < ik ≤n$ 를 만족할 경우 $S’$ 을 $S$의 subsequence ..