에코 서버란 클라이언트에서 수신 된 데이터를 그대로 다시 클라이언트에게 되돌려 보내는 서버를 의미한다.

Iterative란 반복적이라는 의미로 각 클라이언트의 연결 요청을 순차적으로 처리하는 서버를 의미한다.

이 서버는 한 번에 하나의 클라이언트 요청만 처리하며, 하나의 연결이 완료된 후 다음 연결을 처리한다.

 

// Server

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <winsock2.h>
#include <ws2tcpip.h>
#pragma comment(lib, "ws2_32.lib")
#define BUF_SIZE 1024
void ErrorHandling(char* message);

int main(int argc, char* argv[]) {
	WSADATA wsaData;
	SOCKET hServSock, hClntSock;
	char message[BUF_SIZE];
	int strLen, i;

	SOCKADDR_IN servAddr, clntAddr;
	int clntAddrSize;
	

	if (argc != 2) {
		printf("Usage : %s <port>\n", argv[0]);
		exit(1);
	}

	if (WSAStartup(MAKEWORD(2, 2), &wsaData) != 0) {
		ErrorHandling("WSAStartup() error!");
	}

	hServSock = socket(PF_INET, SOCK_STREAM, 0);
	if (hServSock == INVALID_SOCKET) {
		ErrorHandling("socket() error!");
	}

	memset(&servAddr, 0, sizeof(servAddr));
	servAddr.sin_family = AF_INET;
	servAddr.sin_addr.s_addr = htonl(INADDR_ANY);
	servAddr.sin_port = htons(atoi(argv[1]));

	if (bind(hServSock, (SOCKADDR*)&servAddr, sizeof(servAddr)) == SOCKET_ERROR) {
		ErrorHandling("bind() error!");
	}

	if (listen(hServSock, 5) == SOCKET_ERROR) {
		ErrorHandling("listen() error!");
	}

	clntAddrSize = sizeof(clntAddr);

	// 연결 요청 대기 큐의 크기만큼 반복
	for (i = 0; i < 5; i++) {
		
		hClntSock = accept(hServSock, (SOCKADDR*)&clntAddr, &clntAddrSize);
		if (hClntSock == -1) {
			ErrorHandling("accept() error!");
		}
        // 연결 되었다면 몇 번째 클라이언트인지 출력
		else {
			printf("Connected client %d \n", i + 1);
		}
		
        // 클라이언트한테 데이터를 받으면
		while ((strLen = recv(hClntSock, message, BUF_SIZE, 0)) != 0) {
        	// 그대로 돌려주기
			send(hClntSock, message, strLen, 0);
		}

		closesocket(hClntSock);
	}
	
	closesocket(hServSock);
	WSACleanup();

	return 0;
}

void ErrorHandling(char* message) {
	fputs(message, stderr);
	fputs("\n", stderr);
	exit(1);
}

 

// Client

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <winsock2.h>
#include <ws2tcpip.h>
#pragma comment(lib, "ws2_32.lib")
#define BUF_SIZE 1024
#define _WINSOCK_DEPRECATED_NO_WARNINGS
void ErrorHandling(char* message);

int main(int argc, char* argv[])
{
	WSADATA wsaData;
	SOCKET hSocket;
	char message[BUF_SIZE];
	int strLen;
	SOCKADDR_IN servAddr;

	if (argc != 3) {
		printf("Usage : %s <port>\n", argv[0]);
		exit(1);
	}

	if (WSAStartup(MAKEWORD(2, 2), &wsaData) != 0) {
		ErrorHandling("WSAStartup() error!");
	}

	hSocket = socket(PF_INET, SOCK_STREAM, 0);
	if (hSocket == INVALID_SOCKET) {
		ErrorHandling("socket() error!");
	}

	memset(&servAddr, 0, sizeof(servAddr));
	servAddr.sin_family = AF_INET;
	servAddr.sin_addr.s_addr = inet_addr(argv[1]);
	servAddr.sin_port = htons(atoi(argv[2]));

	if (connect(hSocket, (SOCKADDR*)&servAddr, sizeof(servAddr)) == SOCKET_ERROR) {
		ErrorHandling("connect() error!");
	}
	else {
		printf("Connected.........");
	}

	while (1) {
		fputs("Input message(Q to quit): ", stdout);
		fgets(message, BUF_SIZE, stdin);
		
        // 입력 값이 q or Q이면 종료
		if (!strcmp(message, "q\n") || !strcmp(message, "Q\n")) {
			break;
		}
		
        // 입력 값 보내기
		send(hSocket, message, strlen(message), 0);
		strLen = recv(hSocket, message, BUF_SIZE - 1, 0);
		message[strLen] = 0;
        // 서버로부터 받은 값 출력
		printf("Message from server: %s", message);
	}

	closesocket(hSocket);
	WSACleanup();

	return 0;
}

void ErrorHandling(char* message) {
	fputs(message, stderr);
	fputs("\n", stderr);
	exit(1);
}

 

 

2개의 클라이언트를 실행하였다.

2개의 클라이언트를 실행 했으나 서버에는 Connected client1만 뜬 상태에서 client1과 1대1 통신이 진행되었다.

client1에서 입력한 값을 서버에서 그대로 돌려주었고 q를 눌러 연결을 끊었을 때 서버에서 Connected clinet2가 뜨며 client2와 연결이 되었다.

멈춰있던 client2에서도 입력이 가능해졌고 입력값을 그대로 돌려받았다.

 

 

위의 Iterative 에코 클라이언트에서  문제가 생길 수 있는 부분이 있다.

while (1) {
    fputs("Input message(Q to quit): ", stdout);
    fgets(message, BUF_SIZE, stdin);

    if (!strcmp(message, "q\n") || !strcmp(message, "Q\n")) {
        break;
    }

    send(hSocket, message, strlen(message), 0);
    strLen = recv(hSocket, message, BUF_SIZE - 1, 0);
    message[strLen] = 0;
    printf("Message from server: %s", message);
}

해당 부분에서 입력 받은 데이터를 send를 통해 통째로 서버에 보내고 있다.

다음줄에서는 recv를 통해 서버에서 데이터를 통째로 받고 있다.

 

서버에서 데이터를 다 전달하지 못하였는데 recv를 해버리는 경우 문제가 발생할 수 있다.

 

while (1) {
    fputs("Input message(Q to quit): ", stdout);
    fgets(message, BUF_SIZE, stdin);

    if (!strcmp(message, "q\n") || !strcmp(message, "Q\n")) {
        break;
    }

    strLen = send(hSocket, message, strlen(message), 0);
    recvLen = 0;

    while (recvLen < strLen) {
        recvCnt = recv(hSocket, message, BUF_SIZE - 1, 0);
        if (recvCnt == -1) {
            ErrorHandling("recv() error!");
        }
        recvLen += recvCnt;
    }

    message[strLen] = 0;
    printf("Message from server: %s", message);
}

위와 같이 바꾸어 주면 해당 문제를 해결할 수 있다.

strLen에 send 해주는 message의 길이를 저장해 둔 후 recv한 데이터의 길이가 strLen보다 커질 때 while을 빠져나와 출력을 해주면 된다.

'네트워크' 카테고리의 다른 글

소켓 프로그래밍 - TCP 소켓  (0) 2023.09.10
ReaderWriterLock 구현  (0) 2023.08.05
ReaderWriterLock  (0) 2023.08.04
AutoResetEvent  (0) 2023.08.03
SpinLock  (0) 2023.08.02
// Server

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <winsock2.h>
#include <ws2tcpip.h>
#pragma comment(lib, "ws2_32.lib")
void ErrorHandling(char* message);

int main(int argc, char* argv[]) {
	WSADATA wsaData;
	SOCKET hServSock, hClntSock;
	SOCKADDR_IN servAddr, clntAddr;

	int szClntAddr;
	char message[] = "Hello World!";

	// argc가 2가 아니라면 즉, 포트번호가 설정이 안되었다면 종료
	if (argc != 2) {
		printf("Usage : %s <port>\n", argv[0]);
		exit(1);
	}
    
	// Winsock 라이브러리의 초기화를 수행
	if (WSAStartup(MAKEWORD(2, 2), &wsaData) != 0) {
		ErrorHandling("WSAStartup() error!");
	}
    
	// 소켓을 생성하며, 이 소켓은 서버와 클라이언트 간의 연결에 사용
	hServSock = socket(PF_INET, SOCK_STREAM, 0);
	if (hServSock == INVALID_SOCKET) {
		ErrorHandling("socket() error!");
	}
    
	// servAddr 구조체를 0으로 초기화
	// INADDR_ANY를 사용하여 소켓이 동작하는 컴퓨터의 IP주소를 자동으로 할당
	memset(&servAddr, 0, sizeof(servAddr));
	servAddr.sin_family = AF_INET;
	servAddr.sin_addr.s_addr = htonl(INADDR_ANY);
	servAddr.sin_port = htons(atoi(argv[1]));

	// 생성한 소켓에 주소와 포트 번호를 바인딩
	if (bind(hServSock, (SOCKADDR*)&servAddr, sizeof(servAddr)) == SOCKET_ERROR) {
		ErrorHandling("bind() error!");
	}

	// 클라이언의 연결 요청을 기다리기 시작
	// 연결 요청 대기 큐의 크기를 5로 설정하여 클라이언트의 연결 요청을 5개까지 대기 가능
	if (listen(hServSock, 5) == SOCKET_ERROR) {
		ErrorHandling("listen() error!");
	}

	// 클라이언트의 연결 요청을 수락하고, 연결된 클라이언트와의 통신을 위한 새로운 소켓을 반환
	szClntAddr = sizeof(clntAddr);
	hClntSock = accept(hServSock, (SOCKADDR*)&clntAddr, &szClntAddr);
	if (hClntSock == INVALID_SOCKET) {
		ErrorHandling("accept() error!");
	}

	// 연결된 클라이언트에게 "Hello World!" 메시지를 전송
	send(hClntSock, message, sizeof(message), 0);
    
	// 더 이상 필요하지 않은 소켓을 닫기
	closesocket(hClntSock);
	closesocket(hServSock);
    
	// Winsock 라이브러리의 사용을 종료하고, 할당된 리소스를 해제
	WSACleanup();

	return 0;
}

void ErrorHandling(char* message) {
	fputs(message, stderr);
	fputs("\n", stderr);
	exit(1);
}

 

// Client

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <winsock2.h>
#include <ws2tcpip.h>
#pragma comment(lib, "ws2_32.lib")
void ErrorHandling(char* message);

int main(int argc, char* argv[])
{
	WSADATA wsaData;
	SOCKET hSocket;
	SOCKADDR_IN servAddr;

	char message[30];
	int strLen = 0;
	int idx = 0, readLen = 0;
	
    // argc가 3이 아니라면 즉, IP와 포트번호가 설정이 안되었다면 종료
	if (argc != 3) {
		printf("Usage : %s <port>\n", argv[0]);
		exit(1);
	}

	if (WSAStartup(MAKEWORD(2, 2), &wsaData) != 0) {
		ErrorHandling("WSAStartup() error!");
	}

	hSocket = socket(PF_INET, SOCK_STREAM, 0);
	if (hSocket == INVALID_SOCKET) {
		ErrorHandling("socket() error!");
	}

	// 사용자가 제공한 IP주소, 포트번호를 알맞는 형식으로 변환
	memset(&servAddr, 0, sizeof(servAddr));
	servAddr.sin_family = AF_INET;
	servAddr.sin_addr.s_addr = inet_addr(argv[1]);
	servAddr.sin_port = htons(atoi(argv[2]));

	// 위에서 설정한 서버의 주소와 포트번호에 연결 시도
	if (connect(hSocket, (SOCKADDR*)&servAddr, sizeof(servAddr)) == SOCKET_ERROR) {
		ErrorHandling("connect() error!");
	}

	// 서버로부터 데이터를 1바이트씩 수신
	while (readLen = recv(hSocket, &message[idx++], 1, 0)) {
		if (readLen == -1) {
			ErrorHandling("read() error!");
		}

		strLen += readLen;
	}

	// 서버로부터 받은 메세지와 길이를 출력
	printf("Message from server: %s \n", message);
	printf("Function read call count: %d", strLen);

	closesocket(hSocket);
	WSACleanup();

	return 0;
}

void ErrorHandling(char* message) {
	fputs(message, stderr);
	fputs("\n", stderr);
	exit(1);
}

포트번호를 9190을 설정한 후 실행 결과

서버에서 설정한 Hello World! 메세지를 클라이언트에서 수신했다.

'네트워크' 카테고리의 다른 글

소켓 프로그래밍 - Iterative 에코 서버  (0) 2023.09.10
ReaderWriterLock 구현  (0) 2023.08.05
ReaderWriterLock  (0) 2023.08.04
AutoResetEvent  (0) 2023.08.03
SpinLock  (0) 2023.08.02

문제 출처 : https://www.acmicpc.net/problem/2458

 

2458번: 키 순서

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여

www.acmicpc.net

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, a, b, cnt = 0;
    cin >> n >> m;
    int arr[501][501= { 0 };
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        arr[a][b] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) arr[i][j] = 1;
        }
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (arr[i][k] == 1 && arr[k][j] == 1) arr[i][j] = 1;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            arr[i][j] = max(arr[i][j], arr[j][i]);
            arr[j][i] = max(arr[i][j], arr[j][i]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (arr[i][j] == 0break;
            if (j == n) cnt++;
        }
    }
    cout << cnt;
    return 0;
}
cs

 

알고리즘

- 그래프 이론

- 그래프 탐색

- 플로이드-워셜

 

키 순서를 알기 위해서는 자기보다 큰 사람이 누구인지, 작은 사람이 누구인지 모두 알고 있어야 한다.

자기 자신과는 키 비교를 안해도 순서를 알 수 있기 때문에 1로 체크해준다.

키를 비교한 결과 a < b 를 입력받고 arr[a][b] = 1로 체크해준다.

플로이드-워셜 알고리즘을 돌려주면 자기보다 큰 사람이 체크 된다.

배열을 돌며 반대의 경우도 체크하여 자기보다 작은 사람을 체크해준다.

배열을 돌며 0이 하나라도 있다면 비교 불가이므로 넘어간다.

모두 1이라면 비교 가능이므로 cnt를 1 올려준다.

 

플로이드-워셜 알고리즘 이후 작은 사람을 체크 하는 이유

체크 후에 돌리게 된다면 예제와 같은 경우 3 -> 4 -> 5로 3과 5가 이어지게 되어 오답이 나온다.

플로이드-워셜 이후 체크를 한다면 3 -> 4, 4 -> 3, 5 -> 4, 4 -> 5로만 이어지고 3과 5는 이어지지 않아 정답이 제대로 나온다. 

문제 출처 : https://www.acmicpc.net/problem/5972

 

5972번: 택배 배송

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는

www.acmicpc.net

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int dis[50001];
vector<vector<pair<intint>>> v(50001);
 
void dijk(int start) {
    priority_queue<pair<intint>vector<pair<intint>>, greater<pair<intint>>> pq;
    pq.push({ 0, start });
    dis[start] = 0;
    int distance, now, cost;
 
    while (!pq.empty()) {
        distance = pq.top().first;
        now = pq.top().second;
        pq.pop();
 
        if (dis[now] < distance) continue;
 
        for (int i = 0; i < v[now].size(); i++) {
            cost = distance + v[now][i].second;
            if (cost < dis[v[now][i].first]) {
                dis[v[now][i].first] = cost;
                pq.push({ cost, v[now][i].first });
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, a, b, c, s, e;
    cin >> n >> m;
    for (int i = 0; i <= n; i++) {
        dis[i] = 1000000000;
    }
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
        v[b].push_back(make_pair(a, c));
    }
    dijk(1);
    cout << dis[n];
    return 0;
}
cs

알고리즘

- 그래프 이론

- 데이크스트라

 

최대 헛간의 개수 만큼 비용배열을 선언하고 무한(10억)값을 넣어준다.
두 개의 헛간과 소 마릿수를 입력 받아 v[헛간1]에 pair(헛간2, 소 마릿수)을 넣어준다.

헛간2에서 헛간1로도 이동 가능하므로 v[헛간2]에 pair(헛간1, 소 마릿수)도 같이 넣어준다.

 

dijk(헛간1) 함수를 돌려준다.

dis[헛간N]을 출력한다.

dijk 함수
오름차순 우선순위큐(pair)를 선언한다. (마릿수 오름차순으로 정렬)
start에서 start까지의 마릿수는 0이므로 (0, start)를 넣는다.
dis[start]도 0으로 업데이트 한다.

큐가 빌 때까지 반복문을 돈다.

distance에는 큐 top의 첫번째 값을, now에는 큐 top의 두번째 값을 넣고 pop 한다.

dis[now] < distance 라면 이미 체크한 노드이므로 다음 노드를 확인한다.

now와 연결된 노드를 모두 확인한다.
start에서 해당 노드에 가는 비용은 now까지의 비용과 now에서 해당 노드로 가는 비용의 합이다.
만약 방금 구한 값이 비용배열에 있는 값보다 작다면 최소비용이므로 업데이트 하고 큐에 넣어준다.

문제 출처 : https://www.acmicpc.net/problem/17216

 

17216번: 가장 큰 감소 부분 수열

수열 A가 주어졌을 때, 그 수열의 감소 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 인 경우에 합이 가장 큰 감소 부분 수열

www.acmicpc.net

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, result = 0;
    cin >> n;
    int arr[1001= {0}, dp[1001= {0};
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    dp[0= result = arr[0];
    for (int i = 1; i < n; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (arr[i] < arr[j] && dp[i] < dp[j] + arr[i]) {
                dp[i] = dp[j] + arr[i];
                result = max(result, dp[i]);
            }
        }
        if (dp[i] == 0) dp[i] = arr[i];
        result = max(result, dp[i]);
    }
    cout << result;
    return 0;
}
cs

 

알고리즘

- 다이나믹 프로그래밍

 

수열 A의 크기를 n에 담고, arr[] 배열에 수열 A를 담았다.

dp[i]에는 arr[i]를 포함한 가장 큰 감소 부분 수열의 합이 들어간다.

dp[0]은 arr[0]을 포함한 가장 큰 감소 부분 수열의 합이므로 arr[0]을 그대로 넣어준다.

result에는 답을 넣어줄 것인데 현재 가장 큰 감소 부분 수열의 합은 dp[0] (arr[0])이므로 그대로 넣어준다.

 

이후 반복문을 돌며 나머지 배열을 확인한다.

자신보다 값이 큰 배열값을 찾는다.

현재 저장되어 있는 자신을 포함한 가장 큰 감소 부분 수열의 합 (dp[i])보다 해당 값을 포함한 가장 큰 감소 부분 수열의 합 (dp[j])에 자신 (arr[i])을 포함한 값이 더 크다면 이를 업데이트 해준다.

result도 더 큰 값으로 업데이트 해준다.

 

arr[0]까지 다 확인했음에도 dp[i]가 0값을 가진다면 자신보다 큰 값을 가지는 배열값이 없다는 의미이므로 자신을 포함한 가장 큰 증가 부분 수열의 합은 자기 자신이 된다. dp[i]에는 arr[i]값을 넣어준다.

result도 더 큰 값으로 업데이트 해준다.

 

모든 배열값을 확인했다면 result값을 출력한다.

문제 출처 : https://www.acmicpc.net/problem/1965

 

1965번: 상자넣기

정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가

www.acmicpc.net

#include <iostream>
#include <vector>
using namespace std;
 
int main () {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, cnt = 1;
    cin >> n;
    vector<int> v(n), dp(n, 1);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (v[i] > v[j]) dp[i] = max(dp[j] + 1, dp[i]);
            if (dp[i] > cnt) cnt = dp[i];
        }
    }
    cout << cnt;
    return 0;
}
 
cs

 

알고리즘

- 다이나믹 프로그래밍

 

n으로 상자의 개수를 받고, 크기가 n인 벡터에 상자 크기를 담는다.

cnt는 최대 상자의 개수가 넣을 것인데, 하나도 못 넣는다면 자기 자신 1개이므로 1로 선언한다.

 

dp[i]는 v[i]를 포함한 최대 상자 개수이다.

이도 역시 자기 자신 1개가 최소값이므로 1로 선언한다.

 

이후 반복문을 돌며 자기보다 이전 인덱스를 확인한다.

자기보다 작은 값을 발견했다면 해당 상자를 포함한 최대 상자의 개수 (dp[j])에 자신을 포함한 값 (dp[j] + 1)과 현재 들고있는 최대 상자의 개수 (dp[i])를 비교하여 큰값으로 업데이트 한다.

cnt와 dp[i]를 비교하여 정답값도 업데이트 한다.

 

반복문이 끝나면 답을 출력한다.

문제 출처 : https://www.acmicpc.net/problem/11055

 

11055번: 가장 큰 증가 부분 수열

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수

www.acmicpc.net

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, result = 0;
    cin >> n;
    int arr[1001= {0}, dp[1001= {0};
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    dp[0= result = arr[0];
    for (int i = 1; i < n; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (arr[i] > arr[j] && dp[i] < dp[j] + arr[i]) {
                dp[i] = dp[j] + arr[i];
                result = max(result, dp[i]);
            }
        }
        if (dp[i] == 0) dp[i] = arr[i];
    }
    cout << result;
    return 0;
}
cs

 

알고리즘

- 다이나믹 프로그래밍

 

수열 A의 크기를 n에 담고, arr[] 배열에 수열 A를 담았다.

dp[i]에는 arr[i]를 포함한 가장 큰 증가 부분 수열의 합이 들어간다.

dp[0]은 arr[0]을 포함한 가장 큰 증가 부분 수열의 합이므로 arr[0]을 그대로 넣어준다.

result에는 답을 넣어줄 것인데 현재 가장 큰 증가 부분 수열의 합은 dp[0] (arr[0])이므로 그대로 넣어준다.

 

이후 반복문을 돌며 나머지 배열을 확인한다.

자신보다 값이 작은 배열값을 찾는다.

현재 저장되어 있는 자신을 포함한 가장 큰 증가 부분 수열의 합 (dp[i])보다 해당 값을 포함한 가장 큰 증가 부분 수열의 합 (dp[j])에 자신 (arr[i])을 포함한 값이 더 크다면 이를 업데이트 해준다.

result도 더 큰 값으로 업데이트 해준다.

 

arr[0]까지 다 확인했음에도 dp[i]가 0값을 가진다면 자신보다 작은 값을 가지는 배열값이 없다는 의미이므로 자신을 포함한 가장 큰 증가 부분 수열의 합은 자기 자신이 된다. dp[i]에는 arr[i]값을 넣어준다.

 

모든 배열값을 확인했다면 result값을 출력한다.

문제 출처 : https://www.acmicpc.net/problem/1916

 

1916번: 최소비용 구하기

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그

www.acmicpc.net

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int dis[1001];
vector<vector<pair<intint>>> v(1001);
 
void dijk(int start) {
    priority_queue<pair<intint>vector<pair<intint>>, greater<pair<intint>>> pq;
    pq.push({ 0, start });
    dis[start] = 0;
    int distance, now, cost;
 
    while (!pq.empty()) {
        distance = pq.top().first;
        now = pq.top().second;
        pq.pop();
 
        if (dis[now] < distance) continue;
 
        for (int i = 0; i < v[now].size(); i++) {
            cost = distance + v[now][i].second;
            if (cost < dis[v[now][i].first]) {
                dis[v[now][i].first] = cost;
                pq.push({ cost, v[now][i].first });
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, a, b, c, s, e;
    cin >> n >> m;
    for (int i = 0; i <= n; i++) {
        dis[i] = 1000000000;
    }
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
    }
    cin >> s >> e;
    dijk(s);
    cout << dis[e];
    return 0;
}
cs

 

알고리즘

- 그래프 이론

- 데이크스트라

 

최대 도시의 개수 만큼 거리배열을 선언하고 무한(10억)값을 넣어준다.
출발 도시 번호, 도착 도시 번호, 버스 비용을 입력 받아 v[출발 도시 번호]에 pair(도착 도시 번호, 버스 비용)을 넣어준다.

구하고자 하는 출발 도시 번호와 도착 도시 번호를 입력 받아 dijk(출발 도시 번호) 함수를 돌려준다.
이후 거리배열[도착 도시 번호]를 출력한다.

dijk 함수
오름차순 우선순위큐(pair)를 선언한다. (거리 오름차순으로 정렬)
start에서 start까지의 거리는 0이므로 (0, start)를 넣는다.
dis[start]도 0으로 업데이트 한다.

큐가 빌 때까지 반복문을 돈다.

distance에는 큐 top의 첫번째 값을, now에는 큐 top의 두번째 값을 넣고 pop 한다.

dis[now] < distance 라면 이미 체크한 노드이므로 다음 노드를 확인한다.

now와 연결된 노드를 모두 확인한다.
start에서 해당 노드에 가는 비용은 now까지의 비용과 now에서 해당 노드로 가는 비용의 합이다.
만약 방금 구한 값이 거리배열에 있는 값보다 작다면 최소비용이므로 업데이트 하고 큐에 넣어준다.

'알고리즘 > 백준' 카테고리의 다른 글

[백준 1965] 상자넣기 (C++)  (0) 2023.08.10
[백준 11055] 가장 큰 증가 부분 수열 (C++)  (1) 2023.08.09
[백준 1238] 파티 (C++)  (0) 2023.08.07
[백준 1753] 최단경로 (C++)  (0) 2023.08.06
[백준 11438] LCA2 (C++)  (0) 2023.07.25

문제 출처 : https://www.acmicpc.net/problem/1238

 

1238번: 파티

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어

www.acmicpc.net

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int dis[1001];
vector<vector<pair<intint>>> v(1001);
 
void dijk(int start) {
    priority_queue<pair<intint>vector<pair<intint>>, greater<pair<intint>>> pq;
    pq.push({ 0, start });
    dis[start] = 0;
    int distance, now, cost;
 
    while (!pq.empty()) {
        distance = pq.top().first;
        now = pq.top().second;
        pq.pop();
 
        if (dis[now] < distance) continue;
 
        for (int i = 0; i < v[now].size(); i++) {
            cost = distance + v[now][i].second;
            if (cost < dis[v[now][i].first]) {
                dis[v[now][i].first] = cost;
                pq.push({ cost, v[now][i].first });
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, a, b, c, s, temp, maxtime = 0;
    cin >> n >> m;
    cin >> s;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dis[j] = 1000000000;
        }
        dijk(s);
        temp = dis[i];
        for (int j = 0; j <= n; j++) {
            dis[j] = 1000000000;
        }
        dijk(i);
        maxtime = max(maxtime, temp + dis[s]);
    }
    cout << maxtime;
    return 0;
}
cs

 

알고리즘

- 그래프 이론

- 데이크스트라

 

모여야 하는 마을 s를 입력받는다.

도로의 시작점, 끝점, 시간을 입력 받고 v[시작점]에 pair(끝점, 시간)을 넣어준다.

 

모든 마을에 대해서 왕복 시간을 구해준다.

시간배열을 무한값(10억)으로 초기화 한 후 모여야 하는 마을 s로 dijk함수를 돌려준다.

s에서 i까지의 시간을 temp에 저장해 둔 후 시간배열을 초기화 한다.

i에 대해 dijk함수를 돌린 후 i에서 s까지의 시간을 구해준다.

s에서 i까지의 시간과 i에서 s까지의 시간의 합과 현재 들고있는 maxtime(답)을 비교하여 큰 값을 저장한다.

 

maxtime을 출력한다.

 

dijk 함수
오름차순 우선순위큐(pair)를 선언한다. (시간 오름차순으로 정렬)
start에서 start까지의 시간은 0이므로 (0, start)를 넣는다.
dis[start]도 0으로 업데이트 한다.

큐가 빌 때까지 반복문을 돈다.

distance에는 큐 top의 첫번째 값을, now에는 큐 top의 두번째 값을 넣고 pop 한다.

dis[now] < distance 라면 이미 체크한 노드이므로 다음 노드를 확인한다.

now와 연결된 노드를 모두 확인한다.
start에서 해당 노드에 가는 시간은 now까지의 시간과 now에서 해당 노드로 가는 시간의 합이다.
만약 방금 구한 값이 시간배열에 있는 값보다 작다면 최단시간이므로 업데이트 하고 큐에 넣어준다.

문제 출처 : https://www.acmicpc.net/problem/1753

 

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가

www.acmicpc.net

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int dis[20001];
vector<vector<pair<intint>>> v(20001);
 
void dijk(int start) {
    priority_queue<pair<intint>vector<pair<intint>>, greater<pair<intint>>> pq;
    pq.push({ 0, start });
    dis[start] = 0;
    int distance, now, cost;
 
    while (!pq.empty()) {
        distance = pq.top().first;
        now = pq.top().second;
        pq.pop();
 
        if (dis[now] < distance) continue;
 
        for (int i = 0; i < v[now].size(); i++) {
            cost = distance + v[now][i].second;
            if (cost < dis[v[now][i].first]) {
                dis[v[now][i].first] = cost;
                pq.push({ cost, v[now][i].first });
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, a, b, c, s;
    cin >> n >> m;
    for (int i = 0; i <= n; i++) {
        dis[i] = 1000000000;
    }
    cin >> s;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
    }
    dijk(s);
    for (int i = 1; i <= n; i++) {
        if (dis[i] != 1000000000cout << dis[i] << endl;
        else cout << "INF" << endl;
    }
    return 0;
}
cs

 

알고리즘

- 그래프 이론

- 데이크스트라

 

최대 정점의 개수 만큼 가중치배열을 선언하고 무한(10억)값을 넣어준다.

시작점 번호를 입력 받는다.

시작 정점 번호, 도착 정점 번호, 가중치를 입력 받아 v[시작 정점 번호]에 pair(도착 정점 번호, 가중치)을 넣어준다.

dijk(시작점) 함수를 돌린 후 n개의 정점을 돌며 무한(10억)값이 아니라면 해당 값을, 무한값이라면 INF를 출력한다.

dijk 함수
오름차순 우선순위큐(pair)를 선언한다. (가중치 오름차순으로 정렬)
start에서 start까지의 가중치는 0이므로 (0, start)를 넣는다.
dis[start]도 0으로 업데이트 한다.

큐가 빌 때까지 반복문을 돈다.

distance에는 큐 top의 첫번째 값을, now에는 큐 top의 두번째 값을 넣고 pop 한다.

dis[now] < distance 라면 이미 체크한 노드이므로 다음 노드를 확인한다.

now와 연결된 노드를 모두 확인한다.
start에서 해당 노드에 가는 가중치는 now까지의 가중치와 now에서 해당 노드로 가는 가중치의 합이다.
만약 방금 구한 값이 가중치배열에 있는 값보다 작다면 최단경로이므로 업데이트 하고 큐에 넣어준다.

'알고리즘 > 백준' 카테고리의 다른 글

[백준 1916] 최소비용 구하기 (C++)  (0) 2023.08.08
[백준 1238] 파티 (C++)  (0) 2023.08.07
[백준 11438] LCA2 (C++)  (0) 2023.07.25
[백준 2293] 동전1 (C++)  (0) 2023.07.22
[백준 2042] 구간 합 구하기 (C++)  (0) 2023.07.21

+ Recent posts