2JINISHAPPY 2JINISHAPPY

www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net valid parentheses string(vps)를 활용하면서, 스택을 활용하는 전형적인 문제 여는괄호가 나오면 그대로 push하고, 닫는 괄호가 나올 때 pop한 뒤 다시 연산해서 스택에 push한다 정확히는, 위의 그림처럼 1. 여는 괄호가 나오면 기호를 구분해서 push( '('는 0, '['는 1)한다. 2. 닫는 괄호가 나오면 해당 괄호와 일치하는 여는 괄호가 나올 때 까지(중간 과정에 숫자가 있..

www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 미로 만들기 문제 2차원 배열에서의 최단거리 문제이다. 벽부수고 이동하기와 미로만들기처럼 벽(cost가 높은 좌표)를 최소화해서 목적지에 도착하기 위해서는, 가중치 그래프의 최단거리를 이용해야 한다 따라서 2차원 배열에 다익스트라 알고리즘을 적용하면 문제를 해결할 수 있다 문제에서는 흰색(지나갈 수 있는 곳)을 1, 검은색을 0으로 해줬는데 입력받은 뒤 이를 완전히 뒤집고 다익스트라 알고리즘을 통해 (N,N)으로 갈 ..

www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 1. 문제 정의 N줄에 걸쳐 3개의 숫자 중 최대 점수를 얻을 수 있는 숫자를 선택한다. 단, 이전에 선택했던 열과 인접한 열에 있는 숫자만 선택 가능하다. 2. Recursion&Subproblem K-1번째 줄에서 1번을 선택했다면 K번째 줄에서 1, 2번 중 큰 숫자를 선택한다 K-1번째 줄에서 2번을 선택했다면 K번째 줄에서 1,2,3번 중 큰 숫자를 선택한다 K-1번째 줄에서 3번을 선택했다면 K번째 줄에서 2,3번..

www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 1. 문제 정의 좌표 평면 내의 1로 이루어진 가장 큰 정사각형의 넓이를 출력한다 이 때, 넓이를 구하기 위해 가장 큰 정사각형의 한 변의 길이를 구한다 위와 같은 그림에서 최대 정사각형의 한 변의 길이는 2이므로, 답은 4이다 2. Subproblem&Recursion 특정 좌표를 오른쪽아래 꼭지점으로 정사각형의 길이를 구한다고 할 때, 이 좌표의 북, 서, 북서쪽 좌표는 반드시 1이어야 한다. 그리고 좌표가 아래와 같을 경우, 0111001 -> 0111001 0111001 -..

www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 이차원 배열을 이용하는 DP문제 욕심쟁ㅇㅣ 판다🐼 1. 문제 정의 이차원 배열에서 특정 칸에서 연결된 상하좌우의 칸이 인접하다고 할 때, 인접한 칸이 현재 칸보다 숫자가 큰 최대 연결 회수 구하기 2. Recursion & Subproblem 4 14 9 12 10 1 11 5 4 7 15 2 13 6 3 16 8 위의 예시에서, 5의 최대 연결 수는 5-11-15로 3번이다. 이 때, 2의 최대 연결..

www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 바이토닉 부분수열은 가장 긴 증가+감소 수열을 섞은 문제이다 맨 앞부터 가장 긴 증가 수열을 구하고, 맨 뒤부터 가장 긴 증가 수열을 구하면 i번째 원소에 대해 (현재 원소를 포함하는 가장 긴 증가 수열의 길이, 현재 원소를 포함하는(맨 뒤부터) 가장 긴 감소 수열의 길이)를 구할 수 있다 for문을 두번 돌아준 뒤 해당 값들의 합이 가장 큰 쌍을 찾아주면 되는 문제 #include int n,dp[3][1001],ans; int..

www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 컴퓨터를 연결하는 네트워크(가중치 무방향 그래프)가 주어졌을 때, 해당 네트워크의 MST를 구하는 문제이다 MST는 프림 알고리즘으로 구할 수 잇다 #include #include #include #include #define INF 987654321 using namespace std; priority_queue pq; vector edge; int v, e, cost[10005], pre[10005], ans; bool visit[10005]; void prim(int u) { visit[u] =..

www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 유니온 파인드(Disjoint Set)을 활용해서 정점간의 연결을 확인하는 문제이당 도시의 연결 정보가 주어질 때 마다 Union 연산을 한 뒤, 여행 계획에 속한 정점들이 같은 Parent에 속해있는지 확인하면 된다 #include #include using namespace std; struct disjointSet { vector parent, rank; disjointSet(int n) { rank.re..