마쏘's 개발 성장기

1. queue란?
- C++ 표준 라이브러리(Standard Template Library)에 있는 컨테이너(container)가 아니고,
- 특정 컨테이너 클래스(deque, list)의 캡슐화된 개체를 기본 컨테이너로 사용하는 클래스이며,

- container adapter로 구현된다고 한다.

2. queue의 특징

[벡터 원소 및 크기] & [벡터 원소 삽입 및 삭제]

- front(), back(): 제일 앞에 위치한 원소, 제일 뒤에 위치한 원소

- push(n), pop(): queue 뒤에 원소 n 삽입, queue 뒤에 원소 삭제

[벡터의 순회 및 출력]

- queue 자체는 iterator를 필요로 하지 않는다.

1. Vector란?
- C++ 표준 라이브러리(Standard Template Library)에 있는 컨테이너(container)로,
- 사용자가 쉽게 사용할 수 있도록 사전에 정의된 class이다.

2. Vector의 특징

[벡터 원소 및 크기] 

- front(), back(): 첫 번째 원소, 마지막 원소
- size(), capacity(): 원소의 개수 <-> 원소가 할당된 공간 크기
- begin(), end(): 첫 번째 위치, 마지막의 다음 위치

[벡터 원소 삽입 및 삭제]

- push_back(n): 마지막 위치에 n추가
- pop_back(): 마지막 원소 제거

- insert(pos, cnt, n): 위치 pos에 cnt 개의 n을 추가
- insert(pos, n): pos에 숫자 n을 추가

- erase(pos): pos에 있는 값을 제거

- erase(pos_start, pos_end): pos_start ~ (pos_end-1)까지 값들을 제거

[벡터의 순회 및 출력]

- vector에 index로 접근
- iterator 사용(직접 선언 or auto 문법 사용)

1. 우선 Visual Studio에 'Github Extension for Visual Studio'를 설치해야한다.

2. 새 프로젝트 생성

3. GIT repository 만들고 해당 프로젝트와 연동하기

만약 이미 생성되어 있는 레포지토리를 복사하고 싶다면, git 옵션에서 repository 복제를 해주면 된다!

문제를 잘 이해해야 한다.

우선 내구도가 떨어지는 경우는 두 가지다.
1) 로봇이 어떤 칸으로 올라갈 때, 올라가려는 칸의 내구도가 감소한다.

2) 로봇이 어떤 칸으로 이동할 때, 이동하려는 칸의 내구도가 감소한다.

로봇을 옮기는 과정은 다음과 같다1) 벨트가 회전한다 rotate()2) 가장 먼저 올라와있던 로봇부터(가장 먼저 올라온 로봇이 아님) 벨트가 회전하는 방향으로 한 칸 이동한다. move()    이때 이동하기 위해서는 이동하려는 칸에 로봇이 없고, 내구도 >= 13) 올라가는 위치(컨베이어 벨트의 처음)에 로봇이 없으면 로봇을 올린다 put_robot()4) 내구도가 0인 칸의 개수가 k개 이상이라면 과정을 종료한다. 그렇지 않다면 1)번으로 돌아간다.

// 20055 컨베이어 벨트 위의 로봇
// https://www.acmicpc.net/problem/20055

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

# include <stdio.h>
# include <iostream>
# include <deque>
using namespace std;

int n = 0, k = 0, step = 0, cnt = 0;
deque <int> belt;
deque<bool> robot;

void rotation() {
	belt.push_front(belt.back());
	belt.pop_back();

	robot.push_front(robot.back());
	robot.pop_back();
}

void move() {
	for (int i = n-2; i >= 0; i--){
		if(robot[i] && !robot[i+1] && belt[i+1] >= 1){
			robot[i] = false;
			robot[i+1] = true;
			belt[i + 1]--;
		}
	}
}

void put_robot() {
	if(belt[0]>0) {
		belt[0]--;		robot[0]=true;
	}	
}

int get_zero_cnt(){
	int zero = 0;
	for (int i = 0; i < 2*n; i++){
		if(belt[i]==0)
			zero++;
	}
	return zero;
}

int main(void){
	cin >> n >> k;

	for (int i = 0; i < 2 * n; i++){
		int val;
		cin >> val;
		belt.push_back(val);
		robot.push_back(false);
	}
	while(true){
		step += 1;
		rotation();
		robot[n - 1] = false;
		move();
		robot[n - 1] = false;
		put_robot();
		if(get_zero_cnt() >= k){
			cout << step << "\n";
			return 0;
		}
	}
	return 0;
}

원래는 que를 사용했는데 먼저 올라와 있던 로봇을 먼저 옮겨야 하는 걸 알게 되고나서 deque로 변경하였다.

참고한 블로그가 있는데 너무 설명이 잘 되어있어서 감사하게 공부했다!

deque 아이디어만 얻고 혼자 짜보고 확인했는데 나름 내 코드로 체화된 것 같아서 기쁘다!!

ssinee.tistory.com/entry/%EB%B0%B1%EC%A4%80-20055%EB%B2%88-%EC%BB%A8%EB%B2%A0%EC%9D%B4%EC%96%B4-%EB%B2%A8%ED%8A%B8-%EC%9C%84%EC%9D%98-%EB%A1%9C%EB%B4%87-%EC%82%BC%EC%84%B1-%EA%B8%B0%EC%B6%9C

보통 알고리즘을 작성할 때, 연산 속도와 메모리 공간을 최대한 활용할 수 있도록 효울적으로 작성하는데,

어떤 문제는 메모리 공간을 약간 더 사용하면 연산속도를 비약적으로 증가시킬 수 있는 방법이 있다.

그 방법 중 대표적인 방법이 다이나믹 프로그래밍 기법이다.

[ 다이나믹 프로그래밍을 사용할 수 있는 조건 ]
     1. 큰 문제를 작은 문제로 나눌 수 있다.

     2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

다이나믹 프로그래밍을 코드로 구현하기 위해서는 메모이제이션 기법을 사용하는데,
그저 다이나믹 프로그래밍 구현 방법 중 하나라고 생각하면 된다.

메모이제이션 기법은 한 번 구한 결과를 메모리 공간에 저장해두고 같은 식을 다시 호출하면

메모한 결과를 그대로 가져오는 기법을 의미한다.

(보통 메모리 공간은 dictionary나 list를 사용하는 것 같다)

1. 1로 만들기

나의 생각)
가능한 연산은 2,3,5로 나누는 것과 1로 빼는 것이다.

메모리에 저장할 값은 정수 i에서 1 ~ i까지의 연산 최소 횟수로 정의하였다.

값을 계산하기 위해 arr[0] = 0; arr[1] = 0; arr[2] = 1; arr[3] = 1; arr[4] = 2; arr[5] = 1를 미리 초기값으로 지정하였다.

''' 
input 1:[26]
output: 3 
input 2: [20730, 16465, 27368, 21803, 29081, 23215, 16419, 12244, 16602, 25045]
output 2: 10 13 11 13 14 13 11 11 11 10
input 3: [20730, 16465, 27368, 21803, 29081, 23215, 16419, 12244, 16602, 25045]
output 3: 8 10 9 9 11 11 11 8 11 10 
'''
nums = [8000, 6814, 2553, 3918, 7034, 5806, 5471, 3012, 6986, 5347]

def make_to_one(n):
    arr = [0 for _ in range(n+1)]
    arr[0] = 0; arr[1] = 0; arr[2] = 1; arr[3] = 1; arr[4] = 2; arr[5] = 1

    if n <= 5: 
        print(arr[n])

    operaters = [1,2,3,5]
    for a in range(6, n+1):
        candidates = [30000,30000,30000,30000]
        candidates[0] = arr[a-1] + 1
        if a % 2 == 0:
            candidates[1] = arr[int(a/2)] + 1
        if a % 3 == 0:
            candidates[2] = arr[int(a/3)] + 1
        if a % 5 == 0:  
            candidates[3] = arr[int(a/5)] + 1
        arr[a] = min(candidates)

    print(arr[n], end = ' ')

for num in nums:
    make_to_one(num)

2. 개미 전사

주어진 배열에서 한 칸 이상 띄워서 더했을 때 나올 수 있는 최댓값을 구해야 하는 문제이며,

메모리에 저장할 값은 해당 i번째까지 구할 수 있는 최댓값으로 정의하였다.

최댓값을 구할 때 나올 수 있는 경우의 수는

     1) 더하지 않을 때: i-1번째에 저장된 값을 저장

     2) 더할 때: i-2번째에 저장된 값에 현재 i값을 더한 값을 저장

따라서 i에 저장할 최댓값은 위 경우의 1), 2) 값을 비교하여 나오는 최댓값을 구해서 대입하면 된다.

# n = int(input())
# storage = list(map(int, input().split()))
# print(n, storage)

'''
input 1: 4, [1,3,1,5]
output 1: 8

input 2: 10, [11, 6, 12, 3, 4, 1, 18, 2, 17, 16]
output 2: 62
'''

n, storage = 15, [1, 100, 1, 1, 1, 100, 1, 100, 100, 1, 1, 100, 100, 100, 1]
table_DP = [0 for _ in range(n)]

table_DP[0] = storage[0];
table_DP[1] = max(storage[0], storage[1])

for i in range(2,n):
    candidates = []
    # defore max sum
    candidates.append(table_DP[i-1])
    # front + my sum
    candidates.append(table_DP[i-2] + storage[i])
    table_DP[i] = max(candidates)

print(table_DP[n-1])

3. 바닥 공사

숫자에서 뿐만 아니라 도형적인 패턴에서도 큰 문제를 작은 문제로 쪼갤 수 있는지를 판단하기 위한 문제라고 생각한다.

메모리에 저장할 값을 가로가 i일 때, 바닥을 채울 수 있는 모든 경우의 수로 정의하였다.

그러나, [i-1]과 [i]와의 관계성을 구하는데 2x1의 덮개에서 중복이 발생해 이를 해결해야 했다.

이를 해결하기 위해서는 [i-1]와 [i-2]와 [i]의 관계를 살펴보아야 하는데,

1) [i-1]에서 [i]까지는 2x1만 채울 수 있다.

2) [i-2]에서 [i]까지는 2x1과 1x2와 2x2가 다 채워질 수 있는데,

                              여기서 2x1은 1)의 경우에서 채울 수 있으므로 

총 우리가 고려해야 하는 것은  [i-1]에서 2x1로 채울 때, [i-2]에서 1x2 또는 2x2로 채울 때만 고려하면 된다.

!) 아 참, 큰 수로 나누는 이유는 모든 경우의 수는 값이 커지므로 출력 범위를 줄이기 위함이라고 한다.

#n = int(input())
n = 345
div_num = 796796

'''
input:  [760,    765,    378,    345,    4,  521,    741,    640,    464,    530] # n이 들어있는 배열
output: [536911, 448425, 551139, 336313, 11, 373121, 481185, 496871, 646635, 603879] # n에 해당하는 answer가 들어있는 배열
'''

table = [0 for _ in range(1001)] # 1 <= n <= 1000, table = [0] * 1001
table[1], table[2] = 1, 3

for i in range(3, n + 1):
    table[i] = table[i-1] + 2 * table[i-2]

print(table[n] % div_num)

4. 효율적인 화폐 구성

이부분을 풀면서 그리디와 DP를 구분해보았는데 여기서 중요한 건 "정당성"이다. 그리디에서는 화폐의 단위가 배수로 커졌기 때문에 큰 수부터 나누는 것이 맞으나, 화폐 단위끼리 간격이 달라진다면 무조건 큰 화폐로 채우는 것이 최선이 아닐 수 있다.

예를 들면 화폐 종류가 3개로 1, 7, 11 이렇게 있다고 하자. 우리가 구해야하는 화폐의 금액은 115원이다.

그리디 방식으로 풀게 된다면, '11' 10개, '1' 5개로 총 15개가 필요하다.

그러나, 11+7=18로 115는 18*6 + 7이므로 따라서 '11' 6개 '7' 7개로 총 13개가 필요하다.이로써 화폐 단위가 다를 때 큰 수부터 나누어 구하는 것이 최선의 값을 보장하지 못한다.

다시 DP로 돌아오자면, 메모리에 저장할 값은 화폐로 저장할 수 있는 최소 개수로 정의하였다.화폐 종류가 2 하나라면,a) 2부터 n까지 2로 만들 수 있는 i번째에 값을 갱신한다.

화폐 종류가 하나 이상이라면,b1) 화폐 선택  b2) a)를 반복하면 된다.

이때 갱신할 값은 현재 자신에 채워진 개수 & 자신이 가진 돈에서 화폐 단위만큼 뺐을 때 최소 개수 + 1을 비교해서 작은 값으로 갱신하면 된다.

# n,m = map(int, input().split()) 
# coins = [0] * n
# table = [10001] * (m + 1) # 0 <= m <= 10000
# for i in range(n):
#     coins[i] = int(input());     table[coins[i]] = 1

# input 1 
n, m = 3, 115
coins = [1, 7, 11]
# ouput 1
14

'''
input 2
n, m = 10, 9668
coins = [50, 46, 80, 85, 66, 28, 95, 22, 99, 7] 
output 2
98
input 3
n, m = 10, 5726
coins = [92, 72, 97, 89, 29, 12, 80, 90, 81, 16]
output 3 
60
'''
table = [10001] * (m + 1) # 0 <= m <= 10000

for coin in coins:
    table[coin] = 1

for coin in coins:
    for step in range(coin, m+1):
            table[step] = min(table[step], table[step-coin] + 1)

if table[m] == 10001:
    print("-1")
else:
    print(table[m])

자세한 설명은 아래 포스트를 참고하기
masso.tistory.com/80?category=891816

1. 부품 찾기

: 다른 input 만드느라 애 좀 먹었다..ㅠㅜ

1-0. input & output

# input 1
N, M = 5, 3
store, client = [8, 3, 7, 9, 2], [5, 7, 9]
# ouput 1
# no yes yes

# input 2
N, M = 50, 20
store = [73,15,26,59,49,44,8,47,63,74,66,81,67,41,52,45,57,4,51,12,10,37,64,7,48,23,42,18,71,55,36,61,83,82,2,20,94,76,28,58,50,92,79,70,96,19,54,97,40,86]
client = [4,35,20,53,93,6,63,52,21,41,5,77,91,78,79,7,46,39,64,95]
# output 2
# yes no yes no no no yes yes no yes no no no no yes yes no no yes no

# input 3
N, M = 60, 60
store = [911,643,184,439,855,981,950,776,519,204,321,47,749,53,851,272,970,270,42,137,523,251,990,171,487,860,796,19,841,46,799,215,333,766,214,709,687,299,334,554,991,396,163,473,869,76,549,128,821,756,703,463,60,283,706,81,314,415,517,375]
client = [500,923,351,303,489,294,579,708,287,382,137,906,229,788,332,251,862,486,795,638,932,725,573,541,329,177,324,868,710,277,290,909,948,364,87,727,652,497,977,618,532,258,949,632,687,29,735,580,617,770,70,946,569,743,189,388,322,636,61,200]
# output 3
# no no no no no no no no no no yes no no no no yes no no no no no no no no no no no no no no no no no no no no no no no no no no no no yes no no no no no no no no no no no no no no no

1-1. 정렬한 후 이진 탐색 binary Search

'''=== way1. binary search ==='''
def binary_search(target, start, end, arr):
    if start > end:
        return False
    mid = (start + end) // 2 # 괄호가 없으면 우선 순위가 달라짐
    if arr[mid] == target:
        return True
    elif target < arr[mid]:
        return binary_search(target, start, mid-1, arr) # -1 자꾸 까먹음..!
    else:
        return binary_search(target, mid+1, end, arr) # +1 자꾸 까먹음..!

start_time = timeit.default_timer()
store = sorted(store)
for target in client:
    if binary_search(target, 0, N-1, store):
        print("yes", end = ' ')
    else: 
        print("no", end = ' ')
print()
end_time = timeit.default_timer()
print(">> binary_search time: ", end_time - start_time)

1-2. set의 성질 이용하기

'''=== way2. set() ==='''
# N = int(input())
# store = set(map(int, input().split())) #!! list 대신 set으로!
# M = int(input())
# client = list(map(int, input().split()))

set_store = set(store)
start_time = timeit.default_timer()
for target in client:
    if target in set_store:
        print("yes", end = ' ')
    else:
        print("no", end = ' ')
end_time = timeit.default_timer()

1-3. 계수 정렬(생략)

2. 떡볶이 떡 만들기

: 손님이 원하는 길이에 딱 맞는 최대 높이를 찾을 수 없다면,
  손님이 원하는 길이보다 더 많이 주는 높이 중에서 최댓값을 반환해야한다!! (아래 input 2,3 참고)

2-0. input

# input 1
# N, M = 4, 6
# rice_cakes = [19, 15, 10, 17]
# answer:15

# input 2
# N, M = 50, 456
# rice_cakes = [693, 124, 802, 928, 882, 939, 375, 944, 810, 860, 310, 110, 851, 433, 888, 957, 574, 320, 673, 389, 
# 594, 807, 809, 946, 949, 138, 688, 136, 581, 398, 649, 225, 188, 301, 743, 299, 623, 220, 643, 767, 588, 183, 551, 
# 264, 184, 547, 376, 766, 811, 162]
'''절단기에 설정할 수 있는 높이의 최댓값:  872
>> sequential_search time:  0.0007, >> recursive_binary_search time:  0.0003, >> while_binary_search time:  0.0003
'''

# input 3
N, M = 200, 1357
rice_cakes = [273, 20, 157, 49, 24, 224, 175, 193, 169, 153, 141, 297, 258, 287, 268, 154, 211, 185, 113, 294, 129, 117, 242, 91, 
122, 106, 215, 292, 271, 188, 56, 167, 256, 63, 172, 206, 213, 51, 249, 146, 54, 124, 97, 198, 264, 200, 197, 156, 209,
13, 252, 62, 152, 236, 27, 207, 160, 277, 10, 176, 241, 223, 46, 274, 205, 262, 22, 291, 293, 132, 11, 253, 41, 283, 
199, 110, 126, 36, 71, 105, 220, 87, 231, 31, 171, 128, 263, 270, 30, 95, 281, 183, 155, 260, 216, 135, 44, 257, 276, 
104, 254, 279, 217, 12, 299, 55, 149, 138, 58, 125, 246, 266, 66, 201, 75, 85, 57, 77, 229, 101, 133, 21, 35, 161, 240,
286, 131, 290, 99, 130, 88, 184, 261, 247, 83, 151, 84, 238, 81, 221, 267, 265, 89, 173, 123, 245, 79, 26, 102, 225, 
278, 219, 186, 144, 68, 166, 180, 120, 162, 118, 52, 25, 139, 45, 50, 43, 163, 17, 86, 255, 168, 140, 181, 28, 96, 53,
112, 233, 109, 70, 237, 196, 248, 80, 232, 159, 111, 100, 275, 194, 78, 251, 272, 295, 76, 94, 289, 174, 47, 202]
'''절단기에 설정할 수 있는 높이의 최댓값:  240
>> sequential_search time:  0.0011, >> recursive_binary_search time:  0.0005, >> while_binary_search time:  0.0006
'''
# answer = 240

2-1. 순차 탐색 sequential Search

'''sequential_search'''
def sequential_search(arr):
    max_H = max(arr)
    while max_H > 0:
        total = 0
        for ele in arr:
            if ele > max_H:
                total += ele - max_H
        if total >= M:
            print("절단기에 설정할 수 있는 높이의 최댓값: ", max_H)
            break;
        max_H -= 1
            
'''%% 입력의 범위가 최대 10억까지의 정수이므로 시간 초과를 받는다.'''  
start_time = timeit.default_timer()
sequential_search(rice_cakes)
end_time = timeit.default_timer()
print(">> sequential_search time: ", format(end_time - start_time, ".4f"))

2-2. 이진 탐색 binary Search

'''binary_search'''
def binary_search(ans, arr, minH, maxH):
    global result
    if minH > maxH:
        return -1
    midH = (minH + maxH) // 2
    total = 0
    for ele in arr:
        if ele > midH:
            total += ele - midH
    if total >= ans:
        result = midH
        return binary_search(ans, arr, midH+1, maxH)
    elif total < ans:
        return binary_search(ans, arr, minH, midH-1)

start_time = timeit.default_timer()
result = 0
binary_search(M, rice_cakes, 0, max(rice_cakes))
print("절단기에 설정할 수 있는 높이의 최댓값: ", result)
end_time = timeit.default_timer()
print(">> recursive_binary_search time: ", format(end_time - start_time, ".4f"))