loltochess

이 문제는 MST를 구하는 문제이다.문제를 해결할 수 있는 방법은 2가지가 있다.프림의 알고리즘을 사용하던지 크루스칼의 알고리즘을 사용하면 된다.일반적으로 프림의 알고리즘이 크루스칼의 알고리즘보다 구현하기 쉬워서 프림의 알고리즘을 많이 사용한다. *프림의 알고리즘*은 한 노드를 딱 정해서 그 노드에서부터 이웃한 노드를 우선순위 큐에 넣고 가장 가까운 노드로 나아가는 방법이다.(나아간 후에는 그 나아간 노드에 있는 이웃한 노드 또한 우선순위 큐에 넣어주는 작업을 수행해야 함. visited배열을 사용해서 이미 방문된 노드는 다시 방문하지 않음.) *크루스칼의 알고리즘*은 간선을 우선순위 큐에 모두 넣어놓고 짧은 간선부터 하나씩 빼서 MST를 구성하는데 만약 사이클이 발생하면 그 간선은 사용하지 않고 넘어간..

너비우선탐색 문제이다. 생각보다 고려해야 할 경우의 수가 많아서 헷갈렸다. 1. 지훈이는 이미 이동한 경로로 다시 이동하지 못한다.2. 지훈이는 이전에 불이 난 장소로는 이동하지 못한다.3. 이미 불이 난 곳은 다시 탐색하지 않는다.4. 사람이 모서리에 도착하면 탈출할 수 있다고 판단함.5. 사람이 출발하기 전에 출발하려는 장소가 불이 났는지 안 났는지 판단해야 함. 사람이 출발하기 전에 출발하려는 장소가 불이 났는지 안 났는지 판단해야하는 이유.이렇게 주어졌을 때사람이 먼저 이동 한 후불이 이동을 하게 되면 불과 사람이 겹친다.그렇기 때문에 사람은 출발하기 전 자신의 위치에 불이 났는지 확인하는 작업이 필요하다. #include #include ;using namespace std;char arr[10..

이 문제는 용액과 비슷한 문제이다.세 종류의 용액을 합쳐서 그 합이 0에 가장 가깝게 만드는게 목표이다. 용액 문제는 두 개의 용액을 합쳐서 그 합이 0에 가장 가깝게 만드는 문제였다. 이렇게 시작점과 끝점에 S와 E를 두고 합쳤을 때 합이 만약 0보다 크면 e를 --해주고 합이 0보다 작으면 s를 ++해줘서 문제를 해결해 주었다. 세 용액은 두 가지의 용액이 아니라 세 가지의 용액을 가지고 합이 0에 가깝게 만드는 목표이다. 그러면 어떻게 하면 세 가지 용액을 구할 수 있을까?? 위 용액문제에서 조금만 수정하면 된다.-97을 무조건 하나의 용액에 포함한다고 가정하자. 그러면 나머지 두 용액의 합이 97이 되어야 합이 0이 될 것이다. 나머지 두 용액의 합이 97에 가장 가까운 조합을 찾으면 된다.  -..

암호는 정렬된 문자열로 되어있고 최소 한 개의 모음과 두 개 이상의 자음으로 구성되어 있다. 문제해결방법1. 문자의 종류 C를 입력받은 후 정렬한다.2. 정렬된 데이터를 바탕으로 조합을 만든다.(DFS)3. 완성된 조합이 한 개 이상의 모음과 두 개 이상의 자음을 가지고 있으면 출력한다. #include #include using namespace std;char arr[16];int visited[16];char result[16];void DFS(int start, int num1, int num2, int count);int L = 0;int C = 0;int main(void){ cin >> L >> C; for (int i = 0; i > arr[i]; } sort(arr, arr + C); D..

#include #include using namespace std;long long visited[1000001];int main(void){ long long T = 0; cin >> T; for (long long i = 0; i > k; long long count = 0; priority_queue> pq1; priority_queue> pq2; for (long long j = 0; j > c >> num; if (c == 'I') { pq1.push({ num,j }); pq2.push({ -num,j }); count++; } else if (c == 'D') { if (num == 1) { if (count > 0) { ..

우선 입력으로 20만까지 들어오고 공유기의 개수도 2 어떻게 하면 시간복잡도를 줄일 수 있을까?이 문제는 이분탐색을 활용하는 문제이다.근데 이 문제는 특이하게 거리를 기준으로 이분탐색을 진행한다. 그래서 좀 헷갈렸던 거 같다.거리를 기준으로 이분탐색을 한다는 말이 뭐냐면 만약 입력으로 1 2 4 8 9가 들어왔다고 치자.그러면 가장 먼 거리는 (9-1)이고 가장 적은 거리는 (2-1)이다. 1과 8 이 거리 정보를 가지고 문제를 접근해야 한다. 두 집의 거리의 차이는 적어도 0보다는 크기 때문에 L을 1로 두고두 집의 거리의 차이는 적어도 9보다는 작기 때문에 R을 8로 둔다.L과 R의 합을 2로 나눈 값부터 확인해 나간다. (L+R)/2(1+8)/2=4먼저 거리 4부터 확인한다.먼저 처음에 기준으로 잡..

이분탐색 문제이다. 뭔가 문제를 읽었을 때는 모든 경우의 수를 확인해서 값을 확인해야 할 거 같지만 그렇지 않다.시간 복잡도를 O(n^2) 미만으로 문제를 풀어야 한다. 처음에 문제를 보고 이분탐색을 사용해야 한다고 생각하기는 했는데 음수와 양수를 나눠서 양수의 데이터 하나를 음수로 가지고 간 후 이분탐색을 해서 가장 가까운 데이터를 찾는 방법으로 문제를 접근하려다가 실패했다.너무 어렵게 생각을 하지 말고 특성값이 0에 가장 가까운 용액을 만드는 경우가 두 가지 이상이면 그중 아무것이나 하나 출력하면 된다는 것에 집중을 하자. 문제풀이방법1. 배열을 일단 정렬한다.2. 배열의 arr [0] 값을 start로 두고 arr [N-1]를 end로 둔다.3. arr [start] 값과 arr [end] 값을 더..

걷거나 순간이동해서 가장 빠르게 동생의 위치를 찾는 방법이 몇 가지인지 찾는 문제이다. 이 문제는 가장 빠른 시간 안에 이동하는 문제이기 때문에 BFS를 사용할 수 있다.이런 식으로 BFS를 통해서 모든 경우의 수를 탐색해 주면 최단시간을 구할 수 있다. 그런데 여기서 정말로 모든 경우의 수를 계산하게 된다면 너무 많은 경우의 수가 존재해서 메모리 초과가 발생한다. 그래서 visited라는 배열을 둬서 이미 방문한 곳은 다시 방문하지 않게 하는 게 이 문제의 핵심이다. 만약 시간이 0초이고 시작 지점이 1이라고 생각을 해보자. 동생이 만약 4에 있다면 1 2 4가 가장 빠른 경로이다.1에서 2로 가는 경우의 수는 2가지가 있다. (걸어서 가거나 순간이동해서 가거나)위 2가지는 다른 방법이다. 그래서 시간..

삼각형의 꼭대기에부터 왼쪽 대각선, 오른쪽 대각선으로 내려오면서 숫자를 합치고 맨 아래층에 왔을 때 합이 최대가 되는 값을 찾는 문제이다. 정말 대표적인 DP문제이다. 문제해결방법1. 값을 저장할 배열을 선언해 준다.2. 위에서부터 내려오면서 값을 더한 후 더한 값이 DP배열의 값보다 크면 갱신을 해준다.(누적해서 더해야 함.)3. 맨 아래층에 저장되어 있는 값 중에 최댓값을 출력한다.

네모난 종이에 숫자가 써져 있다. 테트로미노를 종이 위에 올려놓았을 때 합의 최댓값을 찾는 문제이다.테트로미노의 회전, 대칭을 허용한다.나는 이 문제를 처음에 보았을 때 DFS를 사용해서 모든 경우의 수를 4칸씩 이동시켰다. 간단하게 DFS로 깊이 있게 들어가니 이 도형에 대해서는 탐색을 하지 못하는 문제가 발생하였다.그래서 DFS를 사용한 후 저 도형에 대해 탐색하는 로직만 추가로 작성해 주었다.위와 같은 도형이 나오는 경우의 수는 4가지이다위, 아래로 솟아있거나 좌, 우로 솟아있는 경우이다. 한 곳을 중심으로 잡고 상, 하, 좌, 우로 범위를 확인해 본다.만약 (상, 하)중에(OR) 하나라도 범위를 초과하고(AND) (좌, 우)중에(OR) 하나라도 범위를 초과하면그곳에는 저 도형을 놓지 못한다.(상,..