[TIL][Krafton Jungle] 3주차 - (5) : 신입사원 문제 + 플로이드 워셜 + LCS

BaekJun - #1946 : 신입사원 (그리디 탐색법)

 

출처 : https://www.acmicpc.net/problem/1946

1946번: 신입 사원

 

오늘은 신입 사원을 풀었다.

 

문제 이해가 조금 어려운데 풀어서 얘기해보면 실기, 필기 두개의 시험을 등수로 매기는데,

특정 A 라는 사람이 어느 누군가보다 실기도, 필기도 등수가 낮다면 그사람은 탈락된다.

 

문제를 이해하는데 시간이 좀 걸리긴 하지만, 문제가 이해됬다고 하면 이제 어떻게 풀어야할지 고민을 해보자.

일단 다행히 시험이 두개이므로, 한개의 시험으로 정렬한 뒤 나머지 시험으로 비교를 하면 된다.

 

나는 리스트를 선언해서 인덱스 숫자를 첫번째 시험의 등수로 매칭하고,

나머지 시험의 등수를 그 인덱스에 해당하는 리스트 저장소의 값에 저장했다.

 

그렇게 하면 리스트를 오름차순으로 읽어나가면서 만약에 등수가 이전 읽었던 사람들 중 최고 등수보다 좋지 못하면,

그 사람은 첫번째 시험도 인덱스가 높은 것이므로 탈락이다.

 

그런 방식으로 코드를 짜보았다.

 

import sys

testCase = int(sys.stdin.readline())
result = [0 for _ in range(testCase)]

for j in range(testCase):
    member_num = int(sys.stdin.readline())
    members = [0 for _ in range(member_num+1)]

    for i in range(member_num):
        a_test , b_test = map(int,sys.stdin.readline().strip().split())
        members[a_test] = b_test

    max_score = member_num+1
    for i in range(1,member_num+1):
        if members[i] < max_score:
            max_score = members[i]
            result[j] += 1

for i in range(testCase):
    print(result[i])

 

등수는 낮을 수록 높은 점수이기 때문에 members[i] 가 현재 최고 점수(등수)보다 낮은지를 판단하고 낮다면 더 좋은 점수이므로 합격자 수를 +1 해주었다.

 

 

플로이드 워셜 알고리즘

내일 쪽지시험에서 플로이드 워셜과 관련된 알고리즘 문제가 출제된다고 해서 이전에 플로이드 워셜 정리한 포스팅을 다시 가져왔다.

 

이번엔 코드도 같이 삽입해서 이해해 보겠다.

 

플로이드 워셜은 그래프의 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘이다.

 

 

방법은 다음과 같다.

 

1. N개의 정점이 있다면 먼저 바로 옆에 붙어있지 않아서 갈 수 없는 정점을 제외하고 가중치를 인접 그래프 표현법에 기재한다.

 

2. N번의 라운드를 진행하는데, k 라운드 시 k번의 노드를 중간 다리로 선정하여, 만약 중간다리를 거치고 간다면 갈 수 있는 곳 까지 가중치를 합산하여 기록한다.

 

3. N번의 라운드가 모두 끝나면 가중치가 가장 적은 비용으로 저장되어있다.

 

#수도 코드
D = [입력 그래프의 인접 행렬]
for k in range(N):
	for i in range(N):
    		for j in range(N):
        		if D[i][j] > D[i][k]+D[k][j]:
            			D[i][j] = D[i][k]+D[k][j]

확실히 코드가 간결한 것을 확인 할 수 있다.

 

코드로 이해해 보면, 모든 k를 검사하며, 만약 현재 k가 경유지가 되어 더 빠른 길이 생성된다면 그 길을 k 경유지를 포함한 최단 거리로 갱신하는 코드이다.

 

이 알고리즘을 이용하여 가중치가 있는 최단거리 찾기 문제를 쉽게 해결 할 수 있을 것으로 생각 된다.

 

 

워셜 알고리즘은 O(N^3)의 시간복잡도로 매우 성능이 좋지 않아 그래프의 크기가 작을때만 사용한다고 한다.

 

플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장해서 점화식을 이용해서 최단 거리 정보를 추출해 내기 때문에 다이나믹 프로그래밍 유형에 속한다고 한다.

 

https://www.youtube.com/watch?v=hw-SvAR3Zqg

N^3의 시간복잡도는 매우 낮은 성능을 가진다는 것을 의미한다.

이런데도 이 알고리즘을 공부하는 이유는

이방법이 매우 간편하기 때문이다.

따라서 N의 최대값이 100보다 작다면 이 방식으로 결과를 쉽게 도출해 낼 수 있다.

 

 

BaekJun - #9251 : LCS (DP - 최장 공통 부분 시퀀스(LCS) 알고리즘)

출처 : https://www.acmicpc.net/problem/9251

9251번: LCS

 

최장 공통 부분 시퀀스(LCS) 문제는 DP의 대표적인 문제 유형 중 하나이다.

말 그대로 두 문자열을 비교하여 얼마나 유사한지를 판단하기 위해 문자열의 공통된 부분만을 뽑아 나열한 문자열이다.

예를들면 'ABCD' 와 'ABDC' 의 LCS는 'ABC' 혹은 'ABD'이다.

(이 문제는 DNA가 얼마나 유사한지 판단할 때 사용한다고 한다.)

 

이 LCS는 책 'Introduction to Algorithm'에 문제 솔루션이 자세히 나와있는데,

진짜 이것만 이해하면 LCS는 걍 마스터임.

근데 책이 조금 이해하기 조금 어려워서 모든 사람이 이해할 수 있도록 최대한 내 말로 풀어서 설명하겠다.

 

먼저 이 문제는 DP이기 때문에, 이 LCS의 특성을 파악하고 최적 부분 구조를 생성해야 한다.

최적 부분 구조를 생성하는 이유는 문제의 규칙들의 특성을 파악해서 두번째 단계인 재귀해를 생성하기 위해서임.

 

X = <x1,x2,x3, ... , xm> 의 문자열과

Y = <y1,y2,y3, ... , yn> 의 문자열이 있고,

이때 Z = <z1,z2,z3,...,zk> 라는 X와 Y의 LCS 가 있다고 가정하자.

 

각 x1 x2 이런건 X의 첫번째 문자, 두번째 문자 를 의미한다.

 

 

그러면 최적 부분 구조는 3가지로 정리된다.

 

1. X의 마지막 문자와 Y의 마지막 문자가 같다면, Z의 문자도 같으며, 각 X,Y,Z의 마지막 문자를 제거한 Xn-1, Ym-1의 LCS는 Zk-1이다.

 

2. X와 Y의 마지막 문자가 다르고, Z와 X의 마지막 문자가 다르다면, X의 마지막 문자를 제거한 Xn-1과 Y의 LCS는 Zk이다.

 

3. X와 Y의 마지막 문자가 다르고, Z와 Y의 마지막 문자가 다르다면, Y의 마지막 문자를 제거한 Ym-1과 X의 LCS는 Zk이다.

 

간단히 예시를 들어 1,2,3의 경우를 이해해보자면,

 

X = ABCD

Y = ABD

라고 하면 Z = ABD가 된다.

 

1번은 뭔소리냐면 X의 마지막문자 'D'가 Y의 마지막문자 'D'와 같으니까 Z의 마지막문자도 'D'이고 

이 'D'를 세 문자열에서 제거해도 LCS 관계가 성립한다는 말이다. (X = ABC , Y=AB , Z=AB)

 

2번은 위의 XYZ에 해당되지 않으므로 새로 예시를 들어보면,

X=ABCD

Y=ABC

Z=ABC

라면, X와 Y의 마지막 문자가 다르고, X와 Z의 마지막 문자가 다르기때문에, X의 마지막 문자를 제거해도 LCS가 성립한다는 말이다. (X=ABC,Y=ABC,Z=ABC)

 

3번은 2의 역이다. Y가 X의 상황이라도 똑같다는 말이된다.

 

책에는 이렇게 정리되어 있다.

너무도 당연한 이 소리는, 재귀해의 점화식을 만드는 핵심 정리가 된다.

 

점화식에서 해는 우리가 얻고자 하는 LCS의 길이를 공식화 한다.

c[i][j]를 Xi 와 Yj의 LCS 길이라고 한다면, 이렇게 점화식을 세울 수 있다.

 

1. i=0 혹은 j=0 일때, c[i][j] = 0

 

둘중 하나가 문자열이 아닌 공백이라면 당연한 소리.

 

2. i,j>0 이고 <X의 i번째 문자> = <Y의 j번째 문자>라면, c[i][j] = c[i-1][j-1] + 1 이다.

 

이 수식은 갑자기 어디서 나왔나 싶지만, 아까 최적 부분 구조의 1번에서 나온 수식이다.

 

Xi-1번째까지의 문자열과 Xj-1번째까지의 문자열의 LCS에다가 현재 Xi번째 문자와 Yj번째 문자가 같으므로 해당 문자가 LCS에 추가된다.

 

3. i,j>0 이고 <X의 i번째 문자> != <Y의 j번째 문자>라면, c[i][j] = max(c[i-1][j] , c[i][j-1]) 이다.

 

요건 또 뭐냐? 이건 최적 부분 구조의 2,3번에서 나온 수식이다.

 

(2) 만약 문자열 X가 더 길어서 하나를 짤라도 LCS인 상황이라면 c[i-1][j]가 현재 LCS의 길이이고,

(3) 반대로 Y가 더 길어서 하나를 짤라도 LCS인 상황이라면 c[i][j-1]가 현재 LCS의 길이이다.

따라서 두 상황 중 맞는 상황이 더 큰 값(진짜 LCS 값)을 가지고 있을 것이므로, 수식을 저렇게 작성한다.

 

이 재귀해를 위한 점화식은 책 내용에 이렇게 작성되어있다.

 

 

여기까지 c[i][j]를 기록해 나가기 위한 점화식을 이해해 봤다.

그럼 이제 코드를 보자.

 

import sys

fst_word = sys.stdin.readline().strip()
fst_len = len(fst_word)
sec_word = sys.stdin.readline().strip()
sec_len = len(sec_word)
lcs_list = [[0 for _ in range(fst_len+1)] for _ in range(sec_len+1)]
# 인덱스 0 은 0으로 초기화

if fst_len and sec_len:
    for i in range(1,sec_len+1):
        #CAPCAK
        for j in range(1,fst_len+1):
            #ACAYKP
            if fst_word[j-1] == sec_word[i-1]:
                lcs_list[i][j] = lcs_list[i-1][j-1] + 1
            else:
                lcs_list[i][j] = max(lcs_list[i-1][j],lcs_list[i][j-1])

print(lcs_list[sec_len][fst_len])

 

lcs_list가 설명했던 c 리스트 역할을 한다.

 

점화식의 1번은 lcs_list의 0번째 행과 열을 0으로 초기화하는 것으로 표현했고,

2번째 점화식은 for문 안의 첫번째 if문으로,

3번째 점화식은 else문 안으로 작성했다.

 

리스트가 전부 채워진 후엔 마지막 행과 마지막열의 온전한 두 문자열의 LCS 길이를 뽑아 낼 수 있다.

 

++ 그리고 문자열을 직접 뽑고 싶은 경우는 또 다른 알고리즘을 사용해야 하는데, 책을 직접 참고해도 되고, 다음 포스팅에 작성하겠다.