프로그래밍/[Algorithm] 썸네일형 리스트형 [Algorithm] DP-2 동적 테이블을 작성하는 Knapsack 예제풀이이다. [Algorithm] DP-2 동적 테이블을 작성하는 Knapsack 예제풀이이다. https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는.. 더보기 [Algorithm] 다익스트라 알고리즘 도착지 까지 최단 거리를 구하는 다익스트라 알고리즘이다. greedy알고리즘을 통해 구하고 수학적 귀납법을 통해 증명 가능하다. "가정이 방문한 꼭짓점이 n-1일 때 성립한다고 가정하자. 이 경우에, 모든 미방문 꼭짓점에서 dist[u]가 가장 작은 u에 대해서 dist[u] = dist[v] + length[v,u]을 만족하는 변 vu를 선택한다. dist[u]는 source에서 u까지의 가장 짧은 거리로 볼 수 있다. 만약 그 경로보다 더 짧은 경로가 있고, 그 경로의 첫 번째 미방문 꼭짓점을 w라고 한다면 처음의 가정인 dist[w] > dist[u]에 의해서 모순이 생긴다. 이와 비슷하게, u로 가는 경로 중 미방문 꼭짓점을 지나지 않는 더 짧은 경로가 있고, 그 경로의 마지막 꼭짓점이 w라고 한.. 더보기 [Algorithm]그래프 입력받기 많은 알고리즘 문제들은 그래프 기반이다 그래프를 입력받는 방법은 크게 두가지가 있는데 1. 인접행렬을 이용하여 연결관계를 나타내는 방법과 2. 링크드 리스트를 통해 그래프를 나타내는 것이다. 이 중 두번째 리스트를 이용한 그래프 입력을 구현해 보았다. 문제를 풀기 위해 우선순위 큐 선언이 들어가 있는데 무시해도 좋다. 입력은 다음과 같다 노드수, 간선수 시작 노드 출발노드 도착노드 가중치 출발노드 도착노드 가중치 출발노드 도착노드 가중치 ... 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 .. 더보기 [Algorithm] dynamic programming-1 rod(막대기)문제 [메모이제이션과 동적계획법] 메모이제이션은 미리 계산한 캐시값을 이용한 최적화 기법이다. 동적 계획법은 하위 문제에서 계산한 값을 재귀 내지는 반복적으로 문제 풀이에 사용하는 기법이다. 주로 table작성(tabulation기법)을 활용 하지만 메모이제이션 방법을 사용 하기도 한다. 메모이제이션과 동적계획법은 어느 한쪽이 서로에게 속하는 관계가 아니다. [메모이제이션과 tabulation] tabuation은 bottom-up방식으로 상위 문제를 풀기위해 하위문제의 모든 값을 필요로 할떄 유용하다. memoization은 top-down방식으로 이미 푼 문제의 값을 저장하고 있는 것이다. top down의 의미는 top단의 문제부터 푼다는 의미이다. f(7)값을 구한다 치면, tabulation은 f(1.. 더보기 [Algorithm] dfs 간단 구현 (단지 번호 문제) dfs최대한 풀어서 구현해 보았다. 에러나면 row들어갈 자리에 column이 써져 있는지 잘 확인 해봐야한다. 인덱스가 array범위 안에 들어가는지 체크하는 함수를 뺄 수 있다. visited 체크하는 부분이 애매한데 단지가 아닌 곳은 visited체크하지 않고 dfs가 시작할때 visited체크를 해준다. visited체크를 스택에서 뺄때 처리할지 스택에 넣을때 처리 할지도 정할수 있는데 스택에 넣을때 체크하여 스택에 중복되는것이 없게 하는 것이 좋다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 5.. 더보기 [Algorithm]merge sort 병합정렬 한쪽의 배열의 끝에 먼저 도달했을때 처리를 처음에 빼먹었다가 추가했다. Merge함수는 사실 생각하기 쉽고 MergeSort함수가 생각하기 어렵다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 int* Merge(int * left_array, int left_size, int * right_array, int right_size) { int left_index = 0; int right_index = 0; int merged_index = 0; int* merged_array = (int*)malloc(sizeof(int)*(left_.. 더보기 이전 1 다음
