anonymous?

입력 BOJ 유저의 수 친구 관계 출력 케빈 베이컨의 수가 가장 작은 사람, 중복이 있는 경우 번호가 가장 작은 사람 출력 케빈 베이컨 수 = 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합 예제 5 5 1 3 1 4 2 3 3 4 4 5 1: 2(2단계), 3(1단계), 4(1단계), 5(2단계) ⇒ 2 + 1 + 1 + 2 = 6 2: 1(2단계), 3(1단계), 4(2단계), 5(3단계) ⇒ 2 + 1 + 2 + 3 = 8 3: 1(1단계), 2(1단계), 4(1단계), 5(2단계) ⇒ 1 + 1 + 1 + 2 = 5 4: 1(1단계), 2(2단계), 3(1단계), 5(1단계) ⇒ 1 + 2 + 1 + 1 = 5 5: 1(2단계), 2(3단계), 3(2단계), 4(1단계) ⇒ 2 + 3..

PROGRAMMING/Algorithm 2023. 7. 29. 17:20

입력 첫째줄: 테스트케이스 수 둘째줄: 한 줄에 있는 스티커 수 셋째줄: 스티커 별 점수 출력 각 테스트케이스에서 두 변을 공유하지 않는 스티커 점수의 최댓값 조건 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 됨 항상 S[0][0] 또는 S[1][0]부터 스티커를 떼기 시작함 -> S[0][0]을 뗄 때, S[1][0]을 뗄 때를 나누어서 점화식을 구현 항상 2 x n 배열로 스티커가 구성 풀이과정 예시를 통해 점화식을 생각해볼 수 있다. 스티커가 구성된 배열을 DP[2][5+1]라 하자. 편의 상 DP[0][0]과 DP[1][0]은 0으로 비워둔다. 그렇다면 DP[0][0] = DP[1][0] = 0으로 초기화를 하고, 나머지는 스티커 점수로 값을 채워야 한다. 0 50 10..

PROGRAMMING/Algorithm 2023. 7. 17. 00:00

배낭문제와 다이나믹 프로그래밍(DP)으로 생각하고 코드를 구현했다. 처음에 인사할 때 잃는 체력과 얻는 기쁨을 pair로 vector에 저장하고 남은 체력마다의 최대 기쁨도 vector에 저장했는데, 이때 vector에서 가져오고 저장하고 이런 처리하는 속도가 배열과 비교했을 때 상대적으로 너무 오래 걸리는 것 같았다. 그래서 잃는 체력과 얻는 기쁨은 1차원 배열에, 사람마다 남은 체력이 있을 때의 값을 최대 기쁨으로 저장하는 2차원 배열 DP를 이용해서 배낭 문제의 개념으로 문제를 풀었다. 인사하는 사람마다 남은 체력이 1~100일 때 인사했을 때 남은 체력이 0보다 크고 얻는 기쁨이 최대이면 이를 취하고, 그렇지 않으면 이전 사람에서의 해당 체력일 때를 취하였다. 처음에는 2차원 배열로 최대 기쁨을 ..

PROGRAMMING/Algorithm 2023. 7. 16. 15:50

Knapsack 알고리즘 DP[물건 번호][무게] = 최대 가치 -> 해당 물건에서 최대 무게를 가질 때 가질 수 있는 최대 가치에 해당 첫 번째 물건부터 무게 1부터 최대 무게 K까지 무게를 담았을 때 가질 수 있는 최대 가치를 DP에 저장한다. 이 정보는 다음 물건에서 최대 무게-다음 물건 무게가 이전에서 담을 수 있는 최대 무게에서 최대 가치를 가질 것이므로 이때의 가치와 다음 물건의 가치를 더했을 때와 이전 물건에서 최대 가치 중 최댓값을 취할 때 사용한다. 만약 i번째 물건의 무게가 최대 무게 j보다 작은 경우엔 담을 수 없으므로 i-1번째의 최대 무게 j에서의 최대 가치를 취한다. 최종적으로 마지막 물건에서 가질 수 있는 최대 무게에서의 최대 가치가 배낭에 넣을 수 있는 물건들의 가치합의 최댓..

PROGRAMMING/Algorithm 2023. 4. 14. 00:10

#include #include using namespace std; int main(){ int N,K; scanf("%d %d", &N, &K); vector sum(N+1,0); for(int m=0; m

PROGRAMMING/Algorithm 2023. 4. 11. 02:05

구간 합 알고리즘 사용 i~j 사이 합을 반복문을 사용할 때 시간복잡도는 O(n)인데, n이 클수록 시간복잡도가 커진다. 구간 합 알고리즘은 시간복잡도가 O(1) 먼저 현재 인덱스까지의 합을 sum[]에 저장한다. j-1까지의 총합 sum[j-1]에 j를 더하면 sum[j]이므로 sum[j] = sum[j-1] + arr[j] 만약 구간 [i,j]의 합을 구한다면 j까지의 합에서 i 이전까지의 합을 빼면 i부터 j까지의 합이므로 sum[j]-sum[i-1]으로 나타낼 수 있다. 계산의 편의를 위해 0번 인덱스는 0으로 초기화하고 사용하지 않고, 1번 인덱스부터 N까지 사용 #include #include #include using namespace std; int main(){ int N, M; scan..

PROGRAMMING/Algorithm 2023. 4. 11. 01:48

O(N) 문제 #include using namespace std; int main(int argc, char** argv) { unsigned long K, P, N; scanf("%u %u %u", &K, &P, &N); for(unsigned int i=0; i

PROGRAMMING/Algorithm 2023. 4. 8. 20:22

#include using namespace std; int main(int argc, char** argv) { unsigned int T; scanf("%d", &T); for(int i=0; i

PROGRAMMING/Algorithm 2023. 3. 28. 01:09

#include #include using namespace std; int main(int argc, char** argv) { string delim=":"; unsigned int result=0; for(int i=0; i> start >> end; int pos1=start.find_first_of(':'); int pos2=end.find_first_of(':'); int start1 = stoi(start.substr(0, pos1)); int start2 = stoi(start.substr(pos1+1)); int end1 = stoi(end.substr(0, pos2)); int end2= stoi(end.substr(pos2+1)); //printf("start1: %d start2: ..

PROGRAMMING/Algorithm 2023. 3. 28. 01:08

Overview Backtracking n-Queens 문제 Sum-of-Subset 문제 (부분집합의 합 구하기 문제) 그래프 색칠하기 문제 Hamiltonian Circuits Problem Monte Carlo 기법 (probabilistic Algorithm) Backtracking 1) Backtracking 노드의 유망성 점검 후 유망하지 않으면 부모로 되돌아가(backtracking) 다음 자식노드의 유망성 점검하여 문제의 답 찾는 기법 마디의 유망성 전혀 해답이 나올 가능성이 없는 마디는 유망하지 않다(non-promising)고 판단, 그렇지 않으면 유망하다(promising)고 판단 어떤 집합에서 특정 기준을 만족하도록 원소를 선택하는 문제 해결에 적합 예) n-Queens 문제 깊이 ..

PROGRAMMING/Algorithm 2022. 1. 8. 23:20

이전 내용 Greedy Algorithm 거스름돈 문제 최소비용 신장트리(MST, Minimum Spanning Tree) Prim 알고리즘 Kruskal 알고리즘 Greedy Algorithm (탐욕 알고리즘) 어떤 선택을 할 때 그 당시 가장 최선의 선택을 하여 문제를 해결하는 알고리즘 순간의 선택은 지역적으로 최적이나, 이런 선택을 모아 얻은 해답이 최적인 보장이 없다. 따라서 얻은 해답이 최적인지 검사하는 절차 필요 Greedy Algorithm 설계 1. 선정 과정 (selection procedure) 현재 상태에서 가장 좋을 것이라 생각되는(greedy) 해답 찾아서 solution set에 포함 2. 적정성 점검 (feasibility check) 새로 얻은 solution set이 적절한..

PROGRAMMING/Algorithm 2022. 1. 8. 21:09

Greedy Algorithm (탐욕 알고리즘) 어떤 선택을 할 때 그 당시 가장 최선의 선택을 하여 문제를 해결하는 알고리즘 순간의 선택은 지역적으로 최적이나, 이런 선택을 모아 얻은 해답이 최적인 보장이 없다. 따라서 얻은 해답이 최적인지 검사하는 절차 필요 Greedy Algorithm 설계 1. 선정 과정 (selection procedure) 현재 상태에서 가장 좋을 것이라 생각되는(greedy) 해답 찾아서 solution set에 포함 2. 적정성 점검 (feasibility check) 새로 얻은 solution set이 적절한지 결정 3. 해답 점검 (solution check) 새로 얻은 solution set이 최적의 해인지 결정 거스름돈 문제 1. 거스름돈 문제 문제: 동전의 개수가..

PROGRAMMING/Algorithm 2022. 1. 8. 18:06