분류 전체보기
[BaekJoon] 백준 1915번 가장 큰 정사각형
[BaekJoon] 백준 -번 문제이름 문제: https://www.acmicpc.net/problem/1915 내코드 - 점화식을 생각해내기 약간 까다로운 dp문제였다. - 점화식은 다음과 같다. - dp[i][j] = [i][j]칸을 정사각형의 가장 오른쪽 아래라고 했을 때 만들수 있는 가장 큰 정사각형의 한 변의 길이 - dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 - 왜 위의 점화식이 성립하는지는 그림을 그려보면 쉽게 알 수 있다. import java.io.*; import java.util.StringTokenizer; public class test { public static void main(String[] args) throws ..
[BaekJoon] 백준 9084번 동전
[BaekJoon] 백준 9084번 동전 문제: https://www.acmicpc.net/problem/9084 내코드 - 조금 이해하기 어려운 DP문제였다. 나중에 다시 풀어봐야겠다. - 점화식은 다음과 같다. d[0] = 1; for (i = 1; i
[BaekJoon] 백준 11052 카드 구매하기
[BaekJoon] 백준 11052 카드 구매하기 문제: https://www.acmicpc.net/problem/11052 내코드 -DP 문제였다. 주어진 문제에 따르면 점화식은 아래와 같다. 카드 N개를 구매할 때 최대 비용 = MAX(i=1~N)(카드 i개 들어있는 카드팩 구매하는 비용 + 카드 N-i개 들어있는 카드팩 구매하는 비용) import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] result = new int[N+1]; int[] prices = new int[N+1]; fo..
[BaekJoon] 백준 2011번 암호코드
[BaekJoon] 백준 2011번 암호코드 문제: https://www.acmicpc.net/problem/2011 내코드 다이나믹 프로그래밍에 익숙하지 않아서 다이나믹 프로그래밍 문제를 찾다가 발견해서 풀었다. 즉, 다이나믹 프로그래밍 문제인 것을 알고 풀었다. 우선 점화식을 찾았다. f("25114")가 25114에서 나올 수 있는 암호의 개수라고 하자. f("25114") = f("2511") + f("251")이 된다. 즉, f(n) = f(n[:-1]) + f(n[:-2]) 이다. 이렇게 금방 점화식을 찾을 수 있다. 두번째로 생각해야 할 부분은 메모이제이션이다. 시간 초과를 피하기 위해 딕셔너리를 만들어 줬다. 여기서는 f(n)에서 n의 길이가 같다면 f(n)이 같다는 특징이 있다. 즉, 길..
[Spring] 입문2
Spring 입문2 Spring 입문2 오늘 배운 부분 파일 구성 회원 도메인과 레포지토리 만들기 package hello.hellospring.domain; public class Member { private Long id; private String name; // private 변수에 대해 getter setter public Long getId() { return id; } public void setId(Long id) { this.id = id; } public String getName() { return name; } public void setName(String name) { this.name = name; } } domain 폴더를 만들고 안에 Member 모델을 작성해줄 클래스를 ..
[Spring] 입문1(feat. 인프런 김영한님 강의)
Spring 입문1(feat.인프런 김영한님 강의) Spring boot 기초 우선 오늘 공부한 내용의 폴더 구조는 다음과 같다. 프로젝트는 HelloSpringApplication 파일에서 시작된다. Controller는 요청이 들어왔을 때 이를 받아서 처리해주는 부분이고, resources는 정적 컨텐츠를 저장하는 부분인데 단순 정적 컨텐츠와 템플릿 엔진을 썼을 경우를 위해 static, templates로 분리해주었다. 그 외에 service나 다른 파일들은 다음 강의에서 설명한다. 정적 컨텐츠 // java/hello.hellospring/controller/helloController.java @Controller public class HelloController { @GetMapping("h..
[Algorithm] 다이나믹 프로그래밍 Dynamic Programming
다이나믹 프로그래밍 (Dynamic Programming, DP)란? 다이나믹 프로그래밍 (이하 DP)란 여러개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘이다. 분할정복과 비슷하다고 생각할 수 있지만 분할정복은 작은 문제가 중복이 일어나지 않고, DP는 반복(작은 문제의 결과가 같다)된다. 그래서 DP에서는 작은 문제들이 반복되는 것을 이용해 문제를 풀어나간다. 포인트는 모든 작은 문제들은 중복을 제거하고 한번만 풀어야 한다는 점이다. 따라서 정답을 구한 작은 문제들을 어딘가에 메모(Memoization)해둔다. 다시 그보다 큰 문제를 풀 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다. 많이 언급하는 피보나치 수열 문제를 예시로 들어보자. ..
Express 폴더 구조
Express 폴더 구조 Express로 개발을 하면서 느꼈던 장점 중 하나가 자유도가 높다는 점이다. 폴더 구조나 툴, 미들웨어 등 선택할 수 있는 폭이 넓다. 하지만 큰 규모의 프로젝트를 해본적이 없는 나에겐 틀이 없다는게 더 어렵게 느껴졌다. (그래서 어느정도의 구조가 정해져 있는 nestjs가 나온걸수도..!) 그래서 검색을 해보다가 nestjs라는 좋은 프레임워크를 발견했지만 이미 개발을 시작한 상황에서 프레임워크를 변경하기는 어려웠다. + nestjs에 대해 조금 훑어보다가 Spring의 구조와 비슷한걸 깨달았다. 최근에 Spring을 공부하고 있는데 처음에는 구조 파악이 어려웠는데 이제 뭔가 느낌을 알 것 같은 그런 느낌..!! 프로젝트 초반에 가장 고민했던 부분은 프로젝트 구조였다. 어떤 ..