백준 15918 (골드 5, 백트래킹) - 랭퍼든 수열쟁이야!!

해당 문제는 백트래킹으로 접근하여 풀 수 있습니다. 제가 처음에 접근하였을 때는 백트래킹을 1부터 n * 2까지 해당 숫자를 하나 사용하면 position이라는 배열에 메모를 하여 (3)을 3 번째 인덱스에 놔두고 백트래킹이 돌고 돌아( 현재 인덱스 - 3-1 ) == 그전의 내가 저장해둔 position[3]의 위치와 같느냐를 봅니다. 이 방법은 웬만하면 모든 경우를 탐색하기에 1퍼센트 맞고 시간 초과가 떴었습니다. 그래서 아.. 이건 방법이 잘못 되었구나라고 생각하여서 문제를 다르게 접근하였습니다. 만약 내가 첫 번째 위치에 3을 둔다면 (현재 위치 + 값(3) + 1(보정)) 의 위치에 존재하는 값도 (3) 이어야 한다그리고 그 위치는 (N * 2)보다 클 수 없다. (예) 3 0 0 0 3 0..

백준 4195 (골드 2) 친구 네트워크 - 분리 집합 (Union Find)

해당 문제는 그래프 탐색(DFS, BFS), 분리 집합을 활용해서 풀 수 있지만 그래프 탐색의 경우 시간 제한이 걸릴 수 있습니다. 만약 그래프로 푼다면 O(T * F * F)만큼이 걸릴 것 입니다. F의 최대 값이 100,000인데 F * F 라니 너무하지 않나요? 그래서 우리는 다른 방법을 찾아야 합니다. 바로 분리집합(Union Find) 입니다.Union Find란 그래프에서 어떠한 정점들이 연결되어 있는지를 알고 싶을 때 사용한다고 생각하시면 되겠습니다. 아래에는 두 집합이 있습니다. 김병만 팀장의 팀원 -> 수아, 민지박지원 팀장의 팀원 -> 종원, 민재 만약 수아와 민지가 같은 팀인지 종원과 민지는 같은 팀이 아닌지 컴퓨터는 어떻게 알 수 있을까요?우리는 눈으로 단 번에 판단 할 수 ..

#include #include #include int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int twoPointToOnePoint(std::pair tp) { return tp.first * 3 + tp.second;}std::pair onePointToOnePoint(int op) { return {op / 3, op % 3};}int calculate(std::string strValue) { std::string answer = "123456780"; if (answer == strValue) { return 0; } std::queue > q; std::set visited; visited...

오늘은 C# Netonsoft 라이브러리를 사용해서 직렬화와 역직렬화에 대해서 공부해보겠습니다. 직렬화 (Serialization)객체의 형태를 통신을 할 때 사용하는 (예)Json과 같은 형태로 변환시키는 것이다.핵심은 데이터를 통신하기 쉽게 하나로 뭉쳐 연속적인 데이터의 형태로 바꾼다라고 생각하면 될 거 같다. 역직렬화 (Deserialization)역직렬화는 그에 반대되는 의미이다.(예)Json 같은 통신을 할 때 사용하는 형태를 객체의 형태로 변환시키는 것이다. 아래는 예시의 객체 형태이다.public class Person{ public string Name { get; set; } public int Age { get; set; } public DateTime BirthDat..

핵심 풀이 : 첫 번째는 핵심은 10시에 시작하면 (10 + k ) 까지의 시간까지 증설한 서버가 유지된다고 생각하였음두 번째는 현재 서버가 얼만큼 증설 되었는지를 알아야 하기에 currentV라는 변수를 사용해서 누적시켰음 나머지는 문제에 나오는대로 조건을 잘 지키면 됨 #include #include using namespace std;int solution(vector players, int m, int k) { int answer = 0; int currentV = 0; vector vec(25+k, 0); int ct = 0; for(auto i : players) { if(currentV

반갑습니다. 오늘은 최소 스패닝 트리 MST(Minimum Spanning Tree)에 대해서 공부해보겠습니다.MST ( Minimum Spanning Tree ) 란?기존의 그래프에서 신장 트리를 구성할 때 그 간선의 가중치 합이 제일 작은 신장 트리모든 정점이 연결되어있다.간선의 갯수는 정점의 갯수에 -1을 한 것이다.간선에 가중치가 존재한다.트리이기 때문에 사이클이 존재하지 않는다. 가중치가 있는 그래프에서 MST를 2가지 방법으로 추출 할 수 있다. 코드는 아래의 문제를 예시로 하여 작성하였습니다.https://www.acmicpc.net/problem/1197 첫 번째: 크루스칼 알고리즘 (Kruskal's Algorithm)간선 중심의 그리디 알고리즘이다. 동작 원리가중치를 기준으로 간선을 ..