1223v

https://www.acmicpc.net/problem/11657 전형적인 음수 간선 판단 문제이다.벨만포드를 이용하여 내부에서 음수 간선으로 인해 비용 감소가 계속 발생할 경우 -1을 출력하면 된다.import sysinput = sys.stdin.readlineN,M = map(int,input().split())edges = []distance = [float('inf')] * (N+1)def bf(start): distance[start] = 0 for i in range(N): for j in range(M): s,e,cost = edges[j] if distance[e] > distance[s] + cost: ..

https://www.acmicpc.net/problem/13565 위 문제는 아래까지 도착이 가능한지를 확인하는 탐색 문제이다. 해당 문제는 bfs, dfs로 모두 풀 수 있다.dfs 방식import syssys.setrecursionlimit(10**5)input = sys.stdin.readlineN,M = map(int,input().split())s = [list(map(int,input().rstrip())) for _ in range(N)]di = [1,-1,0,0]dj = [0,0,1,-1]def dfs(n,pi,pj): if pi == N-1 and s[pi][pj]==2: print("YES") exit() for i in range(4): ..

https://www.acmicpc.net/problem/10282 기본적인 다익스트라 알고리즘 문제이다.import sysinput = sys.stdin.readlineimport heapqdef dijkstra(graph, start): time = [int(1e9)] * (N+1) time[start] = 0 hq = [] heapq.heappush(hq,(0,start)) while hq: c_time, c_com = heapq.heappush(hq) for s, a in graph[c_com]: if c_time+s endTime: endTime = t return ..

https://www.acmicpc.net/problem/11054 부분 수열 시리즈 문제이다. 당연히 dp 문제이다. 하지만 추가로 조건이증가하는 부분수열 + 감소하는 부분 수열을 더해서 가장 긴 부분 수열을 찾는 것이다.import sysinput = sys.stdin.readlineN = int(input())s = list(map(int,input().split()))reverse_s = s[::-1]dp = [1] * Nreverse_dp = [1] * Nfor i in range(N): for j in range(i): if s[j]  회고.반대로 된 배열을 만들어 하나의 for문으로 하는 것은 좋았으나, 거꾸로 만든 배열을 증가하는 부분수열 + 감소하는 부분 수열 하는 과정..

https://www.acmicpc.net/problem/2631 가장 긴 증가하는 부분 수열의 심화 문제이다.dp를 통해 가장 많이 증가하는 폭을 찾고, 증가하는 폭을 제외한 나머지 값들은 값을 이동 시켜야하므로, (N-가장 긴 증가하는 폭) 정답이다.import sysinput = sys.stdin.readlineN = int(input())dp = [1] * Ns = []for _ in range(N): s.append(int(input()))for i in range(N): for j in range(i): if s[j]  회고.처음 문제를 접근했을때는 dp라는 감도 못잡았다. 또한, 가장 긴 증가하는 부분 수열을 통해 이동하지 말아야할 값을 찾고 이동하는 값을 N으로 빼줌..

https://www.acmicpc.net/problem/1965  부분 수열 dp 문제와 매우 유사한 문제이다. 제일 긴 부분 수열 문제처럼 dp 테이블에 1씩 더해주면서 값을 늘려주고 최댓값을 찾으면 된다. 하지만, 마지막 본인 수까지 포함해야함으로 마지막에 max값에 +1을 해준다.import sysinput = sys.stdin.readlineN = int(input())s = list(map(int,input().split()))dp = [0] * Nfor i in range(N): for j in range(i): if s[j]  회고.부분 수열문제를 최근에 풀어 바로 풀 수 있었던것 같다. 만약 2개월 지난 후 본다면 풀 수 있을까 의문이다...

https://www.acmicpc.net/problem/11055 DP의 대표적인 문제라고 할 수 있다. 여기서 주의할 점은 갯수가 아닌 값을 더해서 최댓값을 찾는 것이다.우선 dp 테이블을 s와 동일하도록 구성해주고, j 부터 i까지 가는 도중에 s[j] import sysinput = sys.stdin.readlineN = int(input())s = list(map(int,input().split()))dp = s[:]for i in range(N): for j in range(i): if s[i] > s[j]: dp[i] = max(dp[i], dp[j]+s[i])print(max(dp)) 회고.처음에 가장 큰 증가하는 부분 수열을 dp테이블 초기화 과정에서..

https://www.acmicpc.net/problem/9655  해당 문제는 2개의 풀이가 가능하다. 그리디 풀이 방식import sysinput = sys.stdin.readlineN = int(input())# 1개 혹은 3개chk = -1while N >0: chk = -chk if N - 3 >0: N -= 3 else: N -= 1if chk == 1: print("SK")else: print("CY")   dp 풀이 방식import sysinput = sys.stdin.readlineN = int(input())dp = [False] * (N+1)dp[1] = Trueif N >= 2: dp[2] = Falseif N >= 3: ..

https://www.acmicpc.net/problem/2116 제한된 조건 내에 최대 값을 찾는 완전 탐색 문제이다.백트래킹으로 탐색을 진행했는데 이 코드에서 유심히 봐야할 코드는 조건문이다.조건에서 0와 5은 서로 반대편이므로 total 값에 사용될 수 없다.마찬가지로 [1, 3 ] [2,4]는 만약 위,아래 값을 마추는 주사위로 사용되었으면, 사용이 불가능한 인덱스가 되어버린다.즉, 이전 재귀함수에서 보내준 주사위 윗값이 같은 인덱스를 찾고 그 인덱스와 연관된 ([1, 3 ] [2,4], [0,5]) 값일 경우를 제외한 모든 값중 가장 큰값을 더한 후 다음 재귀로 넘겨주면 된다.import syssys.setrecursionlimit(10**5)input = sys.stdin.readlineN =..

https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  백트래킹을 이용한 완전 탐색 문제라고 생각했다.방문할 수 있는 던전의 최대값을 백트래킹을 통해 확인해본 뒤, 가장 큰 값을 반환하는 문제이다.max_value = 0def solution(k, dungeons): length = len(dungeons) visited = [False] * (length) def dfs(n, now, cnt): global max_value max_valu..