개발자 아지트

모델링

1. 모델링의 특징

-추상화

-단순화(약속된 표기법으로 단순화 한다)

-명확화 (혼란이나 자기 멋대로 해석하는 것이 없어야 한다)

2. 모델링 시 유의사항(모델링 할 때 피해야 할것 들) ==> 최소화 한다. 

-중복 최소화=> 여기저기 저장하지 말라 => 데이터 불일치 상황 발생

-비유연성 최소화=> 비유연==경직되었다. 유연하게 할라면 정의(담고있는 부분)와 처리를 분리해야함 

-비일관성 최소화 => 데이터간의 관계가 명확하지 않아서 하나를 바꿨는데 다른쪽이 안바껴서 일관성이 깨진다. 

코딩테스트 준비를 하기 위해서 연습 문제를 풀때, 제한 시간을 한번쯤 볼 수 있었을 것이다. 

여기서 말하는 제한 시간은 알고리즘이 실행되고 종료될 때 걸리는 시간의 제한 시간을 말하는 것이다. 

컴퓨터에서 1초당 처리되는 연산 횟수가 대략적으로 정해져있다.

(코딩테스트를 치는 환경(연습으로 문제푸는 환경도 마찬가지)에는 모든 컴퓨터의 성능이 동일하다고 가정한다. )

(1초당 1억개의 연산 가능)

그런데 문제에 대해 알고리즘을 어떻게 짜냐에 따라서 1초당 처리되는 연산 횟수가 줄어들 수도 있고 유지될 수도 있다. 

더 많아질 수는 없다. (컴퓨터가 자가 발전하지 않는 이상(?))

코드를 작성하고 나서 이 알고리즘이 어떻게 짜여졌냐? 어떻게 짜여졌길래 1초당 처리되는 연산 횟수가 이런가?

작성한 알고리즘이 1초당 처리되는 연산 횟수가 이정도면 대략 이정도의 복잡도를 가진 알고리즘일 것이다. 

(단, 입력 크기를 N으로 일반화 해야함. 왜냐하면 입력 크기가 1인 경우 알고리즘을 작성해야 하는 경우로 예를 들자면, 입력크기가 1일때만  연산 횟수가 1인 성능을 가지는 것이기 때문 == 해당 상황에 한정된것, 입력 크기가 다른 값으로 바뀔경우 연산 횟수 성능도 바뀔 것)

이런 맥락에서의 복잡도를 가지고,

==> 우리는 이것을 알고리즘의 시간복잡도라고 하기로 했다. 

입력 크기에 따른 연산 횟수 추이를 활용해 시간 복잡도를 표현하는 방법을 점근적 표기법이라 한다. 

[시간 복잡도(time complexity)]

: 알고리즘의 성능을 나타내는 지표. 입력 크기(알고리즘이 처리해야 할 데이터의 양)에 대한 연산 횟수의 상한을 의미한다. 

시간 복잡도는 낮으면 낮을 수록 좋다. 

시간 복잡도는 최선, 보통, 최악의 경우로 나눌 수 있지만, 코딩테스트에서는 작성한 알고리즘의 최악의 경우를 고려하여 시간 복잡도를 계산해야한다. 왜냐하면, 모든 경우의 수에서 알고리즘이 문제를 처리하는 것을 고려해야 하기 때문이다. 

* 빅오 표기법

: 빅오 표기법은 최악의 경우일 때의 시간 복잡도를 표현하는 방법이다. 

빅오 표기법은 특정 알고리즘의 연산 횟수가 f(x)일 때, 함수의 최고차항만을 남기고 남은 자수를 지워 O(최고차항)와 같이 표현하면 된다. 

* 빅오 표기법을 쉽게 쓸 때 최고차항만 남기고 차수를 지우는 이유

: 시간복잡도 식에서 최고차항 이외의 값들을 2차원 그래프에서 표현해보면 최고차항 이외의 값들은 무시할 수 있을 정도로 작으므로 무시한다. 

컴퓨터는 1초에 최대 1억번 연산할 수 있다. 

코딩 테스트의 문제는 출제자의 의도대로 로직을 구현했을 경우 대부분 코드를 정답처리 할 수 있게끔 채점시간을 정한다. 

이때, 언어별로 다른 성능의 차이는 고려하지 않는다. 

[시간 복잡도 계산해보기]

: 과정

1. 문제 정의

2. 연산 횟수 측정

3. 시간 복잡도 분석

* 고려할 점

출력 자체도 연산이다. 

비교도 연산이다. 

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

LCS란?

:"가장 긴 공통 부분 수열"이다. 알고리즘 LCS에서는 가장 긴 공통 부분 문자열이다. 두 개의 문자열이 있을 때, 그 문자열에서 순서를 유지하면서 공통으로 나타나는 글자들을 이어서 만들 수 있는 가장 긴 문자열을 찾는 것을 의미한다.

*부분 문자열이란?

:부분 문자열에는 연속된 부분 문자열인 Substring과 연속되지 않은 부분 문자열인 Subsequence라는 개념이 있다. 

Subsequence라는 개념을 예시를 들어 설명하자면, "ABCDEF"와 "AEBDF"라는 두 문자열이 있다면, 이 두 문자열에서 공통으로 나타나며 글자들이 두 문자열에서 같은 순서로 나타나는 문자열 중 가장 긴 부분 수열은  "ABDF"이다. 

예시

* 위 배열 활용법 *

조회하는 문자열이 서로 같은 문자열임이 확인되면 현재 자리에서 대각선(왼쪽 위)의 값 +1을 해야한다. 

조회하는 문자열이 서로 다른 문자열임이 확인되면 현재 자리에서 왼쪽, 위의 값 중 큰 값으로 현재의 값을 교체한다. 

맨 첫번째 행의 모든 열을 0으로 하고 다음 모든 행의 첫번째 열에 0은 왜 넣는걸까?

=> 조회하는 문자열이 같을때, 서로 같은 문자열임이 확인되면 현재 자리에서 대각선(왼쪽 위)의 값 +1을 해야하는데, 

앞에 0을 넣지 않으면 첫번째 문자열의 맨첫번째 값과 두번째 문자열의 맨 첫번째 값에 어떤 값을 넣어줘야 할지 모르기 때문이다. 

왜 바로 앞의값(왼쪽)의 값에서 +1을 하지 않을까? 

=> 바로 앞의값에서 +1을 하면 lcs의 값에 +1을 하는 꼴이 된다.

(하지만 두번째 단어의 조회할 자리는 여전히 같은 자리임=> 두번째 단어의 조회할 자리를 +1 하면 할수록 lcs의 값이 중복으로 +1되는 꼴)

왜 조회하는 문자열이 서로 다른 문자열임이 확인되면 현재 자리에서 왼쪽, 위의 값 중 큰 값으로 현재의 값으로 교체할까? 

왜 하필 현재 자리에서 왼쪽, 위의 값을 비교할까? 

 => 현재 자리의 왼쪽은 현재 자리의(같은행, 다른열==현재열-1) lcs값은 고려하지 않고 이전 문자까지의 lcs값만을 가지고 있는 것이고,

현재 자리의 위쪽은 현재 자리의 lcs값을 고려하지만, 새로 조회하는 문자와의 비교는 하지 않은 값이다. (다른행==현재행-1, 같은열)

왼쪽, 위의 값은 각각 자신이 할 수 있는 최적의 lcs를 구한 상태이다.

따라서 둘 중에 큰 값을 골라 현재의 자리의 값을 교체해줌으로써 최적의 값을 유지할 수 있게된다. 

https://www.acmicpc.net/problem/9252

문제 해결 방법

1. dp배열을 만들어서 lcs를 구함

2. lcs를 구한 dp배열을 역추적하여 문자열을 구함 

코드 구현

정답 코드 

s1 = input()
s2 = input()

m=len(s1)
n=len(s2)

dp = [[0] * (n+1) for _ in range(m+1)]

for i in range(1, m+1):
    for j in range(1, n+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i][j-1], dp[i-1][j])

result =''
startm = m
startn = n

print(max(dp[-1]))
if max(dp[-1])!=0:
    while 1:
            if dp[startm][startn]==0:
                break
            # 위에것이 더 큰지
            if dp[startm][startn] == dp[startm-1][startn]:
                startm-=1
            # 왼쪽 것이 더 큰지
            elif dp[startm][startn] == dp[startm][startn-1]:
                startn-=1
            # 둘다 안크면 대각선 이동 
            # 값도 넣어줌 
            elif ((dp[startm][startn]-1) == dp[startm-1][startn-1]):
                
                startm-=1
                startn-=1

                result+=s2[startn]


            
            

    print(result[::-1])

시간/공간 복잡도

0.1초로 시간제한이 있었는데, 해당 시간에 1000만 번의 연산을 해야하는거고, 최대로 입력할 수 있는 문자열의 길이가 1000이기 때문에 

O(n)으로 푸는것이 맞다. 

최적화 및 개선

따로 하지 않음 

어려웠던 점

lcs의 개념, lcs의 역추적의 개념을 잘 몰라서 접근하기 어려웠다. 

역추적 부분은 아직도 어렵게 느껴진다. 비슷한 문제를 여러번 풀어봐야 할 것 같다.