개발세발은 안되요

문제https://www.acmicpc.net/problem/2469 풀이? 줄을 기준으로 위에서 아래로 사다리를 타고 내려왔을 때 결과 배열(=up 배열)과 ?줄을 기준으로 아래에서 위로 사다리를 타고 올라갔을 때의 결과 배열(=down 배열)을 구한 후, 두 배열을 비교하여 up 배열을 down 배열과 같게 만들 수 있는지를 확인한다. 구체적인 구현 방식은 아래의 코드 주석을 참고하면 될 것 같다. 코드#include using namespace std;int k,n;string str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";string result;int flag = 0;int main(){ cin >> k >> n >> result; string s[n] = {};..

문제https://www.acmicpc.net/problem/1874 풀이 n개의 숫자를 입력 받으면서 동시에 stack에 push 하거나 pop 해가며 현재 입력된 수를 stack을 통해 꺼낼 수 있는지를 보인다.현재 입력된 숫자보다 stack의 top() 값이 작다면 입력된 숫자까지 push 해주고, 마지막에 pop을 한 번 해준다.현재 입력된 숫자와 stack의 top()이 같다면, 바로 pop() 해준다. 이때 주어진 수열을 만들 수 있는지 없는지를 확인하는 방법은 여러가지가 있을 수 있겠는데, 나의 경우 2가지 정도가 떠올랐다.모든 수열을 입력받은 후 stack의 top()이 0이 아닌 경우현재 입력받은 수가 stack()의 top()보다 작은 경우2번째 방법이 더 좋긴 하지만 첫번째 방법으로..

문제https://www.acmicpc.net/problem/1261 풀이 방법0-1 BFS를 이용하여 풀 수 있는 문제였다.벽을 부수지 않고 이동할 수 있는 경우 dq.push_front() 를 이용해 deque의 앞에 다음 위치 삽입벽을 부숴야 이동할 수 있는 경우 dq.push_back()을 이용해 deque의 뒤에 다음 위치 삽입 이를 통해 벽을 부수지 않는 방법에 대한 우선순위를 고려할 수 있다. 최대한 벽을 부수지 않고 이동해야 부숴야 하는 벽의 최소 개수를 구할 수 있기 때문에, 벽을 부수지 않고 이동하는 것을 우선적으로 고려해야 한다. 즉 벽을 부수지 않고 이동하는 경우를 dq에서 먼저 빼야 한다. 이때 방문 표시를 해가며 이미 방문한 위치는 다시 방문하지 않도록 한다. 코드#inc..

BFSBFS는 거리(또는 시간 등)이 짧은 것부터 차례로 계산함.BFS로 어떤 지점에 '처음 도달'했을 때가 항상 최단 시간(=거리) 이다.예를 들어, n이라는 위치에서 출발해서 1초 뒤에 갈 수 있는 곳, 2초 뒤에 갈 수 있는 곳~ 이런 식으로 넓혀가는 것임. 0-1 BFS 일반적인 BFS와는 다르게 경로에 따라 가중치가 달라지는 경우에 해당한다. 즉 이동할 때 비용이 0이거나 1밖에 없는 경우에 사용하는 특수한 BFS이다. 이 경우 일반적인 BFS로는 풀기 어려울 수 있다.일반 BFS는 큐에 넣는 순서대로 탐색함.즉 비용에 따른 우선순위를 고려하지 못함. 따라서 일반적으로 BFS에서는 queue를 이용해 구현하지만, 0-1 BFS는 deque를 이용하여 덱의 앞(front)와 뒤(back)에 각..

문제https://www.acmicpc.net/problem/17829   풀이문제의 요구사항을 그대로 구현하여 풀었다.  코드#include #include using namespace std;int n;int arr[1024][1024];int copy_arr[1024][1024];int max_num(int n1, int n2, int n3, int n4){ int num[4] = {n1,n2,n3,n4}; sort(num,num+4); return num[2];}void solution(int N){ // N이 1이 된 경우 종료 if(N==1){ return; } // copy 배열 초기화 for(int i=0; i> n; ..

문제https://www.acmicpc.net/problem/2075  풀이N을 입력받는다.N*N을 우선순위 큐에 넣으며 입력받는다. 이때 큐의 크기는 N으로 제한한다.큐의 마지막 원소를 출력한다.   주의해야 할 점은 큐에 원소를 N*N 개만큼 넣으면 메모리 초과가 발생한다는 점이다. 따라서 큐 안에 들어갈 수 있는 원소의 개수를 제한해주어야 한다.   코드#include #include using namespace std;priority_queue q;int n;int main(){ ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for(int i=0; i> num; ..

문제https://www.acmicpc.net/problem/1966  풀이문서의 중요도와 문서의 순서를 queue에 넣는다. 동시에 priority_queue에 문서의 중요도만 넣어준다.priority_queue의 top() 값과 queue의 front()값을 비교하여 현재 인쇄하려는 문서보다 중요도가 높은 문서가 있는지를 확인한다.만약 문서를 인쇄할 수 있는 경우, priority_queue를 pop() 한다.만약 문서를 인쇄할 수 없는 경우, queue의 front() 값을 다시 queue에 push 해준다. 코드#include #include #include using namespace std;struct Num{ int value, index;};int main(){ int t, n ..

문제https://www.acmicpc.net/problem/19598  풀이1. 시작 시간-종료 시간을 pair 로 우선순위 큐에 저장한다. 이때 시작시간을 기준으로 오름차순으로 정렬되도록 설정한다.2. while을 통해 큐에 넣은 각각의 수업마다 이전 수업 중 이어붙일 수 있는 수업이 있는지를 조사한다. 이때, 이어붙일 수 있는 경우는 아래의 조건을 통해 구할 수 있다.이전 수업 종료 시간   3. 만약 이어붙일 수 있는 수업이 없는 경우, 강의실을 추가로 할당한다. (= 이어붙이지 않고 원소를 새로 삽입한다.)   코드#include #include using namespace std;priority_queue, vector>, greater>> pq;vector> v;int n;int main()..