전체 글23 동적계획법, Dynamic programming 1. 동적계획법이란 큰 문제를 더 작은 문제로 분해해 각각의 결과를 저장하여 본래 문제를 해결하는 알고리즘 설계법이다. 문제의 입력 instance를 더 작은 부분 instance로 나눈다. 작은 instance를 먼저 해결하고 그 결과 저장한다 저장된 결과들로 큰 instance를 해결한다. 이를 주로 Bottom-up, 상향식 방식으로 진행하게 된다. 코딩테스트에서 주로 숫자 제한범위가 크고, 경우의 수가 방대한 문제가 주로 DP로 설계하면 해결된다(고 함) 2. Memoization n번째 피보나치 수열의 수를 구하는 문제를 재귀식으로 풀 때를 생각해보자. func fibonacci(n) if n < 2 n else fibonacci(n - 1) + fibonacci(n - 2) 보다시피 f(n) .. 2024. 4. 5. 장경인대 이후 최근 근황. 헬스 시작 무릎은 아프고, 운동은 해야겠고(꼴에 몇달 달렸다고 몸이 근질..ㅋㅋㅋㅋㅋ) 2주 전에 몇달간 할까말까 고민하던 헬스장을 등록했고 PT 역시 신청했다. 헬스장을 다니기 시작한건 10일이 조금 넘었고. 시작했다기도 뭐한 짧은 기간이고, 헬스에 대해선 완전히 문외한인 헬린이, 아니 헬스신생아 수준. 목표는 주4일 이상, 되도록이면 5일을 오전 중으로 다녀오는걸 목표로 하고있는데 일단은 지키고 있다. 아무튼 다니기 시작하고 느낀 점은 1. 눈치보일것 같고, 기죽을 것 같아서 안 갔던게 후회됨. 헬스를 막 시작하거나 혹은 가려고 마음먹은 사람들 중 기구 사용에 눈치보인다, 우락부락한 몸들에 기죽는다 는 등의 이유로 헬스장에 가길 망설여하는 이들이 많은데, 나 역시 그랬다. 게다가 스스로 조빱이란걸 알고 있다보니.. 2024. 3. 25. c++) 백준 14888 백트래킹, 연산자 끼워넣기 14888번: 연산자 끼워넣기 (acmicpc.net) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 1. 접근 수열과 수열의 각 수 사이에 들어갈 연산자가 주어진다. 수열은 순서에 맞게 계산해야하므로 사실 고려할게 없다. 우리가 고려해야할 것은 주어진 연산자들의 모든 순서와, 그로 인해 계산된 결과들을 출력하는 것 뿐. 사실상 연산자들을 선택하는 순열로 생각하면 된다. 2. 풀이 operands 배열엔 수열을 이루는 수들을 입력받는다. operato.. 2024. 3. 25. 백트래킹(Backtracking) 알고리즘 1.백트래킹이란? 해를 찾을 때 모든 경우의 수를 전부 고려하는 알고리즘이다. 다만 이름처럼 되추적 과정을 거쳐, 사실 모든 경우의 수를 다 돌진 않고 유망성을 판단해 버릴건 버리고 가는 방법이다. 쉽게 말하면 모든 경로를 돌긴하는데, 개중에 특정 조건만 만족하는 경우만 탐색하는 방법이다. 경우의 수 탐색에 트리가 사용되므로, 일종의 트리 검색 알고리즘이라고 봐도 무방하다. Backtracking(되추적) 해를 찾아가는 도중 그 경로가 해가 되지 않을 것 같다고 판단되면, 이전 단계로 돌아가 다시 찾아가는 기법 2. DFS 깊이우선검색(Depth First Search), 트리에서 깊이를 우선 기준으로 두고 탐색하는 방법으로, 백트래킹에서는 DFS를 이용해 트리를 탐색한다. (너비우선 BFS도 사용해 구.. 2024. 3. 24. 이전 1 2 3 4 5 6 다음
