solution

import sys
input = sys.stdin.readline

N,M,H = map(int,input().split())
board = [[0] * N for _ in range(H) ]
for i in range(M):
    a,b = map(int,input().split())
    board[a-1][b-1] = 1
ans = 100

def is_answer():
    global board

    for start in range(N):
        index = start

        for horizon in range(H):
            try :
                if board[horizon][index] == 1:
                    index += 1
                    continue

                if board[horizon][index-1] == 1:
                    index -= 1
                    continue
            except :
                continue
        end = index  
        if start != end:
            return False
    return True


def dfs(index, x):
    global board
    global ans

    if is_answer():
        ans = min(ans,index)
        return

    if index == 3:
        return

    for a in range(x, H):
        for b in range(N-1):
            if board[a][b] == 1:
                continue

            try:
                if board[a][b-1] == 1:
                    continue
                if board[a][b+1] == 1:
                    continue
            except :
                continue

            board[a][b] = 1
            dfs(index+1,a)
            board[a][b] = 0

dfs(0,0)
if ans == 100: print(-1)
else: print(ans)

아이디어

문제를 읽고 나서 사다리를 전부 한 번씩 생각이 들었다. 가로선을 놓을 수 있는 곳을 배열로 만들고 dfs를 통해 탐색을 했다. 완탐으로 모든 경우의 수를 탐색했을 때 시간초과가 나는 것을 확인했다. 백트래킹을 통해서 경우의 수를 줄여줘야할텐데 어떤 경우의 수를 줄여줘야할지 감이 오지 않았다.

포인트

다른 사람이 작성한 코드를 살펴보고 처음 짰던 내 코드와 비교를 해봤다.

1. 나는 왜 재귀를 4번 돌았을까?

DFS로 완탐을 구현할 때 탈출 조건을 검사하는 부분과 정답을 검사하는 부분의 순서가 중요했다.

# 내 코드
def dfs(index):
    if index == 4:
        return

    if is_answer():
        ans = min(ans.index)
        return

# 고친 코드
def dfs(index):
    if is_answer():
        ans = min(ans, index)
        return

    if index == 3:
        return

원래 코드는 재귀를 모든 탐색에서 한번씩 더 호출하기 때문에 시간 복잡도가 배로 늘어나버리는 불상사가 발생한다. DFS는 탈출조건 -> 정답검사 -> 재귀호출 이렇게 생각하고 있었기 때문에 재귀를 한 번 더 호출하는 코드를 짜게 된 것 같다. 정답 검사를 탈출 조건보다 우선 수행하여 재귀를 호출하는 횟수를 줄였다.

2. 백트래킹은 필수!

완전탐색으로 구현을 하고, 재귀 호출을 줄여봐도 결국 시간초과의 늪에 빠졌다. 이 문제에서 시간초과가 나지 않는 중요한 포인트는 "사다리를 놓고 나서 이전에 검사했던 자리에는 사다리를 놓을 필요가 없다." 이다. 코드를 한번 보자. 내가 짠 코드에서는 재귀호출을 통해서 사다리를 놓는다.

# 내 코드
def dfs(index):
    # ...탈출조건 ...정답조건

    #재귀호출 시
    for a in range(H): # 사다리의 가로 수만큼
        for b in range(N-1): # 세로 수 - 1 만큼
            if can_place_ladder(board[a][b]):
                board[a][b] = 1
                dfs(index+1)
                board[a][b] = 0

# 고친 코드
def dfs(index, x):
    # ...탈출조건 ...정답조건

    #재귀호출 시
    for a in range(x,H): # 이전에 놓았던 사다리 index부터 검사 시작
        for b in range(N-1): # 세로 수 - 1 만큼
            if can_place_ladder(board[a][b]):
                board[a][b] = 1
                dfs(index+1,a)
                board[a][b] = 0

두 코드를 비교해보면 이전에 놓았던 사다리 자리를 dfs의 인자로 전달해주고 그 자리부터 탐색을 시작하는 것을 시작한다. 기존의 코드는 사다리를 놓고 재귀로 다음 사다리를 놓으려고 할 때 처음부터 탐색을 시작한다. 고친 코드는 사다리를 놓은 뒤, 그 사다리의 x 위치를 인자로 전달하여 그 위치부터 탐색을 시작한다. 원래 x와 y를 둘 다 전달하면 더 시간이 적게 걸리는 코드가 되겠지만 x만 해도 충분할 것이라고 생각했다.

아 x는 가로선이다.

느낀점

• 알고리즘에 어느정도 자신감이 붙어서인지 실수가 잦아졌다. print()를 지우지 않고 제출하여 출력초과가 나고, 문제를 꼼꼼히 읽지 않아서 사다리의 최소 갯수를 구해야하는데 그냥 사다리의 갯수만 구했다. 문제 뿐만 아니라 내가 짠 코드도 꼼꼼히 읽지 않는다. vscode를 사용하다가 자동으로 import된 라이브러리 때문에 런타임에러가 3번이나 났다. 이상한 라이브러리 import를 하면 내용을 보여주지 않는 런타임에러가 나는 걸 처음 알았다.

• 파이썬은 세상에서 제일 느리다. C++로 풀어도 시간초과가 날까? C++로 한 번 풀어봐야겠다.

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

알고리즘 스터디를 진행하면서 Python을 통해 문제를 풀고 있다. C++과 Python을 섞어가며 문제풀이를 진행할 예정....(두개다 하기 힘들어요!!! 😭 ) 실력증진을 위해...화이팅... 시간아 멈춰! ✋

어떻게 풀 것인가?

Python 장점 : Combination과 Permutation을 만들기 쉽다. 왜? itertools에서 Combination과 Permutation을 제공하기 때문❗ 주어진 알파뱃을 사전순으로 정렬하고, Combination을 통해서 문자를 조립해주면 될 듯?? 근데 여러가지 조건이 있었다.

모음을 하나이상 포함해야 된다구?

그럼 만들어진 Combinations에서 모음 하나 이상인 것만 출력하지 뭐.

자음을 두개이상 포함해야 된다구?

그럼 만들어진 Combinations에서 자음 두개 이상인 것만 출력하지 뭐.

라고 생각했다가. 전체 갯수 - 모음 갯수 > 2이기만 하면 된다는 생각! (모음이 아니면 무조건 자음이기 때문에!)

증가하는 순서대로?

그럼 입력받은 문자열 정렬하고 Combinations 하면 사전순으로 될듯 🙂 그럼 끝!

자드가자 🖖

기본 입출력 정의

파이썬으로 처음 문제풀이기 때문에 입력을 어떻게 받아야될지 고민하다가

래영이형 코드를 훔쳐왔다.

import sys

l, n = map(int, sys.stdin.readline().split())
alphabets = list(map(str, sys.stdin.readline().split()))

print(alphabets)

sys.stdin.readline()을 통해서 입력을 받으면 input()보다 더 빨리 입력받을 수 있다는 사실!

역시 이런거 하나 있을 줄 알았어. C++에서 ios::sync_with_stdio(false); cin.tie(nullptr) 같은 것...

Combinations만들기

Python의 itertools에서 Combination 가져오기~

import sys
from itertools import combinations

l, n = map(int, sys.stdin.readline().split())
alphabets = list(map(str, sys.stdin.readline().split()))

print(alphabets)
alphabets.sort()
res = []

for comb in combinations(alphabets,l):
    res.append(comb);

print(res)

조건에 맞는 Combinations

조건에 맞는 것만 res에 넣기 위해서 chk()라는 함수를 만들었다.

def chk(comb):
    vowel = 0
    for c in comb:
        if c in 'aeiou':
            vowel += 1

    if vowel == 0:
        return False

    if len(comb) - vowel < 2:
        return False

    return True

모음 갯수와 자음 갯수 전부 만족! 그리고 조합 만들때 조건 검사해서 res에 넣기!

import sys
from itertools import combinations

l, n = map(int, sys.stdin.readline().split())
alphabets = list(map(str, sys.stdin.readline().split()))

print(alphabets)
alphabets.sort()
res = []

def chk(comb):
    vowel = 0
    for c in comb:
        if c in 'aeiou':
            vowel += 1

    if vowel == 0:
        return False

    if len(comb) - vowel < 2:
        return False

    return True

for comb in combinations(alphabets,l):
    print(comb)
    if not chk(comb):
        continue
    res.append(comb)

for r in res:
    print(''.join(r))

잘 되는 것 같다.

🏎️ 제출하러 가즈아~ 🚗

맞았다 :) 예전에 풀었던 방식도 있었는데... 그 방식은 설명이 너무 복잡하고 코드도 길고 하튼...많이 별로다. 코드길이 확 줄고....시간도 확 줄고... 그래서 그냥 간단한 방식으로 한번 더 풀었다!

💥FeedBack💥

사실 피드백을 쓰기 위해 이 글을 쓴다고 해도 과언이 아님.

1. 작은 기능을 하는 것은 chk()와 같은 함수로 만들기 → 함수화

이건 뭐 더 이야기 할 것도 없지

2. 변수 이름을 이쁘게 만들고 코드 줄이기.

ans, res, ret → 정답 or 리턴값

p, k, x → 대충 쓰는 변수

pos, idx → 인덱스 가리킬 때

char은 c, string은 s

항상 이쁘고 멋있는 코드에 대한 생각이 많았는데 래영이형하고 이야기하고, 래영이형 코드를 보면서 점점 이쁘고 멋있고 보기 쉬운 코드에 대한 생각이 점점 잡혀가는 것 같다.

실제로 개발을 할때는 몰라도, 알고리즘 문제를 풀 때는 사람들끼리 통용되는 변수가 있는 것 같다. EX) ans..등

그리고 결국에는 코드양이 적을수록 보기 편하다는 생각이 들었다. 완전 숏코팅은 좀 그렇지만

읽어야 할 코드가 적을수록 알기 쉽겠지... 처음 푼 코드는 정말 길어서....나도 다시 보기 싫을 정도였다. 다시 봤는데 절대 이해 못함. 반성해 반성‼️ 🙇‍♂️

3. 남들이 작성한 코드를 5개정도 보고 남들 코드 이해한 것 다시 간결하게 작성해보기

이게 제일 중요한 듯. 혼자 풀고 맞았다고 나 좀 쩌는듯? 하기 보다는 다른 사람들이 푼 방식을 확인하고 더 나은 풀이 방법을 찾는게 실력 발전에 이바지한다고 한다. 항상....느끼지만 문제 풀어서 맞았습니다!! 뜨면 더이상 아무것도 하기 싫음... 앞으로 1. 래영이형 코드 2. 꾸준함 블로그 3. 유성장 블로그 이렇게 세번 코드만 찾아봐도 괜찮을 것 같다.

4. 실천하기....

아무래도 실천이 젤 중요하지요. 😩 항상 피드백 도와주는 래영이형 세상에서 제일 고맙다 🙂 🙏

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

어떻게 풀 것인가?

과정을 생략하고 코드를 보고싶은 분은 *맨 아래로 *

접근 방법 : Dynamic Programming

보자마자 생각했다. Dynamic Programming. 2 * n 의 타일을 만드는 갯수는 2 * (n-1) 또는 2 * (n-2)의 갯수와 관계가 있을것이 분명하다! 이 관계를 찾아야 한다.

기본 입출력 정의

#include <iostream>

using namespace std;

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

    int t; cin>>t;
    int dp[t+1];

        dp[1] = 1;
        dp[2] = 2;

}

t를 입력받아 dp배열을 생성하고 dp[1] = 1, dp[2] = 2로 초기화 한다.

💢 타일이 중복과 추가가 되는구나💢

처음에는 n번째 타일의 양쪽에 세로 타일을 붙이는 것을 생각했다.

근데 중복되는 타일과 추가되는 타일이 생긴다. 중복되는 타일과 추가되는 타일에 대한 규칙을 찾기 어려웠다... 타일을 양쪽에 붙인다는 규칙으로는 규칙성이 생기지 않는 것 같다. → 타일을 한방향(오른쪽)으로 붙이자!

한방향으로 타일 붙이기

그러면 한방향으로 타일을 2개(세로+세로 / 가로 + 가로)를 붙일 것인지? 혹은 타일을 1개를 붙일 것인지 생각해야 했다.

n번째 타일은 n-2번째 타일에서 (세로+세로)타일을 붙이거나 (가로+가로)타일을 붙이는 것이다. ➕ n번째 타일은 n-1번째 타일에서 (세로) 타일을 붙이는 것이다.

그림에서 보이는 것 처럼 중복이 발생한다.

중복은 어떻게 이루어지나?

중복이 되는 타일만 제거를 하면 될 것 같다. 중복이 어떻게 생기는지 알아보기 위해서 다 그려봤다.

그리다 보니 드는 생각 세로 타일로 끝나는 타일만 ➕ 맨 오른쪽 세로타일이 2개 이상인 타일 만 중복이 일어난다!

💥 결론 : n-2번째에서 세로타일을 두개 붙이는 타일은 중복이 일어난다!

그렇다. 그럼 dp식을 완성해보자. dp[n] = dp[n-2] * 2 (n-2 타일에 세로 + 세로, 가로 + 가로 붙이기) ➕ dp[n-1] (n-1 타일에 세로 붙이기) ➖ dp[n-2] (n-2 타일에 세로 + 세로를 붙이는 건 중복된다.)

dp[n] = dp[n-2] + dp[n-1]

#include <iostream>

using namespace std;

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

    int t; cin>>t;
    int dp[t+1];

    dp[1] = 1;
    dp[2] = 2;

    for(int i=3;i<t+1;i++){
        dp[i] = dp[i-2] + dp[i-1];
    }

    cout<<dp[t];
}

예제입력은 잘 돌아간다. 하지만 섣부르게 제출하면 바로 틀립니다..... 😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭

네 그렇습니다. 어쩐지 바로 그냥 틀려버리더라

바로 틀린다 → 큰 수의 입력에서 틀린다!

제출하기 전에 Check할 것!

1. 입력, 계산, 출력값이 int의 자료를 넘어가는가? (int = 2,147,483,648)
2. 작은 값의 입력을 잘 해결하는가? (1, 2 정도의 입력을 해보자)
3. 불필요한 log들 전부 지우고 제출해봅시.
4. ➕ 문제에서 추가로 요구하는 요구사항은 없는가?

코드를 수정해준다.

#include <iostream>

using namespace std;

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

    int t; cin>>t;
    int dp[t+1];

    dp[1] = 1;
    dp[2] = 2;

    for(int i=3;i<t+1;i++){
        dp[i] = (dp[i-2] + dp[i-1]) % 10007;
//        dp[i] = dp[i-2] + dp[i-1];
    }

    cout<<dp[t];
}

👨‍💻 재도전! 🚙

과 함께 성공했습니다 :)

🌕 FULL CODE ⛽

#include <iostream>

using namespace std;

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

    int t; cin>>t;
    int dp[t+1];

    dp[1] = 1;
    dp[2] = 2;

    for(int i=3;i<t+1;i++){
        dp[i] = (dp[i-2] + dp[i-1]) % 10007;
//        dp[i] = dp[i-2] + dp[i-1];
    }

    cout<<dp[t];
}

🤜 FeedBack 🤛

1. 채점 시간이 엄청 오래 걸리던데 왜그런걸까..?
2. 문제 제대로 읽자 ^^......ㅜㅜㅜㅜㅜ

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

어떻게 풀 것이냐?

과정을 생략하고 풀이를 보고싶은 사람은 맨 아래로

접근방식 : N/2 x N/2의 문제로 나누어 생각하면 편하겠다!

NxN 의 정사각형에서 하나의 숫자로 이루어지지 않았다면? → N/2 x N/2 의 정사각형 4개로 쪼개서 다시 검사하자! → 재귀...? 라고 생각이 들었다.

재귀함수를 정의할 때 가장 중요하게 생각하는 것은

1. 전달되는 파라미터
2. 탈출조건
3. 반환값의 유무

이다.

1. 재귀함수의 파라미터로 반으로 짤린 정사각형의 2차원 배열을 전부 전달하기보다는 배열의 인덱스를 전달하는 것이 좋겠다. 배열의 인덱스를 전달하면 검사해야하는 정사각형의 크기를 알 수 없다! 크기가 필요하다.

2. 탈출조건은 정사각형의 크기가 1일때!

3. 파란색 종이🔷 와 흰색 종이 ⬜ 의 갯수를 반환하면 좋겠다고 생각했다.

일단은 이렇게 생각했다. 코딩을 하면서 바뀔 수 있겠다. 그럼 일단 입출력부터 정의해보자.

기본 입출력 정의

#include <iostream>
#include <vector>

using namespace std;

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

    int t; cin>>t;

     //2차원 vector 동적 할당.
    vector<vector<int>> v(t,vector<int>(t,0));

    for(int i=0;i<t;i++) {
        for (int j = 0; j < t; j++) {
            cin >> v[i][j];
        }
    }

    for(int i=0;i<t;i++) {
        for (int j = 0; j < t; j++) {
            cout<<v[i][j]<<" ";
        }
        cout<<"\n";
    }
}

vector로 입력받을까 array로 입력받을까 고민했는데 함수에 동적 2차원 배열을 전달하는 방법을 몰라서 vector로 선언. vector가 편합니다...함수에 2차원 배열 전달 하는 법 몰라요 😭

재귀함수 정의

(파란색 종이🔷 의 갯수, 흰색 종이⬜ 의 갯수) 두개를 반환해야하니 pair<int,int>를 생각했다.

Parameter 로는 가로 인덱스, 세로 인덱스, 정사각형 사이즈, 2차원 배열 전체 를 전달받자!

🛑 여기서 잠깐! 🛑

원래는 재귀함수에서 파란색 종이🔷 의 갯수, 흰색 종이⬜ 의 갯수를 반환하고, 더해주는 재귀함수를 생각했다.

근데 종이 갯수를 저장하는 배열을 전역변수로 선언하여 재귀함수에서 접근할 수 있도록 하면 편하겠다는 생각이 들었다!

흰색종이는 0, 파란색 종이는 1이니

arr[0] → 흰색 종이 갯수

arr[1] → 파란색 종이 갯수

🙂 이거지

🚢 Keep going

배열을 검사하고, 하나의 종이로 이루어져 있지 않으면 재귀함수 4개를 호출한다.

검사를 어떻게 할지 고민하다가 이전값하고 다르면 하나의 종이로 이루어져 있지 않다고 생각하기로 했다!

void recur(vector<vector<int>> &v,int horizonIndex, int verticalIndex, int squareSize){
    if(squareSize == 1){
        //인덱스의 종이 숫자++
        white_blue[v[verticalIndex][horizonIndex]] ++;
    }

    // 종이 검사하기
    int beforeValue = v[verticalIndex][horizonIndex];
    for(int i=0;i<squareSize;i++){
        for(int j=0;j<squareSize;j++){
            if(beforeValue == v[verticalIndex+i][horizonIndex+j]) {
                if(i==squareSize-1 && j==squareSize-1){
                    cout<<"검사 통과!"<<endl;
                    white_blue[beforeValue]++;
                }
                beforeValue = v[verticalIndex+i][horizonIndex+j];
            }
            else{
                recur(v,horizonIndex,verticalIndex,squareSize/2);
                recur(v,horizonIndex+(squareSize/2),verticalIndex,squareSize/2);
                recur(v,horizonIndex,verticalIndex+(squareSize/2),squareSize/2);
                recur(v,horizonIndex+(squareSize/2),verticalIndex+(squareSize/2),squareSize/2);
                break;
            }
        }
    }
}

이 함수를 호출해주자.

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

    int t; cin>>t;

    vector<vector<int>> v(t,vector<int>(t,0));

    for(int i=0;i<t;i++) {
        for (int j = 0; j < t; j++) {
            cin >> v[i][j];
        }
    }

    for(int i=0;i<t;i++) {
        for (int j = 0; j < t; j++) {
            cout<<v[i][j]<<" ";
        }
        cout<<"\n";
    }

    recur(v,0,0,t);
    cout<<"white : "<<white_blue[0]<<"\n";
    cout<<"blue : "<<white_blue[1]<<"\n";

    return 0;
}

우오아아아...한번에 에러없이 예제가 풀렸다!

제출하기 전에 Check할 것!

1. 입력, 계산, 출력값이 int의 자료를 넘어가는가? (int = 2,147,483,648)
2. 작은 값의 입력을 잘 해결하는가? (1, 2 정도의 입력을 해보자)
3. 불필요한 log들 전부 지우고 제출해봅시당.

🙆 제출하러 갑시다 🤘

제출해도 정답이였다 :) 조아요~ ☺️

😀 FULL CODE 🤨

#include <iostream>
#include <vector>

using namespace std;

int white_blue[2] = {0,0};

void recur(vector<vector<int>> &v,int horizonIndex, int verticalIndex, int squareSize){
    if(squareSize == 1){
        //인덱스의 종이 숫자++
        white_blue[v[verticalIndex][horizonIndex]] ++;
        return;
    }

    // 종이 검사하기
    int beforeValue = v[verticalIndex][horizonIndex];
    for(int i=0;i<squareSize;i++){
        for(int j=0;j<squareSize;j++){
            // 이전값과 같으면??
            if(beforeValue == v[verticalIndex+i][horizonIndex+j]) {
                if(i==squareSize-1 && j==squareSize-1){
                    //검색이 끝나면 종이 ++
                    white_blue[beforeValue]++;
                }
                //이전값 갱신!
                beforeValue = v[verticalIndex+i][horizonIndex+j];
            }
            else{
                //재귀는 1사분면, 2사분면, 3사분면, 4사분면 4개!
                recur(v,horizonIndex,verticalIndex,squareSize/2);
                recur(v,horizonIndex+(squareSize/2),verticalIndex,squareSize/2);
                recur(v,horizonIndex,verticalIndex+(squareSize/2),squareSize/2);
                recur(v,horizonIndex+(squareSize/2),verticalIndex+(squareSize/2),squareSize/2);
                return;
            }
        }
    }
}

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

    int t; cin>>t;

    vector<vector<int>> v(t,vector<int>(t,0));

    for(int i=0;i<t;i++) {
        for (int j = 0; j < t; j++) {
            cin >> v[i][j];
        }
    }

    recur(v,0,0,t);
    cout<<white_blue[0]<<"\n"<<white_blue[1];
    return 0;
}

🤜 FeedBack 🤛

1. 솔직히 지금까지 재귀함수는 별로 좋지 않다고 생각하고 있었는데 재귀함수는 강력한 것 같다. 큰 범위 → 작은 범위로 쪼개지는 문제는 재귀를 통해서 해결할 수 있겠다!

2. 코드가 못생겼다. 다른 사람들이 잘 알아볼 수는 있을까? 이쁜 코드를 찾아보고 이쁜 코드를 작성하는 방법을 정리해야겠다.

Raeyoung's feedback

1. 이전 값과 계속 비교할 필요가 없다! 그냥 첫번째 값과 계속 비교하면 됨 → 이전값 갱신이 불필요한 코드라는 것.

2. vertical.... horizon.... 괜히 코드만 길어지는 것. → 편하게 matrix[y][x]로 가자.

3. const nl = "\n"; cout << nl;

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

어떻게 풀 것이냐!

과정을 생략하고 코드만 보고싶으신 분은 맨 아래로

DFS문제이지만 그래프가 아니라 좌표기반으로 되어있다. 일단 입력받는 것 부터가 힘들겠는걸...?

❗ 배열이 좌표로 주어지면 배열을 +2 size만큼 더 생성해주기

항상 좌표 문제는 입력받은 좌표보다 +2 만큼 배열을 만들어 주는게 좋다고 생각한다. 좌표를 탐색할 때 위, 아래, 오른쪽, 왼쪽을 탐색하다 보면 배열의 범위를 벗어날 때가 많고, 런타임에러가 일어나거나 쓰레기값을 가져오기 때문이다. 그걸 방지하려면 많은 IF문을 사용해서 범위를 확인해줘야 하는데 그게 귀찮다.

‼️ 좌표 기반으로 DFS를 사용하자. X,Y를 저장할 수 있는 Stack이 필요하다.

DFS는 Stack, BFS는 Queue를 사용한다. 연결되어 있는 블록을 찾는데는 DFS나 BFS나 둘다 상관 없지만, 나는 DFS가 더 쉽다고 생각해서 DFS를 사용해서 풀었다. X,Y를 Stack에 저장하기 위해 Pair를 사용했다. Pair는 <utility> 안에 있다.

⁉️ 기본 생각 : 주어진 좌표에서 블록들을 찾아 다른 배열에 표시해 놓으면 되겠다!

주어진 지도에서 연속된 블록들을 DFS를 통해서 검사하는 과정에서 다른 지도에 표시를 해놓고, 주어진 지도에 모든 좌표를 검사 완료 했으면 다른지도를 보면서 단지의 갯수와 단지 안의 집의 갯수를 검사하자!

준비물 : x,y를 저장할 수 있는 Stack, 주어진 지도, 다른 지도 ⇒ Stack, arr[][], checked[][] 좋아 가보자. 👟

기본 입출력 정의

#include <iostream>
#include <stack>
#include <utility>

using namespace std;

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

    int t;cin>>t;
    int arr[t+2][t+2];
    int checked[t+2][t+2];
    int cnt = 1;

        //dfs에 필요한 stack
    stack<pair<int,int>> s;
        //정보를 저장하는 vector
    vector<int> v;

    for(int i=0;i<t+2;i++){
        fill_n(arr[i],t+2,0);
        fill_n(checked[i],t+2,0);
    }

    for(int i=1;i<t+1;i++){
        string a; cin>>a;
        for(int j=0;j<a.size();j++){
            arr[i][j+1] = a[j] - '0';
        }
    }

        for(int i=0;i<t+2;i++){
        for(int j=0;j<t+2;j++){
            cout<<arr[i][j];
        }
        cout<<'\n';
    }
    cout<<"\n";
}

입력은 잘 받아진다. 🙂
0으로 둘러쌓여진 것을 볼 수 있다. 저 0이 어떤 완충재 역할을 해줄 것이다.

DFS사용하기

원래는 dfs함수를 만들어서 사용하고 싶엇는데 2차원 배열을 함수로 어떻게 전달해야할 지 몰라 그냥 main문에 다 때려 박았다. ㅇㅇ 주어진 지도(arr[][]) 을 모두 검사해야하기 때문에 2중 포문 을 돌아준다. 이때! i=1부터, i<t+1까지 돌아야한다! 배열의 크기를 +2만큼 추가해줬으니까! arr[i][j]가 1이면 이제 연결된 블록이 있는지 탐색을 시작한다. 처음에는 DFS를 끝내고 checked를 검사하면서 답을 낼려고 햇는데 생각을 해보니 그냥 DFS하는 과정에 Vector에 count를 한 것을 넣어주면 되겠더라.

for(int i=1;i<t+1;i++){
        for(int j=1;j<t+1;j++){
            if(arr[i][j] == 0) continue;
            else{
                //arr[i][j]가 숫자일 때
                if(checked[i][j] == 0){
                    //방문한 적 없는 곳이라면 탐색 시작.
                    s.push(make_pair(i,j));
                    int chk = 0;

                    while(!s.empty()){
                        pair<int,int> p = s.top();
                        s.pop();

                        int x = p.first;
                        int y = p.second;

                        if(checked[x][y] != 0) continue;

                        checked[x][y] = cnt;
                        chk++;

                                                //상하좌우를 검사하고, 있다면 stack에 넣어준다. 
                        if(arr[x+1][y] != 0) s.push(make_pair(x+1,y));
                        if(arr[x][y+1] != 0) s.push(make_pair(x,y+1));
                        if(arr[x-1][y] != 0) s.push(make_pair(x-1,y));
                        if(arr[x][y-1] != 0) s.push(make_pair(x,y-1));
                    }
                    v.push_back(chk);
                    chk = 0;
                    cnt++;
                }else{
                    continue;
                }
            }
        }
    }

하고 나서 정답 출력.

sort(v.begin(),v.end(),less<int>());

cout<<v.size()<<"\n";

for(int i=0;i<v.size();i++){
    cout<<v[i]<<"\n";
}

좋다.

제출

<algorithm>을 include안해줘서 컴파일 에러가 떴지만 그래도 정답이다 😂

😎FULL CODE💯

#include <iostream>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>

using namespace std;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;cin>>t;
    int arr[t+2][t+2];
    int checked[t+2][t+2];
    int cnt = 1;

    stack<pair<int,int>> s;
    vector<int> v;

    for(int i=0;i<t+2;i++){
        fill_n(arr[i],t+2,0);
        fill_n(checked[i],t+2,0);
    }

    for(int i=1;i<t+1;i++){
        string a; cin>>a;
        for(int j=0;j<a.size();j++){
            arr[i][j+1] = a[j] - '0';
        }
    }

    for(int i=1;i<t+1;i++){
        for(int j=1;j<t+1;j++){
            if(arr[i][j] == 0) continue;
            else{
                //arr[i][j]가 숫자일 때
                if(checked[i][j] == 0){
                    //방문한 적 없는 곳이라면
                    s.push(make_pair(i,j));
                    int chk = 0;

                    while(!s.empty()){
                        pair<int,int> p = s.top();
                        s.pop();

                        int x = p.first;
                        int y = p.second;

                        if(checked[x][y] != 0) continue;

                        checked[x][y] = cnt;
                        chk++;

                        if(arr[x+1][y] != 0) s.push(make_pair(x+1,y));
                        if(arr[x][y+1] != 0) s.push(make_pair(x,y+1));
                        if(arr[x-1][y] != 0) s.push(make_pair(x-1,y));
                        if(arr[x][y-1] != 0) s.push(make_pair(x,y-1));
                    }
                    v.push_back(chk);
                    chk = 0;
                    cnt++;
                }else{
                    continue;
                }
            }
        }
    }

//    for(int i=0;i<t+2;i++){
//        for(int j=0;j<t+2;j++){
//            cout<<arr[i][j];
//        }
//        cout<<'\n';
//    }
//    cout<<"\n";
//
//    for(int i=0;i<t+2;i++){
//        for(int j=0;j<t+2;j++){
//            cout<<checked[i][j];
//        }
//        cout<<'\n';
//    }

    sort(v.begin(),v.end(),less<int>());

    cout<<v.size()<<"\n";

    for(int i=0;i<v.size();i++){
        cout<<v[i]<<"\n";
    }

}

비고

어제 풀었는데 오늘 정리를 하려고 하니까 정리가 잘 안된다. 생각의 흐름에 구멍이 생기더라 😢 다음부터는 하나씩 정리를 할 때는 꼭 문제를 풀면서 의식의 흐름에 따라 정리를 할 수 있도록 해야겠다.

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다.

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.

출력

표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다.

어떻게 풀 것이냐

과정을 생략하고 코드를 보고싶은 분은 ** 맨 아래로 **

기본 입출력 정의

#include <iostream>
#include <algorithm>

using namespace std;

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

    int t; cin>>t;
    int arr[t][2];

    for(int i=0;i<t-1;i++){
        cin>>arr[i][0];
    }

    for(int i=0;i<t;i++){
        cin>>arr[i][1];
    }
    //arr[i][0] -> 거리, arr[i][1] -> 기름값.
    arr[t-1][0] = 0;

    for(int i=0;i<t;i++){
        cout<<"|"<<arr[i][1]<<"|"<<"-"<<arr[i][0]<<"-";
    }
}

접근 방식

1. 기름을 가장 싼곳에서 가장 많이 채우는게 이득이다.
2. 가장 싼 곳까지는 그 전 중에서 가장 싼 곳에서 채우는게 이득이다.
3. 이 과정을 반복하면 될 것 같다.

먼저 기름이 가장 싼 곳을 찾아야한다.

int minOil = 1000000000;
int index = t;

for(int i=0;i<index;i++){
    minOil = min(minOil,arr[i][1]);
    index = i;
}

그리고 그 곳에서부터 끝까지 가는데 필요한 기름을 산다.

for(int i=index;i<t;i++){
    sum += (arr[i][0] * minOil);
}

이 과정을 한번만 하면 당연히 안된다.

언제까지 반복할 것이냐?

⚠️여기서 잠깐!⚠️

풀다가 이상한 생각이 들었다. 시간복잡도가 엄청나게 커지는 생각을 했다.

최악의 경우 n^2이 되어버린다.

🙋‍♂️ : 그럼 어떻게 푸누.....

👿 : Greedy Algorithm을 사용해서 풀어야지

🙋‍♂️ : ㅓ죠??그게 뭐죠...?

1. 처음에 일단 기름을 사서 출발한다. 기름이 없는데 어쩔꺼야!
2. 가다가 도시에 도착해서 기름값을 본다. 기름이 전 도시보다 비싸다? → 시간여행 ⏳ 을 해서 전 도시에서 기름을 더 많이 사온다.
3. 기름이 전 도시보다 싸다? → 그럼 이제 여기에 check point를 찍는다. 시간여행을 여기로 오면 된다.
4. 반복한다.

👼 : 이거지 이거지

int oilPrice = arr[0][1];
int sum = 0;

// 3. 반복한다.
for(int i=0;i<t;i++){
    // 1. 도시에 도착했을 때, 기름 가격을 비교한다. 싼곳의 기름을 산다.
    oilPrice = min(oilPrice,arr[i][1]);

    // 2. 기름으로 간다.
    sum += (arr[i][0] * oilPrice);
}

갑자기 엄청 간단해졌다. 예제도 돌려보니까 맞다. 제출 가기 전에 입력이 최소값일 때를 생각해보자. 나름대로 테스트 해봤다 ( 귀찮다 💦 )

🙇‍♂️제출!

5%에서 틀렸음을 기억하자 어디서 틀렸는지 알면 어떤 반례가 있는지 조금이나마 유추를 해볼 수 있다. 왜 틀렸지...?

👊재도전✊

쓸데없는 반복문이 돌아가는건가? t번째 도시에서는 값을 비교할 필요도, 기름으로 갈 필요도 없으니 반복문을 t-1번만 돌아야지 😂

// 3. 반복한다.
for(int i=0;i<t-1;i++){
    // 1. 도시에 도착했을 때, 기름 가격을 비교한다. 싼곳의 기름을 산다.
    oilPrice = min(oilPrice,arr[i][1]);

    // 2. 기름으로 간다.
    sum += (arr[i][0] * oilPrice);
}

바로 틀렸다.

👊재도전2✊

문제를 정독했다. 여전히 모르겠다. 제한 사항에 문제가 있을까? 문제를 찾았다고 생각했다! 아직 정답은 아니니까. sum의 값이 int라서 범위의 문제가 있다!!! int 값의 범위는 2,147,483,647이다. 기름값이 최대값이 10억이기 때문에 범위를 순식간에 넘어버릴 수 있다! int sum = 0; 을 long long sum = 0; 으로 바꿔준다 제발...제발... 🙏 🤷‍♂️ 😭

또 틀렸다.

이제는 절박해졌다.

👊재도전3✊

혹시 몰라서 int 자료형을 전부 long long으로 바꿔봤다.

연산에 관여하는 모든 변수들이 long long이 아니라서 데이터가 문제가 생길 수 있다고 생각했다.

결국엔 int의 범위 문제였다.

👨‍💻Full Code👨‍💻

#include <iostream>
#include <algorithm>

using namespace std;

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

    long long t; cin>>t;
    long long arr[t][2];

    for(long long i=0;i<t-1;i++){
        cin>>arr[i][0];
    }

    for(long long i=0;i<t;i++){
        cin>>arr[i][1];
    }
    //arr[i][0] -> 거리, arr[i][1] -> 기름값.
    arr[t-1][0] = 0;

//    for(int i=0;i<t;i++){
//        cout<<"|"<<arr[i][1]<<"|"<<"-"<<arr[i][0]<<"-";
//    }
//    cout<<endl;

    long long oilPrice = arr[0][1];
    long long sum = 0;

    // 3. 반복한다.
    for(long long i=0;i<t-1;i++){
        // 1. 도시에 도착했을 때, 기름 가격을 비교한다. 싼곳의 기름을 산다.
        oilPrice = min(oilPrice,arr[i][1]);

        // 2. 기름으로 간다.
        sum += (arr[i][0] * oilPrice);
    }

    cout<<sum;
}

⚰️FeedBack 🖌️

1. int 의 범위는 21억정도 까지지만, 10억 정도의 연산을 사용하게 된다면 과감히 long long을 사용하자. 래영이형 깃헙 가서 long long 정의하는 거나 가져와야겠다.
2. 생각하는데로 코딩하다 보면 시간복잡도 터지겠다. 그리디 알고리즘을 사용해서 푸는 방법에 익숙해지자.

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

어떻게 풀 것이냐?

과정을 생략하고 코드를 보고싶은 분은 여기로

기본 입출력 정의

#include <iostream>
#include <algorithm>

using namespace std;

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

    int t;
    cin >> t;

    int arr[t];

    for (int i = 0; i < t; i++) {
        cin >> arr[i];
    }

    for (int i = 0; i < t; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

접근 방식

계단문제(BOJ:2579번)와 비슷하다고 생각했다. 연속해서 3개의 포도잔을 마실 수 없다 == 연속해서 계단 3개를 오를 수 없다.

동적 프로그래밍을 사용하는 문제에서는 보통 연속해서 3개의 어떤 행위를 할 수 없는 것 같다.

최대의 포도주를 시식해야되니까(😏 주당이네) i 번째의 행위를 할 때, 최고의 i-1 또는 i-2번째 행위를 고려하면 된다. DP의 식을 세워야 한다.

3번째 포도주를 마실때를 생각해보자. 1 번째, 2 번째, 3 번째 순서대로 전부 마시고 싶지만,,,, 취하니까 못먹게 하나보다. 그렇다면 생각해야한다. 1번째, 3번째 포도주를 마실것이냐! 아니면 2번째, 3번째 포도주를 마실것이냐! 이 생각부터 시작했다. 1 → 3으로 연속적이지 않게 포도주를 마실것인지, 2 → 3으로 연속으로 포도주를 마실 것인지 생각을 해야한다! 그렇다면 좀 더 자세히 생각해보자.

1. i 번째 포도주를 마실 때, 연속 첫번째로 마시는 경우, i-2번째의 DP값에 현재 포도주 양을 더한다.
2. i 번째 포도주를 마실 때, 연속 두번째로 마시는 경우, i-1번째의 DP값에 현재 포도주 양을 더한다.

즉, DP배열은 2차원 배열로 필요할 것 같다.

dp[i][0] → i 번째 포도주를 첫 번째로 마시는 경우

dp[i][1] → i 번째 포도주를 두 번째로 마시는 경우

dp[i][0] → i 번째 포도주를 첫번째로 마시는 경우! i-1 번째 포도주는 마시면 안된다! 그러므로 i-2번째의 포도주를 마시는데, i-2 번째의 포도주를 어떻게 먹든 최대값으로 먹는 경우를 골라야 하니

max( dp[i-2][0](첫번째로 마신 경우), dp[i-2][1](두번째로 마신 경우) )

둘중에서 큰 값을 골라보자.

int dp[t][2];

dp[0][0] = arr[0];
dp[0][1] = 0;

dp[1][0] = arr[1];
dp[1][1] = dp[0][0] + arr[1];

for(int i=3;i<t;i++){
    //dp[i][0] => i번째 요소를 처음 선택하는 경우
    dp[i][0] = max(dp[i-2][0],dp[i-2][1]) + arr[i];

    //dp[i][1] => i번째 요소를 2번째로 선택하는 경우
    dp[i][1] = dp[i][0] + arr[i];
}
// t번째에서 큰걸 고른다.
cout<<max(dp[t-1][0],dp[t-1][1]);

오잉...틀렸다.

뭐가 잘못된 걸까?? 😰

어디서, 뭐가 잘못된거지...?

일단 오타가 있었다.

dp[i][1] = dp[i][0] + arr[i]; → dp[i][1] = dp[i-1][0] + arr[i];

그랬더니 값이 더 이상하게 나온다. 😭

두번째 오타를 발견했다.

for문의 i 가 3부터 시작한다. → for 문의 i를 2로 바꿔줘야한다.

어쩐지 쓰레기값이 계속 나오더라.

근데 t번째가 29, 32이다! 왜지?

생각을 해봤더니...

굳이 t번째가 마지막이 될 필요가 없지 않나? t-1번째가 마지막이 되어도 되잖아?

예제도 그렇다. t번째가 1이니까

t-1번째를 못먹고 t를 먹기보다는

t를 포기하고 t-1번째를 먹는다!

이렇게 될 수 있다고 생각했으니 dp[t] 와 dp[t-1]중에서 max를 고르면 되겠다.

코딩해보자.

int a = max(dp[t-1][0],dp[t-1][1]);
int b = max(dp[t-2][0],dp[t-2][1]);

cout<<max(a,b)<<endl;

이거지 이거지 👺 정답이다!

이제 제출하기 전에 체크하자 (특히 범위....주유소 문제에서 호되게 당했다.)

1. 입력값과 출력값의 범위가 주어진 자료형(Int) 를 초과하는가? 1 ≤ n ≤ 10,000, 0 ≤ 포도주의 양 ≤ 1,000이니 최대 SUM은 1,000 ✖️ 10,000 = 10,000,000(천만)이니 초과 X 인 것 같다(확실하지 않음...)

2. 최소값을 입력 받았을 때, 최대값을 입력 받았을 때 잘 동작하는가? 최소값 : 1을 입력 받았을 때!

그렇다. 마지막에 dp[i-1]을 탐색하기 때문에 쓰레기값이 나온다. 수정하자.

    int a = max(dp[t-1][0],dp[t-1][1]);
    int b = 0;

    if(t == 1){
        b = 0;
    }else{
        b = max(dp[t-2][0],dp[t-2][1]);
    }

    cout<<max(a,b)<<endl;

최대값은 테스트가 힘드니까...(10,000 번 입력할꺼야? 👊 💢 )

3. 반례가 있는가?

   일단 생각나는건 없다!

처절한 실패....

2%에서 틀렸다. 기억하자.

3. 반례. 연속으로 안 먹는 경우.

누군가 말했다. 안먹을 수 도 있다고..... 😢 아니 왜 안먹고 그르세요... 200 400 1 2 400 500 인 경우를 생각해보면 1, 2를 먹는건 손해 of 손해다. 나도 그렇게 생각한다. 분명히 안먹고 지나가는 경우가 있다.

그렇다면 또 생각해야 하는건 3번 이상 안먹고 지나가는 경우가 있나? → 200 400 1 1 1 400 500인 경우에는 중간에 1을 고르고 가면 되니까....3번 이상 안먹고 지나가는 경우는 없다! 라고 생각했다.

그럼 바로 코딩해보자.

2번이상을 연속으로 안먹는 경우? → 구글링을 통해서 해법을 찾았다. dp[i] = max(dp[i],dp[i-1])이라고 한다

왜 그런지 솔직히 아직까지 이해가 안된다. 400을 고르는 순간에 2를 고른것과 비교를 한다? 나는 아직 많이 부족한 것 같다. 더 열심히 공부하자.

👨‍💻FULL CODE👨‍💻

#include <iostream>
#include <algorithm>

using namespace std;

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

    int t;
    cin >> t;

    int arr[t];

    for (int i = 0; i < t; i++) {
        cin >> arr[i];
    }

//    for (int i = 0; i < t; i++) {
//        cout << arr[i] << " ";
//    }
//    cout << endl;

    int dp[t][2];

    dp[0][0] = arr[0];
    dp[0][1] = 0;

    dp[1][0] = arr[1];
    dp[1][1] = dp[0][0] + arr[1];

    for(int i=2;i<t;i++){
        //dp[i][0] => i번째 요소를 처음 선택하는 경우
        dp[i][0] = max(dp[i-2][0],dp[i-2][1]) + arr[i];

        //dp[i][1] => i번째 요소를 2번째로 선택하는 경우
        dp[i][1] = dp[i-1][0] + arr[i];

        //세개 이상을 안 고르고 건너뛸 수 있나? -> 세개 이상은 건너뛸 필요가 없다. 중간을 고르면 되그등요
        dp[i][0] = max(dp[i][0],dp[i-1][0]);
        dp[i][1] = max(dp[i-1][1],dp[i][1]);

    }

    int a = max(dp[t-1][0],dp[t-1][1]);
    int b = 0;

    if(t == 1){
        b = 0;
    }else{
        b = max(dp[t-2][0],dp[t-2][1]);
    }

    cout<<max(a,b)<<endl;

    return 0;
}

💪FEED BACK🧗

1. 계단문제랑 비슷한 줄 알았더니만 dp[i] = max(dp[i],dp[i-1])이라는 함정이 숨어있었다.

   • 계단을 오르는 경우에는 무조건 밟지 않으면 올라갈 수 없다. (무조건 연속적으로 밟아야 한다.)
   • 포도주 같은 경우 마셔도 되고 안마셔도 된다. 마시지 않는 것이 오히려 최대가 될 수 있다. (연속적이지 않을 수 있다!) 왜 dp[i] = max(dp[i],dp[i-1]) 이렇게 되는지를 고민해야겠다.

2. 마지막 검토하는 순서를 만들었다. 1) int범위 확인 2) 최솟값과 최댓값 확인 3) 반례 확인 추가로 검토방법들을 만들어야겠다. 어처구니 없는 실수를 하지 않기 위해서.

3. 나는 아직 많이 부족하구나...이해를 못하다니

1-1. Digital Computer Digital Computer = Digital System

1-2. Logic Gates 모든 Digital System은 Logic Gates로 이루어져 있다. 즉 Logic Gates는 Digital System의 기본 단위이다.

1-3. Boolean Algebra ( 이진 대수식 ) 이진 대수식을 사용하여 회로를 표현하고 간소화할 수 있다.

1-4. Map Simplification 회로를 간소화하는 또 한가지의 방법.

1-5. Combinational Circuits ( 조합 회로) 결과값이 입력값에 의해서만 결정되는 논리 회로.

1-6. Flip-Flops 한 Bit를 기억하는 기억소자.

1-7. Sequential Circuits Cominational Circuits와 Flip-Flops를 사용하면 Sequential Circuits를 만들 수 있다.

1-1. Digital Computer

0과 1을 사용하여 여러 계산을 수행하는 시스템 bit = 하나의 2진수. 컴퓨터는 이진수로 동작한다.

Ex. 1001011 ⇒ $12^6 + 0 * 2^5 + 02^4 + 12^3+02^2+12^1+12^0$

각각의 자릿수에 대한 Weight라고 생각할수도 있다. 컴퓨터는 하드웨어, 소프트웨어로 이루어진다.

• 하드웨어 컴퓨터의 모든 전자부품과 주변장치를 구성하는 전자기적 부품 하드웨어에서 가장 중요한 부품은 CPU와 RAM, IO Device

  1. CPU ( Central Process Unit ) 데이터를 조작하는 Arithmatic Logic Unit ( 산술 논리 장치), Register, 제어회로로 구성

  2. RAM ( Random Access Memory ) 명령어와 데이터를 저장하는 공간

  3. IO Device 컴퓨터에 연결된 여러 입출력 장치들. Ex. 모니터, 키보드, 마우스... 컴퓨터의 흐름은 다음과 같다. Input Devices → Input-Output Processor → RAM → CPU → RAM → Input-Output Processor →Output Devices

• 소프트웨어 명령어와 데이터로 구성되어 작업을 수행하는 무형의 논리구조(?) ❗ 시스템 소프트웨어 ( 운영체제 ) ❗ 프로그램을 실행시키는데 필요한 Software Ex. Compiler or IO Device를 구동하는 Software

  1-2. Logic Gates ( 논리 소자 )

8개의 논리소자가 있음.

1. AND ⇒ X = AB
2. OR ⇒ X = A+B
3. NOT ⇒ X = A'
4. Buffer ⇒ X = A ❗신호의 세기를 복구하는 역할. ( 3.5V 이상 = 1, 1.5V 이하 = 0)
5. NAND ⇒ X = (AB)'
6. NOR ⇒ X = (A+B)'
7. XOR ⇒ X = A'B + AB'
8. XNOR ⇒ X = A'B' + AB

AND, OR, NOT을 이용하면 다른 소자의 기능을 만들 수 있다.

1-3. Boolean Algebra

논리소자들을 식으로 표현한 것. Ex. AND Gate ⇒ F(A,B) = AB Boolean Function과 Logic Diagram과 Truth Table은 전부 같은 정보를 포함하고 있다. (회로의 기능) Boolean Algebra를 사용하면 회로를 식으로 표현하고, 간소화 할 수 있다. ( 가장 적은 소자의 갯수로 같은 기능을 동작하는 회로를 만들 수 있다. ) 부울 대수의 기본적인 관계에는 17개가 있다.

부울 대수의 기본적 관계

De Morgan's Theorem 어떤 수식에서 모든 OR 연산은 AND로, AND 연산은 OR으로 바꿔주고 각 변수를 보수화 한다.

Ex. F = AB+C'D'+B'D 일때 F' = (AB+C'D'+B'D)' = (AB)' * (C'D')' * (B'D)' = (A'+B') * (C+D) * (B+D')

부울 대수를 사용하면 같은 기능을 하는 가장 간단한 소자를 그릴 수 있다.

Ex.

F = ABC + ABC' + A'C → X(Y+Z) = XY + XZ 공식 사용. = AB(C + C') + A'C → C + C' = 1 공식 사용. = AB*1 + A'C = AB + A'C

논리소자 6개 → 논리소자 4개로 줄었다.

OS의 정의

OS(Operating System)이란 컴퓨터 하드웨어와 컴퓨터 사용자 사이에서 서로를 중재하는 프로그램이다.

OS is Resource Allocator :

컴퓨터의 모든 자원을 관리하고, 효율적이고 공정하게 자원을 할당하는 역할을 한다.

OS is Control Program :

컴퓨터를 더 적절하게 사용할 수 있도록 하고, 에러를 막는다.

OS는 다양한 정의가 있다.

목적

컴퓨터를 사용하는 User가 컴퓨터를 사용하기 더 쉽도록 한다.

하드웨어(HW)를 더 효율적으로 다룰 수 있도록 한다.

컴퓨터 시스템의 구조

컴퓨터는 네가지 시스템으로 구분될 수 있다.

1. HardWare( HW ) : CPU, Memory, I/O Device 등...
2. Operating System( OS ) : 다양한 프로그램,User 와 HW의 사용을 제어한다.
3. Application Programs
4. User

Kernel

Kernel = OS이다 ( 맞는지는 잘 모르겠다)

Kernel은 항상 실행중이고, Kernel을 제외한 프로그램을 System Program 혹은 Application이라고 부른다.

*Bootstrap Program

Bootstrap Program은 ROM, EEPROM에 저장되어 있는 FirmWare로 컴퓨터가 시작시 자동으로 Bootstrap Program이 실행된다.

Bootstrap Program이 실행되면 Bootstrap Program은 System을 초기화하고 OS Kernel을 불러온다.

컴퓨터 시스템 구조

Device Controller

각각의 I/O Device🖱️ ⌨️ 🖨️ 🖥️ 에는각각을 담당하는 Device Controller가 있다.

CPU와 Device Controller들은 Shared Memory에 접근을 제공하는 Common Bus를 통해 연결되어 있고 I/O Device와 CPU는 동시에 실행된다.

각각의 Device Controller들은 Buffer를 가지고 있고 CPU는 프로그램의 실행 결과를 Memory에서 Device Controller 의 Local Buffer로, Device Controller는 I/O Device의 실행 결과를 I/O Device에서 Local Buffer로 옮긴다.

Device Controller의 Local Buffer는 CPU와 I/O Device간의 다리 역할을 하게 된다.

Device Controller는 I/O 작업이 완료되면 CPU에게 인터럽트( Interrupt )를 날려 작업이 완료되었음을 알려준다.

Interrupt(인터럽트)

Interrupt 란 Local Controller가 CPU에게 작업이 완료되었음을 알려주는 방식이다.

Interrupt 발생 시 OS는 Register 값, Program Counter( 다음 Instruction의 주소를 저장하는 Register)의 값을 저장하여 CPU의 상태값을 저장한다.

Interrupt는 Interrupt Vector ( Service Routine의 주소를 포함하고 있는 Vector)를 통해서 Interrupt Service Routine의 제어를 전달한다.

OS는 한번에 하나의 Interrupt만 처리가 가능하다.

*Trap : SoftWare적으로 발생하는 Interrupt / ex) Zero Division Error

인터럽트 처리 방법

1. Polling : 모든 I/O Device를 순차적으로 방문하며 Interrupt 여부를 검사한다. 모든 Device를 검사하므로 비효율적이다.
2. Vectored Interrupt System : Interrupt Vector( Type of Interrupt, Service Routine Address )의 테이블을 조회하여 발생한 Interrupt를 처리하는 Service Routine Address를 찾는다. Polling에 비해서 효율적이다.

*Service Routine : 각 Interrupt에 대한 Actions

I/O 구조

Synchronous I/O ( 동기식 입출력 )

동기식 입출력에는 두가지 방법이 있다.

1. Wait Instruction : 다음 Interrupt가 발생할 때 까지 기다리라는 Instruction을 실행한다.
2. Wait Loop : I/O Device Controller한테 할당된 메모리를 Loop를 돌며 계속 검사하여 입출력이 완료되었는지를 확인한다.

동기식 입출력 방식은 메모리와 버스의 이용률이 증가한다 🆙

Asynchronous I/O ( 비동기식 입출력 )

비동기식 입출력은 CPU가 I/O 작업을 기다리지 않는다.

Process는 기다리고 CPU는 다른 일을 찾아서 하기 때문에 동기식 입출력에 비해 CPU 사용이 효율적이다👍 ⬆️

비동기식 입출력에서는 OS가 Device-Status Table을 관리한다.

*Device-Status Table : 각각 I/O 장치의 정보( Type, Address, Status 등 )를 갖고있는 Table

기술의 발전에 따라 I/O 장치가 Memory의 입출력 속도에 가깝게 입출력이 가능해지면서 I/O 장치가 CPU의 간섭 없이 Local Buffer에서 Main Memory에 직접 Block Data를 전달하는 방식을 DMA (Direct Memory Access) 라고 한다. Buffer → Directly → Main Memory

옛날에는 통신단위(Byte) 마다 Interrupt가 발생하여 비효율적이였지만, DMA가 발전하여 Block 마다 Interrupt가 발생하여 효율적이 되었다.