1031-TIL(coretime: 행렬곱셈,bit_masking, C)

그로밋·2023년 10월 31일

krafton jungle

목록 보기

20/58

행렬 곱셈 순서

참고블로그

외판원(bit masking)

(https://hongcoding.tistory.com/83)
현재 도시에서의 최소비용은 DP를 활용하고, 도시를 방문하는 것은 DFS를 활용.

visited라는 변수에 2진수로 거친 도시를 표시하였다.

0001(2) = 1 이라면 => 0번 도시만을 거침
0011(2) = 3 이라면 => 0, 1 번 도시를 거침
1111(2) = 15 이라면 => 0, 1, 2, 3 번 도시를 거침

n = int(input())

INF = int(1e9)
dp = [[INF] * (1 << n) for _ in range(n)] # [[1000000000, 1000000000, 1000000000,...]]
print(dp)

def dfs(x, visited):
    
    if visited == (1 << n) - 1:     # 모든 도시를 방문했다면,  10000 이라면
        # print('(1 << 4)', (1 << n)) -> 16
        if graph[x][0]:             # 출발점으로 가는 경로가 있을 때
            return graph[x][0]
        else:                       # 출발점으로 가는 경로가 없을 때
            return INF

    if dp[x][visited] != INF:       # 이미 최소비용이 계산되어 있다면
        return dp[x][visited]

    for i in range(1, n):           # 모든 도시를 탐방
        if not graph[x][i]:         # 가는 경로가 없다면 skip
            continue
        if visited & (1 << i):      # 이미 방문한 도시라면 skip
            continue

        # 점화식 부분(위 설명 참고)
        dp[x][visited] = min(dp[x][visited], dfs(i, visited | (1 << i)) + graph[x][i])
    return dp[x][visited]


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

print(dfs(0, 1))

C

pointer

int main() {
    int a = 10;
    int *b = &a;
    int **c = &b;
    
    // b를 통해서 a에 담겨있는 값을 가져오고 싶다면
    printf("%d\n", *b);
    
    // 그냥 b하면 a의 주소다.
    printf("%p\n", &a);
    printf("%p\n", b);
    
    // 더블포인터로 c를 사용해서 a에 담긴 10 값을 가져오자
    printf("%d\n", **c);
    
}

int *b = &a; 부분을 보면 포인터가 변수같이 생겼지만 메모리를 사용하지 않는다는 것을 알 수 있다. b포인터는 단지 a의 주소값을 가리키고 있을 뿐이다.

int num = 42;
int *ptr = &num; // 포인터 선언 및 초기화

포인터와 배열

malloc

free() 해주는 거 잊지 말아야 하는데(안그럼 메모리 누수 일어남), 근데 두번 해주면 또 에러남

포인터의 위험성:

포인터를 부적절하게 사용하면 발생할 수 있는 버그와 보안 문제들은 아래와 같이 많다.

NULL 포인터 참조 (Null Pointer Dereference):
이것은 아마 가장 흔한 실수 중 하나일 것입니다. 포인터가 NULL 값을 가리키면 해당 포인터를 사용하려고 할 때 프로그램이 비정상적으로 종료됩니다. 이는 메모리 누수나 의도치 않은 프로그램 동작으로 이어질 수 있습니다.
Dangling 포인터:
이는 더 이상 유효한 메모리 위치를 가리키지 않는 포인터를 사용하는 오류입니다. 예를 들어, 메모리를 해제한 후에 그 메모리를 가리키는 포인터를 계속 사용하려고 하면 발생합니다.
메모리 누수 (Memory Leaks):
동적으로 할당된 메모리를 해제하지 않고 그 메모리에 대한 포인터를 잃어버리는 것을 말합니다. 이는 메모리 소비가 계속 증가하고 시스템 성능 저하를 초래할 수 있습니다.
배열 범위를 초과한 접근 (Buffer Overflow):
포인터를 사용하여 배열 요소에 접근할 때, 배열의 범위를 벗어나게 되면 메모리 다른 위치에 접근하게 됩니다. 이것은 프로그램의 비정상적인 동작 또는 보안 취약점을 초래할 수 있습니다.
포인터 초기화 문제:
포인터를 선언한 후 초기화하지 않고 사용하려고 시도하면 예상치 못한 동작을 유발할 수 있습니다.
스택과 힙 혼합 오류:
포인터를 사용하여 스택에서 할당한 메모리를 힙에서 해제하거나 그 반대의 조작을 하면 문제가 발생할 수 있습니다.
다중 포인터 레퍼런스 문제:
여러 포인터가 같은 메모리 위치를 가리킬 때, 하나의 포인터가 메모리를 해제하거나 수정하면 다른 포인터들도 영향을 받을 수 있습니다.