NISSO

DFS (Depth First Search) : 깊이 우선 탐색 - 모든 노드 방문 - 스택이나 재귀함수를 통해 구현 - 미로찾기 BFS (Breadth First Search) : 너비 우선 탐색 - 최단 경로 탐색 - 큐를 통해 구현 - 인접 노드를 먼저 탐색

이것도 이전 문제처럼 혼자 힘으로 풀 수 있을 줄 알았다. 일단 애초에 절대 혼자 못 풀었고, 구글링으로 힌트라고 해야하나, 코드만 안 봤지 코드 동작방식 설명을 보고 풀었다. 그리고 첫 계단을 안 밟아도 된다는 걸 몰랐다. 아무리 생각해도 답이 맞았는데 자꾸 틀렸대서 질문검색을 해보고 알았다. 계단은 '한 계단을 밟으면서' 오를 수 있다길래 첫 계단은 기본인 줄 알았다. .... 어쨌든 코드 동작방식을 보고 그대로 구현한 코드는 다음과 같다. n = int(input()) st = [int(input()) for _ in range(n)] dp = st[:1] + [0]*(n) for i in range(1,n): dp[i] = max(st[i]+st[i-1]+dp[i-3], st[i]+dp[i-2])..

드디어! 혼자 힘으로 푼 문제. 사실 전의 문제 [백준 1149]에서 조금 변형된 수준이라 풀 수 있었다. n = int(input()) t = [] for i in range(n): t.append(list(map(int,input().split()))) for i in range(1,n): t[i][0] = t[i][0] + t[i-1][0] t[i][i] = t[i][i] + t[i-1][i-1] for j in range(1,i): t[i][j] += max(t[i-1][j-1],t[i-1][j]) print(max(t[n-1])) 지금까지 풀었던 dp 문제들은 dp 변수에 리스트를 지정해줬기 때문에 이 문제도 그렇게 풀기 시작했다. dp = [[0]*(i+1) for i in range(n)] ..

이전 글에서 DP에 대해 이제 감이 잡히는 것 같다고 했는데 전혀 아니었나보다. 무조건 스스로 풀겠다 다짐해놓고 결국 또 구글링했다. 문제들을 다 구글링으로 풀어서 실력이 과연 늘지 의문이다. n = int(input()) cost = [] for i in range(n): cost.append(list(map(int, input().split()))) dp = [[0]*3 for _ in range(n)] dp[0] = cost[0] for i in range(1,n): dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0] dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1] dp[i][2] = min(dp[i-1][0], ..

DP 문제를 이제 2~3개 정도 풀어본 것 같은데 드디어 감이 좀 잡히려고 한다. 아직 쉬운 것만 풀어봐서 그럴진 모르겠지만 감이라도 잡힌 것에 감사하고 있다. 풀다보면 늘 거라고 생각한다. 1 1 1 2 2 00 11 3 3 001 100 111 4 5 0000 0011 1001 1100 1111 5 8 00001 00100 10000 00111 10011 11001 11100 11111 6 13 000000 000011 001001 001100 100001 100100 110000 001111 100111 110011 111001 111100 111111 7 21 0000001 0000100 0010000 1000000 0000111 0010011 0011001 0011100 1000011 10010..

피보나치를 활용한 답 구하기 문제인 줄 알았는데 해결방법 자체가 피보나치였다. 답을 구하는 과정이 피보나치 수열로 나오기 때문이다. > 실패한 코드 1 def fibo(n): global n0, n1 if n==0: n0 += 1 return 0 elif n==1: n1 += 1 return 1 return fibo(n-1) + fibo(n-2) l = list(int(input()) for j in range(int(input()))) for i in l: n0, n1 = 0,0 fibo(i) print(n0, n1) 처음 썼던 코드. 답은 맞았지만 시간초과로 실패했다. 위에서 말했듯이 재귀를 통해 피보나치를 구하는 과정에 0과 1이 출력되는 경우를 카운팅한 것이다. 문제를 직독직해해서 그대로 풀었다고..

체스를 모르는 나에겐 문제 내용이 너무 부족했다. 서로 공격할 수 없는다는 게 어떤 건지 몰랐다. 체스도 모르고 백트래킹도 잘 모르니 유튜브에 검색하다가 좋은 강의 영상을 봤다. 자세하게 알려주고 기본 설명과 구현, 두가지 영상으로 나뉘어있다. 주니온TV아무거나연구소 - 파이썬으로 배우는 알고리즘 기초: 18. 백트래킹과 n-Queens 문제 문제 설명을 간단히 하자면, 크기가 N*N인 체스판에 퀸 N개를 서로 공격할 수 없게 놓는 방법의 수를 구하는 문제다. 이 때, 퀸은 다른 걸 공격할 수 없도록 같은 행, 열, 대각선 외의 위치에 놓아야 한다. (x1,y1), (x2,y2)가 있을 때 |x1-x2| = |y1-y2| 면 같은 대각선상에 있다. 풀어본 결과, 내 결론은 파이썬으로 푸는 건 거의 불가능..

전 문제(15651)에서 검색을 통해 나름 공부했다고 생각했는데 아니었나보다. 조건 하나만 추가된 건데, 정답률도 80% 이상인데 나는 풀지 못했다. >방법1 a,b = map(int, input().split()) l = [] def back(a,b,i=0,t=0): if b==i: print(*l) return for j in range(t,a): l.append(j+1) back(a,b,i+1,j) l.pop() back(a,b) 15651과 달리 인자 t가 추가되었고 DFS방식을 이용해 해결하는 것이었다. 그래서 append와 pop이 추가되었다. 그리고 다른 사람의 정답들을 보면서 itertools의 또 다른 유용한 함수를 배웠다. > 방법2 from itertools import combina..