알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net BFS를 이용한 문제였습니다. Cnt[X][Y] 배열을 통해, (1,1) 에서 시작해서 (X,Y)까지 왔을때, 벽을 부순 최소 횟수를 저장했습니다. 탐색을 하기전에, Cnt[X][Y] 배열에는 큰 값을 저장하여, 최솟값을 저장할 수 있도록 합니다. (X,Y)를 오는 경우는 4가지가 있는데, 1. (X,Y)가 벽이 아니며, 이전에 오지 않았을 경우 2. (X,..

문제 링크입니다. https://www.acmicpc.net/problem/14923 14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net BFS문제 였습니다. 일반 BFS문제와는 다르게 벽을 부숴야함으로, check배열을 3차원으로 만들어 벽을 부셨는지의 여부를 확인해주면 되는 문제였습니다. 벽을 부셨는지의 여부를 확인해야하는게 포인트 였습니다. check[X][Y][Z] 배열을 선언해, Z부분에서 벽을 부셨는지의 여부를 확인했습니다. 이 부분을 제외하면 다른 BFS 문제와 같은 방법으로 풀면 되..

문제 링크입니다. https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net pair를 사용해, 우선순위 큐를 사용하면 되는 문제였습니다. abs(x)는 x의 절댓값을 나타냅니다. pair의 first에는 절댓값을, second에는 x를 저장해, 오름차순으로 정렬합니다. 나머지는 조건에 따라서 출력해줍니다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #in..

문제 링크입니다. https://www.acmicpc.net/problem/14867 14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a Y로 Y -> X로 가는 2가지 경우가..

문제 링크입니다. https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 재귀를 이용하는 문제였습니다. N의 값에 따라서 탐색해야할 수가 달라집니다. N이 8일 경우 -> (8 * 8) 1번 확인, (4 * 4) 4번 확인, (2 * 2) 16번 확인, (1 * 1) 64번 확인 이와 같이 N/2가 될때마다, 확인해야할 사각형의 수가 4배가 증가합니다. 따라서 재귀 함수에서 N값과 Cnt를 통해서 탐색 범위를 늘려줘야합니다...

문제 링크입니다. https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 우선순위 큐를 사용하는 문제입니다. 우선순위 큐를 사용해 조건에 맞게 출력하면 되는 문제였습니다. 이 문제는 내림차순으로 정렬이 되서 출력이 되기에 오름차순 정렬과는 다르게 선언을 해줘야합니다. int N; priority_queue qu; int main() { cin.tie(0); cout.tie(0); cin >> N; for (int i = 0; i <..

문제 링크입니다. https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 우선순위 큐를 사용하면 쉽게 풀 수 있는 문제였습니다. 우선순위 큐를 선언하여 문제 조건에 맟게 출력만 해주면 되는 문제입니다. 오름차순으로 정렬을 해야하기에, 내림차순과는 다르게 선언을 해줘야합니다. int N; priority_queue qu; int main() { cin.tie(0); cout.tie(0); cin >> N; for (int i = 0;..

문제 링크입니다. https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 좌표 압축 문제였습니다. unique를 통해 중복을 없앤뒤, lower_bound를 이용해 답을 출력한다. 저는 해당 방법으로 풀었습니다. vector에서 unique를 통하면 중복되는 값을 없앨 수 있습니다. 이때는 연속으로 중복되는 값을 지워주는 것이기에 정렬을 해준 뒤에 사용해줘야 합니다. sort(X.begin(), X.e..

문제 링크입니다. https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 브루트포스 알고리즘 문제였습니다. (0 ~ 256) 높이 사이에서 고르게 만들 수 있는지를 확인하는 문제였습니다. 블록을 쌓던가, 없애던가 총 2가지 방법이 있습니다. 따라서 먼저 해당 높이를 만들 수 있는지를 확인해야합니다. B + 제거한 블록의 수 >= 쌓아야하는 블록의 수 -> 해당 조건이 맞을때만 시간 계산을 해야합니다. 해당 조건을 만족한다면 시간을 계산 해야합니다. ..

문제 링크입니다. https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net Queue를 이용한 문제였습니다. Queue에 중요도를 정하고 M번째 수가 언제 나오는지를 물어보는 문제였습니다. Queue의 특징이 FIFO(First in first out)인 만큼 이를 활용하면 풀 수 있는 문제였습니다. 출력 예시 중, 예시 2번과 예시 3번을 활용해 정답을 도출해내는 과정을 확인해겠습니다. 저는 (순서, 중요도)를 저장하는 queue와 중요도를 저장하는 ve..

문제 링크입니다. https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net Stack을 사용한 문제입니다. 괄호가 정확히 사용되었는지를 물어보는 문제였습니다. Stack을 사용했습니다. '(' or '[' 과 같이 여는 괄호는 stack에 저장한 뒤, ')' or ']'와 같이 닫는 괄호가 입력되면 stack의 top을 확인해 쌍이 맞는지를 확인합니다. 쌍이 전부 맞았으며, stack에 남아있는 수가 없을 경우 yes를 출력하고 그 이외의..

문제 링크입니다. https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 브루트포스 알고리즘 문제였습니다. "666"을 포함하여 영화번호를 정하는 문제였습니다. 1번 -> 666, 2번 -> 1666, 3번 -> 2666, 4번 -> 3666, 5번 ->5666, 6번 -> 6660.... 666이 포함되어 있지만, 숫자가 계속 증가하고 있음은 알수 있습니다. 따라서 숫자를 계속 증가하면서, 666이 발견되면 순서를 하나 증가합니다. 이때 순서가 N..