D P

조졌다. 오면 안되는게 왔다.동적 프로그래밍은 사실 동적이냐고 하면 이상하다. Dynamic Programming을 처음 생각해낸 사람 조차 정부의 지원금을 타기 위한 그럴듯한 이름이 필요했다고 설명한다.어쨌든, 동적 프로그래밍의 개발 취지는, 인류 문명에 있어 최적화 문제를 푸는 것이 중요했기 때문이다. 내가 햄북스딱스를 뒤집어먹을건지, 토마토를 빼고 먹을건지, 사이사이에 감자튀김을 살짝 채워먹을건지 순서와 방법 하나하나는 인류가 더 나은 방향성으로써 지내게 하는 주된 내용이지 않은가.예로부터 프로그래밍은 계획을 논하는 경우도 잦았기에, 동적 계획법이라고 번역되기도 한다.어쨌든, DP는 분할정복과 같이 논하게 된다. 하지만..DP도 나눠 푸는 것은 사실이다.DP는 최적화 문제를 푼다는 표현이 맞다.여기..

• format_list_bulleted 컴퓨터 이론
• · 2025. 4. 3.

다익스트라

다익스트라 알고리즘은 방향 그래프 혹은 무방향 그래프에서 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구한다.플로이드 알고리즘 (은 이후 글에서 다루겠다)은 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘이지만, 다익스트라는 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하게 된다. 뭔가 효율적이고 그리고 쓸 곳이 있으니 이런 것을 배우게 된다.제약 조건은 음수 가중치가 포함되어 있는 그래프에서는 사용 할 수 없다.알고리즘 작동 방식시작 노드를 선택한다. 해당 노드의 거리는 0으로 초기화하고, 다른 노드와의 거리는 infinity로 초기화한다.우선순위 큐 자료구조를 이용하여 가장 작은 가중치를 가진 노드를 반복적으로 선택한다.정확하게 말해서 이 상황에서는 우선순위 큐가 별 다른 커..

• format_list_bulleted 컴퓨터 이론
• · 2025. 4. 3.

Topological Sorting

위상 정렬이라 번역되어 불리는 이 알고리즘은 방향성이 있는 그래프에서 노드들을 선행 관계에 따라 정렬하는 방법을 정의한다.특징DAG에만 적용 가능방향성 그래프 중에서도 사이클이 없는 경우에만 사용이 가능하다. 사이클이 존재하면 정렬 할 수 없다.왜?위상 정렬은 진입 차수가 0인 노드부터 시작하여 단계적으로 순서를 정해나간다. 사이클이 있다고 하면, 모든 노드가 서로 연결 되어 있기 때문에 진입 차수가 0이 되는 노드가 존재 할 수 없다. A - B - C - A 같은 순환 구조에서는 어느 하나의 노드도 위상 정렬의 대상 노드로 지정 할 수 없다. 진입 차수 우선이 아닌 진출 차수를 고려해도 상황은 다르지 않다.위상 정렬은 작업을 선후 관계에 따라 배치한다. 사이클이 있다면 어떤 작업이 먼저 시작되어야 하..

• format_list_bulleted 컴퓨터 이론
• · 2025. 4. 3.

[PY] 2252 : 줄 세우기

https://www.acmicpc.net/problem/2252위상 정렬의 기본을 다루는 문제이다.from collections import dequeimport sysinput = sys.stdin.readlinestdCnt, compareNum = map(int, input().split())compareList = [[] for _ in range(stdCnt + 1)]degreeList = [0] * (stdCnt + 1)for i in range(compareNum): compA, compB = map(int, input().split()) compareList[compA].append(compB) degreeList[compB] += 1queue = deque()for i i..

• format_list_bulleted 문제풀이
• · 2025. 4. 3.

트라이 : Trie

트라이는 문자열을 효율적으로 저장하고 검색하기 위한 자료구조이다. 주로 문자열 처리와 관련된 문제를 해결하는데 유용하다.자동완성, 사전(Dictionary) 구현, 검색 추천 등에서 많이 사용된다.특징노드 구조트리는 루트부터 시작하며, 각 노드는 문자(char)와 연결된다.노드에는 해당 문자로 끝나는 단어의 여부를 나타내는 플래그(종료 마커)도 포함 될 수 있다.계층적 구조각 경로는 문자열의 접두사를 표현한다. 예를 들어, "cat"과 "car"가 저장된 트라이에서는 "ca"가 공통 접두사로 저장된다.공간 효율성공통 접두사를 공유하기 때문에 유사한 문자열이 많을 경우 메모리 사용을 줄일 수 있다.하지만, 노드의 갯수가 많아지면 공간을 더 차지하게 된다.시간 복잡도검색, 삽입, 삭제, 모두 문자열의 길이를..

• format_list_bulleted 컴퓨터 이론
• · 2025. 4. 3.

WIL 03

공부의 흐름에 방해가 되는게 몇 개 있다. 내가 그것들을 걱정 없이 받아들이는 것은그 방해들이 내가 원하는 미래를 만드는데 기여하냐를 무의식에서 최소 한 번은 시뮬레이션 하는 것 같다.사람은 입체적이듯, 상황도 입체적인 경우가 많다. 알면서도, 마음으로 받아들이기가 너무 어려운 것 같다. 그럼에도 해내려도 애쓰는 모습이 방해들 조차 내게 도움이 되는 상황으로 만드는 진짜가 아닐까? 이번 주는 그래프에 관한 걸 다뤘는데, 컴퓨터 과학을 접하고 나서 항상 힘들었던 영역이었기에 감회가 새롭다.마음도 여러 방향으로 들락날락 했고, 좋은 일 나쁜 일이 주변에서 일어나니 몰입하기가 쉽진 않았던 것 같다.군대가 다시 생각해 봐도 싫지만 지금의 영적 방어력에 기여가 된다는 말을 부정 할 수는 없을 것 같다. 있는 상황..

• format_list_bulleted WIL
• · 2025. 4. 3.