loltochess

문자열을 왼쪽으로 하나씩 밀면서 올바른 괄호 문자열이 되는 개수를 찾는 문제이다.우선 나는 이 문제를 Queue와 Stack을 이용해서 해결했다.Queue를 이용해서 문자열을 Left로 Shift해줬고 Stack을 이용해서 올바른 괄호인지 확인하였다. 문제 해결 방법1. queue에 문자열 s를 push하고 원하는 만큼 pop을 시킨 뒤 다시 뒤로 push한다.(이렇게 하면 shift 시킬 수 있음.)2. 변경한 queue의 front부터 보면서 '[' or '(' or '{' 이면 stack에 push해준다.3. 만약 queue의 front가 ']' or ')' or '}' 이면 닫는 과정이니 stack의 top과 비교해서 같은 종류인지 확인한다.4. 만약 stack의 top이 비어있거나 다른 종류이면..

정현이가 원하는 제품의 이름과 개수가 주어진다.회원 자격이 10일 동안 주어지고 할인 기간은 n일이다. 할인기간 동안 10일을 정해서 쇼핑을 해야 한다. 10일 동안 원하는 제품을 다 살 수 있는 회원등록 날짜의 총 일수를 구해야한다. 문제 해결 방법1. 우선 원하는 제품의 이름과 개수가 주어지니 이걸 저장하기 위해 unordered_map을 선언한다.2. 마트 할인 이벤트 시작일부터 이벤트 (마지막일 - 10)까지 10일씩 묶어서 원하는 제품을 모두 살 수 있는지 확인한다. #include #include #include #include using namespace std;int solution(vector want, vector number, vector discount) { int answer..

A와 B의 번호가 주어진다.A와 B가 계속해서 이긴다는 가정하에 몇 번째 라운드에서 만나는가? 8명이 토너먼트에 참가한다고 가정하자.A의 번호는 4 B의 번호는 7이다. 1 2 3 4 5 6 7 8 4와 7이 이기면1 2(4) 3 4(7) 2라운드에서 4는 2번이되고 7은 4번이 된다.1(4) 2(7)3라운드에서 4와 7은 만난다. 문제 해결 방법1. A와 B의 다음 라운드 번호를 찾는다.2. A와 B의 번호의 차이가 1인지 확인다.3. 번호의 차이가 1이라도 대결을 안할 수도 있다.(1은 2와 대결 3은 4와 대결한다. // A가 2 B가 3이라면 차이가 1이지만 대결하지 않는다.)4. A의 번호가 B보다 작다면 A와 B가 대결하려면 A의 번호는 항상 홀수여야한다.(A가 B보다 크다면 Swap하고 진행..

끝말잇기를 하고자 한다.우리가 알고 있는 끝말잇기 룰과 동일하다.같은 단어를 말해서는 안 되고 앞사람이 말했던 마지막 문자로 시작하는 단어를 말해야 한다. 몇 명이서 하는지 n으로 주어지고 string 배열이 주어질 때 가장 먼저 탈락하는 사람의 번호와 자신이 몇 번째 턴에서 탈락했는지 return하는 문제이다. 문제 해결 방법1. 같은 단어가 나오면 안되니 단어가 나오면 그 정보를 저장해야한다.(unordered_map 선언)2. 처음 나온 단어지만 앞사람이 말했던 마지막 문자로 시작하는 단어가 아니면 break;3. 같은 단어를 말하면 break; #include #include #include #include using namespace std;vector solution(int n, vector ..

연속된 부분 수열의 합의 개수를 구하는 문제이다. 길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있다길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있다.길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있다.길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있다.길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있다. 문제 해결 방법1. 길이 별로 합을 구하기 위해 for문을 선언한다.(길이 1, 2, 3, 4 ,5 등)2. 0부터 배열의 크기까지 for문을 돌린다.3. 길이만큼 연속 부분 수열의 합을 구한다. #in..

순간이동을 해서 이동하거나 점프를 해서 이동하거나 하는 문제이다.순간이동은 두 배를 움직이고 건전지 사용량 없음.점프는 점프한 만큼 건전지 사용.순간이동을 최대한 많이 사용해야 한다.이 문제도 간단한 아이디어만 있으면 풀린다.예를 들어보자11칸을 이동해야 한다고 치자.일단 11칸은 홀수라서 순간이동으로 11번째 칸에 이동은 불가능하다.그러면 그전에 점프를 해서 11번째 칸에 이동해 야한 다는 건데 10번째 칸에서 점프를 해서 11번째 칸으로 오는게 가장 건전지 사용을 덜한다.10번째 칸은 5번째 칸에서 순간이동이 가능하다(배터리 소모 없음.)5번째 칸은 순간이동이 불가능한 칸이므로 4번째 칸에서 5번째 칸으로 점프를 하는 것이 가장 효율적이다.4번째 칸은 2번째 칸에서 순간이동이 가능하다.2번째 칸은 1..

한 번에 1칸 또는 2칸을 점프할 수 있는데 n칸을 뛰어야 할 때 n칸까지 도달하는 그 경우의 수를 구하는 문제이다.간단한 아이디어면 풀리는 문제이다.효진이가 n번째 칸에 있을 때 n번째 칸에 도달할 수 있는 방법은 n-2번째 칸에서 뛰거나 n-1칸에서 뛰는 방법이다.이 아이디어를 이용해서 문제를 해결하면 된다.2번째 칸에 도달하는 방법은 0 or 1번째 칸에서 뛰기3번째 칸에 도달하는 방법은 1 or 2번째 칸에서 뛰기n번째 칸에 도달하는 방법은 n-2 or n-1번째 칸에서 뛰기 #include #include using namespace std;long long solution(int n) { long long answer = 0; int arr[2001] = {0}; ..

구명보트에 사람을 태워서 구출해야 한다.구명보트에는 무게 제한이 있고, 최소한의 구명보트를 이용해서 인원을 구출하려고 한다.이를 위해서는 간단한 아이디어가 필요하다.우선 무거운 사람을 기준으로 이 사람이랑 같이 타도 괜찮을 사람을 탐색해야 한다.가장 무거운 사람과 가장 가벼운 사람이 같이 타는 것이 가장 효율적인 방법이다. 문제 해결 방법1. 배열을 정렬한다.2. start과 end를 선언한다.3. 반복문을 돌면서 people[start]+people[end]가 limit보다 작거나 같은지 확인한다.4. 만약 limit보다 작다면 start++와 end--를 해주고 limit보다 크다면 end만 --해준다. #include #include #include #include using namespace st..

귤을 상자에 담는데 최대한 단순하게 담는 문제이다.(같은 크기의 귤을 많게 담는다.) 1. 크기에 따라 개수를 count 해야 하니 HashMap을 선언한다.(unordered_map)2. 분류가 되었으면 HashMap의 요소를 순회하면서 priority_queue에 넣어준다.3. pq에서 개수가 작은 크기의 귤부터 꺼내면서 제거한다.4. 남은 귤의 개수가 k거나 k보다 작아지면 break 한다.5. pq에 남은 귤의 종류를 count 해서 반환한다. #include #include #include #include using namespace std;int solution(int k, vector tangerine) { int answer = 0; unordered_map map; pri..

흔한 피보나치 수열 문제이다.F(n) = F(n-2) + F(n-1)을 구해야 한다.입력값이 10만까지 들어올 수 있기 때문에 재귀함수를 사용하면 안 된다.(2의 n승 구조로 시간복잡도가 기하급수적으로 증가함.)가장 기본적인 DP 문제이다. 계산된 값을 배열에 저장하고 배열을 활용해서 다음 값을 구한다. 문제 해결 방법1. arr[0]과 arr[1]에 값을 넣어주고 arr[2]부터 arr[n]까지 값을 구한다.2. 입력값이 10만까지 들어올 수 있게 때문에 long long으로 선언해도 범위를 초과한다.3. 계산하면서 1234567의 나눈 나머지를 배열에 저장하는 방식을 이용한다. #include #include using namespace std;long long arr[100001];int solu..