할머니의 콤퓨타 도전기

Floyd Warshall Algorithm 다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구함 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택 플로이드 와샬 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘 수행 기본적으로 다이나믹 프로그래밍 기술 위의 그래프에서 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열로 출력 0 5 INF 8 7 0 9 INF 2 INF 0 4 INF INF 3 0 위 테이블은 현재까지 계산된 최소 비용 이러한 이차원 배열을 반복적으로 갱신해 최종적으로 모든 최소비용을 구해야함 반복의 기준은 거쳐가는 정점 1. 노드 1을 거쳐가는 경우: 색칠..

unique() vector 배열에서 중복되지 않는 원소들을 앞에서부터 채워나가는 함수 algorithm 헤더에 존재 중복되지 않는 원소들을 앞에서 채워나가는 역할. 따라서 남은 뒷부분은 그대로 vector 원소값이 존재 따라서 뒷 부분에 필요없는 값 삭제시켜줘야함 n개 원소에 대한 unique 함수의 시간 복잡도는 O(n) erase() vector 배열에서 특정 원소 삭제하는 함수 v.erase(v.begin()+s, v.begin()+e) : [s,e)의 원소 삭제. 시작 지점은 닫힌 구간, 끝나는 지점은 열린 구간으로 삭제 시간 복잡도 O(n) v.erase(unique(v.begin(), v.end()), v.end()); 위와 같이 중복된 원소들 제거하고 원하는 원소만 출력 가능

tolower: 대문자를 소문자로 변환 toupper: 소문자를 대문자로 변환 #include #include using namespace std; int main() { string str = "Hello World"; for(int i=0; i

사용자 정의 비교 연산자 구현 우선순위 큐 선언 #include using namespace std; int main(){ priority_queue pq; // 자료형 int, 컨테이너 vector, 사용자 정의 비교연산자 compare 비교 연산자 구현 정수를 오름차순으로 정렬하는 비교 연산자 struct compare{ bool operator()(int a, int b){ return a>b; } }; 우선순위 큐 내부에 새로운 자료가 들어가면 자신의 부모 노드와 크기를 비교하면서 조건에 따라 swap 위 코드에서 a는 부모 노드, b는 현재 노드 만약 a가 b보다 크다면 true를 return에서 swap을 진행함 이를 반복하면 조상 노드는 가장 작은 원소가 차지하게 됨 정수를 내림차순으로 정렬..

위상 정렬 순서가 정해져 있는 작업을 차례대로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘 DAG (Directed Acyclic Graph: 사이클이 발생하지 않는 방향 그래프)에만 적용 가능 사이클이 발생하는 경우 위상 정렬을 수행할 수 없음 위상 정렬은 시작점이 존재해야함. 사이클 그래프에서는 시작점 찾을 수 없음. 불가능 위상 정령은 두 가지의 해결책 보여줌 현재 그래프는 위상 정렬이 가능? 가능하다면, 그 결과는? 구현 방법 진입 차수가 0인 정점을 큐에 삽입 큐에서 원소를 꺼내 연결된 모든 간선 제거 간선 제거 이후에 진입차수가 0이된 정점을 큐에 삽입 큐가 빌 때 까지 2~3번 과정 반복 모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재하는 것 모든 원소를 방문했다면 큐에..

Knapsack 알고리즘 무게와 가치가 따로 있고 가져갈 수 있는 최대 가치를 묻는 문제에 사용 모든 경우를 다 따져보는 Greedy 알고리즘으로 해결할 수 있지만 시간복잡도가 2^n, 최적의 답일 보장 없음 다이나믹 프로그래밍으로 풀어야함 w[i] : i 번째 보석의 무게 v[i] : i 번째 보석의 가치 d[i][j] : i 번째 보석까지 탐색한 현 상태, j 만큼 무게를 가져갔을 때 획득한 최대 가치 i 번째 보석을 가져간 경우 : d[i][j] = d[i-1][j-w[i]] + v[i] i 번째 보석을 가져가지 않은 경우 : d[i][j] = d[i-1][j] i를 첫 번째 보석부터 n 번째 보석까지, j를 0kg부터 k (배낭이 담을 수 있는 최대 무게)까지 d[i][j] = max(d[i][j..