전체 글 (59) 썸네일형 리스트형 백준 2230) 수 고르기 골드 5 투 포인터 풀이: 가장 중요한 부분은 투 포인터 알고리즘을 활용하여 해결 하는 것입니다. n이 100,000까지니까 시간 복잡도 O(n 제곱)은 당연히 안될꺼라는 것을 아실겁니다. 투 포인터로 빠르고 간단하게 순회하기 위해서 vector에 값을 입력받고 오름차순 정렬 시켜주면 됩니다. 그리고 투 포인터의 while 조건이 중요합니다 -> while(i 당연히 i와 j는 n을 넘어가면 OutOfBounds 뜰 것 입니다. i가 j보다 커지는 것은 마이너스로 가기 때문에 m은 0 이상 값만 들어오니 i가 j를 넘어서는 상황은 고려하지 않습니다 #include #include #include using namespace std;int main() { long long n,m; cin >> n >> m;.. 백준 1038) 감소하는 수 골드 5 - 백트래킹 풀이: 이 문제는 백트래킹을 사용하면 된다고 한다 하지만 이 문제를 읽고 구상을 해보면 뭔가 BFS의 느낌으로 구현하여야 하는데 백트래킹은 DFS의 원리와 비슷하여 어떻게 백트래킹을 사용할 것 인가가 중요한 것 같다. 아래는 간단한 예시이다 보면 0 1 2 4 5 6 7 8 9인 1의 자리를 먼저 탐색하고 -> 10 20 21 ... 그 다음 자릿수로 넘어가야한다 0 1 2 3 4 5 6 7 8 9 0 0 0 0 ... 1 1 1 2 2 3 이 문제를 푸는 핵심 방법은 현재 자릿수에서 가장 큰 감소하는 수를 찾았다면 자릿수를 하나 더.. 백준 3745 ) 오름세 골드 2 LIS(n log n) 풀이: 오름세 문제를 읽어보면 LIS(최장 증가 부분 수열)를 찾는 것이다. 아래가 정의이다 이걸 사람 눈으로만 찾는다고 치자 (1 4 5 3 9 3 8 10) 가 예시라면 늦어도 30초 안에는 찾을 수 있을 것이다하나의 수열을 찾았다면 길이가 최장 수열이 하나가 아닐수도 있으니 하나 더 찾아보도록 바란다;;; 일단 n이 10만까지 들어올 수 있으니 사람 눈으로는 절대 못찾는다LIS는 보통 2가지로 방법으로 찾을 수 있다 실버수준의 O(n * n)의 시간 복잡도와 골드 수준의 O(n log n)가 있다 실버수준이라면 n이 10만인 경우를 하나만 입력받아도 10만 * 10만은 100만은 아니고 100억정도 연산하는거다 당연히 안된다 그래서 골드 수준의 방식을 쓰면 10만 * 로그 10만이라 아래 와 같.. 백준 2610 ) 회의 준비 골드 2 C++ #include #include #include using namespace std; int main() { int n, m; ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; vector> dp(n+1, vector(n+1, 100000000)); for (int i = 1; i > x >> y; dp[x][y] = 1; dp[y][x] = 1; } for(int k = 1; k > we(n+1); for (int i = 1; i .. 백준 2458) 키순서 골드 4 C++ 풀이: 플로이드 알고리즘을 x -> y로 가는 커지는 bigDp와 y - x로 가는 smallDp 두개를 만들어서 하나는 큰 방향을 따라가고 하나는 작은 방향을 따라간다 왜냐하면 i 보다 큰 j 의 갯수는 bigDp[i][j...]의 방문한 경우이고 i보다 작은 j의 갯수는 smallDp[i][j...]을 방문한 경우이다 GLOBMAX가 아니라면 방문한 것이기 때문에 최단경로에 휘둘릴 필요 없이 그냥 방문을 했냐 안했냐 이것이 중요하다 i보다 큰 j의 갯수 + i보다 작은 j의 갯수 = n - 1 이 되어야 한다 -1은 자신을 제외한 것이다. 위의 조건이 성립한다면 순서를 i의 키 순서를 알 수 있는 것이 된다. #include #include #define GLOBMAX 100000000using .. 백준 회의준비) 골드 2 2610 플로이드 워셜 풀이: 그룹화, 최대값중의 최소값 #include #include #include using namespace std;int main() { int n, m; ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; vector> dp(n+1, vector(n+1, 100000000)); for (int i = 1; i > x >> y; dp[x][y] = 1; dp[y][x] = 1; } for(int k = 1; k > we(n+1); for (int i = 1; i v; vector visited(n+1, false); for(in.. 백준 2660 플로이드 워셜 ) 골드5 - 회장뽑기 일단 문제를 무지성으로 빠르게 풀려고 최적화나 코드 가독성을 챙기지 못하였습니다. 풀이: x와 y 친구관계를 입력받을때 짝사랑하는 친구가 아니니까 양방향 그래프로 dp[x][y], dp[y][x]를 1로 초기화합니다그 다음 플로이드 워셜 알고리즘을 활용하여 친구들의 수를 세어줍니다 그리고 i 번호의 j번째 친구들 중에 가장 큰 값을 i번호의 친구수로 지정합니당 그럼 score라는 벡터변수에 { 친구수 : 번호 } 이렇게 들어갑니다 그걸 오름차순 정렬을 해주고 제일 작은 친구들의 수를 가진 번호를 찾아 출력하면 간단하게 풀 수 있습니당! 아래는 코드입니다#include #include #include #include using namespace std;int main() { int n; c.. 플로이드 워셜) 백준 11404 C++ 플로이드 워셜 알고리즘은 시간 복잡도와 공간 복잡도가 높지만 간단한 구현력과 음의 가중치를 포함할 수 있어서 좋다원리는 은근 쉽다 a -> b 로 가는길 보다 a -> c -> b 의 경로가 더 짧다면 그 경로를 선택하는 것이다 #include #include #include using namespace std;int main() { vector> floyd(200, vector(200, INT_MAX)); int n, m; ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; for(int i = 0; i > x >> y >> z; floyd[x][y] = min(.. 이전 1 2 3 4 5 ··· 8 다음
