문제: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/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/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..