Algorithm/PS (61) 썸네일형 리스트형 [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, .. [1일 1알고] G4 2110 공유기 설치 https://www.acmicpc.net/problem/2110 N개의 집이 있고 공유기 C개를 설치해야합니다.집의 좌표가 최대 10억이고, 집의 개수가 20만 이하이기 때문에 브루트 포스 식 탐색을 하는 문제는 아닐 것입니다. 한 집에는 하나의 공유기만 설치 가능하며, 가장 인접한 공유기의 설치거리가 최대가 되는 방법이 답이 됩니다. 문제는 특정 간격 d만큼이 답이라고 가정했을 때 공유기 C개를 설치할 수 있는가? 의 물음을 이진 탐색을 통해 찾아갑니다.만약 d로 가정했을 때 C개를 모두 설치할 수 있었따면 d의 값을 늘려보고, 설치할 수 없었다면 d의 값을 줄여봅니다. 중요한 점은 이진 탐색을 할 때 기준이 이 "간격"이라는 것입니다. left = 최소 간격 = 1이 되고, (집의 위치가 모두 다르.. [1일 1알고] G5 16500 문자열 판별 https://www.acmicpc.net/problem/16500 간단한 dp문제입니다. 여느 dp문제가 그렇듯이 풀이 아이디어가 떠오르는 지에 따라 해결 시간이 많이 차이가 나는 느낌입니다. 이번 문제는 문자열 S를 단어목록 A를 통해 공백없이 붙여서 만들 수 있는지 여부를 확인하는 문제입니다. 예를 들어 S = "ABCD"이고, 주어진 A = {"A", "AB", "BCD", "ABCE"} 라면 A와 BCD를 조합해서 S를 만들 수 있고 답은 1이 됩니다. 또한 조건을 보면 S의 길이는 100이하이며, A의 문자열 개수도 100이하이고, A에 포함되는 개별 문자열의 길이도 100을 넘지 않기 때문에 시간 제한 자체는 넉넉해 보입니다.일단 완성을 해야하고, 공백없이 붙여서 만들어야하기 때문에 앞부터.. 이전 1 ··· 3 4 5 6 7 8 다음
