반응형 알고리즘207 백준 2109번 순회강연 - C++ 풀이 1. 시간 역순으로 매일 가장 강연료를 많이 받을 수 있는 강연을 고른다. 1. 시간 역순으로 매일 가장 강연료를 많이 받을 수 있는 강연을 고른다. 1781번 컵라면 문제와 동일한 문제이다. 13904번 과제 문제와도 동일하다. 1781번 게시글에 그리디 알고리즘에 관해 그림과 함께 설명해두었으니 참고. (강연료 = 컵라면이라고 생각하면 된다.) 백준 1781번 컵라면 - C++(cpp) 풀이 + 그림 설명 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. day일에 풀 수 있 please-amend.tistory.com #include #include #include usi.. 2022. 8. 24. 백준 14391번 종이 조각 - C++ 풀이 1. 각 칸을 세로로 사용할지 가로로 사용할지 결정한 뒤, 전체 조각의 합을 구한다. 2. 모든 경우 중 전체 조각의 합이 가장 큰 경우를 고른다. 1. 각 칸을 세로로 사용할지 가로로 사용할지 결정한 뒤, 전체 조각의 합을 구한다. 모든 칸에 대해 각 칸을 세로 조각으로 사용할지, 가로 조각으로 사용할지 결정한다. 결정 결과를 비트 마스킹으로 나타낼 수 있다. (ex. 가로는 1 세로는 0) 모두 결정한 뒤에는 전체 조각의 합을 구하면 된다. 전체 조각의 합을 구할 때, 인접한 두 칸 A, B가 똑같이 가로 또는 세로 칸일 경우, A와 B는 서로 이어져 있는 긴 조각으로 처리해주어야 한다. 2. 모든 경우 중 전체 조각의 합이 가장 큰 경우를 고른다. 모든 경우를 고려한 뒤 그 중 합이 가장 큰 경우를.. 2022. 8. 23. 백준 13904번 과제 - C++ 풀이 1. 시간 역순으로 매일 가장 점수를 많이 받을 수 있는 과제를 고른다. 1. 시간 역순으로 매일 가장 점수를 많이 받을 수 있는 과제를 고른다. 1781번 컵라면 문제와 동일한 문제이다. 1781번 게시글에 그리디 알고리즘에 관해 그림과 함께 설명해두었으니 참고. (점수=컵라면이라고 생각하면 된다.) 백준 1781번 컵라면 - C++(cpp) 풀이 + 그림 설명 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. day일에 풀 수 있 please-amend.tistory.com #include #include using namespace std; typedef pair pii;.. 2022. 8. 22. 백준 1963번 소수 경로 - C++ 풀이 1. 에라토스테네스의 체를 이용하여 4자리 소수를 모두 구한다. 2. BFS를 이용하여 두 소수 사이의 변환에 필요한 최소 회수를 구한다. 1. 에라토스테네스의 체를 이용하여 4자리 소수를 모두 구한다. 네 자리 수가 소수인지 아닌지 판별할 일이 잦으므로 미리 4자리 소수를 모두 구해두어 O(1)에 소수 판별을 할 수 있도록 하자. N 미만의 소수는 에라토스테네스의 체를 사용하면 O(NloglogN)에 구할 수 있다. 2. BFS를 이용하여 두 소수 사이의 변환에 필요한 최소 회수를 구한다. 각 소수를 그래프의 노드라고 생각하면, BFS를 통해 두 소수(노드) 사이의 최단 거리를 구할 수 있다. #include #include using namespace std; const int INF = 987654.. 2022. 8. 20. 백준 17142번 연구소 3 - C++ 풀이 1. M개의 자리를 활성시키는 모든 경우를 시뮬레이션하여 최소 시간을 구한다. 2. 각 경우는 BFS를 이용해서 시뮬레이션한다. 1. M개의 자리를 활성시키는 모든 경우를 시뮬레이션하여 최소 시간을 구한다. 바이러스를 놓을 수 있는 위치가 최대 10군데이고, M이 최대 10이므로 최악의 경우에도 10C5가지 경우 밖에 발생하지 않는다. 또한 각 경우를 시뮬레이션하는 데는 O(N^2)의 시간 복잡도가 들기 때문에 브루트 포스를 사용해도 충분하다. 2. 각 경우는 BFS를 이용해서 시뮬레이션한다. 바이러스가 퍼지는 시뮬레이션은 BFS를 사용하면 쉽게 구현할 수 있다. #include #include #include using namespace std; typedef pair pii; const int EMP.. 2022. 8. 19. 이전 1 2 3 4 5 6 7 8 ··· 42 다음 반응형
