Brute force Study

1. Terminal에서 다음 명령어를 입력

c++ --version

2. InstalledDir에서 bin의 이전 directory로 이동

cd /Library/Developer/CommandLineTools/usr/

위 경로는 사용자 환경에 따라 다를 수 있습니다. cd 명령어 이후 나오는 경로는 1번에서 얻은 경로로 설정하면 됩니다

(3번 과정을 생략하려면 ~~~~/usr/include/로 한 번에 이동하면 됩니다)

3. usr 디렉토리에서 include 디렉토리로 이동

cd include

4. include 디렉토리에서 bits 디렉토리 생성

mkdir bits

5. bits 디렉토리로 이동

cd bits

6. stdc++.h 파일 생성 후 편집기 열기

vi stdc++.h
또는
vim stdc++.h

Permission denined 되는 경우 vi 또는 vim 앞에 sudo를 붙여주면 된다.

7. 코드 복사 후 저장

https://gcc.gnu.org/onlinedocs/gcc-4.8.0/libstdc++/api/a01541_source.html

저는 공식 문서에 소스 코드로 저장했는데 오류가 발생해서 아래 소스 코드로 저장해서 해결했습니다. 

https://gist.github.com/Einstrasse/ac0fe7d7450621a39364ed3b05cacd11

vi 에디터를 사용하실 줄 모르는 분들은

cmd+v로 붙여넣기 후 esc를 누르고 :(쉬프트 + 세미콜론)을 누르고 wq 입력 후 엔터를 누르면 됩니다

여기까지 하면 끝입니다.

파일을 찾을 수 없다는 오류가 발생했다면 1~6번 과정을 제대로 했는지 검토해보세요.

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

힙을 이용하여 문제를 해결해야 하기 때문에 C++에서 제공하는 priority_queue를 사용할 수 있다.

절대값을 기준으로 비교하기 때문에 함수 객체를 만들고, 우선순위 큐의 comparator로 사용하여 문제를 해결하면 된다.

comparator의 구체적인 작동방식이 헷갈려서 우선순위 큐에서 비교자의 작동 방식에 대해 적어보겠다.

비교자의 작동 방식

비교자의 작동 방식을 더 구체적으로 이해해봅시다.

여기서 간주한다는 의미는, 우선순위가 낮다는 의미이다.

• std::less는 x < y가 true일 때 x가 y보다 작다고 간주합니다. 최대 힙에서 이는 큰 값이 높은 우선순위를 가지게 만듭니다.
  • x가 y보다 작을 때, 작다고 간주하는게 당연하다고 생각할 수 있다. 하지만 std::greater는 x가 y보다 클 때 x가 y보다 작다고 간주한다.
  • x값이 y값보다 작을 때 x의 우선순위가 낮다는 의미이다. 값이 작은게 우선순위가 낮다 --> 큰 값이 우선순위가 높다 --> 최대 힙
• std::greater는 x > y가 true일 때 x가 y보다 작다고 간주합니다. 최소 힙에서 이는 작은 값이 높은 우선순위를 가지게 만듭니다.
  
  • x값이 y값보다 클 때 x의 우선순위가 낮다는 의미이다. 값이 큰 게 우선순위가 낮다 --> 작은 값이 우선순위가 높다 --> 최소 힙

따라서, std::less를 사용하면 큰 값이 우선순위를 가지게 되어 최대 힙이 되고, std::greater를 사용하면 작은 값이 우선순위를 가지게 되어 최소 힙이 됩니다.

이 원리를 이해하고 함수 객체를 만들어 문제를 해결해보자. 

Code

함수 객체를 따로 만들긴 귀찮아서 람다 함수를 이용했다.

#include <iostream>
#include <queue>
using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, x;
    auto compare = [](int a, int b) { 
        if (abs(a) == abs(b))
			return a > b;
		else
			return abs(a) > abs(b);
    };
    priority_queue<int, std::vector<int>, decltype(compare)> absHeap(compare);
    cin >> n;
    while (n--) {
        cin >> x;
        if (x != 0) {
            absHeap.push(x);
        }
        else {
            if (absHeap.empty()) {
                cout << 0 << '\n';
            }
            else {
                cout << absHeap.top() << '\n';
                absHeap.pop();
            }
        }
    }
}

문제

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

시간 초과된 풀이

#include <iostream>
using namespace std;

int count;

int recursion(string s, int l, int r){
    ::count++;
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}

int isPalindrome(string s){
    return recursion(s, 0, s.length() - 1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    string temp;
    cin >> n;
    while (n--) {
        ::count = 0;
        cin >> temp;
        cout << isPalindrome(temp) << " " << ::count << '\n';
    }
}

• 함수에서 매개변수 값을 복사하는 시간으로 인해 시간초과 발생

해결 방법 : call-by-reference, 즉 값을 복사하는 것이 아니라, 참조하여 실행 시간을 줄인다

#include <iostream>
using namespace std;

int count;

int recursion(string &s, int l, int r){ // 문자열 참조
    ::count++;
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}

int isPalindrome(string &s){ // 문자열 참조
    return recursion(s, 0, s.length() - 1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    string temp;
    cin >> n;
    while (n--) {
        ::count = 0;
        cin >> temp;
        cout << isPalindrome(temp) << " " << ::count << '\n';
    }
}

문제

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

잘못 접근하기 좋은 풀이

문제에 나와있는 그대로 모든 원소를 삽입, pop을 해보겠다

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Queue<Integer> queue = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            if (arr[i] == 0) {
                queue.add(Integer.parseInt(st.nextToken()));
            }
            else {
                stack.add(Integer.parseInt(st.nextToken()));
            }
        }
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int x;
        for (int i = 0; i < m; i++) {
            x = Integer.parseInt(st.nextToken());
            for (int j = 0; j < n; j++) {
                if (arr[j] == 0) {
                    queue.add(x);
                    x = queue.poll();
                }
            }
            bw.write(x + " ");
        }
        bw.flush();
        bw.close();
    }
}

시간 복잡도(시간 제한을 통과 하지 못한 풀이)

O(nm)으로 시간 제한 1초를 넘어버린다. 불필요한 연산이 포함되어 있다.

-----------------------------------------

접근

• 스택 자료구조의 경우 삽입된 값을 다시 pop을 하기 때문에, 스택의 연산에 대해 신경쓰지 않아도 된다.
  • 예제 입력 2처럼 스택으로만 이루어 진 경우 삽입한 값이 그대로 return 된다
• 따라서 queuestack 내에서 queue가 존재하는 경우 queue의 연산이 작동하는 것을 생각해보자

예제 입력 1을 예시로 봐보자. 큐에는 (후단) [4, 1] (전단) 가 있다.

• 2를 삽입하면
  • 큐 : (후단) [1, 2] (전단),  4가 리턴된다
• 4를 삽입하면
  • 큐 : (후단) [2, 4] (전단), 1이 리턴된다
• 7를 삽입하면
  • 큐 : (후단) [4, 7] (전단),  2가 리턴된다

즉, 후단에서 pop한 값이 리턴되고, 삽입하려는 값은 큐의 전단에 삽입된다. 이를 통해 덱(Deque) 자료구조를 이용해야 겠다는 생각을 해야한다. pollLast()를 통해 리턴되는 값을 찾아야 한다

삽입하려는 값을 덱에 삽입한 후 삽입한 횟수 만큼 pollLast()를 해도 문제를 통과할 수 있고, 큐의 크기와 삽입하려는 수열의 길이의 대소관계를 비교해서 경우에 따라 코드를 세분화해도 된다(세분화 하는 경우 코드가 조금 길어진다).

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Deque<Integer> queue = new LinkedList<>();
        st = new StringTokenizer(br.readLine());
        int temp;
        for (int i = 0; i < n; i++) {
            temp = Integer.parseInt(st.nextToken());
            if (arr[i] == 0) {
                queue.add(temp);
            }
        }
        int m = Integer.parseInt(br.readLine());
        int queueSize = queue.size();
        if (queueSize == 0) {
            System.out.print(br.readLine());
            return;
        }
        else if (m > queueSize) {
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < queueSize; i++) {
                bw.write(queue.pollLast() + " ");
            }
            for (int i = 0; i < m - queueSize; i++) {
                bw.write(st.nextToken() + " ");
            }
        }
        else if (m == queueSize) {
            for (int i = 0; i < queueSize; i++) {
                bw.write(queue.pollLast() + " ");
            }
        }
        else {
            for (int i = 0; i < m; i++) {
                bw.write(queue.pollLast() + " ");
            }
        }
        bw.flush();
        bw.close();
    }
}