📍문제 링크 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 📍알고리즘 분류 - 자료구조 - 문자열 - 스택 📍문제 풀이 전체 문자열에서 특정 문자열(폭탄)을 제거하는데, 제거한 후에 폭탄이 남아있으면 없어질 때까지 계속 제거해야 한다 - replace 함수를 반복하면 간단히 해결될 것 같지만.. 시간초과가 발생한다 - 문자열 입력값의 길이가 100만이기 때문에, 전체 문자열을 반복해서 탐색하는 O(N^2) 복잡도로는 해결이 불가..

📍문제 링크 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 📍알고리즘 분류 - 구현 - 그래프 이론 - 그래프 탐색 - 너비 우선 탐색 - 시뮬레이션 - 깊이 우선 탐색 📍문제 풀이 1과 0으로 이루어진 n * m 보드가 주어진다. - 두 면이 0과 접한 1은 1턴 이후에 0으로 변하는데, 모든 1이 0으로 변하는데 몇 턴이 걸리는지 구하라 📍1트 : 완전탐색 -> 내부 공간 고려 못해 실패 1. 전체 보드 total 구하기 - ..

📍문제 링크 https://www.acmicpc.net/problem/17073 17073번: 나무 위의 빗물 첫째 줄에 트리의 노드의 수 N과 1번 노드에 고인 물의 양을 의미하는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 109) 다음 N-1줄에 걸쳐, 트리에 존재하는 간선의 정보가 U V의 형태로 주어진다 www.acmicpc.net 📍알고리즘 분류 - 수학 - 그래프 이론 - 그래프 탐색 - 트리 📍문제 풀이 간선 정보를 바탕으로 트리를 만들고, 루트에 물을 흘려보낸다 한 턴에 발생하는 동작은 아래와 같다 - 부모 노드가 1 이상의 물을 갖고 있다면 랜덤한 자식 노드에 1의 물을 흘려보냄 - 자식 노드는 물을 받고 저장 더 이상 물이 움직이지 않는 상태에 도달하면 (즉, ..

📍문제 링크 https://www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 📍알고리즘 분류 - 그리디 - 정렬 📍문제 풀이 수열이 주어진다. 인접한 수 끼리의 차가 최소가 되도록 배열을 섞을 수 있을 때, 그 차를 구하라 예를 들어 정렬된 수열 10, 10, 11, 11, 12, 12, 13 이 주어질 때, - 인덱스를 0 1 2 3 4 5 6 이라고 할 수 있다 오름차순으로 양 끝단부터 배치하게 되면 아래처럼 배치할 수 있다 (정렬된 배열이므로 크기가 정..

📍문제 링크 https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 📍알고리즘 분류 - 구현 - 시뮬레이션 📍문제 풀이 최종 후보 풀의 크기 N과 자연수로 이루어진 수열 data을 입력받는다 - data를 순회하며 후보 N의 크기 이내에서 추천수가 높은 순으로 최종 후보를 가린다 문제를 풀며 우선순위 큐로 해결할 수 있겠다 생각이 들었다. 그 이유는... - 힙 구조를 사용하면 배열보다 시간 복잡도가 빠름 (단 메모리를 더 많이 쓸 수 있음)..

📍문제 링크 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 📍알고리즘 분류 - 그래프 이론 - 그래프 탐색 - 너비 우선 탐색 📍문제 풀이 문제를 이해하기 조금 힘들었따.. 출발점, 도착점, 휴식지점 좌표가 주어진다 한 번에 갈 수 있는 거리는 1000 (맨해튼 거리 기준) 출발점에서 도착점까지 휴식지점을 거치든 안거치든 갈 수 있는지 묻는 문제이다 BFS를 쓰든 DFS를 쓰든 해결할 수 있지만, 경로를 구하는 문제가 아니므로 BFS를 ..

📍문제 링크 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 📍알고리즘 분류 - DP 📍문제 풀이 정수가 N개 주어질 때, 연속하는 정수들로 구성된 최댓값을 구하라 DP를 써서 O(N)에 해결할 수 있다 📍의사 코드 주어진 배열을 순회하며, memo 배열에는 arr[i] 까지의 연속합을 저장한다 (단, 더했을때 오히려 마이너스가 되면, 다음에 나오는 수로 업데이트) 예를 들면, 10 -4 3 1 5 6 -35 12 21 -1 배열에서 10 10 -4 10..

📍문제 링크 https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 📍알고리즘 분류 - 그래프 이론 - 브루트포스 - 그래프 탐색 - 깊이 우선 탐색 📍문제 풀이 숫자가 담긴 5 x 5 이차원 배열이 주어진다. 2차원 배열에서 6개의 원소를 연결하여 만들 수 있는 수열의 가짓수를 출력한다 - 왔던 길을 되돌아갈 수 있다 ☑️재귀 DFS를 사용 - 매개변수로 수열을 사용하여 길이가 6이 되기 전까지는 이차원 배..