🔗 문제https://www.acmicpc.net/problem/31863 # 문제 내용 오늘 새벽, 갑자기 규모 5.0 지진이 발생했다. 지진이 발생한 진원지는 N×M 격자 모양의 지역 중 한 곳이다. 진원지에서 발생한 지진을 본진, 건물이 무너졌을 때 발생하는 약한 지진을 여진이라고 하자. 본진은 진원지를 기준으로 상하좌우 각 방향으로 2칸까지 뻗어나가며, 여진은 상하좌우로 1칸까지 뻗어나간다. 본진과 여진은 건물에 영향을 준다. 내진 설계가 되어 있지 않은 건물은 지진이 도달한 즉시 무너지지만, 내진 설계가 되어 있는 건물은 지진이 2번 도달하면 무너진다. 본진과 여진이 뻗어나가는 도중 지진 방파제를 만나거나 격자 모양의 지역 밖으로 나가면 더 이상 뻗어나가지 않는다.  ✏️ 풀이 자 문제를 정리..

🔗 문제https://www.acmicpc.net/problem/1063 ✏️ 풀이 시키는 방향대로 이동하면 된다. 킹이나 돌맹이의 이동은 간단한 `BFS`로 풀 수 있다.  이 문제가 실버3 인 이유는 위치가 x, y가 아니라 문자열로 주어진다는 점이다.문자열 변환은 그냥 아래처럼 배열을 만들어줬다. const char strCol[8] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}; 이렇게 하면 실제 열과 문자열의 순서가 맞는다. 행은 그냥 역순으로 계산해주면 되어서 7-row로 구했다.   이동해야할 것을 dir와 strDir를 순서를 맞춰 보관한다. 방향이 주어지면 for문으로 맞는 방향으로 이동해주었다. const int dir[8][2] = {{-1, -1}, ..

🔗 문제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.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..

🔗 문제https://www.acmicpc.net/problem/10159  ✏️ 풀이N개의 정점 (N ≤ 100)M번의 대소 비교처음에는 대소 관계 위상정렬인가 싶었다.하지만 문제는 i번째 아이템이 다른 아이템의 순서를 파악하지 못 하는 수를 출력해줘야 한다. 대소 관계가 주어졌다는 건 그래프 관계로 만들 수 있다는 것이고, 순서를 파악하지 못 한다는건 분리된 그래프라는거 아닐까? 라는 생각으로 dfs랑 플로이드워셜 알고리즘을 생각했다. dfs는 내가 잘 못 하니까 플로이드 워셜 알고리즘으로 풀었다 🙂 플로이드 워셜 문제는 주로 정점이 500개 이하일때 권장되는 풀이이므로 바로 적용해서 풀었다. 플로이드 워셜 시간복잡도 : `O(V^3)`모든 정점 쌍에 대한 최단 경로를 계산하느라 3중 포문을 돌기..

🔗 문제SW Expert Academy SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  🖍 풀이양방향 리스트를 지원하는 컨테이너 list 를 활용해서 풀어도 된다. 기존 암호문: list의 뒤에 데이터를 연달아 삽입한다.새 암호문: list는 임의 위치 엑세스가 불가하다는 특징이 있다. 그래서 string이나 vector처럼 container[i+x]가 불가능하다. 대신 반복자 iter를 사용해주었다. list의 begin()부터 x번 반복자를 이동시켜야 삽입할 위치를 iter에 저장한다. 그리고 나서 insert(삽입 위치, 데이터)하여 새 암호문을 넣어준다.이 때, 명령문마다 삽입할 위치 (x)가 다르므로..

🔗 문제SW Expert Academy SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com ✏️ 풀이문제에서 대놓고 비트마스크라고 힌트를 주어서 어렵지 않은 문제지만 생각해보지 못한 풀이 방법을 배워서 풀이를 남긴다. 일단 문제를 읽자. (위 사이트 참고) M이 최대 10^8승 (1억)이므로 배열로 순회하면 C++ 기준 1000ms 이내에 제출해야 하는데 바로 시간초과행이다 🙂그에 비해 N은 최대 30이므로 절대 시간초과가 안 걸릴 줄 알았는데 시간초과에 걸렸다.테스트케이스가 1만개 중에 9883개를 맞추길래 부랴부랴 FAST IO를 적용해서 맞출 수 있었다. FAST IO를 습관화 하자.1000ms를 못 넘겨서 ..

🔗 문제https://www.acmicpc.net/problem/1236  ✏️ 풀이풀이는 간단하다.각 행과 열에서 X 경비원이 없는 곳의 개수를 세면 된다.그리고 그 개수 중 큰 것이 답이 된다.  예제 2를 보자. 정답은 3이다.행에서는 X가 없는 곳이 3 줄열에서는 X가 없는 곳이 1 줄5 8....XXXX........XX.X.XX................. 배열로 확인하면 되지만 비트마스킹으로 푼 것에 의의를 두었다.안 쓰면 까먹게 되는 지식들.. 다시 한 번 정리하며 풀이 소스를 올린다. 비트 설정 (set)int number = 0b0000; // 초기 값int mask = 0b0001; // 1을 설정할 마스크number |= mask; // number는 이제 0001 ..