Algorithm (7) 썸네일형 리스트형 BOJ 1485: 정사각형 각 점들에 대한 길이를 모두 s배열에 저장하면 정사각형 네변의 길이, 대각선 2개 총 6개의 길이를 저장합니다. 이를 오름차순으로 정렬하면 대각선 2개에 대한 길이는 자연스럽게 뒤에 위치하게 됩니다. 이제, 앞에 4개 길이가 같은지 판별하고, 뒤에 2개 대각선길이가 서로 같다면 정사각형이라는 의미이므로 True를 리턴해줍니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include #include using namespace std; struct POINT { int x, y; }; POINT point[4]; int s[6]; int abss(int a) { return .. BOJ 6439번: 교차 입력으로 주어진 선분과 직사각형이 교차하는지를 판별하는 문제이다. 직사각형의 좌표들가 대각선으로 2개 들어오는데, x, y좌표를 각각 크기 비교해서 사용해야하는데 당연히 작은게 우선 들어올거라 판단해 여러번 틀린 문제였다. 이 문제는 크게 2가지 기준을 통과하면 T로 판별하게 하였다. 먼저, 직사각형 점들을 저장해주고, CCW로 선분이 직사각형 4개의 변과 교차하는지 판별해주었다. 이후, 직사각형 4개의 각 변들과 선분과의 CCW >0 이면 선분이 직사각형 내부에 있다는 뜻이므로 이 또한 T로 판별하게 해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 .. # BOJ 2162번: 선분 그룹 2차원 평면상에 선분들이 주어질 때, 두 선분이 만나면 같은 그룹이라 한다. 이때 가장 큰 그룹에 속한 선분의 개수를 구하는 문제이다. 그룹핑하기 위해 Union Find를 사용했고, CCW로 선분의 교차 유무를 판별하였다. 코드는 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 #include #include int p.. Labin-Karp 알고리즘 Labin-Karp 알고리즘 이란? 라빈카프 알고리즘이란 이전에 계산한 T[i, i+M-1] 부분 문자열의 해시 값을 이용해서 T[i+1, i+M]의 해시값을 빠르게 구하는 알고리즘이다 구체적인 내용은 이전 KMP 알고리즘을 소개할 때 했으므로 넘어가겠다. 아래는 라빈카프를 활용한 문제풀이이다. 이 문제의 핵심은 두번 이상 등장하는 부분 문자열중 가장 길이가 긴 것을 구해야 하므로 부분 문자열의 길이가 모두 상이 하므로 이분탐색으로 임의의 K를 찾아나가며 가장 긴 길이를 구하는 방식으로 해야한다. 탐색을 하면서 가능한 모든 위치에서 길이 mid인 부분 문자열의 해시값을 구해, 해시값이 충돌했다면 같은 문자열이 앞에 등장했는지 모두 비교를 하고, 아니라면 현재 문자열의 첫 인덱스를 해시에 저장하고 계속 진.. TRIE 자료구조를 사용한 문자열 검색 Trie 자료구조란? 다음과 같이 여러 문자열 사전을 저장하는 트리 형태의 자료구조 이다. Trie에 텍스트 T의 모든 접미사를 저장한다고 하면 O(M)만에 패턴 P를 찾을 수 있다. 다음은 Trie 구조에 전화 번호 목록을 저장해 탐색해가며 일관성 여부를 출력하는 문제와 코드이다. # BOJ 5052:전화번호 목록 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 #include #.. KMP 알고리즘 주로 문자열 관련 패턴을 찾는 알고리즘으로 대표적인 2가지가 있다. 바로 Hashing에 기반한 Rabin-Karp 알고리즘과 KMP알고리즘이다. Rabin-Karp알고리즘은 해시를 사용해 두 문자열의 해시 값을 구해 이둘을 비교하는 방식으로 오차를 감안하고 찾는다. 해시 값이 다르면 두 문자열은 100% 다르다는 것이지만, 해시값이 같다면 두 문자열은 같을 수 도 있다는 점에서 정확도가 100%가 아니다. 대신, 이전 계산한 부분 문자열의 해시값을 이용해 현재 해시값을 빠르게 구할 수 있기 때문에 탐색 속도가 빠르다. 대표적인 공식은 다음과 같다. 길이가 M인 패턴 P=p1*p2*p3*....pm에 대해 f(p1)=p(m)+p(m-1)*a+p(m-2)*a^2+....p(1)*a^m-1 f(p2)=p(m.. Suffix Array & LCP 알고리즘 Suffix Array에 접미사들을 저장하고, Counting Sort로 정렬해주었다. # Counting Sort는 O(N)시간 복잡도를 가지며, 주로 문자열을 다룰 때 (26개의 알파벳) 주로 사용된다. Quick Sort가 O(NlogN) 복잡도를 가지는 것에 비해서는 매우 짧지만, 같은 패턴이 나오는 문자의 길이가 길어질 수록 Counting Sort도 비효율적이다. Suffix Array를 구성하고 이를 활용해 LCP를 구성한다. # LCP (Longest Common Prefix) : 접미사 배열에서 i번째 접미사와 i-1번째 접미사 사잉서 일치하는 접두사의 길이 LCP 알고리즘을 사용하는 이유는 이전에 비교했던 결과를 최대한 이용해서 i번째 접미사를 비교할 때, i-1번째 접미사에서 비교한 .. 이전 1 다음
