🎆

https://www.acmicpc.net/problem/14499Intuition문제 자체가 그렇게 이해하기 어렵진 않아서 주사위를 이동하는 것만 잘 구하면 된다고 생각했다.Approach어느방향으로 움직이더라도 특정 면이 아래에 있을때 동서남북에 오는 면이 고정될 것이라 생각했는데 아니었다. 이걸로 30분 날렸다top_n이 하늘을 바라보는 면, ns 가 top_n 기준으로 북쪽에 있는 면으로 한다.특정 면을 기준으로 북쪽에 어떤 면에 있는지에 따라 동 서에 오는 면이 달라지므로 이를 넣었다.예를들어 top_n = 1, ns = 2라면 동쪽으로 움직일때 top_n이 4, 6, 3, 1 ~~ 원형으로 변한다. // 1 -> 5 4 2 3// 2 -> 1 4 6 3// 3 -> 5 1 2 6// 4 -> ..

Intuition단순 수학 구현으로 풀면 된다고 생각했다.Approach(각 시험장의 감시자 수 - 총감독관(B))/C + (각 시험장의 감시자 수 - 총감독관(B))%C ? 1 : 0;으로 구현했다. 하지만 각 시험장의 감시자 수 - 총감독관(B)이 음수가 되는 경우를 고려하지 못해 몇번 틀렸다.음수인 경우 각 시험장의 감시자 수 - 총감독관(B)을 0으로 바꿔주면 된다.Complexity- Time complexity : O(N)- Space complexity : O(N)Code#include using namespace std;long long ans;int main() { long long N, arr[1000001]; cin>>N; for (int i=0; i>arr[i]; ..

https://www.acmicpc.net/problem/3190 풀이먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.다음 순서에 맞게 구현하면 된다.뱀 전체 칸을 따로 관리하지 않고, Queue에 들어가는 값이 머리, 외부 변수에 꼬리를 저장하고 머리가 움직이는 방향 그대로 꼬리가 움직이도록 dirb 배열에 머리가 움직이는 방향을 넣어줬다. #include #include #include #include using namespace std;// 1행 1열..

https://www.acmicpc.net/problem/12100소요시간 (2:01:00)풀이4개의 방향으로 갈 수 있는 모든 경우의 수를 생각해서 이동해주면 되는 문제다.블록이 밀리면서 합쳐지는 것만 잘 구현해주면 된다.void shift_left(vector >& ori) { vector > v(N); // 전부 왼쪽으로 이동 for (int i=0; i네 방향으로 합치는 로직이 다음과 같이 동일하게 구성되어 있다.방향에따라 우선순위를 가지는 칸부터 행렬형식으로 만들어 준 다음 좌표에 따라 합쳐주는 역할을 한다.네방향으로 이동, 합치는 로직만 잘 써주면 된다. //// Created by ljh on 25. 3. 28.//#include #include #include using n..

https://leetcode.com/problems/remove-element/description/?envType=study-plan-v2&envId=top-interview-150IntuitionInplace로 변환을 해야하기 때문에 추가적인 변수 선언을 하지 않고 배열을 변경하는 방법을 사용한다고 생각했다.Approach배열의 탐색과 무관한 idx 포인터를 잡아 배열의 원소 중 val과 다른 원소가 나올 경우 idx에 저장하도록 구현하였다. Inplace의 목적에 맞게 배열에 대한 추가적인 공간이 필요 없도록 구현하였다.Complexity- Time complexity : O(N)- Space complexity : O(1) Codeclass Solution {public: int remov..

지금까지 사용한 동전의 총 금액이 같다면 -> 동전이 적을수록 / 많을수록 더 좋다.dp[i] = 지금까지 선택한 동전의 합이 i일때, 가능한 최대 동전의 개수. dp[i] = max/min ( 0= coin[j] ) dp[i - coin[j]] + 1  for(int i=1; i i || dp[i - coin[j]] == -1) continue; if(dp[i] == -1) { dp[i] = dp[i - coin[j]] + 1; }else { dp[i] = min(dp[i], dp[i - coin[j]] + 1); } } } dp[0] = 0이고, 0을 기준으로 coin ..

문제더보기풀이조건은 찾았는데 순열을 출력을 못해서 틀렸다.... 우선 identity permutation 에서 수의 위치를 바꿔 나올 수 있는 최대 차의 합은 역순이다.그리고 결국 특정 x와 y에 대한 순서를 바꾸게 된다면, abs(x-y) + abs(x-y)이다. 그러므로 두 쌍식 나오게 되므로 홀수가 답이 될 수 없다. 순열을 구하기 위해서는 수학적인 규칙을 찾아야된다.[1, 2, 3, 4, 5, 6 ~~~~ xn] 가 있다고 하자. 1의 위치를 특정한 xi와 바꾼다고 하면, 그로 인해 발생하는 값은 1 - xi, xi - 1이다. 차의 절댓값의 합으로 나타내야 하므로 결국 (xi - 1) * 2 ( xi > 1 ) 이 된다.1의 위치와 xi 의 위치를 바꾸는 경우가 위치를 바꾸는 경우의 수 들 중..

문제더보기풀이일하다가 정규식을 많이 경험했는데 딱 보자마자 그냥 정규식 쓰라는 문제라고 생각했다. (100+1+|01)+가 끝이다..정규식 몇백자짜리 조건맞추느라 눈물흘리면서 썼었는데 도움이 되는거같다. #include #include #include using namespace std;bool matchReg(const string& str) { regex reg("(100+1+|01)+"); return regex_match(str, reg); }int main() { string str; cin>>str; if(matchReg(str)) cout

문제더보기풀이그리디하게 풀 수 있을까 생각해서 시도했지만 풀지 못했다. 포함 배제 원리를 기반으로한 카운팅 방식으로 문제를 해결해야한다. 포함 배제의 원리포함배제 원리란 각 집합의 합집합의 크기를 구하기 위해 사용되는 방법이다. Ai가 하나의 집합일때, A1 ~An의 합집합을 구하기 위해서는 겹치는 부분(교집합)을 빼줘야한다.하지만 교집합을 빼주는 과정에서 중복된 부분이 생기고, 이 중복된 부분을 다시 체크해줘야 된다.포함 배제의 원리는 집합의 개수가 홀수일때 전체 개수에 더해주고, 짝수일때 빼서 전체 합집합의 개수를 구하는 방법이다. 결국 [1, 2, 3, 4, 5]라는 입력이 들어왔을때 [1], [1,2], [1,3] ~~~ [1,2,3,4,5]와 같은 모든 집합의 조합의 경우의 수를 생각하고, 원소..

문제더보기풀이결국 이분그래프를 만드는 문제다. 51 31 52 1 41 31 2의 경우를 예로 들자. 싫어하는 관계를 유향그래프로 그리면 이렇게 나타낼 수 있다. 여기서 1번노드부터 청팀에 들어간다고 가정하자. 그렇게 된다면 1번 노드는 3번을 싫어하므로 3번은 무조건 백팀에 들어가게 된다. 3번을 기준으로 3번노드는 4번을 싫어하므로 4번노드는 청팀에 들어가게 된다. 4번노드는 싫어하는 노드가 없으므로, 다시 2번노드부터 청팀에 넣고 시작하게 된다면 다음과 같은 그래프가 그려지게 된다. 싫어하는 사람이 하나도 없는 경우는 없으므로, 한명만 싫어하는사람이 한명 있는 경우가 탐색의 기준에서 가장 오래 걸리는 경우다. 모든 노드를 한번씩만 방문하면 되므로 O(N)이다. #include #include #in..