알고리즘 이론

풀이 : 처음 접근했을 떄, 생각난 방법은 필요 피로도는 내림차순 소모 피로도는 오름차순으로 정렬 후 그리디로 접근하는 방법을 생각했다. 하지만 조건을 확인해보니, 던전이 8개로 제한 되있다. 때문에 안전하게 모든 경우의 수를 모두 탐색하는 방법으로 선택하였다. 방법 1) - next_permutation 모든 경우의 순열을 만들도록 사용했다 #include #include #include #include using namespace std; void permutation(int k, vector& dungeons, int & answer){ vector per; int tempK = k; for(int i=0;i k) continue; check[i] =true; DFS(now+1, k-dungeons..

알고리즘 문제를 해결하다보면 순열과 조합을 이용해야하는 일이 빈번히 발생한다. 순열을 구현하는 방법 중 하나인 원소의 방문을 체크해 가며 구현하는 방법과 STL을 이용하는 방법을 소개하겠다. 1. 재귀를 이용한 순열 구현 다음 방법은 크기가 3인 모든 수열을 출력하는 방법이다. checked배열로 현재 vector에 들어있는 값들을 확인하고, 순열에 아직 포함되지 않은 원소를 선택하여 vector에 넣어주는 방식으로 구현하였다. 또한 vector에 필요한 크기의 원소가 모두 들어가면 출력하는 방법으로 순열을 구할 수 있다. //순열구현하기 #include #include using namespace std; int arr[5]; bool checked[5]; vector v; void Input() { ..

Floyd Warshall이란? 대표적인 최단거리 찾기 알고리즘 중 하나 - 다익스트라, 벨만포드, 플로이드 와샬 * 다익스트라 : 모든 쌍의 최단 경로(음의 가중치 X) * 벨만포드 : 모든 정점에 대한 최단경로(음의 가중치 O) * 플로이드 와샬(음의 가중치 O + 음의 사이클이 없어야한다) 모든 정점끼리의 최단거리를 한번에 계산할 때 사용 + 동적 계획법을 사용 ex) 전체 정점에서 다른 정점들까지의 최단거리를 한번에 계산 -> 다익스트라의 경우 어떤 정점 A에서 다른 정점들까지의 최단 거리를 계산 Pseudo Code for(k=1;k> M; vector dis(N+1,vector(N+1,5000)); for (int i = 1; i > from >> to >> c; dis[from][to] = ..

이진탐색(Binary Search)란? 오름차순으로 정렬된 리스트에서 특정값을 찾는 알고리즘 오름차순으로 정렬된 리스트에서 중간 값(mid)을 선택하고 찾고자 하는 값(target)과 비교를 반복 때문에 정렬이 필수적 선형탐색보다 훨씬 빠르게 검색 가능(탐색 범위를 절반씩 줄여나감) 시간 복잡도 O(log N) 구현방법 1~100까지 오른차순으로 정렬된 카드 더미가 있다고 가정하자. 목표는 29를 찾는 것이다. i번째 카드는 c[i]로 나타내고, 목표 값(target)은 val로 표현하자. 결정 문제(Decision Problem, 답이 이분적일 경우)를 "c[i] >= val ?"로 설정하고 답은 i를 증가시키며 탐색을 시작한다. 그리고 v[i] >= val이 되는 지점이 나타나면 탐색을 완료합니다. ..

Sequence Container 시퀀스 컨테이너 리스트 (List) - 저장할 데이터 개수가 가변적일 때 사용 - 데이터가 중간에 삽입되거나 삭제되는 경우가 많을 때 용이 - 데이터의 개수가 크거나 검색을 자주하면 비효율적 -> map, set, hash_map 사용하기 - 데이터에 임의 접근하지 않을 때 사용. (리스트는 '순차접근') 백터(Vector) - 동적 배열 - 객체를 삽입/제거시 자동으로 크기를 조정 - 저장할 데이터의 개수가 가변적일 때 사용 - 데이터가 중간에 삽입/삭제 되는 경우가 없을 때 사용 - 순차 저장이므로 검색속도가 느리다 - 데이터 임의 접근에 용이 (위치만 알면 바로 접근 가능) 메서드 종류 - push_back() 덱(deque) - 데이터를 앞이나 뒤에서 삽입/삭제 ..

11059. 크리 문자열 https://www.acmicpc.net/problem/11059 11059번: 크리 문자열 첫째 줄에 문자열 S가 주어진다. S는 숫자로만 이루어져 있으며, 길이는 1,000을 넘지 않는다. 항상 크리 문자열이 존재하는 입력만 주어진다. www.acmicpc.net 입력의 길이는 1000을 넘지 않는다. 입력의 길이가 굉장히 큰 것은 아니기때문에 부담을 갖지 않아도 될 것 같다. 크리 문자열이 무엇일까? 대칭되는 짝수 길이의 문자열을 의미하는 것인가? (처음 필자는 대칭되는 것만 말하는 줄 알았다..ㅎ;ㅎ;;;;) 대칭이 안되어도 합만 같으면 된다!! int main() { ios::sync_with_stdio(0); cout.tie(); cin.tie(); cin >> s;..

5032. 탄산음료 https://www.acmicpc.net/problem/5032 5032번: 탄산 음료 첫째 줄에 준민이가 가지고 있는 빈 병의 수 e, 그날 발견한 빈 병의 수 f, 새 병으로 바꾸는데 필요한 빈 병의 개수 c가 주어진다. (e < 1000, f < 1000, 1 < c < 2000) e, f, c는 모두 음이 아닌 정수이다. www.acmicpc.net 반 병의 수 e, 그날 발견한 빈 병의 수 f, 새 병으로 바꾸는데 필요한 빈 병의 개수 c가 주어진다. 이를 활용해서 먹을 수 있는 탄산음료의 개수를 출력해야한다. 첫번째 예제 입력을 살펴보자. 입력은 9 0 3이고 출력은 4이다. 많은 사람들이 여기서 많은 고민을 했을거 같다. "처음에 9병이 있었고 0병을 발견했으면 바꿀 수..

2863. 이게 분수? https://www.acmicpc.net/problem/2863 2863번: 이게 분수? 첫째 줄에 표를 몇 번 돌려야 표의 값이 최대가 되는지 출력한다. 만약, 그러한 값이 여러개라면 가장 작은 값을 출력한다. www.acmicpc.net 입력으로 100보다 작은 양의 정수 4개가 입력되고, 이 정수들을 시계방향으로 돌린 후 함수에 해당값을 넣어 계산하는 문제이다. 우선 입력되는 정수가 4개로 고정되어있으므로 결과값이 총 4개가 나온다. 이 문제를 처음 접근할 때, 규칙을 찾아서 각 자리의 인덱스가 어떻게 변화하는 지를 찾아내려고 했지만 결론적으로 경우의 수가 4개밖에 없기 때문에 규칙을 찾아도 주먹구구식 방식이 더 빠르고 간편하다는 결론이 나왔다. 앗! 그리고 필자가 문제를 ..