SY DevLog

어떤 문자열(T)에서 특정 문자열(P)를 찾을 때 사용하는 알고리즘 예를 들어, 문자열(T) : "CDABABKABADABABC" 문자열(P) : "ABABC" 문자열 T에서 문자열 P를 찾는 방법을 단순하게 완전탐색으로 구현해보면 이중 for문을 통해 다음과 같이 구현해 볼 수 있다. String T="CDABABKABADABABC" String P="ABABC" for(int i=0;i pattern과 pattern의 비교 text와 pattern을 비교한 것과 마찬가지로 pattern과 pattern의 비교도 비슷한 방식으로 이루어진다. 따라서 pattern과 pattern을 비교하는 알고리즘을 이해하고 나면, text와 pattern을 비교하는 알고리즘도 이해하기가 쉬울 것이다. 우선 건너뛰기 표..

Disjoint Set(분리집합)이라고도 한다. 서로 중복되지 않는(교집합이 없는) 둘 이상의 집합의 정보를 저장, 조작하는 자료구조이다. 유니온 파인드는 3가지 연산이 존재한다. make - set(x) : 초기화를 하는 연산이다. x를 원소로 하는 새로운 집합을 생성한다. 이때 생성되는 집합은 x만을 원소로 갖는다. union(x, y) : x가 포함된 집합과 y가 포함된 집합을 하나의 집합으로 합친다. find(x) : x가 어느 집합에 속해 있는지를 찾는다. 유니온 파인드를 구현하는 방법은 다양한데, 그 중에서도 가장 잘 알려진 트리를 이용한 방법을 설명할 것이다. 트리를 이용한 Union-Find 트리를 이용하여 유니온 파인드를 구현할 경우, 하나의 트리는 집합 1개를 의미하며 트리의 루트 노드..

2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net room 이차원 배열을 만들어서 방번호를 넣어준다. room 이차원 배열이 여기서 방문처리 역할을 한다. room[m][n] != 0 이미 방번호가 배정된 것이므로(방번호는 1번부터 시작하는 걸로 설정) 방문한 것이나 마찬가지가 된다. area 일차원 배열에는 해당 방들의 넓이를 넣어준다. ex) area[1] : 1번 방의 넓이, area[2] : 2번 방의 넓이 문제에서 성곽의 최대 넓이는 n=50, m=50 일 때 2500이고, 모든 공간마다 벽으로 ..

이번 글은 이분 탐색을 사용하는 알고리즘 문제를 좀 더 쉽게 풀기 위해 작성한 것이다. 대부분의 이분 탐색을 사용하는 문제는 특정 값을 찾는 문제보다도 주어진 조건을 만족하는 수 중에서 최대값을 찾거나, 최소값을 찾는 문제가 자주 등장한다. 무엇을 구하는 문제이냐에 따라서 이분 탐색에서 최종 반환하는 인덱스가 약간씩 달라진다. 특정값을 찾는 문제 최대값을 찾는 문제 최소값을 찾는 문제 아래 글은 기본적인 이분 탐색에 대한 개념을 정리한 것이다. 이분 탐색(Binary Search) - 특정값 찾기 이분 탐색(Binary Search) 정렬된 배열에서 특정 값을 검색할 때 사용하는 알고리즘 탐색을 진행하기 전에 반드시 배열이 정렬된 상태이어야 한다. 이분탐색 알고리즘 문제를 풀 때, 주어진 배열에 lotu..

이분 탐색(Binary Search) 정렬된 배열에서 특정 값을 검색할 때 사용하는 알고리즘 탐색을 진행하기 전에 반드시 배열이 정렬된 상태이어야 한다. 시간복잡도 : O(logN) 한번 탐색을 진행할 때마다 탐색의 범위가 반으로 줄어들기 때문에 선형 탐색에 비해 속도가 빠르다. 알고리즘 : 1. 이분 탐색 범위의 시작 위치를 가리키는 포인터를 pl, 마지막 위치를 가리키는 포인터를 pr로 설정한다. 그리고 탐색 범위의 가운데를 가리키는 포인터를 pc로 설정한다. arr[pc] = key 이면, 탐색하려는 값을 찾았으므로 이분탐색을 종료한다. arr[pc] pl = pc + 1 arr[pc] > key 이면, pr을 pc보다 하나 왼쪽으로..

2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 이분탐색으로 문제를 해결할 수 있다. 이분탐색을 진행하면서 중간값(mid)이 블루레이 최소 크기의 후보가 된다. 각 레슨의 길이가 저장된 배열을 차례대로 탐색하여 한 블루레이당 레슨 길이의 합이 mid보다 작도록 레슨을 그룹으로 분리한다. 예를 들어, mid = 15 이고, 레슨의 길이가 차례대로 1 2 3 4 5 6 7 8 9 이면, 한 블루레이당 레슨 길이의 합이 mid보다 작도록 나누면 (1,2,3,4), (5,6), (7), (8), (9) 로 나눌 수 있다. ..

6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 이분탐색으로 문제를 풀었다. 이분탐색의 먼저 범위(left ~ right)를 정해야 한다. left : 현우가 N번 동안 필요한 금액 중 최대값이 이분탐색 범위의 시작값이 되어야 한다. 예를 들어 현우가 n번째에 500원이 필요한데, 한 번에 인출할 수 있는 금액이 500원보다 작은 400원 이라면 현우는 n번째에 돈을 쓸 수가 없다. right : 현우가 N번 동안 필요한 금액의 총 합이 이분탐색 범위의 끝값이 된다. 이분탐색을 진행하면서 현우가 통장에서 인출해야할..

저번 글에서는 최장 증가 수열의 길이를 구하는 경우에 대해 다루었다. LIS(Lowest Increasing Subsequence) - 길이 구하기 LIS(Lowest Increasing Subsequence) : 최장 증가 수열 : 어떤 수열이 주어졌을 때, 그 수열에서 가장 긴 증가하는 부분 수열을 구하는 알고리즘 (최장 증가 수열의 요소가 꼭 연속하지 않아도 됨) 1. 최장 lotuslee.tistory.com 이분탐색을 이용하여서 새로 입력받은 수가 리스트에 들어갈 위치를 구하였다. 그러나 이 알고리즘은 최장 증가 수열의 길이를 구할 수는 있지만 수열 자체를 구할 수는 없었다. (위의 포스팅 참고) 예를 들어, 다음과 같은 반례가 있다. 수열 10 30 50 20 60 이 있다고 할 때 위의 알고..

5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 트라이(Trie)를 이용하여 문제를 해결하였다. 트라이(Trie) 자료구조에 대한 기본적인 이해가 선행되어야 한다. 트라이(Trie) - 1. 트라이 개념 및 노드 특징 트라이(Trie) 문자열들의 집합을 N진 트리 형태로 표현한 자료구조로, 문자열 검색에 주로 사용된다. 하나의 노드는 하나의 문자를 나타낸다. 단, 루트노드는 아무런 문자도 의미하지 않는다. 트 lotuslee.tistory.com 전화번호에 일관성이 없는 경우는 트라이에..

2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 다이나믹 프로그래밍과 위상정렬을 이용하여 푸는 문제 먼저, 위상정렬을 이용하여 작업간의 순서를 빠른 순서대로 큐에 저장해둔다. Queue order = new LinkedList(); 그리고 dp 일차원 배열에는 작업의 최소 완료시간을 저장한다. dp[n] : 작업 n을 완료하기 위해 필요한 최소 시간 큐에서 가장 먼저 실행되는 작업(n)부터 하나씩 꺼낸다. dp[n] = dp[n] + time[n] 으로, dp[n]에 해당 작업의 소요시간(time[n..