🖍️ 겪은 문제방문처리를 맵 전체를 담기에는 메모리를 많이 잡아먹을 것 같고..하지만 0의 위치만으로는 방문처리를 정확히 할 수 없음..🔍 해결 방법전체 상태를 하나의 키로 저장하기 위해서 set을 이용함.1 2 34 5 67 0 8 이면 -> "123456708"을 set에 등록해서 방문 처리처럼 사용함.📇 코드#include #include #include #include using namespace std;int dx[4] = {-1, 1, 0, 0};int dy[4] = {0, 0, -1, 1};int bfs(string start) { unordered_set visited; queue> q; visited.insert(start); q.push({start, 0});..
Algorithm
차이다익스트라 : 하나의 시작점에서 다른 모든 정점까지의 최소 거리매번 가장 적은 비용을 가진 노드를 하나씩 꺼내, 가장 적은 비용을 하나씩 선택함.플로이드 와샬 : 모든 시작점에서 에서 다른 모든 정점까지의 최단 거리애초에 거쳐가는 정점을 하나씩 다 설정해서 직접 확인함. 거쳐가는 정점을 기준으로 최단 거리를 구성함. 우선순위 큐를 이용한 다익스트라우선순위큐 + BFS의 형태를 가진다.각 정점까지의 최단거리를 저장하는 배열 dp[]를 유지하고, 정점을 방문할 때마다 인접한 정점을 모두 검사한다.#include #include #include #include using namespace std;const int INF = 1e9;int V, E, start;void dijkstra(int start, v..
🖍️ 겪은 문제5 * 5 * 100,000,000,000 = 2조5천억번의 제곱연산...1억번이 1~2초니까 1조번의 연산이면 10000~20000초임(시간초과가 안나는게 이상)🔍 해결 방법지금은 계속 원본 행렬만 곱하는데 a2 * a = a3.. 이런 식으로 원본 행렬의 제곱끼리 곱하는 방식을 이용하는건 어떨까?단, 2의 제곱수가 아닌 5와 같은 수면 a2 * a2 * a라는 걸 어떻게 계산해서 구하지? log연산을 해야하는건가?10이면 a4 * a4 * a22조 5천억은 2의 42제곱이라고 함. 그러니까 연산 횟수를 줄일 수 있을 것 같음.📇 코드#include #include using namespace std;int N;using Matrix = vector>;Matrix multiply(M..
🖍️ 겪은 문제시간 초과🔍 해결 방법substr로 폭발 이전꺼 + 폭발 이후꺼 를 잘라서 더했더니 시간 초과가 발생했다.result배열에 하나씩 추가하며 폭발 시 폭발 문자열 길이만큼만 지우도록 하여 시간 초과를 해결했다.📇 코드#include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string str, boom; cin >> str >> boom; string result = ""; int boomLen = boom.length(); for (char ch : str) { result += ch; ..
풀이 방법을 생각해내지 못해서 결국 검색해서 풀었다.참고로, 입력 종료를 위해 EOF를 입력하려면 맥(리눅스)기준으로 Cmd + D를 입력하면 된다.🔍 해결 방법전위 순회로 30 24 5 28 45 다음과 같은 트리가 있을 때,30(루트)을 기준으로 더 큰 값이 나오기 전까지는 모두 왼쪽 자식 노드에 해당한다. 30 (24 5 28) 45그리고 나머지는 오른쪽 자식 트리에 해당하게 된다.이 탐색을 재귀적으로 반복해서, 탐색하는 범위가 1개가 되는 경우나 맨 마지막 노드일 경우에 출력해주면 된다.📇 코드#include #include using namespace std;vector v;void printPost(int start, int end) { if (start >= end) return; ..
🖍️ 겪은 문제다익스트라로 풀었는데 시간 초과가 발생했다.priority_queue의 기본값은 내림차순 정렬인 것을 망각했다.🔍 priority_queue 선언 방법template, class Compare = std::less> class priority_queue;인자 설명T : 정렬할 요소의 타입, 큐에 저장할 타입Container :내부적으로 데이터를 어떻게 저장할지를 나타내는 컨테이너 타입Compare :요소를 정렬할 기준이 되는 함수 객체(함수 포인터 또는 functor)less: 큰 값을 먼저 꺼냄 → Max Heap (기본값)greater: 작은 값을 먼저 꺼냄 → Min Heap그래서 다음과 같이 선언하면 내림차순이 된다.priority_queue, vector>, greater..
🖍️ 겪은 문제한 번 지나간 길을 다시 안가는 문제가 있었다. visited[방향][x][y] 배열 때문이었다.🔍 해결 방법최단거리가 아니므로, visited 배열이 필요가 없다. bfs로 모든 루트를 돌면서 도달하는 cnt만 재면 되었던 문제다.📇 코드#include #include using namespace std;int N, cnt = 0;bool board[16][16];enum DIR { HOR, VER, DIAG};enum MAP { EMPTY, WALL};struct Pipe { int x; int y; int dir;};bool checkEnd(Pipe p) { if (p.dir == HOR && p.x == N-1 && p.y == ..
🖍️ 겪은 문제문제 해결 아이디어가 안떠올랐다. 완전 탐색으로 풀면 시간 초과였다. 역시나 DP였다.🔍 해결 방법DP최소 단위를 설계한다.dp[n]을 n무게일 때 최대 가치라고 하자.점화식을 세운다.dp[i] = max(dp[i], dp[i - weight[i]] + value[i]);포인트는 순회를 거꾸로 K에서부터 1씩 줄여나가며 한다는 것이다.1에서 부터 돌면 점화식에서 더 작은 값을 이용하기 때문에, 이미 계산한 물건을 또 담을 수 있다.📇 코드#include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, K; ..
🖍️ 겪은 문제한 글자씩 이동시켜가면서.. 누적해서 탐색해야하나? 생각을 했는데 풀이 방법이 떠오르질 않았다.보통 이러면 DP더라.🔍 해결 방법A문자열에 대한 인덱스 i, B문자열에 대한 인덱스 j를 1씩 증가시켜가면서 LCS값을 누적하며 계산해서 최종적으로 [A문자열 길이][B문자열 길이]를 알아낸다. -> DP로 풀이해야 한다.DP설계하기 : dp[i][j]를 A문자열의 i번째 문자까지 부분 문자열과, B문자열의 j까지 부분 문자열 간의 LCS 길이라고 하자.점화식 세우기dp[i][j]가 같으면 현재 비교하는 문자 이전 까지 비교한 거에 1더한거 => dp[i][j] = dp[i-1][j-1] + 1같지 않으면 A에서 하나 빼고 & B 그대로, A 그대로 & B에서 하나 뺀거 중에 더 큰 LCS값..
🖍️ 겪은 문제최댓값과 최솟값 계산 결과를 담기 위한 배열을 [100000][3] 사이즈로 만들었다.총 byte수로는 360만 = 3600KB = 3.6MB라서 4MB 이내니까 괜찮겠지 했는데 메모리 초과가 발생했다.🔍 해결 방법어짜피 이전행과 현재행만 필요한 거기 때문에 dp배열을 [2][3]으로 선언해서 i%2로 줄만 번갈아서 사용해서 해결했다.GPT가 이 방식을 슬라이딩 윈도우라고 알려줬다.마치 미닫이문이 스르륵 옮겨가듯 조회하는 행이 스르륵...............📇 코드#include #include using namespace std;int N;int board[100000][3];// N 최댓값만큼 만들 필요가 없구나...// 2줄만 만들고 최근 누적값까지만 기록하고 i % 2 로 줄..
