WASD BLOG

링크 dp로 풀이하려다 막혀 시간복잡도를 계산해 보니 10! * 20 = 7천만 정도로 가능할 것 같아 Brute Force로 풀이했다. 숫자를 담을 벡터와 연산자를 담을 벡터를 따로 두고 Brute Force를 진행한다. 1 + 3 + 5 + 7 위와 같은 식이 있다면, 숫자 벡터엔 1 3 5 7 , 연산자 벡터엔 + + + 이 처음에 들어가 있게 된다. 연속된 두 개의 숫자, 중간의 연산자를 묶어 계산한 뒤, 벡터를 복사하여 넘겨주는 식으로 진행한다. 1. 4 5 7 , + + 2. 1 8 7 , + + 3. 1 3 12 , + + 위 작업을 숫자 벡터의 크기가 1이 될 때까지 하고, max값을 갱신한다. dp 풀이: https://www.acmicpc.net/problem/11066 (파일 합치기) 위 문제와 비슷한 방법으로 풀이한다. maxdp[i][j] = i ~ j 까지의 최댓값 mindp[i][j] = i ~ j 까지의 최솟값 위 두 배열을 이용하여, i ~ j 가 작은 범위부터 0 ~ n 범위까지 구해가면 된다. 이 때, 음수로 인해 4가지 경우에 대해 모두 연산을 해 주어야 한다. (음수(최소) * 음수(최소) -> 최대일 수도 있기 때문) 최대, 최대 최대, 최소 최소, 최대 최소, 최소 Brute Force 풀이 #include<iostream> #include<algorithm> #include<math.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> #include<set> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii p...

링크 먼저 조건에 따라 모든 섬에 번호를 매깁니다. (dfs로 해당 섬과 연결된 모든 x에 번호를 매깁니다.) 이 때 당연하게도 어떤 섬 A가 섬 B에 포함된다면, (A의 번호) > (B의 번호) 가 되게 됩니다. (겉 부분인 섬은 dfs를 통해 이미 번호가 매겨져 있기 때문) 따라서 어떤 섬의 가장 가깝게 포함하고 있는 섬(parent) = 도달할 수 있는 섬의 번호 중 최소 값이 됩니다. (탐색 중 맵을 벗어날 경우는 -1로 해 주었습니다.) 모든 섬에 대해 parent를 구했으면 역으로 child를 모두 달아주고, child 중 가장 깊은 child의 깊이가 해당 섬의 높이가 됩니다. #include<iostream> #include<algorithm> #include<math.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> #include<set> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair<int, int> #define pdd pair<double, double> #define pic pair<int, char> #define ll long long #define vi vector<int> #define vl vector<long long> #define vc vector<char> #define vii vector<pii> #define IMAX 2000000001 #define LMAX 1000000000000000000 #define DMAX 0xFFFFFFFFFFFFF int...

회원가입 페이지에서 오류 메세지를 출력할 때, res.render()로 매번 렌더링을 하니 오류메세지는 원하는 대로 매번 바뀌면서 출력됐지만 새로고침 시에 양식 제출을 확인하라는 메세지가 떠서 res.redirect() 로 해야한다는 걸 깨달았다. redirect 할 주소로 오류메세지를 넘겨주는 방법이 필요했는데, 마침 딱 알맞는 미들웨어가 flash 미들웨어였다. flash 미들웨어는 req 객체에 (key, value) 를 담아 주고 받게 되는데, 처음 한 번 넘겨 주고, 받고 하면 사라진다. 즉 일회성이다. 따라서 일회성 경고메세지, 오류메세지에 적합하다. 먼저 connect-flash 를 npm으로 설치해준다. npm i connect-flash 그 다음, import flash 미들웨어는 쿠키, 세션을 사용하기 때문에 뒤에 붙여준다. 키값은 tryMsg로 만들어서 redirect 해주고, 받은 곳에선 tryMsg로 value 값을 찾아준다. 중복 회원가입 시 다음 메세지가 뿌려지고, 새로고침하면 일회성이기 때문에 사라진다!

문제(링크) https://hellogaon.tistory.com/75 위 블로그를 참고하여 풀이했습니다. 구현이 까다로운 문제였습니다. 왼쪽 덱(DL), 오른쪽 덱(DR)을 각각 만들어 그리디(?)하게 L연산 시에는 왼쪽부터 가장 처음 나오는 W문자열을 지워주고, R연산 시에는 오른쪽부터 가장 처음 나오는 W문자열을 지워줍니다. (왼쪽, 오른쪽부터 두 개의 포인터를 두어 두 포인터가 겹칠 때까지 진행합니다.) 두 포인터가 겹친다면, DL 엔 왼쪽의 문자열들, DR 엔 오른쪽의 문자열들이 모두 있기 때문에 DL의 오른쪽, DR의 왼쪽을 합쳤을 때 W문자열이 존재할 수 있습니다. DL의 오른쪽을 pop -> DR의 왼쪽에 push 해가며 W문자열을 만들 수 있는지 조사하면 됩니다. Perfect 인지 You Lose 인지 여부는 n개의 L, R 연산 뒤에 임의의 연산 L 을 추가하여 해결했습니다. #include<iostream> #include<algorithm> #include<math.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair<int, int> #define pdd pair<double, double> #define pic pair<int, char> #define ll long long #define vi vector<int> #define vl vector<long long> #define vc vector<char> #define vii vector...

문제(링크) 나올 수 있는 수는 -2, -1, 0, 1, 2 로 5개고, 최댓값을 만들기 위해선 음수의 개수가 짝수인 경우를 체크해줘야 합니다. 그리고 1은 결과에 상관이 없으므로 무시합니다. 정답인 경우는, 음수의 개수가 짝수개 이면서 2의 개수가 최대가 되는 지점입니다. 만약 현재까지의 음수의 개수가 홀수개 였는데, 음수를 한번 더 만나면 현재까지의 수를 모두 곱한 값이 최대가 됩니다. 따라서 그리디하게 풀이할 수 있습니다. 단, 0을 만났을 시 다시 음수의 개수, 2의 개수를 카운트해줘야 합니다. 2 2 2 -1 2 2 2 2 2 2 2 와 같이 왼쪽 -> 오른쪽을 탐색할 때의 오른쪽 -> 왼쪽을 탐색할 때의 결과값이 다르므로 양쪽에서 모두 진행해 줍니다. 배열을 끝까지 탐색하면서 음수가 짝수개가 될 때 현재까지의 2의 개수를 계속 갱신해주고, 최종 2의 개수만큼 곱해주면 답이 됩니다. 2가 하나도 안 나온 경우엔 -1, 0, 1 세 값 중 하나가 정답이므로 예외처리 해주면 됩니다. #include<iostream> #include<algorithm> #include<math.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair<int, int> #define pdd pair<double, double> #define pic pair<int, char> #define ll long long #define vi vector<int> #define vl vector<long long...