[백준]

https://www.acmicpc.net/problem/18870 #문제 간단 정리 #문제 해결 방법인덱스 추적을 위해서 pair 로 받고원소들을 정렬 후에순서를 추적하기 위해 rank 변수 선언 후에정렬된 값이 이전 값과 같다면 rank를 증가하지 않고다르다면 rank를 증가한다 그리고 추적한 인덱스에 rank 값을 넣어주면 된다. #전체 코드#include #include #include #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector> inputs(n); for (int..

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net #문제 간단 정리 다익스트라 문제 이전에 풀었던 알고스팟 https://dfdfg42.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EC%8A%A4%ED%8C%9F-1261%EB%B2%88 백준 1261번 알고스팟 [C++] https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net #문제 간단 정리 다익스트라를 활용하자 #문제 해결 방법 벽을 부수는건 1 코스트가 들기 때문에 벽을 부수는 걸 우선으로 하는 우선순위 큐를 활용해서 bfs 를 사용 (다익스트라) 해서 문제를 풀면 된다 #전체 코드 #include #include #include #include using namespace std; const int INF = numeric_limits::m..

https://www.acmicpc.net/problem/1584 1584번: 게임 첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 www.acmicpc.net #문제 간단 정리 0-1 bfs 문제 #문제 해결 방법 기존의 bfs 에서 비용이 들지 않는 것을 먼저 우선순위를 두어 계산해주는 0-1 bfs 를 활용하자 덱을 사용해서 생명소모없이 지나갈 수 있는 안전지대를 덱의 앞으로 푸쉬하고 생명소모하는 위험지대를 덱의 뒤로 푸쉬해서 우선순위에 차이를 둬서 탐색하도록 하면 된다 또한 주의해야될게 각 모서리 두 부분이 주어지는데 모서리에..

https://www.acmicpc.net/problem/6126 6126번: Cow Cash The cows have not only created their own government but they have chosen to create their own money system. In their own rebellious way, they are curious about values of coinage. Traditionally, coins come in values like 1, 5, 10, 20 or 25, 50, and 100 units www.acmicpc.net #문제 간단 정리 일종의 배낭문제 #문제 해결 방법 dp[i] = 금액을 만들 수 있는 가지수 즉 dp[i] = dp[i-coin..

https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net #문제 간단 정리 흔한 괄호문제의 응용 스택을 활용한다. #문제 해결 방법 스택을 활용해 괄호일 경우 스택에 넣어주고 같은 괄호일경우에 pop 비어있는 경우나 괄호가 닫는괄호가 아닐경우 오답으로 간주, 수많은 스택 활용 괄호 문제중에 하나이다. getline 으로 한줄 전체를 읽어오는 것을 활용하자 그리고 가독성좀 생각해야겠다.. #전체 코드 #include #include ..

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net #문제 간단 정리 세그먼트 트리를 활용하자 #문제 해결 방법 기본적으로 a b 구간에서 최솟값과 최댓값을 구한다면 ab 전체를 훑도록 구현할 수 있는데 이는 시간 초과가 나는게 자명하다. 때문에 세그먼트 트리를 활용해서 빠르게 구해주도록 하자 우선 세그먼트 트리에 대한 지식이 있다고 가정하고 설명하자면 최솟값을 저장하는 트리와 최댓값을 저장하는 트리를 만들어서..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net #문제 간단 정리 이분 탐색을 사용하는 문제 #문제 해결 방법 이분탐색으로 입력된 길이중 가장 긴 랜선을 max 로 잡고 탐색할때마다 mid 를 각 랜선들을 잘랐을때 자른 개수가 N개 이상이 되면 mid 를 점점 올리면서 이분 탐색을 해서 최대 길이로 자를 수 있는 값을 구한다. #전체 코드 C++ 풀이 #include #include #include using nam..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net #문제 간단 정리 명백히 이분탐색으로 푸는 문제 #문제 해결 방법 #전체 코드 #include #include #include #include #include using namespace std; int binarySearch(vector &vec, int target) { int start = 0; int end = vec.size()-1; whi..

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net #문제 간단 정리 일단 배낭문제이다. 기존의 가방문제는 최소 무게를써서 최대 가치를 찾고 최대 가치를 가진 마지막 dp 배열이 정답이였다면 이 문제는 최소 비용으로 최대메모리를 찾고 그중에서 그 메모리이상의 첫번쨰 dp 배열을 찾는다는게 차이점 #문제 해결 방법 DP 배열을 dp[i][j]로 정의하고, 이를 "처음부터 i번째 앱까지 고려했을 때, 비활성화의 총 비용이 j일 때 확보할 수 있는 메모리의 최..