전체 글

🖍️ 겪은 문제방문처리를 맵 전체를 담기에는 메모리를 많이 잡아먹을 것 같고..하지만 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});..

차이다익스트라 : 하나의 시작점에서 다른 모든 정점까지의 최소 거리매번 가장 적은 비용을 가진 노드를 하나씩 꺼내, 가장 적은 비용을 하나씩 선택함.플로이드 와샬 : 모든 시작점에서 에서 다른 모든 정점까지의 최단 거리애초에 거쳐가는 정점을 하나씩 다 설정해서 직접 확인함. 거쳐가는 정점을 기준으로 최단 거리를 구성함. 우선순위 큐를 이용한 다익스트라우선순위큐 + 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..

함수 타입은 어떤 "타입의" 매개변수를 받고, 어떤 "타입의" 결과값을 반환하는지 표현한다.반환값 타입은 생략해도 알아서 추론하기 때문에 생략해도 괜찮다.function func(a: number, b: number) { return a + b;}화살표 함수의 타입일반 함수에서와 동일하게 반환값 타입은 생략해도 알아서 추론하기 때문에 생략해도 괜찮다.const add = (a: number, b: number): number => a + b;필수 매개변수와 선택적 매개변수function intruduce(name = "머랑", tall: number) { console.log(`name : ${name}`); if (typeof tall === "number") { con..

🖍️ 겪은 문제시간 초과🔍 해결 방법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; ..