포도밭 개발자

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net BFS로 풀이하였습니다. visit[x][y][0]은 벽을 하나도 부수지 않고 (x,y)에 도달했을 때의 최단거리, visit[x][y][1]은 벽을 하나 부순 상태에서 (x,y)에 도달했을 때의 최단거리입니다. a[x][y]일 때 이미 벽을 지난 상태 & a[nx][ny] 가 벽일때 : 이동 불가 (wall 과 a[nx][ny]의 합이 2인 경우) a[x][y]일 때..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 3차원 BFS로 풀이했습니다. C++ 소스 코드 #include #include #define MAX 101 using namespace std; const int dx[]={0,0,-1,1,0,0}; const int dy[]={-1,1,0,0,0,0}; const int dz[]={0,0,0,0,1,-1}; int a[MAX][MAX][MAX]; struct pos { ..

https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 � www.acmicpc.net 다이나믹 프로그래밍을 이용해 풀이하였습니다. 현재 칸 i에서 갈 수 있는 칸 j까지 최소 점프 횟수를 갱신해줍니다. C++ 소스 코드 #include #include #define MAX 1002 using namespace std; int n; int a[MAX],d[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout..

https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr BFS를 이용해 풀이하였습니다. 현재 거리에 있는 노드들의 수를 업데이트 해주면서 마지막으로 업데이트 된 노드의 수가 반환됩니다. C++ 소스 코드 #include #include #include #define MAX 20001 using namespace std; bool visited[MAX]; int solution(int n, vector edge) { int answer = 0; vector adj[MAX]; for(int..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 �� www.acmicpc.net 경로를 압축한 유니온 파인드 알고리즘을 이용해 풀이하였습니다. C++ 소스 코드 #include #define MAX 1000001 using namespace std; int parent[MAX]; int find(int x){ if (x == parent[x]){ return x; } else { int y = find(parent[x]); parent[x..

병합정렬은 어떤 경우에도 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..