땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

반복문은 당연히 시간초과일거라고 생각해서 수식을 만들기로 했다~ 입출력 예제 3번이 수식 만드는데에 도움이 되었다

1. 밤에 미끄러지기 전에 이미 정상에 도착한 경우
2. 밤에 미끄러지기 전에도 정상높이와 일치하지않는경우 이렇게 두 경우로 나누어서, 1번 경우에는 수식의 답 고대로 출력하고 2번 경우에는 ++해주는 걸로 출력해주었다.

   import java.io.*;
   import java.util.StringTokenizer;
   

public class BOJ_2869 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken());

    if(a == v){
        System.out.println(1);
    } else {
        if((v-b)%(a-b) == 0) {
            System.out.println((v-b)/(a-b));
        } else {
            System.out.println((v-b)/(a-b)+1);
        }
    }
}

}

```

import java.io.*;

public class BOJ_1259 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str;

        while(true) {
            str = bf.readLine();
            boolean chk = true;

            if(str.equals("0")) break;

            for(int i = 0; i < str.length()/2; i++){
                if(str.charAt(i) != str.charAt(str.length()-i-1))
                    chk = false;
            }

            if(chk) System.out.println("yes");
            else System.out.println("no");
        }
    }
}

첫날은 몸풀기로하쟈,,,🙄

-> 그냥 a href이용해서 register.html로 넘기면 됨

2. regist 페이지에서 Book객체 생성해서 출력 url : http://localhost:8080/{Context-root}/main method : post hidden : action=regist

-> regist.html에서 form을 button으로 만들어서 submit될 때 form의 action을 main으로 하여 post방식으로 main서블릿으로 넘겨주면서 hidden태그에서 action(act)를 regist로 넘겨주어 main서블릿에서 doPost에서 doGet으로 넘겨주고(한글받는문제때문) action파라미터를 regist로 받게하여 그에 따른 함수를 만들어 일을 하게 한다.

• 문제 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까? 천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다. 케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다. 오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다. 예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자. 1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다. 2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다. 3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다. 4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다. 마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다. 5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다. BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

• 입력 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. 사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다.

• 출력 첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

답은 나오는데.. 메모리초과가 계속 떠서 너무 오래걸렸다.. 나는 for i in range(n+1): for j in range(n+1) 이런식으로 i에서 시작해서 j까지 끝내는 케빈베이컨 값을 하나하나 다 저장하였는데 이 방법으로는 메모리초과가 뜬다.. 그리고 이 방법의 다른 의문점은 큐에 넣어진 순서대로 탐색을 하기 때문에 각 노드의 케빈베이컨의 값이 최소라는 보장이 없다. 큐의 앞에 자리한 노드로만 탐색을 하게 된다.. 그래서 노드의 시작점은 정하되 끝은 정하지 않고 BFS안에서 알아서 탐색하여 n까지의 케빈베이컨 수를 모두 구하도록 하였다. 주의) 인덱스가 1부터 시작함, visited배열을 전역에서 선언하면 안됨(초기화 안해줘서 다음 i에 영향을 미침), sum함수/index함수 등 잘 써먹기.., 리스트.clear()하면 아예 []가 되어버림.

from collections import deque

def bfs(i):
    cnt = [0] * (n+1)    # 각 케빈베이컨 수 저장해놓을 배열
    queue = deque()
    visited[i] = 1    # 이미 현재 방문중이어서 큐에 추가하기전에 방문처리해줌
    queue.append(i)
    while queue:
        start = queue.popleft()
        for x in arr[start]:
            if visited[x] == 0:    # 방문되지 않은거면
                cnt[x] = cnt[start] + 1
                queue.append(x)
                visited[x] = 1    # 큐에 추가해주고 나서 방문처리해주어야!!
    # visited.clear() --> 이렇게하면 visited배열을 아예 []로 만드는거!!!!
    return sum(cnt)    # 배열을 이렇게 더할수있다!


n, m = map(int, input().split())
arr = [[] for i in range(n+1)]    # 인덱스 0은 사용안할거라서
# arr1 = [[] for i in range(n)]
# arr2 = [[]] * n
# 위의 두개는 같은거!
# ⭐⭐⭐append 써줄라면 배열 저렇게 선언해야⭐⭐⭐
for i in range(m):
    a, b = map(int, input().split())    # 공백있어서 split해주기
    arr[a].append(b)
    arr[b].append(a)


ans = []    # 각 케빈베이컨의 합 담을 배열
for i in range(1, n+1):    # 1부터인거 조심, n+1인거 조심
    visited = [0 for i in range(n + 1)]  # 방문 !!!!!!! 얘를 for문밖에 놓으면 안됨 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ
    ans.append(bfs(i))

print(ans.index(min(ans))+1)    # 인덱스에 1더해줘야함!

• 문제 뿌요뿌요의 룰은 다음과 같다. 필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다. 뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다. 뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다. 아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다. 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다. 남규는 최근 뿌요뿌요 게임에 푹 빠졌다. 이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만, 상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다. 하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다. 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자!

• 입력 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. 입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태이다. 즉, 뿌요 아래에 빈 칸이 있는 경우는 없다.

• 출력 현재 주어진 상황에서 몇연쇄가 되는지 출력한다. 하나도 터지지 않는다면 0을 출력한다.

어려워보여서 풀기싫었다 사실.. 원석오빠가 좋은문제라고 추천해줘서 풀어보았는데 역시 시간이 좀 많이 걸렸당 ㅠㅠ 그래도 어려운문제 중에 다른풀이 참고안하고 나혼자 푼 몇안되는 문제여서 뿌듯하군.. 근데 시간이 너무 오래걸려서 ㅠㅠ 시간줄이는 연습해야겠다이제! 일단 뿌요들을 폭파시키는 함수와 공백을 없애는 함수를 만들었다. 뿌요폭파함수는 DFS로 구현하였는데 그러다보니 ㅗ, ㅜ, ㅓ, ㅏ 를 구현하려면 2단계에서 현위치에서 재탐색해주어야 했다. BFS가 더 편할듯싶다. 어 그러면 테트로미노도 BFS가 더 편하려나..? 해봐야겠다 그리고 dfs에서 리턴하면 리턴값이 씹히는..? 것 때문에 시간이 엄청 오래걸렸다! 아무래도 재귀다보니까 당연한건데 그걸로 시간끌었당.. 그리고 음 공백없애는 함수에서도 맨 아래 행부터 탐색해야되는 것을 깨닫는데에 오래걸려서 .. 이제 어려운 문제들도 차근차근 풀어봐야겠다

from collections import deque

def dfs(x, y, step):    # 인접한 것들 터뜨리는 함수
    global check
    dx = [-1, 1, 0, 0]    # 방향벡터
    dy = [0, 0, -1, 1]
    cnt = 0    # 터뜨릴지 확인하는 용도
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<12 and 0<=ny<6 and lst[x][y] == lst[nx][ny] and lst[x][y] != 'x' and visited[nx][ny] == 0:
            # 범위안에 있고 방문되지않았고 같은 색깔인 경우(공백은 안침)
            queue.append((nx, ny))
            visited[nx][ny] = 1
            dfs(nx, ny, step+1)
            visited[nx][ny] = 0

            if step == 2:  # ㅓ, ㅏ, ㅗ, ㅜ 만들기위함!!!!!!!!!!!!!! 이것때문에 BFS가 편할 수 있을거같음 !!!!!!ㅠㅠㅠ
                visited[nx][ny] = 1
                dfs(x, y, step+1)    # 탐색은 현위치에서 다시
                visited[nx][ny] = 0
        else:
            cnt += 1    # 인접한것이 없으면 +1
    if step >= 4 and cnt == 4:    # 4개이상이고 더이상 인접한게 없으면
        while queue:    # 큐가 빌때까지
            xx, yy = queue.popleft()  # 터뜨릴좌표 꺼냄
            lst[xx][yy] = 'x'
            # print(step, xx, yy)
        # print("y")
        check = 1



def emp():    # 공백 비우는 함수
    for i in range(11, -1, -1):    # 꼭 밑에서부터 !!!
        for j in range(5, -1, -1):
            if lst[i][j] == 'x' and 0 < i:    # 공백이고 맨윗줄이 아니면
                n = 1
                for k in range(i-1, -1, -1):    # 위로 거슬러감
                    if lst[k][j] != 'x':
                        break
                    else:
                        n += 1    # 공백 세로 수
                for k in range(i, -1, -1):    # 공백 윗줄들
                    if k-n >= 0:
                        lst[k][j] = lst[k-n][j]    # 공백만큼 아래로 끌어옴
                    else:
                        lst[k][j] = '.'
            if lst[i][j] == 'x' and i == 0:    # 공백이고 맨 윗줄이면
                lst[i][j] = '.'


if __name__ == "__main__":
    # lst = [list(input().split()) for i in range(12)] ------> 이렇게 하면 안됨!!!!
    lst = [list(input()) for i in range(12)]
    visited = [[0 for i in range(6)] for j in range(12)]    # 방문체크
    queue = deque()    # 터뜨릴 좌표
    check = 1
    ans = 0
    while check == 1:    # 터지는게 있는동안만
        check = 0
        # print("start")
        for i in range(12):
            for j in range(6):
                if lst[i][j] != '.':
                    visited[i][j] = 1    # 초기값도 방문 꼭꼭
                    queue.append((i, j))    # 터뜨릴 좌표 큐에 현위치 넣어줌
                    dfs(i, j, 1)    # 리턴값
                    visited[i][j] = 0
                    queue.clear()    # 다음턴을 위해 큐 초기화
        # print("End, %d" % check)
        if check == 1:    # 전체 한번 돌았을때 터지는게 있다면
            emp()    # 공백 치우기
            ans += 1    # 횟수늘리기
            # print(lst)
        # else:
        #     break
    print(ans)

• 문제 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

• 입력 첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500) 둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

• 출력 첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

DFS는 진짜 오랜만에 풀어봤당 처음에 BFS문제인줄 알고 방향 잘못잡았다가 혼란스러웠음.. 풀이들이 되게 다양했는데 내 아이디어와 가장 비슷한 풀이를 보고 참고하였다. 각 좌표마다 dfs로 4단계까지 탐색하고 값이 가장 큰 것을 찾는다는 것까지는 비슷했는데 내가 미처 생각하지 못했던 것은 ㅗ ㅜ ㅓ ㅏ 모양은 2단계에서 현위치에서 재탐색해야한다는 점이었다.

# 포인트 : 너무길면 함수로만들기, max_val로 계산해서 안될거같으면 재빨리 포기, dfs는 큐안쓰고 재귀
# 참고 : - map 사용법: https://koos808.tistory.com/34
def dfs(x, y, step, sum):
    global ans    # 함수 밖에서 선언된 전역변수의 접근위해
    if step == 4:
        ans = max(ans, sum)
        return
    if sum + max_val * (4-step) < ans:    # 후순에 큰게 나와도 최대보다 작으면
        return
    dx = [-1, 1, 0, 0]  # 방향벡터
    dy = [0, 0, -1, 1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<n and 0<=ny<m and visited[nx][ny] == 0:
            visited[nx][ny] = 1
            dfs(nx, ny, step+1, sum+lst[nx][ny])
            visited[nx][ny] = 0
            if step == 2:  # ㅓ, ㅏ, ㅗ, ㅜ 만들기위함
                visited[nx][ny] = 1
                dfs(x, y, step + 1, sum + lst[nx][ny])    # 탐색은 현위치에서 다시
                visited[nx][ny] = 0


if __name__ == "__main__":
    n, m = map(int, input().split())
    lst = [list(map(int, input().split())) for i in range(n)]
    visited = [[0 for i in range(m)] for j in range(n)]    # 방문체크
    max_val = max(map(max, lst))    # 최댓값
    ans = 0
    step = 1
    for i in range(n):
        for j in range(m):
            visited[i][j] = 1    # (i,j)가 첫블록이라서 이것도 방문처리해줘야
            dfs(i, j, 1, lst[i][j])
            visited[i][j] = 0
    print(ans)

• 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다. 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 1 1 1

• 입력 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

• 출력 각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

가장 기본적인 BFS문제를 찾다가 발견한 문제이다. 방문체크를 잊어서 시간이 좀 소요되었다. 배추밭 전체를 탐색하지않고 배추가 있는 곳들만 탐색하는 문제이다. 네 방향 모두에 배추가 존재하지 않는다면 while문에서 나가고 이 때 cnt를 높여준다.

from collections import deque
T = int(input())    # TC수
for tc in range(T):
    row, col, pos = map(int, input().split())    # 가로, 세로, 배추위치
    lst = [list(map(int, input().split())) for _ in range(pos)]    # 배추위치 배열
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]    # 방향벡터
    queue = deque()
    visited = [[0 for _ in range(col)] for i in range(row)]    # 배추밭 방문체크
    cnt = 0    # 배추흰지렁이 수
    # for x, y in lst:    # 배추를 심은곳만
    for x, y in lst:
        if visited[x][y]:    # 방문된곳이면 지나치고
            continue
        else:
            queue.append((x, y))
            visited[x][y] = 1  # 꼭 해주기!!!!
            while queue:    # 큐가 차있는동안
                x, y = queue.pop()
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx < row and 0 <= ny < col and visited[nx][ny] == 0 and [nx, ny] in lst:    # 방문x & 이어짐 & 범위안에 있음
                        queue.append((nx, ny))    # 큐에 넣어주고
                        visited[nx][ny] = 1    # 방문체크
            cnt += 1
    print(cnt)

• 문제 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다.

• 입력 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

• 출력 첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

쉬워보였는데 오래걸려서 현타왔던 문제,, 우선 부모노드의 번호를 인덱스로 하는 리스트에 자식노드의 번호들을 원소들로 저장하고 이 리스트를 큐에 넣어서 사용하였다. BFS방식으로 루트노드부터 리프노드까지 내려가며 탐색하였고 방문 체크를 해주었다. 우선, 생각하지 못한 예외사항 첫번째는 어느 노드가 하나의 자식노드를 가지고 있을 때 자식노드가 삭제된다면 그 부모노드가 리프노드라는 사실이다. 두번째는 루트노드가 0번이 아닐 수도 있다는 사실이다.

from collections import deque

N = int(input())
arr = list(map(int, input().split()))
del_n = int(input())    # 삭제 노드
cnt = 0    # 리프노드 개수
check = [0 for _ in range(N)]    # 노드의 삭제여부
tree = deque([] for _ in range(N))    # 트리[부모] = 자식들
for i in range(N):
    if arr[i] == -1:    # 루트면
        root = i
        continue
    else:
        tree[arr[i]].append(i)
check[del_n] = 1    # 삭제체크
queue = deque()    # dfs
queue.append(root)    # 0에서 시작하게
while queue:
    x = queue.popleft()
    if check[x] == 1:    # 삭제된 노드면
        continue
    if len(tree[x]) == 0:    # 리프노드면(자식이 없으면)
        cnt += 1
        continue
    n = len(tree[x])
    while tree[x]:    # 자식이 존재하면
        y = tree[x].pop()
        if n == 1 and check[y] == 1:    # 자식이 하나있는데 그게 삭제된거면
            cnt += 1
            break
        else:
            queue.append(y)    # 큐에 넣음
print(cnt)

# 리프노드인 경우 : 1. 자식이 없음 2. 삭제된 자식
# 주의 : 루트가 0이 아닐수도 있음 !

• 문제 지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다. 각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

• 입력 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

• 출력 첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.

처음 제출한 코드는 왜 틀렸는지 모르겠다 ㅠㅠ 테케 다 맞고 문제없어보이는데 정신없는 막코딩은 항상 틀리는 것 같다,,

문제 해결 : 가장 큰 제한무게를 가진 크레인이 가장 큰 무게의 박스를 옮기도록 한다.

import sys
n = int(input())    # 크레인 수
c_arr = map(int, sys.stdin.readline().split())
m = int(input())    # 박스 수
b_arr = map(int, sys.stdin.readline().split())

c_arr = sorted(c_arr, reverse=True)    # 내림차순 정렬
b_arr = sorted(b_arr, reverse=True)    # 내림차순 정렬

if c_arr[0] < b_arr[0]:
# 박스무게가 크레인의 최대제한무게보다 크면
    print(-1)
    exit()

c_check = [0 for _ in range(len(c_arr))]    # 사용크레인 체크
# cnt = 0    # 옮겨지는 박스의 수
# turn = 0    # 시간
ans = 0
while len(b_arr) > 0:
    for i in c_arr:    # 크레인의 제한무게. 크레인 다쓰면 다음턴으로 넘어가서 ans에 1 더해줌
        for j in range(len(b_arr)):
            if i >= b_arr[j]:
                del b_arr[j]
                break
    ans += 1
print(ans)

• 문제 N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다. 연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다. 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수를 하나 만들 수 있다. 연두가 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구해보자. 완전 제곱수란 어떤 정수를 제곱한 수이다.

• 입력 첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지고, 공백없이 모두 붙여져 있다.

• 출력 첫째 줄에 연두가 만들 수 있는 가장 큰 완전 제곱수를 출력한다. 만약, 완전 제곱수를 만들 수 없는 경우에는 -1을 출력한다.

이거 쉽다구 다른문제도 풀던데 난 어려웠당..ㅎ.. 일단 아이디어 생각해내는거부터 막막했고 4중포문으로 x, y, x공차, y공차 하나하나 다 돌려갈 때 온갖 경우의 수가 나온다는 것을 이해하는 것도 시간이 걸린 것 같다 그리고 공차가 0, 0 일 때 무한루프를 돌게 되는 것을 생각하지못해서 무한루프 때문에 해결하는 데에 또 애를 먹었다,,

import math

N, M = map(int, input().split())
arr = []
for i in range(N):
    arr.append(list(map(int, input())))

ans = -1

for i in range(N):
    for j in range(M):
        for n in range(-N, N):
            for m in range(-M, M):
                if m == 0 and n == 0:    # 공차가 0이면 무한반복이어성
                    continue
                x = i
                y = j
                cnt = 0    # 공차에 곱해줄 수
                val = ''    # 문자열
                while 0<=x<N and 0<=y<M:
                    val += str(arr[x][y])    # 현재값을 문자열에 합쳐줌
                    cnt += 1
                    value = int(val)
                    value_sqrt = math.sqrt(value)
                    value_decimal = value_sqrt - int(value_sqrt)
                    if value_decimal == 0 and ans < value:   # 제곱수이고 최대면
                        ans = value
                    x = i + cnt*n
                    y = j + cnt*m
print(ans)

• 문제 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.

• 입력 첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 자연수이다.

• 출력 첫째 줄에 문제의 정답을 출력한다.

한시간 반 정도 삽질 좀 했다,, 기울기랑 y절편 다 구해서 그래프 만들고 그래프 원소들을 하나씩 꺼내서 그 방정식을 다시 x = 0, x = 1, ..., x = n-1 과 비교해서 만나는 점이 없으면 건물이 보이는 걸로 생각하고 카운트해서 이걸 다 세려고 했다...ㅎㅎ... 그래프 만들고 이제 다시 다 비교하려는 찰나에 그럼 포문을 몇개를 해야되는건가 싶기도 하고 시간보고도 아차싶어서 .. 남들은 어떻게 풀었나봤더니 왜이렇게 다들 기막힌 아이디어를 잘 떠올리는걸까?? ㅠㅠ 난 생각도 못했는데 후 ; 암튼 결론은 현재 위치에서 시작하여 오른쪽으로 갈 때 기울기가 반드시 현기울기보다 커야 그 건물을 볼 수 있다 따라서 기울기가 현재보다 큰 경우에만 cnt를 높여주고 현기울기를 갱신해주면 된다 왼쪽도 마찬가지..

그리구 이건 좀 tmi긴한데 제출했는데 런타임에러가 뜨는거임.. 그래서 대체 내가 또 어떤 바보짓을 했을까..했더니 일주일동안 그새 싸피문제들에 익숙해져서 나도 모르게 테스트케이스들을 입력받고 뭐.. 그러고 있었따.. 네..

def left(curr):    # 왼쪽에 있으면 기울기가 현재보다 작아야만 볼 수 있음
    l_cnt = 0    # 보이는 건물 수
    max_g = float("inf")    # 양의 무한대
    for i in range(curr-1, -1, -1):    # 거꾸로!!!!!!!!!!꼭
        gradient = (arr[curr]-arr[i])/(curr-i)
        if gradient < max_g:    # 현기울기보다 작으면 보이고 최소기울기는 계속 갱신
            max_g = gradient    # 갱신
            l_cnt += 1    # 보이면 +1
    return l_cnt


def right(curr):    # 오른쪽에 있으면 기울기가 현재보다 커야만 볼 수 있음
    r_cnt = 0    # 보이는 건물 수
    min_g = -float("inf")    # 음의 무한대
    for i in range(curr+1, N):
        gradient = (arr[curr]-arr[i])/(curr-i)
        if gradient > min_g:    # 현기울기보다 크면 보이고 최대기울기는 계속 갱신
            min_g = gradient    # 갱신
            r_cnt += 1    # 보이면 +1
    return r_cnt


N = int(input())
arr = list(map(int, input().split()))
ans = 0    # 보이는 건물수 비교할 값
for i in range(N):
    sum = left(i) + right(i)
    if sum > ans:
        ans = sum
print(ans)

• 문제 아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다. 입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

• 입력 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

• 출력 첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

BFS인건 감이 왔는데 이걸 한번에 해치우는 BFS 함수를 만드려니까 어지러웠다. 그래서 블로그를 참고,,,, 한번 가장자리를 없앨때마다 즉, 한시간에 한번씩 BFS를 다시 호출하는 방법이 제일 간단해보여서 그걸로 해결했고, 난 왜 맨날 행과 열이 헷갈릴깡... 이제 걍 외워야겠당. 암튼 생각보다 간단한 문제였다 !! 아 글구 마지막에 다 녹기 한시간 전 가장자리 개수 출력할때 ans[-2] 해주는게 아주 깔끔해보였당 그리고 deque에 두개 넣어줄때 괄호 묶어주는거 잊지말기!!

import collections

n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]

def bfs():    # 중요) 가장자리 한번 녹을때마다 한번 호출
    queue = collections.deque()
    queue.append((0,0))   # 처음부터 시작
    visited = [[0] * m for _ in range(n)]    # 체크
    count = 0
    dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:    # 자꾸 행과열 헷갈림 ㅜㅜㅜㅜㅜ
                if lst[nx][ny] == 0 and visited[nx][ny] == 0:    # 가장자리가 아닌 바깥
                    visited[nx][ny] = 1    # 체크하고
                    queue.append((nx, ny))    # 계속 가야하니까 큐에 넣는다
                elif lst[nx][ny] == 1 and visited[nx][ny] == 0:    # 가장자리면
                    lst[nx][ny] = 0    # 녹인다
                    visited[nx][ny] = 1    # 체크
                    count += 1    # 녹는개수 즉 가장자리 세기
    return count

ans = []
time = 0

while True:
    cnt = bfs()
    ans.append(cnt)
    if cnt == 0:    # 가장자리가 없으면, 즉 다녹으면
        break
    time += 1

print(time)
print(ans[-2])    # 뒤에서 두번째, 즉 녹기 바로 전

• 문제 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

• 입력 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다. 각 사람의 부모는 최대 한 명만 주어진다.

• 출력 입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

인접한 노드들의 그래프를 만들어야겠다는 생각이 처음부터 나지가 않았다ㅜ 그래서 예전에 공부했던 BFS노트를 보면서 복기해보았고 그렇게 감을 잡아갔던것같다. 생각보다 간단한 문제였고 이정도는 외워두어야 할 것 같다!

from collections import deque

n = int(input())
a, b = map(int, input().split())
m = int(input())
graph = [[] for i in range(n+1)]    # 부모자식 관계 기록
visited = [False] * (n+1)

for i in range(m):    # 부모자식 관계 기록
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

q = deque()
q.append((0, a))    # 0부터 시작해서 촌수 늘려감

def bfs():
    while q:
        num, x = q.popleft()
        visited[x] = True
        for i in graph[x]:    # x번 사람의 관계뒤지기
            if not visited[i]:    # 방문안했을경우에만
                q.append((num+1, i))
            if i == b:    # 도달하면
                return num+1    # 리턴
    return -1    # 큐 끝날때까지 도달안했으면 -1

print(bfs())

• 문제 은혜는 정육점에서 고기를 사려고 한다. 보통 정육점에서는 자신이 원하는 양을 이야기하면 그 양만큼의 고기를 팔지만, 은혜가 방문한 정육점에서는 세일 행사를 하고 있었기 때문에 N 덩어리의 고기를 이미 잘라놓고 판매하고 있었다. 각각의 덩어리들은 이미 정해져 있는 무게와 가격이 있는데, 어떤 덩어리를 샀을 때에는 그 덩어리보다 싼 고기들은 얼마든지 덤으로 얻을 수 있다(추가 비용의 지불 없이). 또한 각각의 고기들은 부위가 다를 수 있기 때문에 비용과 무게와의 관계가 서로 비례하는 관계가 아닐 수도 있다. 은혜는 이러한 점을 고려하지 않고, 어느 부위든지 자신이 원하는 양만 구매하면 되는 것으로 가정한다. 또한 만약 가격이 더 싸다면 은혜가 필요한 양보다 더 많은 고기를 살 수도 있다. 각 덩어리에 대한 정보가 주어졌을 때, 은혜가 원하는 양의 고기를 구매하기 위해 필요한 최소 비용을 계산하는 프로그램을 작성하시오.

• 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 100,000), M(1 ≤ M ≤ 2,147,483,647)이 주어진다. N은 덩어리의 개수를 의미하고, M은 은혜가 필요한 고기의 양이다. 다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나타내는 음 아닌 두 정수가 주어진다. 무게의 총 합과 가격의 총 합은 각각 2,147,483,647을 넘지 않는다.

• 출력 첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

이 문제는 우선 이해하는 데에 시간투자를 많이 했던 것 같다. 사실 이해하고 난 뒤에 생각해낸 방법도 너무 간단해서 이게 맞나..? 싶기도 했는데 역시나 틀렸담.. 예외케이스가 좀 있는 문제라서 마냥 간단하지만은 않아서 이것저것 참고하면서 풀어보았다.

import sys

n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]

lst = sorted(lst, key=lambda x:(x[1], -x[0]))    # 낮은가격부터, 무거운 무게부터

def fun():
    sum = 0
    for i in range(n):
        sum += lst[i][0]
    if sum < m:
        return -1

    ans = sys.maxsize
    weight = 0
    same_price = 0

    for i in range(n):    # 낮은 가격 순으로 돌림
        weight += lst[i][0]    # i번째 낮은 가격의 무게 합해감
        if i > 0 and lst[i][1] == lst[i-1][1]:    # 바로 전 가격과 같다면
            same_price += lst[i][1]    # 현 가격과 동일한 전 가격 더해줌
        else:
            same_price = 0    # 아니라면 초기화

        if weight >= m:    # 무게가 채워졌다면
            ans = min(ans, lst[i][1] + same_price)    # 비교
    return ans

print(fun())

• 문제 N×M크기의 배열로 표현되는 미로가 있다.

  1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

  위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

• 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

• 출력 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

BFS로 풀었다. 갈 수 있는 위치에 전 위치의 값+1 씩 계속 더해나가주면 마지막 [N-1][M-1] 위치에 최소 칸 수가 들어있다! 사실 이게 첨엔 이해가 안됐는데 그리면서 직접 해보니까 이해갔당

그리구 파이썬에서는 deque를 쓰는 것도 오늘 알앗다,, 반성반성,,

from collections import deque

n, m = map(int, input().split())
lst = []
for i in range(n):
    lst.append(list(map(int, input())))    # 공백없어서 split()쓰면X

def bfs(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    q = deque()
    q.append((x, y))

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue

            if lst[nx][ny] == 0:
                continue

            if lst[nx][ny] == 1:
                lst[nx][ny] = lst[x][y] + 1
                q.append((nx, ny))

    return lst[n-1][m-1]


print(bfs(0,0))

• 문제 눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다. 앞마당의 길이는 $N$이고 위치 $1$부터 위치 $N$ 까지만 눈이 쌓여있다. 위치 $i$에 눈이 $a_i$만큼 쌓여있다. 대회 규칙은 해당 앞마당에서 $M$초 동안 눈덩이를 굴려 눈사람을 만드는 것이다. 눈덩이의 시작 크기는 $1$이다. 눈덩이의 시작 위치는 $0$이다. 가장 큰 눈사람을 만들고 싶던 수수는 눈덩이를 굴리는 법을 연구했다. 눈덩이를 굴리는 방법에는 두 가지가 있다. 눈덩이를 굴리거나 던질 때 1초가 소모된다. 눈덩이를 현재 위치 +1칸으로 굴린다. 현재 칸의 위치를 $i$라고 하면 눈덩이의 크기는 $a_{i+1}$ 만큼 늘어난다. 눈덩이를 현재 위치 +2칸으로 던진다. 눈덩이가 착지하며 충격을 받아 눈덩이의 크기는 원래의 크기의 반으로 줄어들고 현재 칸의 위치를 $i$라고 하면 눈덩이의 크기는 $a_{i+2}$ 만큼 늘어난다. 이 때 소수점은 절사한다. 눈덩이를 던져 크기가 $0$이 되어도 눈덩이는 사라지지 않는다. 눈덩이가 앞마당의 끝에 도달한 경우 남은 시간과 관계없이 눈덩이 굴리기는 끝이 난다. 대회 시간 내에 가장 크게 만들 수 있는 눈덩이의 크기를 구하는 프로그램을 작성해보자.

• 입력 첫째 줄에 공백을 기준으로 앞마당의 길이 $N$ ($1 \leq N \leq 100$), 대회의 시간 $M$ ($1 \leq M \leq 10$)이 주어진다. 둘째 줄에 길이가 $N$인 수열 $a$가 주어진다. ($1 \leq a_i \leq 1,000,000$)

• 출력 첫째 줄에 대회 시간 내에 가장 크게 만들 수 있는 눈덩이의 크기를 출력한다.

두 가지 문제점만 빼고는 얼추 맞아서 그 두 가지는 주석에 달아놓았다

n, m = map(int, input().split())
lst = [0] + list(map(int, input().split()))    # 눈덩이의 시작위치가 0인거 생각
ans = -1

def fun(idx, size, t):
    global ans

    if t > m:    # t 전까지는 유효
        return

    if t <= m:
        ans = max(size, ans)
    if idx+1 <= n:
        fun(idx+1, size+lst[idx+1], t+1)
    if idx+2 <= n:
        fun(idx+2, size//2 + lst[idx+2], t+1)

fun(0, 1, 0)
print(ans)

• 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

• 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

• 출력 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

당분간 백트레킹문제를 주로 풀어볼 생각이담 문제이해는 쉬웠지만 내가 떠올린 방식과 다른사람들이 푼 방식이 조금 달라서 내 방식이 엄청 비효율적이라고 느꼈다 ㅜ 그래서 다른 코드들 참고해서 고쳐보았다

n, s = map(int, input().split())
lst = list(map(int, input().split()))
cnt = 0

def fun(num, sum):
    global cnt

    if num >= n:
        return

    sum += lst[num]

    if sum == s:
        cnt += 1

    fun(num+1, sum)
    fun(num+1, sum - lst[num])

fun(0,0)
print(cnt)

이 문제는 원석오빠가 백트레킹 문제를 풀어보라고 준 문제이담! 근데 씨쁠에서 파이썬으로 바꾼 뒤로 백트레킹을 처음 풀어보는게 레전드,, 감두 안와서 블로그들 보면서 해봤는데 설명이 길게 나와있는 블로그가 없었답 ㅜ 쉬운문제여서 그런거같당 그래서 코드를 계속 보면서 이해해보려고 했는데 처음엔 그것도 잘 안됐당.. 근데 한번 이해가 되고 난 뒤로는 실마리가 풀리는 느낌이었담! 생각보다 쉬운거였어서 왜 사람들이 설명을 길게 안 적어놨는지 알 것 같았다 왜냐면 쓸말이 정말 없기 때문.. 그래도 아직 혼자 코드 짜라고 하면 못짜겠어서.. 반복하고 외우는것만이 살길이다 ㅠㅠ!

num = int(input())
op = input().split()
mx, mn = "", ""    # 최대, 최소숫자
check = [False]*10    # 백트래킹 체크할 배열

def verify(a, b, c):    # 해당 자리에 숫자가 들어갈 수 있는지 검증
    if c == '>':
        return a>b
    else:
        return a<b

def fun(depth, s):    # 재귀함수 호출 DFS
    global mx, mn

    if depth == num+1:    # 끝까지 도달했을때
        if len(mn) == 0:    # 0부터 9로 가다보니 처음성공한게
            mn = s    # 제일 최소
        else:
            mx = s    # 최대는 계속 갱신
        return

    for i in range(10):    # 0 - 9 까지
        if not check[i]:
            if depth == 0 or verify(s[len(s)-1], str(i), op[depth-1]):    
            # depth가 0이면 오류나서
                check[i] = True    # 체크하고
                fun(depth+1, s+str(i))    # 재귀부르고
                check[i] = False    # 재귀 끝나면 체크해제

fun(0,"")    # 무에서 시작
print(mx)
print(mn)

• 요즈음 구글, 카카오, 네이버등 다른 서비스의 아이디를 이용해서 로그인을 하는 기술을 OAuth라고 하는데, Oauth 제공 서비스인 Firebase를 이용하여 google 로그인을 구현해보았다.

• 위 사진은 Oauth의 구성요소들과 각각의 동작방식을 나타낸 로직이다.

2. Firebase로 Google 로그인 구현하기

1) 프로젝트 셋업

• 
• Firebase Admin SDK에서 시작하기를 누르고 비공개키를 다운받은 뒤, 그 위치를 환경변수로 등록해준다.

2) Firebase 초기화

• FirebaseInitializer라는 Configuration을 하나 만들어 FirebaseAuth(인증 관련 모듈)을 초기화한다.

3) Filter에서 인증토큰 검증하기

• Controller에 접근하기 전에 먼저 Request를 인터셉트 해서 전처리 역할 및 후처리 역할을 할 수 있는데, 우리는 전처리 역할을 하게끔 만들었다.

• Filter는 Spring Security 설정과 결합하면 특정 Request와 결합할때만 사용자 요청을 처리할 수 있다. 따라서, 토큰을 검증하는 Filter를 만들고 Security 요청에 따라 검증하도록 하였다. (Client 단에서 Header에 Authorization: Bearer {FirebaseIdToken} 형태로 메세지가 온다고 가정)

• FirebaseTokenFilter : doFilterInternal를 override해서 Request가 들어오면 Header에서 토큰을 가져와서 FirebaseAuth로 토큰을 검증하고 UserDetailsService에서 사용자 정보를 가져와 SecuriyContext에 추가해주는 로직을 따르도록 하였다.

• SecurityConfig : HttpRequest를 받는 부분에 filter를 적용(addFilterBefore)하고 WebSecurity를 받는 부분에서 ignoring()에 Filter를 적용하지 않을 요청들을 추가하였다. 추가하지 않은 요청들은 FirebaseTokenFilter에서 토큰검증이 수행된다.