CS

[Algo] DP (dynamic programming)

DP(dynamic programming) 복잡한 문제를 여러 개의 간단한 작은 문제로 나누어 푼 다음 작은 문제의 답을 모아 최종적으로 문제를 해결하는 방법 "중복되는 부분 문제"와 "최적 부분 구조"를 만족할 때 사용 중복되는 부분 문제(overlapping subproblem): 동일한 부분 문제(작은, 간단한 문제)를 반복적으로 해결 최적 부분 구조(optimal substructure): 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결 가능 Memorization, 이전에 해결한 하위 문제의 답을 저장해서 반복 작업을 줄이는 것이 핵심

[자료구조] 이분그래프 (Bipartite Graph)

이분그래프란? 2가지 특성으로 나눌 수 있는, 이분되어 있는 그래프 vertex를 2개의 그룹으로 나눌 수 있는데, 같은 그룹의 vertex끼리는 인접할 수 없는 그래프 특징 하나의 edge의 양 끝 vertex는 서로 다른 그룹에 속해 있어야 함 같은 그룹의 vertex끼리는 하나의 edge로 이어질 수 없음 cycle이 발생했을 때, 그 cycle을 잇는 edge의 개수는 짝수여야 함 edge가 없고 vertex만 있는 경우도 이분그래프 응용 각 그룹에 포함되어 있는 원소끼리의 관계를 나타낼 수 있다 학생 - 수업 : 학생들이 어떤 수업을 듣고 있는지, 각각의 수업을 듣고 있는 학생들은 누군지 관계를 나타낼 수 있다 구직자 - 선호 회사 : 구직자가 어떤 회사를 선호하는지 관계를 나타낼 수 있다 유저..

[Algo] 유클리드 호제법 (최대공약수, 최소공배수 구하기)

유클리드 호제법/알고리즘 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘 " 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. " 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여, 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 최대공약수 구하기 유클리드 호제법을 이용해 두 수 a, b의 최대공약수를 구할 수 있다. /* get_gcd: parameter로 주어지는 두 수 a, b의 최대공약수를 구하는 함수 (a > b) */ int ge..

[자료구조] heap

Heap 최댓값 및 최솟값을 빠르게 찾아내기 위해 만들어진 자료구조 '완전이진트리(completely binary tree)'를 기초로 함 중복된 값을 허용 ( cf. 이진 탐색 트리(binary search tree)는 중복값 허용 x ) A가 B의 부모 노드이면 A의 key 값과 B의 key 값 사이엔 대소관계가 성립 최대힙 - A key 값 > B key 값 최소힙 - A key 값 < B key 값 위 성질로 인해 항상 반정렬 상태가 유지됨 Heap 구현 힙은 보통 '배열'로 구현됨 ( 부모 노드 ) = ( 자식 노드 ) / 2 ( 왼쪽 자식 노드 ) = ( 부모 노드 ) * 2 ( 오른쪽 자식 노드 ) = (부모 노드) * 2 + 1 index 0 1 2 3 4 5 6 7 value x 9 7 ..

[Algo] 다익스트라 알고리즘 (dijkstra)

Dijkstra Algorithm DP 를 이용한 대표적 최단 경로 알고리즘 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있음 음의 간선 불가능 Idea " 최단 거리는 여러 개의 최단 거리로 이루어져 있다 " 출발 정점에서 가장 가까운 정점을 중간 정점으로 했을 때의 거리와 비교하여 최단 거리를 업데이트 ex) 출발 정점이 1이고, 1에서 가장 가까운 정점인 4를 중간 정점으로 했을 때, 3, 5의 경우 1에서 바로 가는 것보다 중간 정점인 4를 거쳐서 가는 것이 더 가까움 출발 정점인 1에서 3과 5로 가는 최단 거리를 3, 7로 업데이트 모든 정점에 대해 출발 정점에서 가까운 순서대로 위 동작을 반복하면 출발 정점에서 각 정점까지의 최단 경로를 알 수 있음 1과 가장 가까운..