Algorithm/PS

🖍️ 실패한 원인드래곤 커브 구현 방법을 생각하는 과정에서 방향 변화에 규칙이 있을 것 같다고 유추는 하였으나,규칙을 발견을 못했고, 공식으로 풀어내지 못함 ㅜㅜ (결국 답안을 보고 풀이했다...)🔍 해결 방법드래곤 커브 n세대는 드래곤 커브 n-1세대의 방향을 역순으로 해서, +1한 뒤(반시계 90도 회전) %4를 하면 된다.(x+1)%4까지는 계산해봤는데 역순일거라고 생각을 전혀 못했다.회전을 하게되면 방향의 순서가 바뀌게 되어서 역순이 되는데 그걸 캐치를 못했다... 다음에 비슷한 문제가 나오면 생각해서 풀 수 있도록 잘 익혀두자!!📇 코드#include #include #include #include #include using namespace std;const int SIZE = 101;b..

🖍️ 겪은 문제백트래킹으로 푸는 방법을 아예 몰라서 1~3중까지 for문으로 구현해 풀려고 하였으나, 코드가 길어지다보니 로직에 오류가 생겼음.그래서 문제를 풀지 못했다 ㅜㅜ 복습을 할 때 참고하려고 가장 마음에 드는 풀이를 보고 글을 적는다.🔍 해결 방법DFS 백트래킹을 적용함.check() 함수는 열에 대해 순회하며현재 위치에 true가 있으면 다리를 타고 우측으로 이동하므로 pos를 ++, 현재 위치 좌측에 true가 있으면 다리를 타고 좌측으로 이동하므로 pos를 --해서최종 pos가 시작한 열과 동일하면 조건을 만족한다고 판단함.📇 코드#include #include #include #include #include using namespace std;int N, M, H;int minCnt..

🔍 해결 방법행 열에 대해 검사하는 bfsRow()와 bfsCol()을 만듦.재귀로 구현할 수도 있었을텐데 queue를 쓰는게 더 편할 것 같아서 이렇게 짬.그리고 이미 경사로가 만들어진 것을 구분하기 위해 already라는 bool형 벡터를 만들어놓고 탐색 시작.경우의 수는 다음과 같음앞으로 이동할 곳의 높이가 더 높은 경우더 낮은 경우각 경우에 맞게 경사로를 설치할 수 있는지 여부를 판단해서 불가하면 false를 리턴하도록 함수를 설계함.📇 코드 (주석 포함)#include #include #include #include #include using namespace std;struct Axis { int x; int y;};int n, l;vector> v;bool bfsRow(int ..

이전에 낚시왕 문제에서 1억이면 1~2초정도 걸린다는 걸 배웠다. 그래서 최악을 생각해보니 1억 미만이길래 아 그럼 완전탐색으로 풀어도 되겠구나 싶어서 무려 6중 for 문을 만들었다 ㅋㅋ📇 코드#include #include #include #include #include using namespace std;struct Axis { int x; int y;};int dx[4] = {-1, 1, 0, 0};int dy[4] = {0, 0, -1, 1};const int DIR_MAX = 4;int n, m;const int WALL_MAX = 3;const int WALL = 1;const int VIRUS = 2;const int EMPTY = 0;vector> v;int bfs(queue..

문제 안에 봄, 여름, 가을 겨울이 있는 마치 폭싹 속았수다 같은 문제였다..🖍️ 겪은 문제시간 초과..로직은 잘못된 게 없는 것 같은데 시간 초과가 났다.🔍 문제 파악기존 코드에서 vector에 새로 추가할 나무를 다 담아놓고, 매년마다 맨 처음에 age 오름차순 기준으로 정렬했었다.이를 해결하기 위해서 연도에 해당하는 for문 들어가기 전에 정렬을 1번만 하고,나무를 저장하는 자료구조를 deque로 변경하고, 새로 추가될 나무들은 맨 앞에 삽입하도록 수정했다.이후에는 babyTrees라는 deque를 따로 분리해서 매년 겨울 종료 후 앞에 붙여주도록 했다.📇 코드#include #include #include #include #include using namespace std;struct Tre..

우리 조카가 보는 아기상어는 귀여운데.. 문제 속 아기 상어는 그렇게 귀엽진 않다.. 약육강식 야생의 상어다.문제 이해의 미흡이 가장 크다....끝까지 다 안읽고 int n.. 하고 코드를 쓰고있다..(^.ㅜ) 습관을 고치자!!!!🔍 문제 파악상어는 현재 크기만큼의 물고기를 먹어야 사이즈업을 한다!📇 코드#include #include #include #include #include using namespace std;struct sharkMove { int x; int y; int time;};int n, sx, sy, sSize = 2, t = 0, eatCnt = 0;vector> v;int dx[4] = {-1, 1, 0, 0};int dy[4] = {0, 0, -1, 1};c..

왼쪽(9시 방향)과 오른쪽(3시 방향)의 인덱스를 기억해서시계 방향 회전 시 인덱스가 하나씩 줄어들고반시계 방향 회전 시 인덱스가 하나씩 늘어나는 원리를 이용함.🖍️ 겪은 문제회전을 하기 전에 양 옆의 노드랑 같은지 체크하고, 회전한 뒤에 다른 값을 가지던 톱니는 반대로 회전해줘야하는데회전을 한 뒤에 양 옆의 노드를 비교하니까 결과가 다르게 나옴 ㅜㅜ 🔍 문제 해결회전하는 로직을 재귀함수의 맨 뒤로 이동시켜서 회전을 나중에 수행하도록 변경!📇 코드#include #include #include #include #include using namespace std;struct Topni { int leftIdx; // 9시 int rightIdx; // 3시};const int TOPNI_L..

상어를 크기순으로 소팅하고 시작해서, 해당 칸에 이미 상어가 있으면 나중에 온 상어는 추가하지 않도록 했다.🖍️ 겪은 문제상어를 이동시킬 때 shark.speed만큼 반복 하다보니 시간 초과가 발생했다.100 (턴) × 1000 (속력) × 10,000 (상어 수) = 1,000,000,000 (10억 번 연산)1억이면 1~2초정도 걸린다고 하는데, 이 경우면 10초가 넘게된다..🔍 문제 해결현재 위치에서 한 주기를 돌면 다시 현재 위치로 오니까주기를 계산해서 모듈러 연산으로 주기만큼 제거하고 나머지 이동량만큼만 이동시켰다.📇 코드#include #include #include #include using namespace std;struct Shark { int x; int y; i..

겪은 문제 (멍청)7 74 2 11 1 1 1 1 1 11 0 0 0 1 0 11 0 1 1 0 0 11 0 0 0 0 1 11 0 0 1 0 0 11 0 0 0 0 0 11 1 1 1 1 1 1>> 답 11위 케이스에서 답이 11이 나와야 했는데 9가 나왔다. 🔍 문제의 원인게시판을 돌다보니 나처럼 해당 케이스에서 어려움을 겪는 사람이 있었고, 해결사가 댓글에 루트를 달아주었는데, 이런!!! 나랑 영 다른 길을 간다...알고보니 멍청한 실수를 했다. 방향이 1~4가 아니라 0~3 인데, 나는 1 베이스를 제로베이스로 만든다고 dir을 -1한 뒤 시작했다...🥹... 코드이해하기 쉬우라고 일부러 주석을 안지웠다.#include #include #include #include using namespac..

어떻게 풀까 막연히 생각해보면,테이블 블록을 bfs로 찾고 (A)게임 보드의 빈공간을 bfs로 찾아서 (B)A와 B가 같은 모양일 때 블록 칸 수를 answer에 더해주면 되겠는데? 크게 보면 간단한데, 같은 모양을 판별하는데 시간이 오래걸렸다.회전을 시킬 수 있기 때문이다...  그래서 같은 모양 판별을 하기 위해서 아래 작업들을 해줬다. 1. 같은 모양이더라도 누군 (2,4)부터 그려지고, 누군 (3,8)부터 그려지고.. 하면 비교가 어려우므로 각 블록들의 좌표를 0-base로 만들어줬다. 그리고 좌표를 시계방향으로 돌리다 보니까 규칙을 발견했다!!!현재 좌표를 x, y 라고 하고, 90도 시계방향 회전한 좌표를 x', y'라고 하면 아래 공식이 성립된다.x' = yy' = (돌리기 전 height ..