계란 블로그

1. 등굣길 - lv 3 출처 https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Sol) // 프로그래머스 - 등굣길 import java.util.Arrays; public class Practice2 { public static int solution(int m, int n, int[][] puddles) { int mod = 1000000007; int[][] board = new int[n + 1][m + 1]; for(int i = 0;..

1.스도쿠 - DFS, 재귀함수 (골드 4) https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net Sol) 스터디원 코드 - 스터디원 블로그 /** 0 4 0 0 0 0 2 0 0 0 6 0 0 0 5 0 0 0 2 0 5 0 8 0 0 0 7 0 0 6 0 0 0 0 0 0 5 0 7 0 0 1 9 0 0 0 0 0 0 4 0 0 1 0 0 0 0 3 0 0 0 0 8 0 2 0 0 0 0 0 0 0 9 0 1 0 0 4 7 0 0 * 0 0 0 ..

1. 동적 계획법(Dynamic Programming, DP) - 특별한 속성을 가진 복잡한 문제를 푸는 방법 - 단순한 하위 문제를 나눠서 푼다. Ex) 배낭 문제 - 물품 하나가 추가될 때마다 경우의 수가 2배씩 늘어난다. - 시간복잡도: O(2^n) 2. 메모이제이션(memoization) - 계산 결과를 캐시에 저장해둔 뒤, 나중에 재사용하는 기법 -> 처음 계산할 때, 그 결과를 캐시에 저장한다. - 메모이제이션에 "배열"이 가장 적합하다. -> 배열은 매개변수에 대해 값을 저장할 수 있다. Ex) 메모이제이션을 사용한 피보나치 함수 public static int fibonacciRecursive(int number, int [] cache) { if(number 동적 계획에서 메모이제이션이 ..