포도밭 개발자

https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 처음 풀이할 땐 S에서 T의 길이까지 만들 수 있는 모든 문자열의 경우를 구해보았습니다. 나름 Set을 사용해서 중복체크도 했지만.. 메모리 초과 새로운 풀이에서는 반대로 접근하여 T에서 S를 만들 수 있는지 체크하였습니다. 문제에 주어진 S -> T 연산을 거꾸로 적용합니다. - 문자열의 뒤에 A를 추가한다 : 문자열 뒤에 A를 제거한다. - 문자열을 뒤집고..

https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 수의 갯수와 범위가 크기 때문에 Prefix Sum 방식을 통해 풀이하였습니다. - S[i] : A[1] ~ A[i] 까지의 합의 나머지 - MODS[K] : 나머지가 K인 S[i]의 갯수 i> n >> m; int temp,mod; mods[0]=1; for(int i=1;i> temp; s[i] = s[i-1]+temp; // s[i] : a[1..

https://www.acmicpc.net/problem/12970 12970번: AB 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. www.acmicpc.net 백트랙킹으로 접근했을 때, 메모리/시간 모두 간신히 통과했던 문제입니다. 새로운 방식의 풀이에 - A의 갯수 + B의 갯수 = 전체 문자열의 길이 N - 만들어야 하는 쌍의 갯수 K의 범위 : 0 ~ (A의 갯수)x(B의 갯수) 위 두 가지 성질을 이용해 그리디 기법으로 접근하여 적은 메모리와 빠른 시간에 문제를 해결할 수 있었습니다. C++ 소스 코드 #include #include using namespace std; in..

https://programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 크루스칼 알고리즘을 이용하여 풀이하였습니다. 이론으로 공부했던 알고리즘을 실제로 적용해보며 재밌게 푼 문제였습니다 :) C++ 소스 코드 #include #include #include #include using namespace std; const int dx[] = {0,0,-1,1} ,..

퀵 정렬은 분할정복 기법으로 pivot값을 이용해 정렬하는 알고리즘입니다. 한 번 수행할 때 마다 크기가 반씩 줄어들며, pivot 값을 기준으로 왼쪽은 pivot 보다 작은 수, 오른쪽은 pivot보다 큰 수들이 모이게 됩니다. 퀵 정렬은 평균적으로 O(NlogN)의 시간복잡도로 수행되지만 최악의 경우 O(N^2)의 시간복잡도를 가집니다. C++ 소스 코드 #include using namespace std; int nums[] = {3,6,1,2,9,7,4,4,10,8}; void quickSort(int s,int e){ if (s>=e) return; int p = s; int i = s+1; int j = e; while(i j){ // 인덱스가 엇갈렸으면 작은 수, pivot swap int ..

삽입정렬은 현재원소를 앞의 원소들과 비교해가며, 적절한 위치에 삽입하는 정렬기법입니다. for문과 while 문을 중첩하기에 O(N^2)의 시간복잡도를 가집니다. C++ 소스 코드 #include using namespace std; int main(){ int nums[] = {3,6,1,2,9,7,4,5,10,8}; for(int i=0;i=0 && nums[j]>nums[j+1]){ int temp = nums[j]; nums[j] = nums[j+1]; nums[j+1] = temp; j--; } } for(int i=0;i nums[j+1] { let temp = nums[j] nums[j] = nums[j+1] nums[j+1] = temp j-=1 } } for num in nums { pr..

https://www.acmicpc.net/problem/2008 2008번: 사다리 게임 사다리 게임을 할 때 사용되는 사다리가 있다. 세로선은 N개가 있고, 가로선은 M개가 있다. 세로선은 맨 왼쪽 것부터 1, 2, …, N의 번호가, 가로선은 맨 위의 것부터 1, 2, …, M으로 번호가 붙어 있�� www.acmicpc.net C++ 소스 코드 #include #include using namespace std; int a[501]; //a[i] = 위에서 i 번째 높이에 있는 가로선 int d[501][501]; // d[i][j] = i번째 가로선까지 고려했을때, start에서 j까지 가는 최소비용 int main() { ios_base::sync_with_stdio(0); cin.tie(0)..

선택정렬은 원소의 갯수만큼 루프를 수행하면서, 제일 작은 수를 선택하여 해당 루프의 맨 앞으로 보내는 정렬기법입니다. for 루프를 두 번 중첩하기에 O(N^2)의 시간복잡도를 가집니다. C++ 소스 코드 #include using namespace std; int main(){ int nums[] = {3,6,1,2,9,7,4,5,10,8}; for(int i=0;i