loltochess

암호는 정렬된 문자열로 되어있고 최소 한 개의 모음과 두 개 이상의 자음으로 구성되어 있다. 문제해결방법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부터 확인한다.먼저 처음에 기준으로 잡..

자기 최고점을 가지고 평균을 다시 내는 문제이다. (과목점수/최고점)*100 문제풀이방법1. 배열에 과목별 점수를 저장한다.(저장하면서 최고점을 구함.) //최고점은 double로 저장2. 모든 과목의 점수를 다시 계산해서 sum에 누적한다.3. sum을 과목 수만큼 나눠준다.  #include using namespace std;int arr[1001];int main(void){ int N = 0; cin >> N; double max = 0; for (int i = 0; i > arr[i]; if (arr[i] > max) { max = arr[i]; } } double sum = 0; for (int i = 0; i

이 문제는 공백 없이 숫자가 주어졌을 때 그 합을 구하는 문제이다. 문제풀이방법1. 숫자를 공백없이 입력받으라고 했으니 string으로 입력받는다.2. 0부터 N-1까지 string에 index로 접근해서 값을 구한다. 이때 구해지는 값은 문자형태(char)로 반환되기 때문에 -48을 하거나 -'0'을 해줘야 한다.3. sum에 구한 값을 누적해 준다. string a="123";stoi(a) //string을 int로 형변환string b="123.123"stof(b) //string을 float로 형변환 #include #include using namespace std;int main(void){ int N = 0; string s = ""; cin >> N >> s; int sum = 0; for..

이분탐색 문제이다. 뭔가 문제를 읽었을 때는 모든 경우의 수를 확인해서 값을 확인해야 할 거 같지만 그렇지 않다.시간 복잡도를 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) 하나라도 범위를 초과하면그곳에는 저 도형을 놓지 못한다.(상,..

첫째 줄 문자열을 넣으면서 폭발 문자열과 같은 문장이 생기면 폭발시키는 문제이다.위 그림을 보면 느끼겠지만 이 문제는 Stack과 관련이 있는 문제이다. 문제해결방법1. 문자열의 문자를 하나하나 스택이 집어넣는다. 2. (스택의 크기-폭발 문자열의 크기)부터 스택의 크기까지 문자열과 폭발 문자열이 같은지 비교한다.3. 만약 같으면 스택에서 폭발 문자열을 제거한다.#include using namespace std;char arr[1000001];int main(void){ string s1 = ""; string s2 = ""; cin >> s1 >> s2; int index = 0; for (int i = 0; i = 0) { int sig = 0; for (int j = (index ..