공부/알고리즘30 [0626] 알고리즘 12015. 가장 긴 증가하는 부분 수열 2 저번에 풀었던 문제와 똑같지만 조건이 틀리다. 저번건 수열 크기(N)의 조건이 1 ≤ N ≤ 1,000 이었는데, 이번 문제는 1 ≤ N ≤ 1,000,000 이다. 따라서 저번에 쓴 O(N^2) 방식을 사용하면 시간 초과가 난다. 보니 이분 탐색을 사용하라는 것 같아서 오랜만에 또 자료구조 책을 뒤졌다. 대충의 느낌은 오는데 구체적으로 어떻게 해야할지 잘 모르겠어서 머리를 굴려보다 최종적으로는 서치를 해서 풀었다... #include #include #include int binarySearch(int left, int right, int item); int num[1000001]; int lis[1000001]; int main() { std::cin.ti.. 2021. 6. 27. [0625] 알고리즘 2565. 전깃줄 가뜩이나 문제를 늘 늦은 시간에 푸는데 오늘은 정말 늦게 잡아서... 어제 문제의 연장선 문제인 전깃줄 문제를 풀었다. 어제와 똑같은 다이내믹 프로그래밍 + LIS 문제로 코드 자체는 어제와 똑같은데, 먼저 배열을 pair로 입력받고 first 기준으로 정렬한다. 그리고 second를 기준으로 LIS의 길이를 구해 전체 전깃줄 개수에서 뺀다. #include #include #include int main() { std::cin.tie(NULL); std::ios_base::sync_with_stdio(false); int n, num1, num2; std::cin >> n; std::vector pair; std::vector memory(n, 1); for (int i = 0; i .. 2021. 6. 26. [0624] 알고리즘 동아리 알고리즘 스터디는 사실상 끝나긴 했는데... 그래도 하루 한 문제씩 풀다보니 나름 뭔갈 하고 있다는 기분이 들어서 할 수 있는대로 이어가보려고 한다. 어차피 알고리즘 공부는 해야했고... 11053. 가장 긴 증가하는 부분 수열 다이내믹 프로그래밍 문제. 고민을 좀 오래했는데 코드 자체는 무척 간결하게 나왔다. #include #include #include int main() { std::cin.tie(NULL); std::ios_base::sync_with_stdio(false); int n; std::cin >> n; std::vector num(n); std::vector memory(n, 1); for (int i = 0; i > num[i]; } .. 2021. 6. 25. [0622] 알고리즘 1149. RGB거리 다이내믹 프로그래밍 문제. 반복문을 사용하여 풀었다. 각 집까지의 경로의 최소값을 구하는데, row값이 같으면 같은 색을 칠하는 것이 되기 때문에 색이 다른 두 값을 비교해 더 작은 값을 골라 최소값을 구하는 방식. #include #include int main() { std::cin.tie(NULL); std::ios_base::sync_with_stdio(false); int n, min; std::cin >> n; int rgb[1001][3]; int memory[1001][3] = { 0 }; for (int i = 0; i > rgb[i][0] >> rgb[i][1] >> rgb[i][2]; } for (int .. 2021. 6. 23. [0621] 알고리즘 1932. 정수 삼각형 다이내믹 프로그래밍 문제. 원래는 재귀를 이용하여 해결하려 했지만 생각해보니 굳이 재귀 안 써도 반복문으로 풀 수 있겠다 싶어서 노선을 바꾸었다. #include #include #include #include int triangle[501][501]; int memory[501][501]; int main() { std::cin.tie(NULL); std::ios_base::sync_with_stdio(false); int n, max = 0; std::cin >> n; for (int i = 0; i triangle[i][j]; } } memory[0][0] = triangle[0][0]; for (int i = 1; i.. 2021. 6. 22. [0620] 알고리즘 1541. 잃어버린 괄호 또다시 그리디 알고리즘 문제, 인데 딱히 그리디 알고리즘이라는 자각을 가지고 푼 건 아닌 것 같다. C++을 잡은 이래로 파싱을 다루는 건 아마 처음이라 좀 애먹었고... 애초에 생각했던 파싱 방법은 사용하지도 않았음(너무 복잡했었다.) #include #include #include int main() { std::cin.tie(NULL); std::string f; std::cin >> f; int sum = 0, num = 0; bool cal = false; //cal => 앞에 마이너스가 등장했는가? for (int i = 0; i < f.length(); i++) { if (f[i] == '+') { if (cal) { sum -= num; num = 0; } else.. 2021. 6. 21. 이전 1 2 3 4 5 다음