본문 바로가기

Algorithm

 (72)
[1일 1알고] G4 1806 부분합 https://www.acmicpc.net/problem/1806 이번 문제는 투 포인터를 사용하는 문제입니다. 부분합을 보고 처음에는 1부터 시작해 부분합 범위를 점점 늘려가며 답을 찾아보려했습니다.하지만 이 방법은 O(N^2)인데, 조건이 N이 최대 10만이고 시간 제한이 0.5초이기 때문에 이 방법은 불가했습니다. 따라서 O(N)방법인 투 포인터를 사용했습니다. #include #include #include #include #include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, S; cin >> N >> S; vector v(N, 0); ..
[1일 1알고] G4 2294 동전 1 유명한 dynamic programming문제인 동전 문제입니다.이전의 동전2문제와 다르게 https://basaeng.tistory.com/125 [1일 1알고] G5 2294 동전 2https://www.acmicpc.net/problem/2294 가장 기본적인 DP문제입니다.예전에는 아이디어가 전혀 떠오르지 않았는데 이제는 생각나는게 신기하네요 n가지 동전을 통해 k원을 만드는 문제입니다.배낭문제와basaeng.tistory.com이번 문제는 특정 숫자 K를 위한 최소 동전의 개수가 아닌 K를 만들 수 있는 경우의 수를 계산합니다. 여기서 중요한 것은 경우의 수는 순서를 고려하지 않는 것입니다. 예를 들어 3을 만들 때 1+2와 2+1은 같은 경우의 수입니다.int main(){ ios::sy..
[1일 1알고] G4 11054 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 이 문제는 LIS문제에서 조금만 더 생각해보면 쉽게 해결할 수 있습니다. https://basaeng.tistory.com/118 [1일 1알고] G5 2565 전깃줄https://www.acmicpc.net/problem/2565 꼬여있는 전깃줄을 풀어야 하는 문제입니다.먼저 입력이 뒤죽박죽 주어지기 때문에 문제를 쉽게 풀기 위해서 A 전봇대의 높이에 따라 정렬해보았습니다. 그러고 보basaeng.tistory.com위의 문제는 LIS문제였습니다.바이토닉 부분 수열이란 어떤 수 Sk를 기준으로 S1 2 k-1 k > Sk+1 > ... SN-1 > SN을 만족 하는 수입니다. 결론적으로 Sk를 기준으로 좌측에서는 증가 부분 수열, 우측..
[1일 1알고] G5 5175 문제없는 문제 https://www.acmicpc.net/problem/5175 해당 문제는 간단한 dfs, 백트래킹 문제입니다.N,M이 20이하로 굉장히 작은 범위이며, 정답을 찾기 위해서는 모든 조합을 탐색해야하기 때문에 조합을 탐색하는 방법을 그대로 사용하면 됩니다. 조합으로 표현하면 (N)C(1~N)을 모두 경우의 수로 하여 이 중 M을 충족하는 지 확인해야합니다. 일반적으로 생각해보면 bool vector혹은 array를 통해 모든 알고리즘을 사용하는지 확인하며 백트래킹 할 수 있겠지만위에서 말한 것 처럼 N과 M의 범위가 매우 작기 때문에 bool vector 대신 비트마스킹을 사용해볼 수 있습니다. 예를 들어 알고리즘 1과 2를 사용한다면 11, 1과 3을 사용한다면 101과 같이 저장하면 됩니다.최대 ..
[1일 1알고] G4 9207 페그 솔리테어 https://www.acmicpc.net/problem/9207 문제와 조건을 이해하면 간단하게 해결할 수 있는 문제입니다. 다만 저는 문제 이해에 시간이 오래걸렸네요" 현재 게임판에 꽂혀있는 핀의 상태가 주어진다. 이때, 핀을 적절히 움직여서 게임판에 남아있는 핀의 개수를 최소로 하려고 한다. 또, 그렇게 남기기 위해 필요한 최소 이동횟수를 구하는 프로그램을 작성하시오." 이 말에서 핀을 적절히 움직이라는 것이 전체 보드 내에서 핀을 자유롭게 배치하라는 말인 줄 알았는데, 초기 핀은 고정이고 말그대로 "적절히" 움직이라는 것이었습니다 ㅎㅎ... 보드의 크기가 세로 r = 5, 가로 c = 9로 고정이기 때문에 dfs, 백트래킹을 통해 조건에 맞게 탐색하면 답은 간단히 나옵니다.#include #inc..
[1일 1알고] G5 16494 가장 큰 값 https://www.acmicpc.net/problem/16494 dp혹은 브루트포스를 사용해 풀 수 있는 문제입니다. 개인적으로는 dp를 생각하고 풀어 G5가 왜이렇게 어렵지 라고 생각했는데dfs를 활용해 간단하게 해결도 가능한 문제였네요.문제는 N개로 이루어진 수열을 M개의 그룹으로 나누었을 때 속한 수의 최댓값을 구하는 것입니다. 연속된 수가 최댓값이 되게 해야하는데 예를 들어 10, -4, 5이 있을 때 그룹이 1개라면 최댓값은 3개를 한번에 묶은 11, 그룹이 2개라면 10, 5를 각각 그룹으로 한 15가 됩니다. 이러한 상황을 고려하기 위해서는, 현재 수를 고르지 않는 경우, 현재 수가 이전값과 이어져 한 그룹인 경우, 현재 수가 새로운 그룹의 시작점인 경우, 이렇게 나눌 수 있습니다.혹은 ..
[1일 1알고] S3 3100 국기 인식 https://www.acmicpc.net/problem/3100 6*9크기의 배열을 삼등분된 국기로 만드는 문제입니다. 가로 세로를 나눠서 계산해야하나, 그런데 중간은 달라야하니 어떻게 계산해야하나 여러 고민을 했었는데 실제로는 배열의 크기가 6*9이고 가능한 색(알파벳)의 종류가 등분에 따라 중복을 포함해도 26*26*26이기 때문에 얼마 되지 않스빈다. 결론적으로 브루트 포스로 푸는 것이 가장 간단한 풀이였네요 #include #include #include #include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); vector v(6); for (int i = 0..
[1일 1알고] G5 2294 동전 2 https://www.acmicpc.net/problem/2294 가장 기본적인 DP문제입니다.예전에는 아이디어가 전혀 떠오르지 않았는데 이제는 생각나는게 신기하네요 n가지 동전을 통해 k원을 만드는 문제입니다.배낭문제와 비슷하지만 해당 동전 문제는 같은 동전을 중복해서 사용할 수 있다는 차이점이 있습니다. 평범한 배낭 문제에서는 중복을 피하기 위해 뒤에서 앞으로 탐색했지만 동전 문제는 중복이 가능하기 때문에 앞에서 뒤로 탐색하는 것이 더 간편한 방법입니다.#include #include #include #include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, ..

티스토리툴바