동바리의 공부방

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

import sys

N = int(input())
my_arr_element = list(map(int, input().split()))

my_arr_element.sort()

flag_list =[]

def do_searching(start_idx, end_idx, searching_num):
    if (start_idx > end_idx):
        return

    mid = int((start_idx + end_idx) / 2)
    if my_arr_element[mid] == searching_num:
        flag_list.append(1)
        return

    if (my_arr_element[mid] > searching_num):
        end_idx = mid - 1
        do_searching(start_idx, end_idx, searching_num)
    else:
        start_idx = mid + 1
        do_searching(start_idx, end_idx, searching_num)

    return


M = int(input())
target_element = list(map(int, input().split()))
for i in range(0, M):
    flag_list.clear()
    do_searching(0,N  - 1, target_element[i])
    if (len(flag_list) == 0):
        print(0)
        continue

    print(1)

1. 이진탐색을 이용하여 풀 수 있는 문제였습니다.
2. 처음엔 입력으로 들어온 값을 인덱스로 처리하여 쉽게 풀 수 있을거라고 생각했지만, 이는 틀린 생각이었습니다.
3. 왜냐하면 입력으로 음수가 들어올 수도 있기 때문입니다.
4. 따라서 이진탐색으로 방법을 변경했습니다.

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

from audioop import reverse
import sys
from collections import deque

t = int(input())

for i in range(t):
    reverse_cnt = 0
    p = sys.stdin.readline().rstrip()
    n = int(input())
    arr = deque(sys.stdin.readline().rstrip()[1:-1].split(","))
    j = True
    for i in range(0, len(p)):
        if p[i] == 'R':
            reverse_cnt += 1

        elif p[i] == 'D':
            if n == 0 or len(arr) == 0:
                print("error")
                j = False
                break

            if reverse_cnt % 2 == 0:
                arr.popleft()
                continue

            arr.pop()

    if (j == False):
        continue

    if reverse_cnt % 2 == 0:
            print("[" + ",".join(arr) + "]")
    else:
        arr.reverse()
        print("[" + ",".join(arr) + "]")

1. R 함수가 있다해서, 반드시 뒤집을 필요 없습니다. 만날때마다 뒤집기를 실행하면 시간 초과가 발생합니다.
2. R 함수 카운트가 홀수일 경우만 뒤집어주면 됩니다. 왜냐하면 "RR" 이렇게 두번 나온다면 원래 배열과 동일하기 때문입니다. "R" 또는 "RRR" 이런식의 홀수 카운트라면 뒤집는게 유효합니다.

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

int element_cnt;
const int lotto_cnt = 6;
array<int, 49 + 1> input_array;

void remark(const int idx, int check_cnt, array<int, lotto_cnt>& lotto)
{
    if (lotto_cnt == check_cnt) {
		for (const auto& i : lotto) {
            cout << i << ' ';
        }

        cout << '\n';
        return;
    }

    for (int i = idx; i <= element_cnt; i++) {
        lotto[check_cnt] = input_array[i];
        remark(i + 1, check_cnt + 1, lotto);
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    while (true) {
        cin >> element_cnt;
        if (!element_cnt) {
            break;
        }

        for (int i = 1; i <= element_cnt; i++) {
            int input_cnt;
            cin >> input_cnt;
            input_array[i] = input_cnt;
        }

        const int check_cnt = 0;
        array<int, lotto_cnt> lotto{ 0, };
        remark(1, check_cnt, lotto);

        cout << '\n';
    }

    return 0;
}

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

재귀함수를 이용해 풀 수 있는 전형적인 문제였습니다.

#include <iostream>
#include <iterator>
#include <string>
#include <array>
#include <list>
using namespace std;

list<char> editor;

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string input_str;
    cin >> input_str;
    for (int i  = 0; i < input_str.size(); i++) {
        editor.push_back(input_str[i]);
    }

    auto current_idx = editor.end();
    int cnt;
    cin >> cnt;
    while (cnt-- > 0) {
        char command;
        cin >> command;
        char append_char;
        switch (command) {
        case 'P':
            cin >> append_char;
            current_idx = editor.insert(current_idx, append_char);
            current_idx++;
             break;

        case 'B':
            if (editor.begin() == current_idx) {
                break;
            }

            --current_idx;
            current_idx = editor.erase(current_idx);
            break;
        case 'D':
            if (editor.end() == current_idx) {
                break;
            }

            ++current_idx;
            break;
        case 'L':
            if (editor.begin() == current_idx) {
                break;
            }

            --current_idx;
            break;

        default:
            break;
        }
    }

    for (auto& i : editor) {
        cout << i;
    }
    cout << '\n';
    return 0;
}

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

문제 descption을 읽어보면 전형적인 linked list 동작이었습니다.

처음엔 string 객체를 이용해 문제를 풀었으나, 시간 초과를 초래했네요.

그래서 std::list로 컨테이너를 교체했습니다.

import sys
n = int(sys.stdin.readline())

back = 0
my_q = [0 for i in range (0, 100000 + 1)]
for i in range(n):
    command = sys.stdin.readline().split()
    if command[0] == 'push':
        my_q[back] = command[1]
        back +=1

    elif command[0] == 'pop':
        if 0 == back :
            print(-1)
            continue

        print(my_q[0])
        for i in range(0, back):
            if back - 1 == i:
                continue

            my_q[i] = my_q[i + 1]

        back -= 1

    elif command[0] == 'size':
        print(back)

    elif command[0] == 'empty' :
        if back != 0:
            print(0)
            continue

        print(1)

    elif command[0] == 'front' :
        if 0 == back:
            print(-1)
            continue

        print(my_q[0])

    elif command[0] == 'back' :
        if 0 == back:
            print(-1)
            continue

        print(my_q[back - 1])

큐를 이해하고 있으면 쉽게 풀 수 있습니다.

import sys
n = int(sys.stdin.readline())

sp = 0
my_stack = [0 for i in range (0, 100000 + 1)]
for i in range(n):
    command = sys.stdin.readline().split()
    if command[0] == 'push':
        my_stack[sp] = command[1]
        sp += 1

    elif command[0] == 'pop':
        if 0 == sp :
            print(-1)
            continue

        print(my_stack[sp - 1])
        my_stack[sp - 1] = 0
        sp -= 1

    elif command[0] == 'size': # 크기 조회
        if sp == 0:
            print(0)
            continue

        print(sp)

    elif command[0] == 'empty' : # 크기 조회
        if sp != 0:
            print(0)
            continue

        print(1)

    elif command[0] == 'top' :
        if 0 == sp:
            print(-1)
            continue

        print(my_stack[sp - 1])

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

스택을 이해하고 있으면, 쉽게 풀 수 있습니다.

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

제가 40분컷 내버린것을 보면 아주 쉬운 문제였다는 것을 알 수 있습니다.

​

예제 입력으로 보는 풀이는 아래와 같습니다.

0 3 -> 3행에서 자른다.

1 4 -> 4열에서 자른다.

0 2 -> 2행에서 자른다.

위 경우로는, 아래와 같이 총 6개로 나뉩니다.

​

(2 - 0) * (4-0)

(2 - 0) * (10 - 4)

​

(3 - 2) * (4 - 0)

(3 - 2) * (10 - 4)

​

(8 -3) * (4 - 0)

(8 - 3) * (10 - 4)

​

가장 큰 것을 찾습니다.

​

어떤 클래스의 non static 멤버의 포인터를 가져오고 싶다면 아래와 같이 코딩을 해서 해결할 수 있습니다. thread를 생성하는 방법으로 설명하겠습니다.

#include <iostream>
#include <utility>
#include <thread>
#include <chrono>

#define	IS_STATIC	1	

class foo
{
public:
#if IS_STATIC
	static void bar()
#else
	void bar()
#endif
	{
		for (int i = 0; i < 5; ++i) {
			std::cout << "Thread 3 executing\n";
			//++n;
			std::this_thread::sleep_for(std::chrono::milliseconds(10));
		}
	}
};

int main()
{
	int n = 0;
	foo f;
#if IS_STATIC	
	std::thread t5(foo::bar); // t5 runs foo::bar() on object f
#else
	std::thread t5(&foo::bar, &f); // t5 runs foo::bar() on object f
#endif // 0
	t5.join();

}

std::thread t5(&foo::bar, &f);

인스턴스 f의 bar 함수를 수행하는 스레드를 생성하기 위한 코드입니다. 이를 위해 f의 포인터를 넘기고, member pointer인 &foo::bar까지 같이 넘깁니다.

그러면 static function이 만들어지고 이를 t5가 수행하게 됩니다.

위처럼 코딩하면 non static 멤버의 포인터를 이용할 수 있습니다. getter를 굳이 만들지 않고서도요. 하지만 이는 thread를 생성할때 문법적으로 맞춰줘야 하는 부분이므로 굳이 다른 상황에서 이용할 필요는 없을것 같습니다.

​

** 만일 static 메서드라면 아래와 같이 이용할 수 있습니다. static이기 때문에 인스턴스는 param에서 제외되도 됩니다.

std::thread t5(foo::bar);