해설지에서 미쳐 다 담지 못한 디테일한 풀이를 정리해서 올려보았습니다. 혹시라도 읽어보고 이해가 되지 않는 부분이나 다른 의견은 댓글에다가 남겨주시길... 문제: https://www.acmicpc.net/problem/32224난이도: 골드 상위 ~플레 하위Code Master 2024에 내가 직접 출제한 문제이다. DFS를 사용하여 풀면 된다.뭔 문제야 이게?혹시라도 문제를 이해하지 못 한 사람들을 위해 예제를 통해 설명해주겠다.7 64 2 2 1 1 1 11 1 2 2 3 3예제입력 1을 tree 구조로 나타내면 이러한 형태일 것이다.이 상황에서 6의 물을 어느 물탱크부터 넣어야 가장 많은 물탱크를 채울 수 있을까? 중요한 조건은 현태 물탱크가 꽉 찬다면, 부모 물탱크로 물이 넘쳐 올라간다는 것이다..

문제:https://www.acmicpc.net/problem/17070난이도: 골드5파이프를 (1,1),(1,2) 부터 시작하여 반대쪽 끝점까지 옮기면 되는 문제이다.아이디어1우선 보자마자 bfs를 떠올렸고, 탐색을 할때 x,y 말고도 방향 r을 넣어서 케이스를 나눴고, 각 방향마다 요구하는 빈칸이 다르기 때문에 이를 if문을 통해 걸러 리스트에 넣어준다.시도1from collections import dequen=int(input())l=[]for i in range(n): l.append(list(map(int,input().split())))cnt=0d=deque([(0,1,0)])#세로,가로,방향while len(d)!=0: p,q,r = d.popleft() if(p==n-1 ..

문제:https://www.acmicpc.net/problem/17298난이도: 골드 4스택을 이용하여 최댓값을 구하는 문제. 처음 보는 개념이라 이해하는데 꽤 애를 먹었다.아이디어1처음에는 단순하게 최댓값을 찾아서 계속 업데이트 해주는 방식을 생각해봤는데, 단순 계산으로도 O(n^2)이 넘어서 안된다. 입력 값이 10만이기 때문에 O(nlogn) 또는 O(n)으로 풀어야 된다.아이디어2다음은 스택을 사용한 풀이이다. 혼자 생각한건 아니고, 대충 찾아보면서 삽질 좀 했다.스택은 선입후출(Last In Fisrt Out)의 방식을 가진 자료구조로, 선입선출 방식인 큐와 대비되는 방식이다. 이를 이용해서 최댓값을 구할 수 있는데, 스택을 하나의 탑으로 보자면, 값이 들어올때마다 탑의 맨 윗부분부터 비교하면서..

https://www.acmicpc.net/problem/1202난이도: 골드 2학교에서 친구와 함께 푼 문제. 그리디 알고리즘을 쓰되, 최대한 효율적으로 최댓값을 구해야 한다.아이디어1우선 가방마다 담을 수 있는 무게가 다 다르기 때문에, 가방에 담을 수 있는 무게 C에 대하여 C보다 작은 보석 중 가장 가치 있는 보석을 계속해서 가져가면 된다.실패한 이유그러나 이 알고리즘은 잘못됐다. 왜냐하면 계산 과정이 매우 오래 걸리기 때문이다. 우선 C가 어디 사이에 있는 값인지 알아야 한다. 물론 bisect라는 이진탐색을 지원해주는 함수를 쓰면 되지만 그런다 하더라도, 최댓값이 어딨는지 찾는 과정에서 배열 순회를 해야하기 때문에 시간 초과가 날 것이다. 이를 해결해주기 위해서 전에 공부했던 우선 순위 큐를 ..

문제:https://www.acmicpc.net/problem/9251난이도: 골드 5 LCS(Longest Common Subsequence, 최장 공통 부분 수열)를 찾으면 되는 문제이다. DP를 쓰는 방법에 있어서 꽤 애를 먹었다.아이디어1처음 생각했던 풀이는 배낭 문제에서 영감을 얻어 두 번째 리스트에서 각 문자열마다 가질 수 있는 최장 부분 문자열을 저장해주는 것이었다. 이중 for문을 사용해서 같은 문자열이 나오면 그 전 값 중에서 최댓값을 찾아 +1 해주는 식으로 코드를 짜봤다. 아래는 모식도이다.입력:ACAYKPCAPCAK시도1n=input()m=input()l=[0]*len(n)for i in n: t=l[:] for j in range(len(m)): if i==..

문제:https://www.acmicpc.net/problem/11444난이도: 골드 2단순히 피보나치 수를 구하는 문제. 다만 n이 무지막지하게 큰.아이디어 1처음에는 분할 정복을 어떻게 쓸지 생각이 안 떠올랐다. 그렇게 고민을 하다가 피보나치 수를 직접 나눠서 써보기로 하였다.우선 n이 짝수일 때이다. n=2k일 때 k번째 항까지 분할을 하였다.f(10)을 예시로 들어봤다. 2개로 계속해서 나누었을 때 항의 개수가 피보나치수열을 이루는 것을 알 수 있다. n/2까지 과정을 반복해 보면 다음과 같은 식을 얻을 수 있다.다음은 n이 홀수 일 때다.n=k//2+1이라 할 때 k번째 항까지 분할하였다. 일반항으로 나타내면 다음과 같다.나도 왜 이런 식이 나오는지는 모른다. 2시간 정도 노트에다가 끄적여보며 ..

문제:https://www.acmicpc.net/problem/12851난이도: 골드 4숨바꼭질(실버 1)의 확장판. 숨바꼭질 같은 경우는 visited를 0과 1로 체크해 주면서 이동하면 bfs로 해결할 수 있었지만, 최단 경로의 개수를 구해야 하므로 단순히 0과 1로만 체크를 하면 안 된다는 걸 알 수 있다. 아이디어 1처음에는 단순 bfs를 변형해서 풀 생각을 했다. 최솟값을 찾으면 그걸 저장해 주고 개수를 세주다가 더 작은 최솟값이 나오면 갱신해서 다시 세주는 방식으로 끝까지 세어줬다. 시도 1from collections import dequen,k = map(int,input().split())c=[0]*100001d=deque()d.append(n)c[n]=1s=0check=Truemin_s..

문제:https://www.acmicpc.net/problem/12865정석적인 dp 문제이나... 이해하는데 꽤나 애를 먹었다. 다음 문제를 위해 정리해서 글을 끄적여본다.아이디어1우선 처음에는 이중 for문을 돌면서 리스트에다가 가능한 모든 조합을 넣어서 max 값을 뽑아냈다.(난 이게 완전 탐색인지도 몰랐다) 시도1from collections import dequen,k=map(int,input().split())w=[0]*nv=[0]*nfor i in range(n): w[i],v[i] = map(int,input().split())d=deque()c=0for i in range(n): d.append((w[i],v[i])) for j in range(0,len(d)-1): ..

문제:https://www.acmicpc.net/problem/9663 n*n 격자판 위에 n개의 퀸을 배치할때, 퀸이 서로를 공격하지 못하게 배치하는 경우의 수를 구하시오.백트래킹을 이용하는 굉장히 유명한 문제이다.아이디어백트래킹을 이용해서 위쪽 줄부터 차례대로 재귀함수를 사용해 탐색하면서 내려가면 된다.이때 겹치는 세로줄,대각선을 체크하여 들어갈 수 있는지 확인하기 위한 리스트를 만든다. 우하향,우상향 대각선을 분리해서 생각해주었다. 퀸이 있는 자리에 배열 값을 바꿔주면서 내려와서 마지막줄에 도달하면, count +=1을 해주어 개수를 세었다.각 x,y에서 col1,diag1,diag2의 어떤 값이 올지 생각해주는게 관건이었던거 같다.정답 코드n=int(input())col1=[0]*n#세로diag1..