Little Jay

스택을 활용하는 전형적인 문제 처음에 커서라는 단어를 봤을 때 이걸 환영 링크드 리스트로 구현을 해야되나라고 생각을 했었는데 생각을 해보니까 커서를 기준으로 왼쪽, 오른쪽으로 스택을 나누어 풀면 쉽겠다라고 생각했다. #include #include #include using namespace std; int main() { string s; cin >> s; int n; cin >> n; string temp; stack left; stack right; for (int i = 0; i > temp; if (temp == "L") { if (left.empty()) con..

'{'가 들어오면 push하고 '}'가 들어올 때는 먼저 stack이 비었는지 확인하고 비어있으면 '{'로 바꿔주고 바꾼 횟수를 늘려준다 만약 empty가 아니라면 pop해주면 된다 스택이 비었으면 return change 스택이 차 있으면 return change + st.size() / 2 #include #include using namespace std; int main() { string s; int test = 1; while (true) { cin >> s; int change = 0; if (s[0] == '-') break; stack st; for (int i = 0; i < s.length(); i++) { if (s[i] == '{') st.push(s[i]); else { if (..

브루트포스 문제 for 문을 돌면서 자신보다 큰 값이 있으면 rank를 하나씩 올려주면 된다. #include #include #include using namespace std; pair arr[50]; int main() { int n, rank = 1; cin >> n; for (int i = 0; i > arr[i].first >> arr[i].second; } for (int i = 0; i < n; i++) { for (int k = 0; k < n; k++) { if (arr[i].first < arr[k].first && arr[i].second < arr[k].second) { rank += 1; } } cout

마지막에 조건으로 이름을 사전순으로 출력해야 되는것을 제대로 못보고 왜 틀렸는지 하루종일 보고 있었다..... 일단 맵이나 해쉬로 풀지 않았다. 이거 같은 경우는 그냥 벡터를 계속 정렬해주면서 binary_search로 빠르게 이름을 찾으면 되는 문제인 것 같다. #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector v(n); v.resize(n); string s; for (int i = 0; i > v[i]; } sort(v.begin(), v.end()); vector ..

hash_table로 풀려고 했지만 채점서버에서 내 코드를 읽지 못해서 vector의 pair기능을 활용해서 다시 풀었다 이것 때문에 많이 문제를 채점해서 좀 그렇다 vector을 두개 사용했는데, 첫 번째 벡터는 바로 번호만 넣으면 출력이 되도록하는 도감으로 만들었고, 두 번째 벡터는 pair을 사용해서 이름과 번호를 같이 넣어서 sort해준 다음 이름순으로 정렬해서 이분탐색하여 찾았다. #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector v1(n + 1); vector v2; v1.push_back(..

쉽게 풀 수 있어 보이는 문제지만 우리는 항상 테스트케이스에 대해서 생각을 해야한다. 무지성으로 임시 변수에 계속 값을 더하면 테스트케이스를 전부 감당할 수 없을 정도의 값이 입력되어 시간초과로 틀릴 수 있는 가능성이 크다 이럴 때는 구간 합 알고리즘을 사용하면 된다. 구간 합 알고리즘은 간단히 설명하자면 어떤 배열이 주어졌을 때, 다른 임시 배열을 만들어서 그 임시 배열에 원래 배열의 부분 합을 더해주면 된다. 흡사 다이나믹 프로그래밍과 비슷하다고 생각하면 된다. #include using namespace std; int arr[100001]{ 0, }; int sarr[100001]{ 0, }; int main() { ios::sync_with_stdio(false); cin.tie(0); cout..

sort를 잘 사용하면 되는 문제 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector v; v.resize(n); int total = 0; for (int i = 0; i > v[i]; } sort(v.begin(), v.end()); for (int i = 0; i < v.size(); i++) { for (int j = 0; j

다이나믹 프로그래밍을 활용해서 푸는 문제이다 이게 조건 3개를 잘 선택해서 배열에 계속 더해야 한다 이 부분을 생각하는데 정말 많은 시간을 소비했다 #include using namespace std; int dp[1000001]; int main() { int n; cin >> n; dp[0] = 0; dp[1] = 0; for (int i = 2; i

map을 이용해서 풀면 간단히 해결할 수 있는 문제 linux 채점환경이기때문에 시간초과가 나지 않으려면 ios::sync_with_stdio(false); cin.tie(0); 를 추가해주어야 한다 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; string site, pw; map mp; for (int i = 0; i > site >> pw; mp.insert(pair(site, pw)); } for (int i = 0; i > site; cout second

비트마스킹 처음으로 비트마스킹에 대해서 다뤘던 문제이다. 처음에는 무지성으로 벡터를 이용해서 풀면 될 줄 알았지만, 백준에 달려있는 태그랑 메모리를 보니까 이거는 벡터로 풀면 안되겠다는 것을 깨달았다. 자바를 배울때 stream 연산자를 배워놔서 조금은 쉽게 공부하고 풀 수 있었다. #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); long long n; cin >> n; string s; int x, BIT = 0; for (long long i = 0; i > s; if (s == "add") { cin >> x; BIT |= (1 > x; BIT &= ~..