그냥 하는 노트와 메모장

아호 코라식(Aho-chorasick) 여러 문자열 패턴이 있고, 특정 문자열에 어떤 패턴이 어디에 존재하는지 확인하고 싶을 때 쓰는 알고리즘입니다. 기술적으로는 prefix와 suffix를 가지고 노는 문자열 탐색 알고리즘이라고 말하고 싶네요. KMP도 마찬가지지만 이 알고리즘 역시 매칭 실패했을 때 지금까지 사용한 데이터를 그대로 활용해서 효율적으로 탐색하고 싶어합니다. 아시다시피 그 동작을 실패 함수(Failure function)라고 합니다. [사전 지식] * 트라이(trie) - prefix 문자열을 저장하는 자료구조. 만약 검색 대상 문자열이 패턴과 정확히 일치해야만 한다면 적절한 자료구조입니다. * BFS - 아호코라식 자료구조를 동적으로 건설해나가는데, 여기서 실패함수 구조에 의해 BFS를..

BOJ 2638 - 치즈 [분류 - BFS] [풀이1] 빈 공간이 보장되는 (0, 0)부터 계속 BFS를 돌면서 4방향에 대해 2방향 이상에 공기에 노출되는 경우에 대해서 삭제한다. 그러다가 모두 지워지는 시점을 출력한다. [풀이2] 빈 공간 (0, 0)부터 시작해서 공기가 될 부분, 즉 치즈가 사라질 부분을 또다른 큐에 넣도록 한다. 그러면 그 위치부터 공기가 시작되는 부분이기 때문에 [풀이1]에서 사용한 (0, 0)에서 다시 돌릴 필요가 없어지는 것이다. 두 개의 큐를 사용하여 공기인 부분은 진행하고 치즈인데 2방향 이상이 공기에 맞닿은 부분이 있다면 다른 큐에 넣어두는 것이다. 이 방식은 따로 명명할 방법이 없어 나는 토글 큐(toggle queue)라고 부르긴 한다. #include #includ..

BOJ 1053 - 팰린드롬 공장 [분류 - 다이나믹 프로그래밍] [풀이] 4번 연산이 엄청 까다로워 보인다. 하지만 딱 한 번만 사용할 수 있으니 이에 대해 전처리를 진행해보자 1. 4번 연산을 사용하지 않는다. 2. 4번 연산을 사용한다(swap(s[i], s[j]), i != j). 나머지 연산에 대해서 생각해보자. 최소 연산수를 만족하기 위해서 삽입을 하거나, 삭제를 하거나, 특정 문자로 교환하는 행위는 반드시 팰린드롬을 만들기 위해 이득이 되어야한다. 다시 말하면 연산을 진행했을 때, 결과 팰린드롬의 일부가 반드시 되어야한다. 양끝부터 시작해서 팰린드롬 연산을 진행한다. 이 과정은 위의 4번 연산을 쓸 때와 안 쓸 때에 모두 계산이 필요하다. dp[l][r] = 구간 [l, r]에 대해 팰린드롬..

BOJ 2618 - 경찰차 [분류 - 다이나믹 프로그래밍] [풀이] 경찰차 1이 있는 (1, 1)을 1번 사건, 경찰차 2가 있는 (N, N)을 2번 사건, 그리고 나머지 N개의 사건을 3, 4, ..., N+2번 사건이라고 하자. 각 경찰차가 마지막 사건을 처리한 위치가 각각 a, b라고 하면 그 다음 사건을 처리할 때 그 사건의 번호는 max(a, b) + 1이 된다(순차적으로 진행해야 하므로). dp[a][b] = 경찰차 1이 a를 해결했고, 경찰차 2가 b를 해결했을 때 남은 모든 사건을 해결하기 위한 이동 최소 이제 문제는 꽤 간단해진다. 당연하게도 그 다음 사건 w(w = max(a, b) + 1)번 사건을 해결하기 위해서는 경찰차 1에 할당할 것인지 경찰차 2에 할당할 것인지 두 가지밖에 없..

BOJ 1600 - 말이 되고픈 원숭이 [분류 - BFS] [풀이] 말처럼 뛰는 동작은 k를 정확히 1만큼을 올리기 때문에 k+1과 k는 인접해있다. 따라서 k+1번째에 특정 좌표 (y, x)에 도달했다면 그 값이 곧 최소 동작이 된다. vi[k][y][x] - y행 x열에 k번만 말처럼 뛰어서 도달할 수 있는 동작 수의 최소값 BFS 특성상 진행하려는 방향에 대해 정확히 1만큼 증가시키고 vi[k+1][y][x]에 도달할 수 있는 위치가 (y1, x1), (y2, x2)일 때, 1. vi[k][y1][x1] > vi[k][y2][x2] BFS 큐에 들어가는 좌표는 (y2, x2)가 더 우선순위를 가진다. 2. vi[k][y1][x1] = 0) for (j = 0; j < n[i]; j++) { int ..

BOJ 8902 색상의 길이 [분류 : 그리디, 다이나믹 프로그래밍] [풀이] 하나의 색에 대해서만 생각해보자. 합쳐질 차선에 배치할 때 그 색상 중 가장 왼쪽에 올 수 있는 1차선의 후보와 2차선의 후보를 가려내보자. 순서상 같은 차선에서 같은 색상을 가지는 인덱스 i 3 a=5, F[0][a] -> 6 dp[a][b]=현재 1차선에서 a번째 후보와 2차선에서 b번째 후보를 사용할 수 있을 때 만족하는 최소 거리 (거리를 계산해야하는 색의 수) 나는 후보를 하나씩 사용하면서 거리를 계산했다. 현재 후보군 위치가 (a, b)이므로 이 이전에 사용한 데이터를 가지고 현재 어떤 색상을 쓰고 있는지(이하 usedCnt) 또 그 색상을 모두 배치 했는지(이하 doneCnt)을 알 수 있다. 각 색마다 가장 왼쪽..

BOJ 1226 국회 [분류 - 다이나믹 프로그래밍, 그리디] [풀이] 당을 하나씩 추가하면서 전체의 절반을 초과하는 경우를 봐야한다. $$a_i=의석수$$ $$total=\sum_{i=1}^{n} a_i$$ $$ half=\lfloor{total/2}\rfloor $$ [접근] 0부터 half까지 순회하면서 현재 좌석수를 더해줌으로 절반을 초과하는지 확인하면된다. [그리디] 단, 좌석수 기준 비오름차순으로 정렬한 데이터를 가지고 추가해야한다. 조건에서 보면 현재 좌석 수를 x로 구성했을 때 x를 만들기 위해 연합된 당들 각각 하나를 빼면 좌석수가 절반 이하이어야만 한다. 현재 당의 좌석수가 ci라고 할때 현재 당을 제외한 나머지 당으로 half를 구성했다고 치자. 그러면 half + ci도 정답 후보가..