PS(Problem Solving)

문제 링크 https://www.acmicpc.net/problem/7576 문제 정보 입력 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 토마토가 하나 이상 있는 경우만 입력으로 주어진다. 출력 여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만..

문제 링크 https://www.acmicpc.net/problem/2178 문제 정보 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. 출력 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다. 풀이 이 문제는 BFS의 응용 문제로 다차원 배열에서의 거리 측정 문제다! 소스 코드 #include using namespace std; #define X first #define Y second string board[102]; int dist[102][102]; // 거리를 저장할 배열 int n, m; int dx[4] = { 1, ..

문제 링크 https://www.acmicpc.net/problem/1926 문제 정보 입력 첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다) 출력 첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다. 풀이 이중 for문을 통해 시작좌표를 구하는 방법을 알고있으면 BFS 알고리즘으로 해결할 수 있다. 소스 코드 #include using namespace std; #defin..

문제 링크 https://www.acmicpc.net/problem/2504 문제 정보 입력 첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다. 출력 첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다. 풀이 스택을 이용해서 풀이할 수 있다. 굉장히 많은 고민을 해봐도 해결하기 힘들었다. 여는 괄호 중 소괄호가 나오면 2를 num에 곱하고 스택에 push 하고, 대괄호는 3을 num에 곱하고 스택에 push 한다. 그리고 닫는 괄호 중 소괄호가 나왔을 때 괄호 쌍이 올바르다면 곱해준 num 값을 sum에 더한다. 그러면 소괄호 쌍 1개를 계산한 것이므로 스택에서 pop해서 제거해준 후 소괄호..

문제 링크 https://www.acmicpc.net/problem/10799 문제 정보 입력 한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다. 출력 잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다. 풀이 생각이 어려웠고 구현은 쉬웠던 문제였다. 여는 괄호는 스택에 push 해주고 닫는 괄호일 때 바로 앞에 괄호가 여는 괄호인지, 닫는 괄호인지를 통해 레이저와 쇠 막대기의 끝을 구별하면 된다. 소스 코드 #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); string str; cin >> str; stack S; int ans..

문제 링크 https://www.acmicpc.net/problem/9012 문제 정보 입력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 출력 출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 풀이 스택을 활용해서 수식의 괄호 쌍을 해결하는 알고리즘을 이용하면 된다! 소스 코드 #include using namespace std; int main(void) { ios::sy..

문제 링크 https://www.acmicpc.net/problem/3986 문제 정보 입력 첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다. 출력 첫째 줄에 좋은 단어의 수를 출력한다. 풀이 스택을 활용하여 해결 할 수 있는 문제다. 스택이 비어있을 경우에 스택을 추가하고 스택의 top과 문자를 비교해서 같으면 pop하고 다르면 push 하는 것을 통해 스택이 비어있으면 좋은 단어이고, 스택이 비어있지 않으면 좋은 단어가 아니다. 소스 코드 #include using namespace std; int main(void)..

문제 링크 https://www.acmicpc.net/problem/4949 문제 정보 입력 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다. 출력 각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다. 풀이 스택을 활용하여 수식의 괄호 쌍 문제를 해결 할 수 있다. 수식의 괄호 쌍 알고리즘은 블로그 내 글을 통해 확인할 수 있다. - 스택의 활용(수식의 괄호 검사) 소스 코드 #include using namespace std; int main(void) { ios::sync_wi..