Krafton_jungle 5기 22일차 TIL - LCS, CSAPP

CSAPP

 

이기종 자료구조 (Heterogeneous)

이기종 자료구조란?	다른 여러가지의 데이터를 포함하고 있는 구조체(struct)와 공용체(Union)을 뜻한다.
구조체(struct)	C 언어의 구조체(structure)는 다양한 데이터 타입의 멤버들을 하나로 묶어서 새로운 데이터 타입을 정의하는 데 사용. 자바의 class의 개념과 아주 약간 비슷함
구조체의 offset	각 구조체의 필드값에 따른 byte 용량으로 정한다. char = 1byte, long = 8byte...
공용체(union)	말 그대로 필드값의 가장 큰 Byte만큼만 메모리를 할당하고, 그 메모리를 모든 필드값들과 공유하며 사용함. 메모리를 효율적으로 사용할 수 있지만, 한번에 하나의 필드값밖에 할당할 수 없어 지금은 잘 사용하지 않음
데이터의 정렬	컴퓨터 아키텍처는 메모리에 데이터를 읽고 쓸 때 특정한 정렬 규칙을 가질 수 있다. 예를 들어, 대부분의 시스템에서는 데이터의 주소가 4 또는 8의 배수일 때 더 효율적으로 접근할 수 있음. 구조체의 멤버들을 정렬함으로써 메모리에 대한 이러한 요구사항을 충족시키고 메모리를 더 효율적으로 사용함.

 

알고리즘

 

9084 동전

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    coins = list(map(int, input().split()))
    dp_size = int(input())
    dp_table = [0 for _ in range(dp_size + 1)]
    dp_table[0] = 1
    for coin in coins:
        for i in range(coin, dp_size+1):
            dp_table[i] = (dp_table[i] + dp_table[i - coin])
    print(dp_table[-1])

대부분의 풀이가 2차원 배열을 사용하는 방식을 채택했는데, 난 1차원 배열이 좀 더 깔끔하고 보기 좋아서 이 방법을 사용했다.

 

 

12865 평범한 배낭

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

wv_list = []
for _ in range(n):
    wv_list.append(list(map(int, input().split())))

dp_table = [0]*(k+1)

# 좌표 압축
for w, v in wv_list:
    if w > k:
        continue
    for j in range(k, w-1, -1):
        dp_table[j] = max(dp_table[j], dp_table[j - w] + v)

print(dp_table[k])

DP의 가장 기초적인 문제인 배낭문제이다.

이 문제 또한 1차원 배열으로 해결함

 

 

9251 LCS

# 1차원 배열 압축 실패!
import sys
input = sys.stdin.readline

LCS_patten1 = input().rstrip()
LCS_patten2 = input().rstrip()

if len(LCS_patten1) > len(LCS_patten2):
    LCS_patten1, LCS_patten2 = LCS_patten2, LCS_patten1

dp_table = [0] * (len(LCS_patten2) + 1)

for i in range(1, len(LCS_patten1) + 1):
    for j in range(1, len(LCS_patten2) + 1):
        if LCS_patten1[i-1] == LCS_patten2[j-1]:
            dp_table[j] = dp_table[j-1] + 1
        else:
            dp_table[j] = max(dp_table[j], dp_table[j-1])

print(dp_table[-1])

# 결국 2차원 배열로 풀이!
import sys
input = sys.stdin.readline

LCS_patten1 = input().rstrip()
LCS_patten2 = input().rstrip()

# 두 문자열의 길이
m = len(LCS_patten1)
n = len(LCS_patten2)

# LCS를 구하기 위한 DP 테이블 초기화
dp_table = [[0] * (n + 1) for _ in range(m + 1)]

# LCS를 구하는 과정
for i in range(1, m + 1):
    for j in range(1, n + 1):
        if LCS_patten1[i-1] == LCS_patten2[j-1]:
            dp_table[i][j] = dp_table[i-1][j-1] + 1
        else:
            dp_table[i][j] = max(dp_table[i-1][j], dp_table[i][j-1])

# LCS의 길이 출력
print(dp_table[m][n])

LCS 문제 또한 DP의 대표적인 유형이라고 할 수 있다.

해당 방법도 1차원 배열로 날먹하려다가 도저히 안되서 2차원 배열로 풀이함.

뭔가 될것같은데 내일 다시 한번 도전해봐야겠다.