전체 글

🔗 문제https://www.acmicpc.net/problem/17299 ✏️ 풀이 입력되는 N의 개수는 1,000,000 (백만)이다.숫자의 크기 또한 최대 1,000,000 (백만)이다. 가장 나이브하게 할 수 있는 방법 Ai 마다 F 배열을 탐색하면 O(백만 X 백만) => 시간초과다.  어떻게 푸는지 모르겠어서 30분 고민했는데 모르겠어서 답을 봤다. 일단 유형이 `stack`이었고, 나는 그걸 생각해 내지 못했으니까 문제에서 무엇을 보고 알고리즘을 유추했어야 했는지 해석하는 풀이를 올리겠다.   `stack`에는 idx가 들어간다. 값이 아니라 idx가 들어가는 이유는 답을 idx 순으로 출력해주어야 하기 때문이다.  stack에 저장되는 조건은 F[idx]가 stk.top()에 들어 있는 ..

🔗 문제https://www.acmicpc.net/problem/15989✏️ 풀이 이 문제가 어려운 이유는 중복 순서가 허용되지 않기 때문이다.  당연히 숫자를 바텀업 방식으로 이전의 숫자를 만드는 방법을 활용해야겠다는 생각이 든다. 이게 바로 dp 구나 깨닫는 과정 같은데 점화식 만드는 게 쉽지 않다.  나는 이 문제를 완전 탐색으로도 못 짜겠어서 고생을 했다!그래도 문제가 1, 2, 3으로만 이루어져 있다는걸 생각하면 활용할 수 있다.  이 문제는 점화식을 만드는 과정이 아니라 설명을 하는게 맞는 것 같다. DP.resize(MAX, vector(4, 0)); // 1, 2, 3 인덱스를 사용하기 위한 사이즈 조정DP[0][1] = DP[1][1] = DP[2][1] = DP[2][2] = 1; ..

🔗 문제 https://www.acmicpc.net/problem/1445 ✏️ 풀이문제를 잘 읽어야 하므로 특. 별. 히 캡처를 해왔습니다. 저는 노란 부분만 잘 읽으면 된다고 생각하고 난이도도 골4라고 생각됩니다.  구현 문제는 정리를 하고 풉니다.  [나는 무엇을 구현해야하는가?]2차원 배열에서 출발지가 주어지고 '쓰레기칸', '쓰레기인접칸'을 최소로 밟고 목적지까지 도달하는 것.출발지와 목적지가 주어져있고, 재방문 여부와 상관없이 가중치만 최소로 해야 한다. -> 다익스트라 이렇게 차분히 생각하면 알고리즘을 특정할 수 있고 문제가 쉬워집니다.  [조금의 최적화]특정 위치가 쓰레기 인접칸인지 확인하려고 매번 4방 탐색을 한다?같은 칸을 여러 번 방문하는 다익스트라 특성상 비효율적입니다. 쓰레기위치..

https://www.robotstxt.org/robotstxt.html  The Web Robots PagesAbout /robots.txt In a nutshell Web site owners use the /robots.txt file to give instructions about their site to web robots; this is called The Robots Exclusion Protocol. It works likes this: a robot wants to vists a Web site URL, say http://www.example.cwww.robotstxt.org  구글이 참 정리를 잘 해놓음 https://developers.google.com/search/docs/cra..

🔗 문제https://www.acmicpc.net/problem/13549  ✏️ 풀이 [알고리즘]다익스트라 X*2로 이동할 경우는 가중치가 0이기 때문에 나이브하게 BFS로 풀면 안 된다.이 경우는 다익스트라로 접근하여 최소 가중치를 찾아주는 방식을 떠올려서 풀면 된다.  [시간 최적화 방법]수빈이가 동생보다 앞에 있다면 뒤로 한 칸씩 이동해줄 수밖에 없다.수빈이가 동생과 같은 위치라면 연산이 필요 없다.if(N >= K) cout  💾  소스#include #include #include #include using namespace std;typedef pair pii;const int MAX_N = 200000 + 1;int N, K;int getAnswer(){ priority_que..