나를 돌아보기
공부를 너무 안하는 모습이 보였다.
동기가 없는 걸까..? 왜 안하는 걸까..? 내가 게으른 건가? 그렇다 치곤 매일 운동하며 독서는 하고 있다. 아니 어쩌면 개발자라는 직업을 갖기 싫은 걸까? 아니면 빨리 취직하고 싶은 조급한 마음에 공부하는 것이 너무 많음을 알고 두려워하는 걸까? 나이때문에 내 자신은 안될거라고 생각하는 걸까? 도무지 모르겠다. 개발을 시작할때는 개발 하는 것이 너무 즐거웠는데, 지금은 즐겁기보단 버거운 것 같다. 투자하는 시간에 비해 목표만 너무 높게 잡은 걸까? 자존감이 바닥이다.. 공부를 잘못해오고 있는 걸까? 진짜 내가 한 선택의 순간순간들이 내 인생을 갉아먹은 걸까..? 지금 심정은 진~짜 아무것도 하고 싶지 않다. 이런 마음이 들땐, 하나님께 죄송하다. 뭔가 내 스스로가 하나님이 세워 놓으신 완벽한 계획을 뒤로 늦춰지게 하는 기분이다. 너어어무 답답하다. 뭐가 문제일까? 표면적으로 드러나는 것은 우선 내가 하는 공부 방식이다.
내 습관대로 해왔던 공부방식이 맺는 지금 나라는 열매는 뭐 제대로 된게 아무것도 없다. 그럼 나는 지금까지 공부를 어떻게 해왔는가?
시간을 정해놓고, 새로운 정보를 습득 끝.. 새로운 정보를 습득하고 그 당시만 이해하고 넘어가는 공부 방식이였다. 복습은 안했다. 복습은 공부하다면 알아서 되겠지~ 이 생각으로 했다. 공부를 하는 원초적인 이유는 내가 몰랐던 것을 알게 되는 것인데, 새로 알게된 정보에대해서 안다고 착각하고 넘어간 것 같다. 누군가에게 설명하는 공부를 해야하는데, 그냥 눈으로만 읽고 이런 내용이 있구나~ 이런식으로 공부했던 것 같다. 누군가에게 설명하듯이 공부를 하고, 공부했던 내용에 대해서 복습하는 공부 방식으로 완전히 바꾸어야 겠다. 내 마인드 또한 바꿔야겠다. "이걸 한다고 되겠어?" 이 마인드 보다는 "된다고 생각하고 해보자"로 마인드를 변경하자..! 하나님과 함께 하는데 무엇을 못하리요 믿는자에게 능치 못함이 무엇이 있으리요!! 이 전공을 택하게 하신 하나님의 크신 계획을 기다리고 인내하며 오늘 하루도 다시 새롭게 공부에 몰두해보자!! 완벽함은 오직 하나님만 가능하신 것이다. 나는 완벽할 수 없다. 공부또한 완벽히 하는 것은 불가능하다. 완벽에 집착하지 말고, 지금 현재에 최선을 다하자..! 감사합니다 주님!
알고리즘
DP
문제 풀이 흐름 복습
1. 완전 탐색이 가능한가?
2. 경우의 수가 너무 많아서 시간초과 날꺼 같은데?
3. 메모이제이션이 가능한가?
4. 메모이제이션 할 배열이 너무 큰데? 그리디 아니면 다른 알고리즘으로 접근해보자.
백준 - 2240번
https://www.acmicpc.net/problem/2240
2240번: 자두나무
자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어
www.acmicpc.net
코드 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int T;
public static int W;
public static int[] zadu;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
T = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
zadu = new int[T + 1];
for (int i = 1; i <= T; i++) {
zadu[i] = Integer.parseInt(br.readLine());
}
int[][][] dp = new int[3][T + 1][W + 2];
for (int i = 1; i <= T; i++) { // 시간
for (int j = 1; j <= W + 1; j++) { // 이동 횟수
if (zadu[i] == 1) {
// 가만히 있다가 먹거나 아니면 이동해서 먹거나 둘 중 큰걸로 먹어~
dp[1][i][j] = Math.max(dp[1][i - 1][j] + 1, dp[2][i - 1][j - 1] + 1);
dp[2][i][j] = Math.max(dp[2][i - 1][j], dp[1][i - 1][j - 1]);
} else {
if (i == 1 && j == 1) { // 어차피 못먹어~
continue;
}
dp[1][i][j] = Math.max(dp[1][i - 1][j], dp[2][i - 1][j - 1]);
dp[2][i][j] = Math.max(dp[1][i - 1][j - 1] + 1, dp[2][i - 1][j] + 1);
}
}
}
int result = Integer.MIN_VALUE;
for (int i = 1; i <= W + 1; i++) {
result = Math.max(result, Math.max(dp[1][T][i], dp[2][T][i]));
}
System.out.println(result);
}
}
이 문제는 여전히 완벽 이해가 아직 안된다.
이 문제의 핵심 정보는 1번인지 2번인지의 위치, 시간, 움직임 횟수다.
이 3가지 요소에 따라 자두의 최댓값이 달라진다. 그러므로 이 3가지 요소를 3차원 배열로 두자!
쉽게 생각해보자. 자두를 먹기위해서는 크게 2가지 방법이 존재한다.
현재 1번위치에 있다고 가정하면,
(1) 1번 위치에서 가만히 서있기
(2) 1번 위치에서 2번 위치로 이동하기
자두가 1번위치에 떨어진 경우를 생각해보면 자두를 먹는 2가지 방법이 존재한다.
(1) 1번위치에 계속 가만히 있다가 자두를 먹는 경우
(2) 2번위치에서 1번위치로 이동하여 자두를 먹는 경우
마찬가지로 자두가 2번 위치에서 떨어진 경우를 생각해보면 자두를 먹는 2가지 방법이 존재한다.
(1) 2번위치에 계속 가만히 있다가 자두를 먹는 경우
(2) 1번위치에서 2번위치로 이동하여 자두를 먹는 경우
점화식을 생각해보자 (1번나무에 자두가 떨어지는 경우)
dp[1][i][j] = Math.max(dp[1][i-1][j] + 1, dp[2][i-1][j-1] + 1);
dp[2][i][j] = Math.max(dp[2][i-1][j], dp[1][i-1][j-1]);
DP에서 최댓값을 추출해야한다.
그 기준은 우선 자두를 가장 많이 먹게되는 경우는 시간이 다지나고 마지막 시간일때가 가장 크다. (T 시간일때)
그리고 비교해주어야 할 것은 움직임 횟수에 따른 최대로 먹을 수 있는 자두의 개수를 비교해주면 된다.
for (int i = 1; i <= W + 1; i++) {
result = Math.max(result, Math.max(dp[1][T][i], dp[2][T][i]));
}
백준 - 15989번
https://www.acmicpc.net/problem/15989
15989번: 1, 2, 3 더하기 4
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2
www.acmicpc.net
코드 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int[][] dp = new int[10001][4];
int t = Integer.parseInt(br.readLine());
// 합이 3이하인 경우 사전에 초기값 1을 넣어준다.
dp[1][1] = dp[2][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1;
for (int i = 4; i <= 10000; i++) {
dp[i][1] = dp[i - 1][1];
dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3];
}
for (int i = 0; i < t; i++) {
int n = Integer.parseInt(br.readLine());
sb.append(dp[n][1] + dp[n][2] + dp[n][3]);
if (i < t - 1) {
sb.append("\n");
}
}
System.out.println(sb);
br.close();
}
}
DP문제에서 경우의 수가 나오는 경우 다 더해주면 된다.
점화식을 어떻게 세울까..? 점화식조차 세울 수 없다..
문제가 너무 어렵다.
풀이를 보고 다시 풀어보았다.
1,2,3으로 구성된 숫자로 중복을 포함하지 않고 나타낼 수 있는 모든 경우를 세주어야 한다.
우선 1,2,3의 구성을 먼저 살펴보자.
1은 1 1개 존재
2는 1+1, 2 2개 존재
3은 1+1+1, 1+2, 3 3개 존재
이 문제에서 숫자를 더해줄 수 있는 경우는 1,2,3 이 3가지밖에 존재하지 않는다.
그럼 이 3가지 숫자를 기준으로 생각하면 되지 않을까? 어떻게 말인가?
1을 더해주어야 하는경우, 2를 더해주어야 하는 경우, 3을 더해주어야 하는 경우로 나눠보는 것이다.
현재 주어진 값이 N인경우
1을 더해주어야 하는 경우는 N-1경우에다 1을 더해주어야 하는 경우를 세고,
2를 더해주어야 하는 경우는 N-2경우에다 2를 더해주어야 하는 경우를 세고,
3을 더해주어야 하는 경우는 N-3경우에다 3을 더해주어야 하는 경우를 세면 되지 않을까?
최종적으로는 이 3가지 경우를 더해서 나타내주면 되지 않을까? 라는 생각을 해본다.
4를 예시로 들었을때,
1을 더해주어야 하는 경우는 1로만 이뤄진 경우이므로 다음과 같이 보아도 된다.
dp[4][1] = dp[3][1]
dp[3][1]은 여기서 1+1+1을 의미한다.
dp[4][1]은 4인 숫자의 경우를 세려고 하는데, 그 중 1을 더해서 4를 나타낼 수 있는 경우라는 의미를 내포하고 있다.
1+1+1+1 과 같은 의미를 나타내므로, dp[3][1](1+1+1)과 같다고 볼 수 있다.
2를 더해주어야 하는 경우를 생각해보자.
2를 더해주어야 하는 경우는 우선 주어진 숫자보다 2가 작은 수에다가 2를 더해주어야 한다.
dp[4][2] = dp[2][1] + dp[2][2];
dp[2][1]은 여기서 1+1을 의미한다. 왜? 2인 숫자의 경우를 세려고 하는데, 그 중 1을 더해서 2를 나타낼 수 있는 경우는 1+1밖에 존재하지 않는다.
dp[2][2]은 여기서 2를 의미한다. 왜? 2인 숫자의 경우를 세려고 하는데, 2를 사용하는 경우는 2밖에 존재하지 않는다.
dp[4][2]는 4인 숫자의 경우를 세려고 하는데, 그 중 2를 더해서 4를 나타낼 수 있는 경우라는 의미를 나타낸다.
dp[2][1] + 2 (1+1+2)를 한경우와 dp[2][2] + 2 (2+2)를 한경우를 생각하면 된다.
3을 더해주어야 하는 경우를 생각해보자.
3을 더해주는 경우는 우선 주어진 숫자보다 3이 작은 수에다가 3을 더해주어야 한다.
dp[4][3] = dp[1][1] + dp[1][2] + dp[1][3];
3을 만드는 경우는 3가지가 존재한다.
(1+1+1, 1+2, 3)
지금은 4이기 때문에 dp[1][2]와 dp[1][3]은 0으로 존재하지 않을 것이다.
4말고 6일때를 생각해보자.
dp[6][3] = dp[3][1] + dp[3][2] + dp[3][3] 이 성립할까?
숫자 6에 3을 더해 나타내기 위해서는
1+1+1+3
1+2+3
3+3
1+1+1 은 dp[3][1]을 나타내고, 1+2는 dp[3][2]를 나타내고, 3은 dp[3][3]을 나타내므로 성립하는 것을 알 수 있다.
점화식을 유추해보자.
dp[n][1] = dp[n-1][1];
dp[n][2] = dp[n-2][1] + dp[n-2][2];
dp[n][3] = dp[n-3][1] + dp[n-3][2] + dp[n-3][3];
dp가 너무 어렵다..!
DP의 종류
(1) 바텀업 - 반복문 구조를 자기조 있는 DP
(2) 탑다운 - 재귀적인 구조를 가지고 있는 DP
DP를 잘하는 팁
1. 문제를 잘 정의하는 능력 필요
2. 부분문제들 사이의 관계를 파악하는 능력 필요
펜윅트리
이진트리기반의 자료구조이며 세그먼트 트리의 원리를 가지고 있다.
이진 트리란?
각 노드가 최대 2개의 자식노드를 가지는 트리
최대 2개이므로, 자식이 없을 수 도 있고, 한 개만 존재할 수 도 있다.
세그먼트 트리란?
1. 이진트리에
2. 어떤 쿼리에 대해 최적화한 값을 담아 놓은 것을 말한다.
누적합의 경우 정적배열에서 사용되지만 동적배열에서 그리고 최소값 등 조금 복잡한 쿼리의 경우는 이런식으로 세그먼트 트리를 만들어서 해야 한다.
요소가 업데이트 되더라도 트리의 높이가 logN이기 때문에 연산을 하는데 시간이 그렇게 많이 걸리지 않는다.
업데이트, 쿼리 모두 O(logN)의 시간복잡도를 가진다. 문제를 풀 때 어떠한 구간에 대해 구간 쿼리를 표현할 때 시간복잡도가 많으니 안될 것 같거나 O(logN)짜리의 알고리즘이 필요한 것 같다라고 할 때 생각하고 써야 하는 알고리즘이다.
ex)
최솟값을 구한다고 해보는 경우 0 ~ 3 까지의 요소의 최솟값은 한번의 LEVEL 2만에 구할 수 있다.
짧은 시간만에 구할 수 있다. 아무리 끝까지 찾으려 해도 O(logN) 밖에 걸리지 않는다.
이러한 세그먼트 트리의 특징이 담긴 펜윅트리이다.
펜윅트리란?
최하위 노드, (idx & -idx)를 배가며 갱신하고 업데이트하는 간단한 트리, Binary Indexed Tree라고도 함.
세그먼트 트리와는 다르게 모든 세그먼트를 만들 필요가 없음.
최하위 노드를 갱신해가며 업데이트 하는 트리이다. 세그먼트트리와는 달리 모든 세그먼트를 만들 필요가 없으며
이진트리 인덱스를 효율적으로 계산 및 업데이트 할 수 있는 자료구조
백준 - 2042 구간합 구하기
https://www.acmicpc.net/problem/2042
2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
Spring
docker를 사용해 프로젝트를 구축하려고 한다.
mysql에 대한 이미지 만들기
Error : Ports are not avaliable : exposing port TCP 0.0.0.0:3306 -> 0.0.0.0.0: listen tcp 0.0.0.0:3306: bind: address already in use
포트번호가 이미 사용중이라고 나와있다..
정말 사용중인지 직접 확인해보자!
3306포트번호로 잘 사용 중이다.
mysql workbench에서 사용중이다.
호스트의 3307 포트를 컨테이너의 3306 포트에 매핑해서 해결해보자!
생성 완료
intelij에서 연동이 잘 되는지 확인
Redis에 대한 이미지 만들기
컨테이너 생성해주기
Redis insight에서 확인완료
'Backend > 공부 일지' 카테고리의 다른 글
| 2024/03/13(수) (3) | 2024.03.14 |
|---|---|
| 2024/03/12(화) (0) | 2024.03.13 |
| 2024/03/05(화) 가자! 네카라쿠배당토 (0) | 2024.03.05 |
| 2024/03/04(월) (0) | 2024.03.05 |
| 2024/03/03(일) (0) | 2024.03.04 |
