알고리즘!76 [C] 1026: 보물 결국 함수 S를 최소화하기 위해 배열 A를 재배열 해야한다. 최소화 하기 위해서는 현재 남아있는 A배열에 가장 작은 수와 B배열에 남아있는 가장 큰 수를 곱해줘야지만 S의 값이 최소가 된다. 이 문제에서는 B에 있는 수를 재배열하면 안된다고 했지만 어차피 문제는 답만 맞으면 된다는 생각으로 A는 오름차순으로 B는 내림차순으로 정렬한뒤 같은 index끼리 곱해주었다. 사실 이 문제와 완전 같은 방식으로 하기 위해서는 이차원 배열 두 개를 만든 뒤 현재 남아있는 A배열에 가장 작은 수와 B배열에 남아있는 가장 큰 수를 곱해주고 그 수는 지나갔다는 표시를 남겨주어 다음번에 이 수는 아예 빼고 생각하도록 코드를 짜면 된다. #include int arrA[51]; int arrB[51]; void swap(in.. 2023. 8. 25. [C/C++] 1541: 잃어버린 괄호 이 문제는 -가 언제 나오냐가 중요하다. -가 나올 때 그 다음 -가 나올때 까지 합을 빼는 것이 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 것이다. 또한 -가 나올 때마다 다음 -가 나올 때까지 합을 빼는 것이 가장 최소이기 때문에 현재에 이익이 문제 전체의 이익이 되는 Greedy 알고리즘의 일종이다. 나는 배열 2개만 써서 구현하였지만 아예 -가 나올 때마다 부분 집합을 만들어서 (slice를 통해) 각 값을 더하거나 빼서 구현할 수도 있을 것 같다!! 아래는 소스코드다!! #include #include char arr[52]; int store[3]; int ContinueCalculate(int i,int max) { if(arr[i]=='+') { store[0]+=store[1]; s.. 2023. 8. 24. [C] 1697: 숨바꼭질 사실 이 문제가 BFS 관련 문제라는 것을 빨리 깨달았다면 구현은 생각보다 쉽게 할 수 있었을 것이다. 그냥 어떻게 풀지 모르겠어서 각 경우의 수를 나누어 구해보고 있었는데 5에서 시작해 17로 가기 위한 경우를 그리던 중 가지가 뻗어지는 tree형태인 것을 확인할 수 있었다. 그리고 몇 초만에 갔는지 확인해야하므로 BFS 관련 문제인 것을 파악했다. 모르겠으면 무식하게 좀 해봐야겠다. 특히 이 문제 같은 경우는 갈 수 있는 방법이 3가지이므로 가지가 3개인 tree인 것을 알 수 있다. 그리고 2차원 배열을 구현할 때 각 index를 써주는 것이 귀찮아서 그냥 처음에 int *ret0=&queue[front][0];로 선언하였더니 코드가 더 깔끔하고 읽기 쉽게 느껴졌다. 또 queue[1000000][.. 2023. 8. 23. [C] 11403: 경로 찾기 문제는 정점 (i,j)에 대해서 i에서 j로 가는 길이가 양수인 경로가 있는지 확인하는 프로그램을 짜야한다. 여기서 알아야할 알고리즘은 Floyd's Algorthim으로 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우' 사용이 가능한 알고리즘이다. 2차원 배열에 저장을 하며 노드의 개수가 N개라고 할 때 N번만큼의 단계를 반복하여 리스트를 갱신하기 때문에 DP라고 볼 수도 있다. 이 알고리즘의 점화식은 Dab=min(Dab,Dak+Dkb)이지만 이 문제를 풀 때는 최단 경로가 아닌 경로가 있는지 확인만 하면 되기 때문에 코드가 조금 다를 수 있다. 그리고 이 점화식의 시간복잡도는 O(n^3)이다. #include #include int graph[101][101]; int mai.. 2023. 8. 23. 이전 1 ··· 6 7 8 9 10 11 12 ··· 19 다음
