하루에 하나씩

www.acmicpc.net/problem/5639

처음 풀이

/*
    재귀를 이용해서 leftNode에는 subtree의 왼쪽 node들을 저장
    rightNode에는 subtree의 오른쪽 노드들을 저장
    인자로 vector를 전달하기 때문에 메모리 초과 발생
*/
void recursive(vector<int> vec) {
  if(vec.size() == 0) return ;
  int root = vec[0];
  vector<int> leftNode, rightNode;
  for(int idx = 1; idx < vec.size(); idx++) {
    if(vec[idx] < root) leftNode.push_back(vec[idx]);
    else rightNode.push_back(vec[idx]);
  }
  recursive(leftNode);
  recursive(rightNode);
  cout << root << endl;
}

정답 코드

vector를 넘기는 대신 왼쪽과 오른쪽 인덱스를 넘겨 구한다.

#include <iostream>
#include <vector>
using namespace std;
vector<int> vec;
void input() {
  int N;
  while(cin >> N) vec.push_back(N);
}

void recursive(int left, int right) {
  int root = vec[left];
  int idx = left + 1;
  for( ; idx <= right; idx++) 
    if(vec[idx] >= root) break;
  if(left < idx - 1) recursive(left + 1, idx - 1);
  if(idx <= right) recursive(idx, right);
  cout << root << endl;
}

int main(void) {
  input();
  recursive(0, vec.size() - 1);
  return 0;
}

배열의 양 끝을 left와 right로 잡은 후 root보다 값이 큰 인덱스를 idx변수로 잡아준다.

left + 1에서부터 idx - 1까지가 root의 왼쪽 subtree가 된다.

idx에서부터 right는 root의 오른쪽 subtree가 된다.

위와 같이 진행이 된다.

jaimemin.tistory.com/1095 를 참고하여 해결하였습니다.

처음에는 가장 긴 증가하는 부분 수열 1, 2, 3에서 해결한 방법과 똑같이 접근을 했고 lower_bound로 만든 배열의 값을 출력해서 제출했었습니다.

그 결과 '틀렸습니다'를 받았고 반례가 생각나지 않아 위 블로그를 참고해서 해결하였습니다.

vector<int> lis 는 어떤 값을 저장하는가?

가장 긴 증가하는 부분 수열 1, 2, 3과 마찬가지로 가장 길게 증가하는 크기를 구하기 위해 사용하는 배열

vector<pair<int, int>> answer는 어떤 값을 저장하는가?

answer[i]은 {0 ~ i번째 중 몇 번째로 증가하는 수열인가, 입력받은 값인 input[i]}를 저장

answer배열을 왜 써야 하는가?

단순히 크기를 구하는 문제를 해결할 때에는 answer배열을 사용하지 않고 lis배열의 크기만 출력해주면 된다.

그렇지만 이 문제는 가장 길게 증가하는 배열의 크기와 그때의 원소들을 모두 출력해줘야 하는데 그냥 lis값을 출력했을 때의 반례는 다음과 같다.

8

1 5 3 4 2 6 7 8
올바른 정답은 1 3 4 6 7 8이지만 lis값은 1 2 4 6 7 8값이 나오게 된다.

따라서 몇 번째로 증가하는지에 대한 정보를 이용해서 input배열의 끝(i 가 N - 1일 때)에서부터 수열을 찾아준다. 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define MAX 1000001
using namespace std;
vector<int> input(MAX), lis;
vector<pair<int, int>> answer(MAX);

int main(void) {
    int N;
    cin >> N;
    for(int i = 0; i < N; i++) cin >> input[i];

    lis.push_back(input[0]);
    answer[0] = {1, input[0]};

    for(int i = 1; i < N; i++) {
        vector<int>::iterator idx2 = lower_bound(lis.begin(), lis.end(), input[i]);
        if(idx2 == lis.end()) { //lis에 있는 값 중에 가장 큰 값이라면
            lis.push_back(input[i]);
            answer[i] = {lis.size(), input[i]};
        } else {
            lis[idx2 - lis.begin()] = input[i];
            answer[i] = {idx2 - lis.begin() + 1, input[i]};
        }
    }

    stack<int> s;
    int idx = lis.size();
    cout << lis.size() << endl;
    for(int i = N - 1; i >= 0; i--) {
        if(answer[i].first == idx) {
            s.push(answer[i].second);
            idx--;
        }
    }

    while(!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }

    return 0;
}

www.acmicpc.net/problem/14002

www.acmicpc.net/problem/14003

가장 길게 증가하는 수열의 길이만 구하면 되는 문제였기 때문에 lower_bound를 이용해서 문제를 해결하였습니다.

가장 긴 증가하는 부분 수열(1, 2, 3) 모두 범위만 다를 뿐 같은 결과를 구하는 문제였기 때문에 아래 코드로 모두 통과하였습니다.

lower_bound의 시간 복잡도가 log이기 때문에 전체 시간 복잡도는 O(NlogN)만에 해결할 수 있었습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
    int N, answer = 987654321, num;
    cin >> N;
    vector<int> vec;
    for (int i = 0; i < N; i++)
    {
        cin >> num;
        vector<int>::iterator iter;
        iter = lower_bound(vec.begin(), vec.end(), num);
        if (vec.size() == 0) vec.push_back(num);
        else if (iter == vec.end()) vec.push_back(num);
        else vec[iter - vec.begin()] = num;
    }
    cout << vec.size() << endl;
    return 0;
}

www.acmicpc.net/problem/11053

www.acmicpc.net/problem/12015

www.acmicpc.net/problem/12738

https://www.acmicpc.net/problem/11000

백준 1931(회의실 배정)문제와 비슷한 문제라고 생각해서 회의가 끝나는 시간을 기준으로 잡고 정렬(오름차순)을 해서 접근을 했다.

1차 시도. (결과: 시간초과)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N;
vector<pair<pair<int, int>, bool>> vec;

void input(){
    cin >> N;
    int start, finish;
    for(int i = 0; i < N; i++){
        cin >> start >> finish;
        vec.push_back({{start, finish}, false});
    }
}

bool compare(pair<pair<int, int>, bool> a, pair<pair<int, int>, bool> b){
    if(a.first.second < b.first.second) return true;
    else if(a.first.second == b.first.second){
        if(a.first.first < b.first.first) return true;
        return false;
    }
    return false;
}

int main(void){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    input();
    sort(vec.begin(), vec.end(), compare);
    int result = 0;
    while(N) {
        int finish = 0;
        result++;
        for(int i = 0; i < vec.size(); i++){
            if(!vec[i].second && vec[i].first.first >= finish){
                vec[i].second = true;
                finish = vec[i].first.second;
                N--;
            }
        }
    }
    cout << result << endl;
    return 0;
}

배정이 된 시간표는 true로 표시하며 강의실 개수를 구하려고 했다.

그런데 이렇게 구현을 하게 되면 최악의 경우 200000 * 200000의 연산을 수행하기 때문에 시간 초과가 발생한다.

2차 시도 (결과: 시간 초과)

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int N;
queue<pair<pair<int, int>, int>> q;
vector<pair<int, int>> vec;

void input(){
    cin >> N;
    int start, finish;
    for(int i = 0; i < N; i++){
        cin >> start >> finish;
        vec.push_back({start, finish});
    }
}

bool compare(pair<int, int> a, pair<int, int> b){
    if(a.first < b.first) return true;
    else if(a.first == b.first) {
        if(a.second < b.second) return true;
        return false;
    }
    return false;
}

int main(void){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    input();
    sort(vec.begin(), vec.end(), compare);
    for(auto i: vec) q.push({i, 1});        //queue에 정렬된 데이터들을 복사

    int result = 1;
    int finish_time = 0;
    while(!q.empty()) {
        int start = q.front().first.first;
        int finish = q.front().first.second;
        int room = q.front().second;        //몇번째 방인가
        q.pop();      
        if(result < room) {  //다음 방에 배치해야 됨
            result = room;
            finish_time = finish;
        } else if(finish_time <= start) {      //방에 들어올 수 있다면
            finish_time  = finish;
        } else if(finish_time > start) {
            q.push({{start, finish}, ++room});
        }
    }
    cout << result << endl;
    return 0;
}

두 번째는 vector의 중복되는 true, false를 계산하지 않기 위해 queue를 이용해서 구하려고 했다.

그런데 이 또한

5
5 6
4 6
3 6
2 6
1 6

와 같은 경우에서 O(N^2)의 연산이 나와 시간초과가 발생했다.

그래서 다른 블로그를 참고해서 문제를 해결하였다.

강의가 시작하는 시간을 기준으로 오름차순 정렬을 한 후 priority_queue를 이용해서 강의실 개수만 추가해주면 되는 문제였다.

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int N;
vector<pair<int, int>> vec;

void input(){
    cin >> N;
    int start, finish;
    for(int i = 0; i < N; i++) {
        cin >> start >> finish;
        vec.push_back({start, finish});
    }
}

bool compare(pair<int, int> a, pair<int, int> b){	//강의 시작 시간을 기준으로 정렬
    if(a.first < b.first) return true;
    else if(a.first == b.first) {
        if(a.second < b.second) return true;
        return false;
    }
    return false;
}

int main(void){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    input();
    sort(vec.begin(), vec.end(), compare);
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(vec[0].second);
    for(int i = 1; i < N; i++){
        if(pq.top() <= vec[i].first)
            pq.pop();
        pq.push(vec[i].second);
    }
    cout << pq.size() << endl;
    return 0;
}

참고 블로그

https://hyeonnii.tistory.com/181

https://www.acmicpc.net/problem/1327

1. 입력받은 값을 0번째부터 K번째까지 모두 뒤집으며 큐에 집어넣는다.

2. map을 이용해서 이미 만들었던 문자열인지 확인하며 계속 찾아나간다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
#include<queue>
using namespace std;
map<string, bool> m;
string str = "", result = "";
int N, K;

int bfs(){
    queue<pair<string, int>> q;
    m.insert({str, 0});
    q.push({str, 0});
    while(!q.empty()){
        string s = q.front().first;
        int cnt = q.front().second;
        if(s == result) return cnt;
        q.pop();
        for(int i = 0; i <= str.length() - K; i++) {
            string temp = s;
            reverse(temp.begin() + i, temp.begin() + i + K);    //K개만큼 뒤집음
            if(m.find(temp) == m.end()) {        //찾지 못했다면
                m.insert({temp, true});
                q.push({temp, cnt + 1});
            } 
        }
    }
    return -1;
}

int main(void){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    vector<int> vec;
    int n;
    for(int i = 0; i < N; i++){
        cin >> n;
        vec.push_back(n);        
        str += to_string(n);        
    }

    sort(vec.begin(), vec.end());
    for(int i = 0; i < vec.size(); i++)
        result += to_string(vec[i]);

    //result는 우리가 찾으려고 하는 문자열
    cout << bfs() << "\n";
    return 0;
}

https://jaimemin.tistory.com/1124 를 참고해서 해결한 문제

알고리즘: 투포인터

G의 범위가 100,000이기 때문에 N^2 - (N - 1)^2 >= 100,000인 N의 범위까지 조사하면 된다.

위를 만족하는 N은 50,000.

front, last를 이용해서 투포인터 알고리즘을 사용하여 구현

1) diff가 G보다 크다면 front를 증가, 

2) diff가 G라면 출력값 벡터에 push.

3) diff가 G보다 작다면 last를 증가.

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
int main(void){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int G;
    cin >> G;
    int front = sqrt(G) + 1, last = 1;
    vector<int> vec;
    while(1) {
        int origin = front * front;
        int thinking = last * last;
        int diff = origin - thinking;
        if(front == 50001 && last == 50000) break;
        if(diff == G){
            vec.push_back(front);
            if(front != 50001) front++;
        } else if(diff < G) {   
            if(front != 50001) front++;
            else if(front == 50001) break;
        } else last++;
    }

    if(vec.size()) {
        for(int i = 0; i < vec.size(); i++)
            cout << vec[i] << "\n";
    } else cout << "-1\n";
    return 0;
}

pointer배열은 인덱스마다 N번째 최대값의 위치를 저장하고 있다.

pointer배열을 돌면서 가장 큰 값을 찾아주고 pointer배열의 값을 수정해준다.

#include<iostream>
using namespace std;
int arr[1501][1501] = { 0, };
int pointer[1501] = { 0, };
int main(void){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++)
            cin >> arr[i][j];
    }
    fill(pointer, pointer + N + 1, N);
    for(int i = 1; i <= N; i++){    //N번째 수 찾기
        int maximum = -1000000001, x = 0;
        for(int j = 1; j <= N; j++){
            if(maximum < arr[pointer[j]][j]){
                maximum = arr[pointer[j]][j];
                x = j;
            }
        }
        pointer[x]--;
        if(i == N)
            cout << maximum << "\n";
    }
    return 0;
}

이 문제는 로봇들이 이동하면서 충돌이 없보토이 움직일 수 있느냐를 구하는 문제였다.

이 문제에서 가장 실수를 많이 할 수 있는 부분은 땅의 인덱스였던 것 같다.

보통의 배열이라면 왼쪽 위에 (1, 1)이 위치해 있는데 이 문제에서는 왼쪽 아래에 (1, 1)이 위치해 있다.

이 부분은 같이 스터디 하는 분들도 헷갈렸다고 할 정도로 신경을 써서 구현을 해야 한다.

우선 이 문제를 해결하기 위해 입력값을 저장해보도록 하자.

나는 배열에 문자가 들어가는 것을 좋아하지 않기 떄문에 decide_direction()이라는 함수를 이용해서 E, N, W, S를 0, 1, 2, 3의 값으로 변경해서 각 로봇마다 방향을 지정해주었다.

이때 방향을 정하는 구조체인 Dir의 dir객체를 보면 {0, 1}, {-1, 0}, {0, -1}, {1, 0)의 순으로 저장이 되어 있는데 이는 E, N, W, S의 방향과 같다. (방향이 헷갈리지 않게 로봇의 방향과 구조체의 방향을 모두 E는 0, N은 1, W는 2, S는 3으로 맞춰주었다.)

그리고 입력을 마친 로봇은 map배열의 지정된 x, y좌표에 로봇의 번호를 값으로 가지고 저장되게 된다.

다음으로는 move함수이다.

만약 F를 입력하게 되면 move_forward()라는 함수를 이용해서 내가 바라보는 방향으로 한칸을 전진하도록 했다.(로봇이 바라보는 방향과 dir의 인덱스를 같게 한 이유가 여기에 있다.)

한칸을 전진한 후의 위치에(map 배열에) 다른 로봇이 있다면 충돌이 났다는 문자를 출력해주고 프로그램은 끝이 나게 된다.

혹은 벽이 있을 때도 해당 문자열을 출력하고 프로그램이 끝이 나게 된다.

다음으로 만약 L, R가 들어오게 되면 아래 코드에서 볼 수 있듯이 방향을 바꿔주도록 했다. 

만약 이렇게 모든 입력이 끝이 날때까지 충돌이 나지 않는다면 OK를 출력하고 끝이 나게 된다.

#include<iostream>
#include<vector>
using namespace std;
int A, B, N, M;
int map[101][101] = { 0, };
struct Robot {
	int y, x, d;
};

struct Dir { 
	int y, x;
};

Robot robot[101];
Dir dir[4] = { {0, 1}, {-1, 0}, {0, -1}, {1, 0} };	//E N W S

void decide_direction(int num, char c) {
	if (c == 'E')
		robot[num].d = 0;
	else if (c == 'N')
		robot[num].d = 1;
	else if (c == 'W')
		robot[num].d = 2;
	else if (c == 'S')
		robot[num].d = 3;
}

void move_forward(int num) {
	robot[num].y += dir[robot[num].d].y;
	robot[num].x += dir[robot[num].d].x;
}

bool move(int num, char d, int cnt) {
	if (d == 'F') {
		map[robot[num].y][robot[num].x] = 0;
		for (int i = 0; i < cnt; i++) {
			move_forward(num);
			if (map[robot[num].y][robot[num].x]) {
				cout << "Robot " << num << " crashes into robot " << map[robot[num].y][robot[num].x] << endl;
				return false;
			}
			else if (robot[num].y < 1 || robot[num].y > B || robot[num].x < 1 || robot[num].x > A) {
				cout << "Robot " << num << " crashes into the wall\n";
				return false;
			}
		}
		map[robot[num].y][robot[num].x] = num;
	}
	else if (d == 'R') {
		cnt %= 4;
		robot[num].d += 4 - cnt;
		robot[num].d %= 4;
	}
	else if (d == 'L') {
		robot[num].d += cnt;
		robot[num].d %= 4;
	}
	return true;
}

int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> A >> B >> N >> M;
	int y, x, num, cnt;
	char d;
	for (int i = 1; i <= N; i++) {
		cin >> x >> y >> d;
		robot[i].y = B - y + 1;
		robot[i].x = x;
		decide_direction(i, d);
		map[B - y + 1][x] = i;
	}


	for (int i = 0; i < M; i++) {
		cin >> num >> d >> cnt;
		if (!move(num, d, cnt)) {
			break;
		}
		else if (i == M - 1)
			cout << "OK\n";
	}

	return 0;
}