loltochess

첫째 줄 문자열을 넣으면서 폭발 문자열과 같은 문장이 생기면 폭발시키는 문제이다.위 그림을 보면 느끼겠지만 이 문제는 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 ..

서로 다른 높이를 가진 N개의 탑을 세운다. 탑에서 왼쪽 방향으로 레이저 신호를 보내는데 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.(자신보다 높은 탑)자신의 레이저 신호를 어떤 탑이 수신했는지 출력하는 문제이다.(수신하는 탑이 존재하지 않으면 0을 출력)그림을 보면 첫 번째 탑은 자기보다 큰 탑이 왼쪽에 없기 때문에 0을 출력하고 두 번째 탑도 자신보다 큰 탑이 존재하지 않기 때문에 0을 출력한다. 세 번째 탑은 바로 왼쪽에 두 번째 탑의 높이가 9라서 2를 출력하고 네 번째 탑은 두 번째 탑의 높이가 더 높기 때문에 2를 출력한다. 다섯 번째 탑은 바로 왼쪽 네 번째 탑이 자신보다 높기 때문에 4를 출력한다.이렇게 가장 먼저 만나는 탑(자신보다 높이가 높아야 함)을 찾는 문제이다.  모든 ..

그림의 개수와 가장 넓은 그림의 넓이를 출력하는 문제이다.(섬의 개수를 찾는 문제와 비슷함.)이 문제는 가로나 세로로 연결된 것만 연결되어 있다고 본다.(대각선으로 연결되면 떨어진 그림임.)특정한 지점을 선택한 후 DFS나 BFS로 탐색을 하고 방문 여부를 체크해줘야 한다.(중복 방문을 회피)나는 이 문제를 DFS로 해결하였다. 문제해결방법1. (0,0)부터 (n-1, m-1)까지 모든 경우를 탐색하는데 방문되어 있지 않은 곳만 탐색한다.2. 탐색을 시작하면 동서남북 방향으로 DFS로 탐색을 시작한다.(탐색을 한 곳은 visited를 1로 바꿔야 함)3. 탐색을 할 때마다 넓이를 1씩 더해준다.(DFS로 탐색하기 때문에 사람이 바구니에 공을 하나씩 집어넣는다고 생각하면 편함.)#include #inclu..

이 문제는 조합을 이용하는 문제이다. 모든 경우의 수를 확인해서 차이가 최소인 값을 출력하면 된다.1, 2, 3, 4가 있으면 (1,2 / 3,4), (1,3 / 2,4), (1,4 / 2,3)  이 경우에 대해서만 확인을 하면 된다. 문제해결방법1. 모든 경우의 조합에 대해 확인한다. (6명이 있으면 3명만 뽑는다. 나머지 3명은 남는 사람으로 따로 계산)2. 스타트 팀과 링크팀의 차이를 구한다.(abs(스타트-링크))#include #include using namespace std;void DFS(int size, int count, int start);vectorv[1000];int visited[1000];int result = 987654321;int main(void){ int N = 0; ..

이 문제는 연결리스트를 활용하는 간단한 문제이다.연결리스트를 직접 구현해서 문제를 해결해도 상관없지만 나는 라이브러리에 있는 list를 사용해서 문제를 해결하였다. 문제해결방법1. list를 선언한다.2. iterator(반복자)를 활용해서 요소에 접근한다.3. L을 입력받았을 때 반복자의 위치가 맨 앞이면 무시한다.4. D를 입력받았을 때 반복자의 위치가 맨 뒤면 무시한다.5. B를 입력받았을 때 반복자의 위치가 맨 앞이면 무시한다.6. P를 입력받으면 문자를 추가한다.  list ::iterator it = l.begin();list ::iterator it = l.end();begin은 맨 앞(첫 번째 요소)을 의미하고 end는 맨 끝(빈 공간)을 의미한다.만약 반복자가 end를 가리키고 있고 4를..

이 문제는 투포인터 문제이다.문제를 보면 눈치챘다시피 정렬을 하고 문제를 풀어야 한다.이 문제에서 주의할 점은 Ai는 음수도 나올 수 있다는 점이다. 이 점을 숙지하고 문제를 풀어야 한다. 문제풀이방법1. 배열을 정렬한다.2. L와 R을 두고 양쪽에서 서서히 좁히면서 값을 찾는다.(L은 배열의 가장 앞, R은 배열의 가장 끝부분)3. 만약 arr[L]+arr[R]의 값이 지금 찾고자 하는 값보다 크다면 R을--하고 작다면 L을++한다.(이 문제를 풀기 위해 꼭 떠올려야 함)4. 만약 L과 R이 지금 찾고자 하는 값의 index와 같다면 L은 ++를 해주고 R은 --를 해준다.(이 과정을 한 뒤에는 L 꼭 continue를 해줘서 다시 범위를 확인해줘야 한다.)5. 만약 arr[L]+arr[R]의 값이 찾..

누적합, 투포인터 문제이다. 문제풀이방법start와 end 포인터를 둬서 하나씩 이동시키면서 문제를 풀어야 한다.start와 end를 -1로 초기화했다고 치자.sum은 0이기 때문에 end를 오른쪽으로 한 칸 이동 키면서 sum+=arr[end]를 해준다.구하고자 하는 값보다 sum이 작으면 end를 ++해주고 구하고자 하는 값보다 크면 start를 ++해줘서 sum-=arr[start]해준다. #include #include using namespace std;vector v;int main(void){ int N = 0; int S = 0; int start = -1; int end = -1; cin >> N >> S; for (int i = 0; i > num; v.push_back(num); }..

이 문제는 목표지점에서 모든 지점의 최단거리를 BFS를 통해 찾아주면 되는 문제이다. 입력으로 2를 받으면 그 좌표를 기준으로 너비우선탐색을 진행해 준다. 문제해결방법1. arr와 visited배열을 선언해 준다.2. queue를 선언하고 입력으로 2를 받은 지점을 큐에 넣어준다.(큐에는 x, y, distance와 같은 정보가 필요하다)3. 큐가 빌 때까지 탐색을 진행한다.4. 출력은 arr의 내부 값을 출력하면 된다.(단 visited가 0이고 arr가 1이라면 이곳은 탐색이 불가능한 곳으로 간주해서 -1을 출력한다. 왜?? 방문을 하지 못했기 때문) #include #include using namespace std;int arr[1001][1001];int visited[1001][1001];in..

이 문제는 이웃하는 집은 같은 색으로 칠하면 않고 비용을 최소화하는 문제이다. 문제풀이방법1. 우선 세 방향에서 접근해야한다. (왼쪽, 중앙, 오른쪽)  처음 집을 빨강으로 칠하면 다음 집은 초록이나 파랑으로 칠해야한다.2. 위와 같은 방식으로 처음집을 빨강, 초록, 파랑으로 모두 칠해보고 그 다음집에 색칠 가능한 색깔을 고려해서 다음집에 최소값을 저장한다. 이 그림처럼 값을 더해보고 만약 저장되어 있는 값보다 더 작다면 값을 갱신한다. 전형적인 DP문제이다. #include #define INF 987654321;using namespace std;int arr[1001][3];int DP[1001][3];int main(void){ int N = 0; cin >> N; for (int i = 0; i..

문제풀이방법1. 중복을 제거하기 위해 Hashmap을 선언하고 arr, arr2배열을 선언하였다(arr2가 원본배열)2. 만약 이전에 입력이 되지 않았다면 arr에 요소를 추가해 주었다(중복 방지).3.sort함수를 통해 요소를 정렬한다(arr를 정렬 - arr는 중복이 제거된 배열임-).4.HashMap에 정렬된 요소의 순서를 넣는다.5.HashMap에 저장된 값 이용해서 arr2 원본배열을 좌표를 출력한다. 이 방식은 시간, 공간복잡도 측면에서 효율성이 떨어진다.더 좋은 방식으로 다음번에 한번 풀어보도록 하겠다.(다른 분들의 코드를 보니 erase를 이용해서 중복을 제거하고 lower_bound를 이용해서 요소값의 위치를 찾음....) #include #include #include using nam..