🔍 다익스트라 해결 포인트그래프 자체를 vector> buses[N]; 으로 선언해서 a->b로 이어지는 간선을 buses[a].push_back({b, 비용}); 이렇게 표현한다.그래프를 탐색할 때는 Priority Queue를 사용해서 비용이 작은 순서로 순회하도록 한다.선언은 오름차순이면 priority_queue> pq;내림차순이면 priority_queue, vector>, less> pq;시작 노드부터 출발해서 누적된 거리를 담기 위한 dist 배열은 최댓값으로 초기화한다.📇 코드#include #include #include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.ti..
Algorithm
🖍️ 겪은 문제DFS 백트래킹으로 풀었다가 시간 초과가 발생했다.🔍 해결 방법알고리즘 보기를 눌러보고 DP로 풀어야 한다는 점을 알게됐다. 그래서 DP로 풀이했는데 너무 오랜만에 DP문제 혼자 성공해서 뿌듯해서 로그를 남긴다 🥹근데, DP로 풀어야하는 문제인지를 어떻게 알 수 있을까?각 집마다 3가지 색상을 선택할 수 있음. 최악의 경우에 3^1000이 됨.int의 범위가 -2^31 ~ 2^31 - 1 이므로, 엄~~~~청 큰 수다.📇 코드#include #include #include #include #include using namespace std;int dx[] = {1, 0, -1, 0};int dy[] = {0, -1, 0, 1};struct Price { int r; int..
🖍️ 실패한 원인드래곤 커브 구현 방법을 생각하는 과정에서 방향 변화에 규칙이 있을 것 같다고 유추는 하였으나,규칙을 발견을 못했고, 공식으로 풀어내지 못함 ㅜㅜ (결국 답안을 보고 풀이했다...)🔍 해결 방법드래곤 커브 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..
