[PS] 백준 15483번: 최소편집

|

문제

내가 이해한 문제 내용

삽입,삭제,치환의 3가지 연산이 주어졌을 때 문자열 $A$를 문자열 $B$로 바꾸는데 필요한 최소 편집 횟수를 구하시오.

접근 방식

  • 처음엔 단순하게 문자열 비교로 보면서 1차원적으로 접근했으나 풀 수 없었고 질문란을 보니 LCS랑 연관있는 것임을 알았다.

  • 그래서 LCS를 다시 공부했고 점화식을 파악했지만 단순 LCS로는 해결이 불가능했다.

  • 풀이를 보니 LCS랑 풀이방식이 비슷했다.

    • 예를 들어 abccde로 만드는 최소편집 횟수를 구한다면 2차원 배열을 만든 뒤 특정 문자열의 접두사에서 다른 문자열의 접두사를 만드는데 필요한 모든 최소편집 횟수를 구하면 된다.

    • dp[i][j] = "abc"의 길이 i 접두사를 "cde"의 길이 j 접두사로 만드는데 필요한 최소편집횟수
      // 접두사의 마지막 문자가 같을 때
      dp[i][j] = dp[i-1][j-1]
      // 접두사의 마지막 문자가 다를 때
      dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1])) + 1
      
    • 마지막 문자가 같다는 것은 현재 문자를 제외한 경우를 그대로 추가해주면 되는 것이므로 dp[i-1][j-1]값을 사용하면 된다.

    • 마지막 문자가 다르다는 것은 이전 값을 그대로 쓸 수 없으므로 경우를 또 나눠주어야 한다.

      • 왼쪽에서 삽입연산을 하는 경우
      • 대각선에서 교체연산을 하는 경우
      • 위쪽에서 삽입연산을 하는 경우
      • 위의 3가지 경우가 존재하기 때문에 1을 더해주는 것이다.

어려웠던 점 & 배운 점

  • LCS를 다시 생각하니 생각이 안났던 점이 어려웠다.
  • LCS를 그대로 사용하지 않고 다른 방식으로 사용하는 점이 어려웠는데 이래서 코드가 아니라 개념과 아이디어가 중요하다는 것을 다시 한 번 깨달았다.

시간복잡도

  • $O(N^2)$

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String s1 = br.readLine(),s2 = br.readLine();
        int len1 = s1.length(), len2 = s2.length();

        int dp[][] = new int[1001][1001];

        for(int i=0; i<=len1; i++) dp[0][i] = i;
        for(int i=0; i<=len2; i++) dp[i][0] = i;

        for(int i=1; i<=len2; i++){
            for(int j=1; j<=len1; j++){
                if(s1.charAt(j-1)==s2.charAt(i-1)) {
                    dp[i][j] = dp[i-1][j-1];
                }
                else {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
                }
            }
        }

        bw.write(String.valueOf(dp[len2][len1]));
        bw.flush();

        br.close();
        bw.close();
    }
}

[C++] equal_range, distance

|

std::equal_range

Definition

template< class ForwardIt, class T >
std::pair<ForwardIt,ForwardIt> 
	equal_range( ForwardIt first, ForwardIt last,const T& value );

2개의 반복자를 기준으로 주어진 범위 내에서 value를 만족하는 범위를 나타내는 2개의 반복자를 리턴한다. 컨테이너는 정렬된 상태여야 한다. 리턴되는 1번째 반복자는 value 이상이며 2번째 반복자는 value 초과이다. 다시 말해서 1번째 반복자는 std::lower_bound로 얻을 수 있고 2번째 반복자는 std::upper_bound로 얻을 수 있다. 시간복잡도는 여전히 $O(lgN)$이다.

int main(void)
{
    vector<int> v = {1, 1, 2, 3, 3, 4, 5};
    pair<vector<int>::iterator, vector<int>::iterator> p = equal_range(v.begin(),v.end(),3);
    cout << *p.first << ' '<< *p.second << '\n';
    return 0;
}

결과는 3과 4가 나옴을 알 수 있다.

std::distance

Definition

template< class InputIt >
typename std::iterator_traits<InputIt>::difference_type 
    distance( InputIt first, InputIt last );

1번째 반복자와 2번째 반복자를 포함해서 그 사이에 있는 원소들의 개수를 구한다.

int main(void)
{
    vector<int> v = {1, 1, 2, 3, 3, 4, 5};
    cout << distance(v.begin(),v.end()) << '\n';
    return 0;
}

7이 나온다.

[JAVA]String vs StringBuffer vs StringBuilder

|

String

일반적인 문자열 클래스이며 접합(concatenation)연산이 가능하다. 그러나 접합연산에 있어서 기존의 객체를 버리고 다시 새로운 객체를 생성한 뒤에 복사해서 접합하기 때문에 상당히 비효율적이다. 따라서, 많은 양의 문자열을 접합할 경우에는 쓰지 않는 것이 좋다. 하지만 불변(immutable)한다는 특징을 갖고 있어 단순히 읽는 연산에서는 다른 클래스보다 성능이 좋기 때문에 읽기연산에서는 String 을 사용하는 것이 좋다.

StringBuffer vs StringBuilder

StringBuffer와 StringBuilder는 모두 가변적(mutable)이고 String 과 다르게 접합연산에서 다시 객체를 생성하지 않는다. 따라서 많은 양의 문자열을 접합할 경우에 훨씬 효율적이다. StringBuffer의 경우 thread-safe하며 StringBuilder는 thread-safe하지 않다. 따라서, 멀티쓰레드 환경이라면 StringBuffer를 사용하고 싱글쓰레드 환경이라면 StringBuilder를 사용하는 것이 좋다.

결론

  • 문자열이 변하지 않을 경우 String을 사용하자.
  • 문자열이 변하는데 싱글 쓰레드일 경우 StringBuilder를 사용하자.
  • 문자열이 변하는데 멀티 쓰레드일 경우 StringBuffer를 사용하자.

Refrences

  • https://stackoverflow.com/a/2971343/9437175
  • https://jeong-pro.tistory.com/85

[C++] binary_search, lower_bound, upper_bound

|

Definition

template< class ForwardIt, class T, class Compare >
constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );

이분탐색을 실행하여 $O(lgN)​$만에 해당하는 값이 컨테이너에 있는지 여부를 알려주는 함수이다. 기본적으로 오름차순 기준으로 설정되어 있으며 내림차순 기준으로 변경할 수 있다.

  • 오름차순
int main(void)
{
    vector<int> v = {1, 2, 3, 5, 7};

    cout << (binary_search(v.begin(),v.end(),3) ? "Found" : "Not Found") << endl;
    cout << (binary_search(v.begin(),v.end(),4) ? "Found" : "Not Found") << endl;

    return 0;
}
  • 내림차순
int main(void)
{
    vector<int> v = {7, 5, 3, 2, 1};

    cout << (binary_search(v.begin(),v.end(),3,greater<int>()) ? "Found" : "Not Found") << endl;
    cout << (binary_search(v.begin(),v.end(),4,greater<int>()) ? "Found" : "Not Found") << endl;

    return 0;
}

std::lower_bound

Definition

template< class ForwardIt, class T, class Compare >
constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

이분탐색을 실행하여 $O(lgN)$ 만에 해당하는 값 이상의 값의 위치를 가리키는 반복자(Iterator)를 리턴하는 함수이다. 아래와 같이 사용할 수 있으며 벡터의 반복자를 이용하여 인덱스를 구하는 것은 현재 반복자에서 시작위치의 반복자를 빼는 것과 같다는 것을 알아두자.

int main(void)
{
    vector<int> v = {1, 2, 3, 5, 7};

    vector<int>::iterator it = lower_bound(v.begin(),v.end(),4);
    auto it2 = lower_bound(v.begin(),v.end(),5);

    cout << "index of number which is greater than equal to 4: " << it - v.begin() << endl;
    cout << "index of number which is greater than equal to 5: " << it2 - v.begin() << endl;

    return 0;
}

std::binary_search와 같이 내림차순으로도 쓸 수 있다.

std::upper_bound

Definition

template< class ForwardIt, class T, class Compare >
constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

std::lower_bound와 동일하지만 해당 값 이상에서 해당 값 초과로 바뀐 것, 즉 찾고자 하는 값이 3이라면 3보다 큰 값이 있는 위치의 반복자를 리턴하는 함수이다.

int main(void)
{
    vector<int> v = {1, 2, 3, 5, 7};

    vector<int>::iterator it = upper_bound(v.begin(),v.end(),4);
    auto it2 = upper_bound(v.begin(),v.end(),5);

    cout << "index of number which is greater than 4: " << it - v.begin() << endl;
    cout << "index of number which is greater than 5: " << it2 - v.begin() << endl;


    return 0;
}

실행해보면 std::lower_bound와는 다른 인덱스 값이 나오는 것을 볼 수 있다.

References

  • https://en.cppreference.com/w/
  • https://www.youtube.com/watch?v=rXuqUtifDU8

[PS] 백준 8984번: 막대기

|

문제

내가 이해한 문제 내용

여러개의 막대기가 임의의 배치로 주어질 때 지그재그 모양의 막대기 중 가장 긴 길이를 구하시오.

접근 방식

  • DP라는 것을 캐치하고 수십개의 막대기를 그려본 결과 다음과 같은 점화식을 얻었다.
    • dp[0][i]=i번째 막대기가 위쪽에서 시작할 경우의 최대길이
    • dp[1][i]=i번째 막대기가 아래쪽에서 시작할 경우의 최대길이
    • 위와 같이 정의하고 막대기가 주어지면 위쪽 수직선 기준으로 정렬한 후에 dp를 돌렸지만 시간초과.
    • 고민하다가 더 이상은 시간낭비인 것 같아 답을 봤다.
  • 풀이의 접근방식
    • 제일 중요한 관찰은 특정 점에 중복되는 막대기를 제거하는 것인데 그 이유는 해당 점에 아무리 막대기가 많다 하더라도 최대 길이만 찾으면 되기 때문이다.
    • 이제 위쪽과 아래쪽을 각각 정렬하여 따로 dp 식을 구성한다.
    • 주어진 입력을 돌면서 위쪽 좌표와 아래쪽 좌표에 대해 정렬한 배열에서 해당하는 인덱스를 찾는다.
    • 반복하면서 dp 식을 업데이트 해주면 된다.
    • t_dp[i]=위쪽 수직선에서 i번째 좌표로 시작하는 막대기 길이의 최댓값
    • d_dp[i]=아래쪽 수직선에서 i번째 좌표로 시작하는 막대기 길이의 최댓값

어려웠던 점 & 배운 점

  • 시간초과가 발생하고 나서 이분탐색을 쓰려고 했으나 특정 좌표에 해당하는 막대기 길이의 최댓값을 찾아야 했기 때문에 불가능해서 어려웠다.
  • 위쪽 수직선과 아래쪽 수직선을 나눠서 접근하는 방식이 난해했고 나눈 상태에서 점화식을 세울 수 없었다.
  • 풀이에선 벡터의 함수를 사용해서 중복을 제거하지만 이분탐색으로 해결할 수 있다.

시간복잡도

  • $O(NlgN)$

코드

코드는 거의 비슷하지만 그래도 다시 혼자 힘으로 구현했기에 첨부한다.

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int MAX_SIZE = 100005;

pii stick[MAX_SIZE];
int top[MAX_SIZE],down[MAX_SIZE];
ll tdp[MAX_SIZE],ddp[MAX_SIZE];
vector<int> rtop,rdown;
int N,L;

bool findValue(int left, int right, int target, vector<int>& vec) {
    while(left<=right) {
        int m = (left+right)/2;
        if(target<vec[m]) right = m-1;
        else if(target>vec[m]) left = m+1;
        else return true;
    }
    return false;
}

int main(void)
{
    scanf("%d%d",&N,&L);

    for(int i=1; i<=N; i++) {
        scanf("%d%d",&stick[i].first,&stick[i].second);
        top[i] = stick[i].first;
        down[i] = stick[i].second;
    }

    sort(stick+1,stick+N+1);
    sort(top+1,top+N+1);
    sort(down+1,down+N+1);

    rtop.push_back(top[1]);
    rdown.push_back(down[1]);
    for(int i=2; i<=N; i++) {
        if(!findValue(0,rtop.size()-1,top[i],rtop)) {
            rtop.push_back(top[i]);
        } 
        if(!findValue(0,rdown.size()-1,down[i],rdown)) {
            rdown.push_back(down[i]);
        }
    }

    ll ans = 0LL;
    for(int i=1; i<=N; i++) {
        int tidx = lower_bound(rtop.begin(),rtop.end(),stick[i].first) - rtop.begin();
        int didx = lower_bound(rdown.begin(),rdown.end(),stick[i].second) - rdown.begin();

        ll len = abs(rtop[tidx]-rdown[didx]) + L;
        ll ttemp = tdp[tidx];
        ll dtemp = ddp[didx];
        tdp[tidx] = max(ttemp, dtemp+len);
        ddp[didx] = max(dtemp, ttemp+len);
        ans = max(ans,max(tdp[tidx],ddp[didx]));
    }

    printf("%lld",ans);

    return 0;
}