알고리즘

(C++) 백준 4179번 - 불!

문제 링크 : https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 풀이 BFS를 응용한 문제로, 불에 대한 BFS와 지훈이에 대한 BFS를 동시에 사용하는 방법으로 풀이하면 된다. 골드 4 문제답게 조건들을 설정하는 것이 매우 복잡했다. #include #include #include #define X first #define Y second using namespace std; int dx[4] = {1,0,-1,0}; int d..

(C++) 백준 7576번 - 토마토

문제 링크 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 BFS를 이용한 거리 문제와 비슷하게 풀이하면 된다. 거리를 토마토가 익는 데 걸리는 시간의 길이라고 생각하고 풀면 어렵지 않게 해결할 수 있다. 문제 해결 시 중요한 점은 시작점이 될 수 있는 후보들, 즉 익은 토마토들의 위치를 먼저 파악 후에 이들을 Queue에 넣고 시작해야 한다는 점이다. #include #include #include #define X ..

(C++) 백준 2178번 - 미로 탐색

문제 링크 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 BFS를 사용하여 풀이하였다. 다른 BFS 문제를 풀어보았다면 실버 1 문제라기엔 크게 어렵지 않은 문제이다. 오히려 공백없이 들어오는 숫자들을 어떻게 한 자리씩 입력받아 저장할지를 더 많이 고민하였다. #include #include #include #define X first #define Y second using namespace std; int dx[4] = {1,0,-1,0}; int dy[4] =..

(C++) 백준 1926번 - 그림

문제 링크 : https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 BFS를 사용하여 풀이하면 되는 문제이다. 그림의 시작점을 찾기 위해 전체적으로 이중 for문으로 스캔하면서 아직 방문하지 않은 시작점을 찾는다. 그 후 BFS를 사용하여 인접 칸들을 순회하면서 그림의 크기를 알아내었다. #include #include #include #define X first #define Y second using namespace std; int dx[4] ..

(C++) 우선순위 큐(Priority Queue)

우선순위 큐란? 우선순위를 가지는 데이터들을 저장하는 큐(Queue)를 말한다. 데이터를 꺼낼 때 우선순위가 높은 데이터가 가장 먼저 나온다는 특징이 있어 운영체제의 작업 스케줄링, 정렬, 네트워크 관리 등의 다양한 기술에 적용되고 있다. 우리가 흔히 말하는 큐(Queue)와의 차이는 일반적인 큐는 아래 그림과 같이 선형적인 구조를 가지는 반면 우선순위 큐는 트리 구조로 생각할 수 있다. 우선순위 큐의 동작 원리 일반적으로 우선순위 큐는 최대 힙(Max Heap)을 이용해 구현한다. 그래서 우선순위 큐의 동작 원리를 알아보기 전에 먼저 최대 힙에 대해 알아보자. 최대 힙은 부모 노드가 자식 노드 보다 값이 큰 완전 이진트리를 의미한다. 그렇기에 루트 노드는 전체 트리에서 가장 큰 값을 가진다. 이제 우선..

(C++) 백준 2504번 - 괄호의 값

문제 링크 : https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net 풀이 스택을 이용하여 풀이를 진행하면 된다. 올바른 입력인지 확인하는 것은 이전에도 풀어보았기 때문에 어렵지 않으나, 값들을 곱해주는 것이 무척 어려웠다. 더하는 것은 단순히 이전에 나온 것이 짝이 맞는 괄호인지만 확인하면 돼서 어렵지 않았는데, 곱해주는 것은 고민해 봐도 도저히 생각이 나지 않아서 다른 사람의 풀이를 참고하였다. 열린 괄호가 입력되었을 때 곱해주는 아이디어가 ..

(C++) 백준 1021번 - 회전하는 큐

문제 링크 : https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 풀이 덱의 push와 pop을 사용하여 회전하는 큐를 어렵지 않게 구현할 수 있다. 다만 왼쪽으로 가는 것과 오른쪽으로 가는 것을 선택하는 알고리즘을 짜는 것에 고민을 많이 했는데, 단순하게 순회하며 어디가 더 가까운지 세는 것으로도 해결이 된다. #include #include using namespace std; deque D; int main() { ios::sync_wit..

(C++) 백준 4949번 - 균형잡힌 세상

문제 링크 : https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 풀이 닫는 괄호들이 나왔을 때 짝이 맞는 괄호가 stack의 Top에 위치해 있다면 이는 균형 잡힌 문장이라고 볼 수 있다는 점이 이 문제 풀이의 핵심 요소이다. 처음에 제출했을 때 실패가 나와서 왜 그런지 생각해 봤더니 "( ) ( ) ["와 같이 열린 괄호가 더 많은 경우여서 애초에 균형이 맞지 않은 것들을 예외 처리하지 못한 것이 원인이었다. 따라서 마지막..

(C++) 백준 10866번 - 덱

문제 링크 : https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 Deque의 다양한 메서드들을 사용하는 문제이다. 실버 4 문제치곤 전혀 어렵지 않은 문제이다. 하지만 예외 처리해줘야 할게 꽤 있고, 반복적인 코드들이 많아 실수하기는 쉬운 것 같다. #include #include using namespace std; deque D; int main() { ios::sync_with_stdio(0); cin.tie(0); i..

(C++) 백준 10845번 - 큐

문제 링크 : https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 이전에 Python을 사용해서 풀어보았던 문제이기에 어려움 없이 풀 수 있었다. STL Queue를 사용하여 풀어서 실버 4문제치곤 정말 쉬운 문제라고 할 수 있다. #include #include using namespace std; queue Q; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >..