최근 최종 팀 프로젝트 준비 및 회의로 인해서 개인 공부를 많이 진행하지 못했습니다.. 1. 코딩 테스트오랜만에 코딩테스트 문제를 풀었습니다.이번 문제는 저번에 정리한 MST를 활용한 문제였습니다.https://gbleem.tistory.com/170 MST참고자료https://blog.encrypted.gg/1024 [실전 알고리즘] 0x1B강 - 최소 신장 트리안녕하세요, 오늘 다룰 주제는 최소 신장 트리(Minimum Spanning Tree)라는 개념입니다. 보통 코딩 좀 치는 사람들 사이에서는 MSgbleem.tistory.com 문제는 백준 class 5 "도시 분할 계획" 입니다.https://www.acmicpc.net/problem/1647 코드MST 기본 코드에 한가지 조건만 추가해 주..

1. 코딩테스트오늘은 class 5의 LCS 2 문제를 풀었습니다.https://www.acmicpc.net/problem/9252 DP쪽 문제 풀이에 아직 약점이 있다고 생각이 들었고, LCS 관련된 내용이 정리되지 않은 것 같아서 해당 내용을 추가적으로 정리해 보았습니다.https://gbleem.tistory.com/168 LCS1. Longest Common Substring두 문자열 사이에서 연속적으로 공통된 문자 중 가장 긴 문자열 찾기 (최장 공통 문자열) 과정2차원 배열을 통해서 하나씩 비교하면서두 문자가 다르면 dp[i][j] = 0같은 문자가gbleem.tistory.com 2. 언리얼어제 다 정리하지 못한 멀티플레이 최적화에 대한 내용 정리를 마무리했습니다.https://gbleem..

1. 코딩테스트오늘은 class 4의 특정한 최단 경로 문제를 풀었다.https://www.acmicpc.net/problem/1504 문제를 보고 다익스트라 문제일 것이라는 생각이 들었다.이유는 가중치가 존재하고,최단 경로를 구해야 했기 때문이다.아직 다익스트라 코드에 익숙하지 않아서 기존에 공부한 코드를 좀 참고하여 풀었다. 추가로 다익스트라 문제를 몇 개 풀었는데, 배열로는 시간초과가 발생하는 문제가 있어서 우선순위 큐 이용한 방식에 익숙해지면 될 것 같다. 코드 해설이 문제에 있어서는 추가적으로 무조건 지나가야할 정점이 2개가 주어진다. 이 정점을 모두 지나면서 최단경로를 구해야하기 때문에 아래와 같은 과정을 수행했다.다익스트라 하는 함수를 시작점을 매개변수로 넣어 여러번 수행할 수 있게 하였다...

1. 코딩테스트백준 클래스 4의 알파벳 문제https://www.acmicpc.net/problem/1987처음 풀이bfs로 찾을 것인데, 특이점은 선택한 경로로 이동하는 동안에 방문 배열을 유지해야 한다.예를 들어, CAAB /n ADCB 라는 char 배열이 주어졌을 때C -> A -> D 로 가는 경로가 있다면, 이 "해당 경로에만 유지되는" 방문체크 배열이 필요하다.그 이유는 bfs 방문하는 순서가 인접한 것들부터 방문하고 퍼져 나가는 순서인데, 이렇게 되면 오른쪽으로 방문하는(y가 커지는) 경로와 아래로 방문하는(x가 커지는) 경로에 둘 다 A가 있으므로 만약 오른쪽으로 먼저 진행했다면, 아래로는 방문을 못하는 경우가 생긴다. (이미 A는 방문체크를 해버리니까) 그래서 해결책으로 queue 자체..

1. 코딩테스트오늘 오전에는 저번에 연습이 필요하다고 느껴진 배낭문제 유형의 DP 문제를 풀었습니다. 평범한 배낭https://www.acmicpc.net/problem/12865더보기#include using namespace std;int n, k;pair props[102];int dp[102][100'002];int answer = 0;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for (int i = 1; i > w >> v; props[i].first = w; props[i].second = v; } for (int i = 1; i  동전https://www.acmicpc.net/problem/9084더보기#include..

1. 언리얼오늘은 오전부터 멀티플레이 공부를 하고 프로젝트를 진행하고 있습니다. https://gbleem.tistory.com/156 Unreal Engine - 데디케이티드 서버 5 (RPC, Replication)https://gbleem.tistory.com/152  Unreal Engine - 데디케이티드 서버 4 (RPC)1. RPC 개념https://gbleem.tistory.com/140#6.%20RPC-1-5 Unreal Engine - 데디케이티드 서버 개념 및 실습1. 서버의 종류P2P각 컴퓨터가 서버랑 클라gbleem.tistory.com멀티플레이 관련 공부를 하면서, 개념은 점차 잡혀가고 있어서 다행인 것 같습니다.오늘은 NetMulticast와 프로퍼티 리플리케이션 관련해서 공부..

1. 코딩테스트오늘은 수업중에 DP관련 문제를 풀었습니다.https://www.acmicpc.net/problem/1535DP 배낭문제 유형의 문제였는데, 이 문제 유형 관련해서 좀 더 공부를 해봐야겠다는 생각이 들었습니다.현재 턴을 가지고 진행하면서체력과 같은 제한이 있는 경우2차원 배열을 사용하고 2중 for문을 통해서 문제를 해결하는 것 같은데, 좀 더 템플릿화해서 익숙해져야 할 것 같습니다.더보기#include using namespace std;int n;pair board[22];int dp[22][102]; //현재 i번째 왔을때 남은 체력 j 일때의 기쁨int answer = 0;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; fo..

1. 코딩테스트class 5의 용액 문제를 풀었습니다.https://www.acmicpc.net/problem/2467더보기#include #include using namespace std;int n;int board[100'002];int answer = INT_MAX;pairans;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; fill(board, board + 100002, INT_MAX); for (int i = 0; i > board[i]; } int st = 0; int en = n - 1; while (st abs(sum)) { answer = abs(sum); ans = make_pair(board[st], boa..

1. 코딩테스트class 4 한 문제와 class 5 한 문제를 풀었습니다. DP 문제로 유명한 LCS문제https://www.acmicpc.net/problem/9251더보기#include #include using namespace std;string str1, str2;int dp[1002][1002];int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> str1 >> str2; for (int i = 1; i   class 5 다각형의 면적https://www.acmicpc.net/problem/2166 우선 외적을 통해서 원점과 다각형의 두 개의 점을 연결한 삼각형의 넓이를 구했습니다.주의할 점은 오목한 다각형이 존재하기 때문에, 넓이를 더할 때 ..

1. 코딩테스트오늘은 class4에 "치킨 배달" 문제를 풀었습니다.https://www.acmicpc.net/problem/15686 생각의 흐름이 문제는 처음 보고 백트래킹이랑 bfs을 쓰는 문제인 줄 알았는데, 사실 N x N 의 borad는 크게 신경쓸 필요가 없었다.치킨집이랑 집의 위치만 저장해두고 for문 돌면서 체크만 해주면 된다. (일단 N이 작으니까)또한 N이 작기 때문에 모든 경우의 수를 백트래킹으로 그냥 골라버리면 된다.더보기#include #include #include using namespace std;int n;int m;vector> chicken;vector> home;vector> ans;int isused[15];int answer = INT_MAX;void Check(..