BFS5 BOJ2020 부분 염기서열 2020번 부분 염기서열 주어진 염기서열을 문자열로 볼 때, 문자열의 모든 부분 문자열에 대해 m번 이상 나타나는 부분 문자열의 개수를 구하고 1)길이 2)사전식 으로 나열했을 때 k번째의 부분 문자열을 구한다. 두 가지 방법이 있다. 1. BFS 2. Suffix, Prefix 활용 두 방법 모두 길이 순으로 부분 문자열을 찾는다는 게 그나마의 공통점인 듯 1. BFS 길이가 len인 어떤 문자열 s가 m번 이상 등장한 경우 문자열 s를 prefix로 하고 길이가 len+1인 문자열 s'를 찾아 탐색하면서 길이가 짧은 순으로 문자열을 탐색할 수 있다. 아래 두 자료구조를 사용한다. queue Q; map M; 먼저 길이가 1인 부분 문자열을 찾아야 한다. for (int i = 0; i < n; i++.. 2021. 8. 25. BOJ2549 루빅의 사각형 2549번 루빅의 사각형 4×4 격자판이 있다. 행을 한 개 골라 아래쪽으로 k번(1≤k≤3) 움직이거나 열을 한 개 골라 오른쪽으로 k번(1≤k≤3) 움직이는 것을 한 번 움직인다고 한다. 격자판의 숫자가 주어질 때, 최소 횟수로 격자판을 움직여 1부터 16까지 순서대로 배열된 격자판으로 만드는 횟수(≤7)와 방법을 출력한다. 일단은, 되는대로 BFS를 돌려봤지만 역시 메모리 초과로 통과할 수 없었다. 한 번 움직이는 경우의 수는 8(행/열 개수)*3(k 개수)였고 아무리 정답이 7번 이내로 나온다 해도 24^7개의 경우를 확인하려니 당연히,, 몇 가지 최적화로 가짓수를 줄여봤지만 그래도 메모리초과였다. 방법 1. BFS + 양방향 탐색 + map BFS로 찾되 양방향으로 탐색하기로 했다. 주어진 상태.. 2021. 7. 25. 그래프 (2) 문제들 2593 Elevator BFS DP N층짜리 건물에서 주어진 수열의 층에서만 멈추는 엘레베이터가 M대 있을 때 A층에서 B층까지 가기 위해 최소한으로 갈아타는 엘레베이터의 수 & 내렸던 층을 구한다. 트래킹때문에 좀 복잡했던 문제같음.. 더보기 현재 층 curf에서 탈 수 있는 엘레베이터 cure cure에서 내릴 수 있는 다음 층 nxtf nxtf가 B와 같다면 종료 다르다면 nxtf를 큐에 넣고 다음 엘레베이터 nxte로 갈아타며 dp를 업데이트 // Initiate for (int e : f[A]) dp[A][e] = { 1,0 }; Q.push(A); // BFS and Get Ans bool arrived_at_B = false; while (!Q.empty()) { arrived_at_B =.. 2021. 4. 26. 그래프 (1) 최근 푼 문제 아니,,블로그 정리를 어떻게 해야할지 모르겠다. 15559 내 선물을 받아줘 15886 내 선물을 받아줘2 2536 버스 갈아타기 5214 환승 15559 내 선물을 받아줘 → union find (Disjoint Set) 15886 내 선물을 받아줘2 → 문자열 내 EW의 개수 2536 버스 갈아타기 → BFS 가로/세로로 움직이는 버스를 나누어 갈아탈 수 있는 버스를 찾아내는 방법을 생각해낼 것 bfs 더보기 ver[N] ver[ i ] = x=i에서 세로로 움직이는 버스들 저장 hor[N] hor[ i ] = y=i에서 가로로 움직이는 버스들 저장 vis[N] vis[ i ] = i번째 버스를 타기까지 갈아탄 최소 횟수 int bfs() { // STEP 1. 시작점을 포함하는 버스 for (inf.. 2021. 3. 15. 구현 (1) 18809번 Gaaaaaaaaaarden BFS BF 그래프 구현 시뮬레이션 14865번 곡선 자르기 구현 3954번 Brainf**k 인터프리터 자료구조 구현 스택 3678번 카탄의 개척자 구현 시뮬레이션 17472번 다리 만들기 2 BFS BF 그래프 구현 MST 16637번 괄호 추가하기 BF 17135번 캐슬 디펜스 BFS BF 그래프 구현 시뮬레이션 17406번 배열 돌리기 4 BF 구현 진짜 나는 좌표가 너무 헷갈린다. 공간지각능력이 좋은 사람은 아니라... 시각화가 너무나 중요하다. 과연 이 필기를 다시 꺼내볼 일이 있을 것인지,, 2021. 1. 29. 이전 1 다음
