포도밭 개발자

https://www.acmicpc.net/problem/2422 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 문제 한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 www.acmicpc.net N의 범위가 작고 3가지를 선택하면 되기에 3중 for문을 이용해서 풀이했습니다. 아이스크림 (i, j, k) 가 섞어먹으면 안되는 조합을 포함하지 않는다면 선택 가능한 경우입니다. C++ 소스 코드 #include using namespace std; bool ck[201][201]; int main(){ int n,m,ans=0; scanf("%d %d", &n, &m..

https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 한 정점에서 다른 정점으로 중복 방문이 가능하기에, 인접 정점으로 DFS를 수행하면서 깊이가 6이 될 때의 값을 Set에 저장합니다. Set은 중복된 값을 허용하지 않기에 Set의 사이즈가 답이 됩니다. C++ 소스 코드 #include #include #include using namespace std; set st; int a[5][5]; const ..

https://www.acmicpc.net/problem/3568 3568번: iSharp 문제 선영이는 C, C++, Java와는 다른 아주 세련된 언어를 만들었다. 선영이는 이 아름답고 예술적인 언어의 이름을 i#으로 정했다. i#은 기본 변수형과 배열([]), 참조(&), 포인터(*)를 제공한다. 배열 www.acmicpc.net C++ 소스 코드 #include #include #include using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); string s; getline(cin, s); vector a; string now = ""; for(int i=0;i 0) { a.push_back..

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 ..