컴공 재학생의 공부 일기

지난 시간에 그래프의 기초 개념을 다루었으니 그래프 응용 시간을 가져보겠다. 이번 시간에 할 건 그래프의 최소비용 신장트리의 구성이다. 그전에 우리는 무방향 그래프만 다룰 것이고, 시작에 앞서 용어를 몇 개 짚고 가자 가중치 그래프 : 정점을 잇는 간선에 값이 부여된 그래프이다. 인접행렬을 보면 0과 0이상의 값, 무한대로 3가지의 값의 표현이 있다. 0 : 자기 자신을 가리키는 간선이 없으니 0 0 이상의 값 : 가중치, weight라고 부른다. 무한대 : this 정점에서 해당 정점까지 한 번에 가지 못한다는 걸 의미한다. 지난 시간에는 정점이 간선으로 연결되어 있다는 사실로, 인접행렬을 0과 1로 표현했지만 이제는 간선에 값이 주어지기에 1이 아닌, 그 값을 인접행렬에 넣는다. 신장트리(Spanni..

그래프란 ? : 정점(Vertex)과 그 정점을 잇는 간선(edge)으로 구성되어 있는 자료구조 무방향 그래프 : 간선의 방향이 없는 그래프 방향 그래프 : 간선의 방향이 있는 그래프 그래프를 표현하는 두 가지 방법 1. 인접행렬 2. 인접리스트 인접행렬 표현법 (무방향과 방향 그래프) 무방향 그래프를 인접행렬로 표현하면 대칭적인 형태를 볼 수 있다. 인접행렬을 작성하는 코드는 다음과 같다. // 그래프의 인접행렬 생성 함수 void createGraph(int arr[][MAX_SIZE], int vertex, int edge) { int start, destination; // 인접행렬 초기화 for (int i = 0; i < vertex; i++) { for (int j = 0; j < verte..

동적 계획법을 지난 시간에 배웠으니, 그에 맞는 문제를 풀어보려 한다. 백준의 실버3 난이도 DP 알고리즘을 쓰는 '2579번 : 계단 오르기' 문제이다. 문제 규칙 이 문제에서는 규칙을 문제 설명에 명시해 두었다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 동작 원리의 핵심은 2번에 있다. 세 개의 계단을 연속되게 밟으면 안 되고, 한 번에 세 칸 이상씩은 이동할 수 없다는 점이다. 백준에 나와있는 입력 예제이다. 첫 번째 int 변수 n에 계단 개수를 받아주고 계단의 값을 담아..

이번 주 백준 문제 유형이 자료구조 수업 때 배우지 않은 DP이기에 이를 공부한 바탕으로 DP를 정리해보려 한다. 두괄식으로 먼저 DP를 정의한 문구들을 보고 가자. DP란 ? → *메모이제이션(Memoization) 기법을 이용하며 '하나의 문제는 단 한 번만' 풀도록 하게 하는 알고리즘 * 계산했던 것을 메모리 공간에 기억해 두고, 같은 식을 써야한다면 앞에서 기억한 것을 재사용하는 기법 분할 정복 기법과 DP의 차이점 분할 정복 : 큰 문제를 작은 부분 문제로 나누고, 그 하위 문제를 독립적으로 해결하고 이를 합쳐서 원래 문제를 해결함 동적 계획법(DP) 분할 정복 중복되는 문제 O X 메모이제이션 O (중복 문제의 결과를 저장하고 재활용함) X 문제 분할 방식 문제의 크기와 형태에 따라 다름 동일..