구름톤 챌린지 3주차 학습 일기 - DP(동적 계획법)
DP, 다이나믹 프로그래밍, 동적 계획법 이라고 불리는 기법은 이전에 구했던 답을 재활용하는 방식이다. 다시 말해, 이전에 구한 값을 저장해두고 다시 사용하므로써 불필요한 중복 계산을 최대한 줄이는 방법이다.(메모이제이션) 예를 들어서, 피보나치 수열을 재귀로 구현해보면 아래와 같다. 참고로 피보나치 수열은 처음 두개의 값이 0과 1이고, 이 다음 값은 맨 끝의 두 값을 더해서 만들어진다. 0, 1, 1, 2, 3, 5, 8, 13, 21, ... function fibo(N){ //첫 두값을 종단점으로 잡아줍니다. if (N === 0) return 0; if (N === 1) return 1; // N 번째 피보나치수는 N - 1번째, N - 2번째 피보나치수의 합이므로 재귀로 호출합니다. retur..
2023. 8. 29.
구름톤 챌린지 2주차 학습 일기 v2 (2차원 배열 완전 탐색, dx/dy 기법)
2차원 배열에서 자주 사용되는 기법인 dx/dy 기법에 정리하려고 한다. dx/dy 기법은 현재 내 위치에서 상화좌우, 대각선 방향으로 이동이나 탐색을 구현할 때 사용한다. 예를 들어 arr[1][1]의 상하좌우 값은 arr[0][1], arr[2][1], arr[1][0], arr[1][2] 다. 이를 인덱스로 표현한다면 아래와 같다. dx = [0, 0, -1, 1] // 열 dy = [-1, 1, 0, 0] // 행 이를 코드로 적용해보면 아래와 같다. let dx = [0, 0, -1, 1]; let dy = [-1, 1, 0, 0]; // 시작 위치 설정 let x = 1; let y = 1; // 4방향 탐색 for (let i = 0; i < 4; i++) { let nx = x + dx[i..
2023. 8. 23.
