포도밭 개발자

병합정렬은 어떤 경우에도 O(NlogN)의 시간복잡도를 보장합니다. 현재 정렬 순서에 상관없이 분할정복 기법에 의해 일단 반으로 나누고 합치는 과정을 통해 정렬을 수행합니다. 중간 정렬 결과를 담을 임시 변수가 필요하기에 O(N)의 공간복잡도를 가집니다. C++ 소스 코드 #include using namespace std; int temp[10], nums[10] = {3,6,1,2,9,7,4,5,10,8}; void merge(int s, int m, int e){ int i=s; int j= m+1; int k=s; while(i

https://www.acmicpc.net/problem/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사 www.acmicpc.net 배열의 값을 입력받으며 a[i][j] 에 a[0][0] ~ a[i][j]까지의 누적합을 저장하였습니다. 밝기의 평균을 구해야하는 구간을 입력받으며 해당 구간의 합을 칸 수로 나누어 답을 구했습니다. C++ 소스 코드 #include using namespace std; int a[1002][1002]; int main(){ int r,c,q,temp..

https://programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr DP로 해결했습니다. 첫번째 스티커를 떼는 경우(마지막 스티커를 뗄 수 없음)와 두번째 스티커를 떼는 경우(마지막 스티커를 뗄 수 있음)를 나눠 계산한 후, 그 중 최대 값이 답이 됩니다. C++ 소스 코드 #include #include using namespace std; int d[100001][2]; int solution(vector s..

행/열에 대한 합을 저장하는 (col, row) 배열과. 증가대각선,감소대각선에 대한 합을 저장하는 변수(Adddiagonal/Minusdiagonal)를 미리 선언했습니다. - 2중 for문을 통해 수를 입력받으면서 해당 행/열의 합, 대각선의 합에 값을 더해줍니다. - 입력이 끝난 후 배열과 변수에 저장된 값 중 가장 큰 값이 답이 됩니다. C++ 소스 코드 #include #include using namespace std; int col[100],row[100],Adddiagonal,Minusdiagonal; int main(){ int t,num; for(int tc = 1;tc> t; for(int i=0;i num; col[j]+=num; row[i]+=num; if (i==j) { Addd..

입력받은 2차원 배열 전체를 돌면서, 모든 (i,j) 쌍에서 가능한 회문의 최대 길이를 구하면 그 중 최대값이 답이 됩니다. C++ 소스 코드 #include #include #define MAX 100 using namespace std; string map[MAX]; int check(int x, int y){ for(int k=MAX;k>=2;k--){ int width = k,height = k; for(int t = 0;t 1) return height; } return 1; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tc; for(int test_case = 1; test_case> tc; int ans =..

https://www.acmicpc.net/problem/5427 5427번: 불 문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. www.acmicpc.net Queue를 두개 사용한 BFS로 구현하였습니다. C++ 소스 코드 #include #include using namespace std; char b[1002][1002]; queue fire; queue pos; int n, h, w, si, sj, ex, ey; int visit[1002][1002]; const int dx[]= {0,0,-1,1}, dy[] = {-1,1,0,0}; void bfs(){..

https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr BFS로 풀이하였습니다. C++ 소스 코드 #include #include using namespace std; const int dx[] = {0,0,-1,1}, dy[]={-1,1,0,0}; int dist[101][101]; int solution(vector maps){ dist[0][0]= 1; in..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료�� www.acmicpc.net priority_queue와 queue를 사용해서 풀이하였습니다. C++ 소스 코드 #include #include using namespace std; int main(){ int prior[101]; queue q; priority_queue pq; int tc; cin >> tc; while(tc--){ while (!q.empty()) q.pop(); while (!pq.empty()) p..