import java.io.*;
import java.util.*;
class Main {
static int[] dx = {0, -1, 0}, dy = {1, 0, -1}; // bfs를 위한 델타 배열 생성(위로는 못 올라감)
static int[][] mm, arr;
static int N, M;
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N][M]; // 유적 금화를 저장하는 배열
mm = new int[N][M]; // 메모이제이션(위치, 방향 저장)
// 유적 내 금화 저장
for(int i=0;i<N;i++) {
st = new StringTokenizer(bf.readLine());
for(int j=0;j<M;j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
boolean[][] visited = new boolean[N][M];
visited[N-1][M-1] = true;
mm[0][0] = arr[0][0];
System.out.println((1000000000+dp(N-1, M-1, visited)));
}
public static int dp(int x, int y, boolean[][] visited) {
// if(mm[x][y] != 0) return mm[x][y];
int returnVal = arr[x][y];
int maxRoute = 0;
// 현 위치 기준 좌, 우, 상 에서 내려오는 경우 중 가장 큰 값 체크
for(int i=0;i<3;i++) {
int nX = x+dx[i];
int nY = y+dy[i];
if(isInRange(nX, nY) && !visited[nX][nY]) {
visited[nX][nY] = true;
maxRoute = Math.max(maxRoute, dp(nX, nY, visited));
visited[nX][nY] = false;
}
}
// if(x == N-1 && y == M-1) {
// for(int i=0;i<N;i++) {
// for(int j=0;j<M;j++) {
// System.out.print(visited[i][j]+" ");
// }
// System.out.println();
// }
// }
return mm[x][y] = returnVal + maxRoute;
}
public static boolean isInRange(int x, int y) {
return 0 <= x && x < N && 0 <= y && y < M;
}
}
일단 저는 메모이제이션을 통해 탑다운 방식으로 풀어보려 했어요.
(N-1, M-1) 에서의 최댓값을 구하려면, (N-2, M-1) 과 (N-1, M-2)에서의 최댓값 중 더 큰 것을 고르면 된다고 생각했습니다.
하지만 여기서 논리적인 오류가 발생하는데..
(0, 0)에서 시작한다.
(N-1, M-1)에서의 최댓값을 가지는 경로가 (a, b)를 지난다고 가정했을 때, (a, b)에서의 최댓값을 가지진 않을 수 있다.
이 두 가지를 고려하지 않았습니다...
예를 들어봅시다.
3 5
1 1 1 3 4
0 0 5 2 -1
0 0 1 1 1
의 input이 있다고 가정합니다.
제 코드로 돌려본다면, 12라는 output이 나오게 됩니다.
하지만 정답은 19 입니다.
네
그냥 설계부터 잘못된 코드입니다!
아무튼 그래서 다른 방법을 찾게되었고,
가장 첫 행에서는 왼쪽에서 오른쪽으로밖에 이동할 수 없다.
라는 점을 깨달았습니다.
// 가장 첫 행 계산하기 -> 우측으로밖에 가지 못함
mm[0][0] = arr[0][0];
for(int i=1;i<M;i++) {
mm[0][i] = mm[0][i-1] + arr[0][i];
}
그래서 mm 배열 중 가장 첫 행은, 직전 값에 해당 칸의 value를 더한 값으로 업데이트 해줬습니다.
다음 행부터는 가짓수가 증가합니다.
왼쪽에서 오른쪽으로 이동하거나
오른쪽에서 왼쪽으로 이동하거나
위에서 아래로 이동한다.
이 세 가지입니다.
위에서 아래로 순차적으로 내려올 수 있기 때문에,
두 번째 행부터 차근차근 계산을 해줄겁니다.
각 행마다 fromLeft (왼쪽에서 오른쪽), fromRight (오른쪽에서 왼쪽) 배열을 만들어줍니다.
fromLeft의 가장 왼쪽 값과, fromRight에서 가장 오른쪽 값은, 위에서밖에 내려와 업데이트 되지 못합니다.
FROM : 검색할 테이블(들)을 지정하며, 기본적으로 Cartesian product(데카르트 곱)를 생성
WHERE : 튜플을 선택하기 위한 조건을 지정
여러 테이블의 데카르트 곱을 생성하므로, 반드시 WHERE 조건으로 원하는 튜플만 선택해야 함
select name, course_id
from instructor, teaches
where instructor.ID = teaches.ID;
<br>
### Natural Join
<br>
- 두 테이블 간 동일한 이름의 속성에 대해 자동으로 조인
- 아래 두 SQL문은 같은 결과를 출력한다
```sql
select name, course_id
from instructor natural join teaches;
select name, course_id
from instructor, teaches
where instructor.ID = teaches.ID;
Join ... USING
특정 속성만으로 조인하도록 지정
아래 두 SQL문은 같은 결과를 출력한다
select name, title
from (instructor natural join teaches) join course using (course_id);
select name, title
from instructor natural join teaches, course
where teaches.course_id = course.course_id;
4. Additional Basic Operations
Rename 또는 별칭 사용
속성 및 테이블 별칭: AS 를 사용하여 이름을 재정의
select T.name as instructor_name, S.course_id
from instructor as T, teaches as S
where T.ID = S.ID;
SELF JOIN: 같은 테이블을 두 번 사용 시 별칭 필수
select distinct T.name
from instructor as T, instructor as S
where T.salary > S.salary and S.dept_name = 'Biology';
문자열 연산 및 패턴 매칭
문자열 표기: '로 감싸서 표현, 내부의 작은 따옴표라면 두 번 사용('')
문자열 함수: upper(), lower(), trim() 등
패턴 매칭: LIKE 연산자와 % , _ 등
select dept_name
from department
where building like '%Watson%';
public class Main { static int arr[], parent[]; public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(bf.readLine()); int N = Integer.parseInt(st.nextToken()), M = Integer.parseInt(st.nextToken()); arr = new int[N]; parent = new int[N]; for(int i=0;i<N;i++) { arr[i] = Integer.parseInt(bf.readLine()); parent[i] = i; } for(int i=0;i<M;i++) { st = new StringTokenizer(bf.readLine()); int a = Integer.parseInt(st.nextToken())-1, b = Integer.parseInt(st.nextToken())-1; int fa = find(a), fb = find(b);
인터넷 환경에서 데이터 전송 시 네트워크의 혼잡을 효과적으로 관리하는 것은 매우 중요합니다. 특히 여러 장치가 동시에 데이터를 주고받는 상황에서는 네트워크 혼잡이 발생하기 쉽습니다. 이때 TCP 혼잡 제어(TCP Congestion Control) 메커니즘이 중요한 역할을 합니다.
이번 포스팅에서는 TCP 혼잡 제어의 개념, 동작 원리, 주요 알고리즘에 대해 자세히 알아보겠습니다.
📦 TCP 혼잡 제어란?
TCP 혼잡 제어(Congestion Control) 는 네트워크의 혼잡 상태를 감지하고, 이에 따라 데이터 전송 속도를 조절하여 네트워크의 안정성을 유지하는 메커니즘입니다.
✅ TCP 혼잡 제어의 필요성
네트워크 과부하 방지: 과도한 트래픽으로 인한 패킷 손실 방지
효율적인 대역폭 사용: 가용한 대역폭을 최대한 활용하면서도 안정적인 전송 유지
신뢰성 보장: 데이터가 안정적으로 전송되도록 손실과 재전송을 최소화
⚙️ TCP 혼잡 제어의 핵심 요소
TCP는 네트워크 혼잡을 감지하고 전송 속도를 조절하기 위해 다음과 같은 요소를 활용합니다.
1️⃣ 혼잡 윈도우 (Congestion Window, cwnd)
송신자가 네트워크로 보낼 수 있는 최대 데이터 양을 결정하는 변수입니다.
cwnd 값이 커지면 전송 속도가 증가하고, 작아지면 전송 속도가 감소합니다.
2️⃣ 혼잡 신호 감지 방법
패킷 손실: 타임아웃 발생 또는 3중 중복 ACK(Duplicate ACK) 수신 시 혼잡 발생으로 간주
ACK 수신 속도: ACK가 느리게 도착하면 혼잡 가능성으로 해석
3️⃣ 혼잡 제어 단계
TCP 혼잡 제어는 Slow Start → Congestion Avoidance → Fast Recovery 단계를 반복하며 혼잡 상태에 대응합니다.
🚀 TCP 혼잡 제어 알고리즘
TCP 혼잡 제어는 다음과 같은 3가지 주요 알고리즘으로 구성됩니다.
📈 1. 슬로우 스타트 (Slow Start)
초기 연결 시 또는 혼잡 발생 후 전송 속도를 빠르게 증가시키는 단계입니다.
cwnd를 1 MSS(Maximum Segment Size)로 시작하고, ACK를 받을 때마다 1 MSS씩 증가합니다.
매 RTT마다 전송 속도가 2배로 증가 → 지수적 성장 (Exponential Growth)
동작 예시
cwnd = 1 MSS로 시작 → 첫 번째 패킷 전송
ACK 수신 → cwnd = 2 MSS로 증가
2개의 패킷 전송 → 각각 ACK 수신 시 cwnd = 4 MSS로 증가
이러한 과정이 계속되어 빠르게 전송 속도가 증가합니다.
슬로우 스타트 종료 조건:
cwnd가 ssthresh(slow start threshold) 에 도달하면 혼잡 회피(Congestion Avoidance)로 전환
