📌 문제 제목문제 링크: BOJ 4179🗒️ 문제 설명미로에 지훈이와 불이 난 위치, 벽이 존재할 때, 지훈이를 탈출시켜야 한다.지훈이와 불은 매 분 상하좌우로 이동한다.지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.시간 제한: 1초메모리 제한: 256MB1 💡 문제 해결 아이디어이차원 for 문을 돌며 지훈이와 불이 있는 위치를 알아야 함.지훈이와 불의 위치를 각 큐를 만들어 넣고 dist 배열도 각자 만들어서 0으로 초기화 시킨다.불 BFS를 먼저 수행한다.지훈이 BFS를 수행하며 불이 오기 전에 갈 수 있으면 이동한다.그래프를 빠져나갈 수 있으면 jihun_dist[xp][yp] + 1을 출력한다.아니라면 IMPOSSIBLE을 출력한다.⌛️ 시간 복잡도O(RC)✅ 최종 코드impor..

📌 문제 제목문제 링크: BOJ 7576🗒️ 문제 설명토마토를 격자 모양의 상자에 보관한다.익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶다.시간 제한: 1초메모리 제한: 256MB2 💡 문제 해결 아이디어이차원 for 문을 돌며 초기에 익은 토마토들의 위치를 큐에 저장한다.큐가 빌 때 까지 BFS를 수행한다.이차원 for문을 돌며 dist의 최대값을 구한다.이차원 for문을 돌 때 dist가 -1이면서 익지 않은 토마토가 있으면 -1을 출력한다.⌛️ 시간 복잡도O(NM)✅ 최종 코드import sysfrom collections import dequeinput = sys.stdin.re..

📌 문제 제목문제 링크: BOJ 2178🗒️ 문제 설명NxM 크기의 배열로 표현되는 미로가 있다.미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.(1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램.시간 제한: 1초메모리 제한: 192MB2 💡 문제 해결 아이디어NM이 10,000 이기 때문에 O(NM)의 시간복잡도를 가지는 알고리즘 사용.BFS를 사용해서 각 칸과 시작점 사이의 거리를 구할 수 있다.⌛️ 시간 복잡도O(NM)✅ 최종 코드import sysfrom collections import dequeinput = sys.stdin.readlineN, M = map(int, input().split())graph..

📌 문제 제목문제 링크: BOJ 1926🗒️ 문제 설명어떤 도화지에 그림이 그려져 있을 때, 그 그림의 개수와 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라.단, 그림이라는 것은 1로 연결된 것을 그림이라고 정의한다.시간 제한: 2초메모리 제한: 128MB세로 크기: 1 가로 크기: 1 💡 문제 해결 아이디어NM이 250,000 이므로 O(NM)의 시간복잡도를 가진 알고리즘을 사용하면 해결 가능.이차원 배열을 순회하며 그림의 시작점을 찾고 BFS로 그림의 개수와 넓이를 구한다.그림의 개수는 이차원 배열을 돌며 BFS를 수행할 때마다 count를 증가시킨다.그림의 넓이는 BFS의 리턴값을 해당 그림의 넓이로 하고, BFS가 끝나면 해당 그림의 넓이와 이전에 저장해둔 그림의 최대 넓이를 비교한다..

📌 문제 제목문제 링크: BOJ 2504🗒️ 문제 설명소괄호와 대괄호만을 이용해 만들어진 괄호열이 있다.입력이 올바르지 못한 괄호열이면 0을 출력하고, 올바른 출력이면 아래의 내용을 참고하여 출력하라.'()'인 괄호열의 값은 2이다.'[]'인 괄호열의 값은 3이다.'(X)'인 괄호열의 값은 2 x 값(X)으로 계산된다.'[X]'인 괄호열의 값은 3 x 값(X)으로 계산된다.올바른 괄호열 x와 y가 결합된 xy의 괄호값은 값(xy) = 값(x) + 값(y)으로 계산된다.e.g. ( ( ) [ [ ] ] ) ( [ ] )의 괄호값은 28이다.2 * (2 + (3 * 3)) + 2 * 3 = 22 + 6 = 28 시간 제한: 1초메모리 제한: 128MB1 💡 문제 해결 아이디어여는 괄호는 스택에 추가닫는..

📌 문제 제목문제 링크: BOJ 10799🗒️ 문제 설명쇠막대기는 여는 괄호와 닫는 괄호로 표현된다.레이저는 여는 괄호와 닫는 괄호의 인접한 쌍으로 표현된다.괄호 문자열이 주어졌을 때 잘려진 쇠막대기는 총 몇 개인지 구하는 프로그램.시간 제한: 1초메모리 제한: 256MB💡 문제 해결 아이디어여는 괄호 = 스택에 추가닫는 괄호레이저: 스택의 마지막 원소가 여는 괄호일 경우 레이저임.스택에 남아있던 여는 괄호들의 개수만큼 쇠막대기가 만들어짐.스택에 남아있던 여는 괄호들의 갯수를 answer에 추가 (추가: +=)스택에 남아있던 여는 괄호들의 갯수를 tmp에 추가 (추가: +=)스택을 비움쇠막대기: 스택의 마지막 원소가 여는 괄호가 아니면 쇠막대기임.answer이 1씩 증가⌛️ 시간 복잡도O(N)✅ 최..

📌 문제 제목문제 링크: BOJ 9012🗒️ 문제 설명VPS: 괄호의 모양이 바르게 구성된 문자열괄호 문자열이 주어질 때, VPS인지 판별하는 프로그램시간 제한: 1초메모리 제한: 128MB💡 문제 해결 아이디어ps를 순회하며 여는 괄호는 스택에 추가닫는 괄호는 스택의 마지막 원소가 여는 괄호일 경우 pop순회가 끝나고 스택에 원소가 남아있으면 False, 아니면 True⌛️ 시간 복잡도O(L_1 + L_2 + ... + L_N) = O(T). T는 모든 입력 문자열의 총 길이✅ 최종 코드import sysinput = sys.stdin.readlineN = int(input().strip())def isVPS(ps: str) -> bool: stk = [] for b in ps: ..

📌 문제 제목문제 링크: BOJ 3986🗒️ 문제 설명좋은 단어: 단어 위로 아치형 곡선을 긋는다. 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을 수 있다면, 좋은 단어이다.좋은 단어 개수를 세는 프로그램시간 제한: 1초메모리 제한: 256MB1 2 💡 문제 해결 아이디어 단어 위로 아치형 곡선을 그었을 때, 각 선끼리 교차하지 않아야 "좋은 단어" 이다.e.g. ABAB 처럼 각 알파벳끼리 선으로 이었을 때, 선이 교차하므로 이 단어는 "좋은 단어"가 아니다.문자열을 순회하며 스택의 마지막 원소가 현재 확인중인 문자와 같으면 아치형 곡선을 그었을 때 다른 선들이 침범할 수 없으므로 pop스택의 마지막 원소가 현재 확인 중인 문자와 다르면 스택에 추가⌛️..

📌 문제 제목문제 링크: BOJ 4949🗒️ 문제 설명어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램괄호는 소괄호와 대괄호로 되어있고, 문자열이 균형을 이루는 조건은 아래와 같다.모든 왼쪽 소괄호는 오른쪽 소괄호와만 짝을 이루어야 한다.모든 왼쪽 대괄호는 오른쪽 대괄호와만 짝을 이루어야 한다.모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.문자열이 주어졌을 때 균형을 이루고 있으면 "yes", 아니면 "no"를 출력온점 하나 (".")만 입력되면 입력이 종료된다.시간 제한:..

스택의 대표적인 활용 사례수식의 괄호 쌍전위/중위/후외 표기법DFSFlood Fill수식의 괄호 쌍이란?주어진 괄호 문자열이 올바른지 판단하는 문제.여는 괄호의 갯수와 닫는 괄호의 갯수가 같아야 함. (단, 괄호의 종류가 2개 이상일 경우에는 여는 괄호와 닫는 괄호의 갯수만으로 판별 불가)문자열을 순회하며 닫는 괄호가 나오면 직전의 여는 괄호와 매칭되는지 확인e.g. 아래의 괄호 문자열이 올바른지 확인하고, 그 이유에 대해 설명하시오.( ( ) ) ( ) ( ) - O. 여는 괄호와 닫는 괄호가 대칭됨.) ) ( ( ) - X. 닫는 괄호와 대칭되는 여는 괄호가 없음.( ) ( ) ) ( ( ) - X. 닫는 괄호와 대칭되는 여는 괄호가 없음.📕 문제 1. ( { ) }순회를 하며 닫는 괄호가 나오면 ..