목록전체 글 (246)

웹찢남

[백준 10942 펠린드롬? 문제] PYTHON

펠린드롬 문제 자체는 어렵지 않아 처음에는 아래 코드와 같이 간단하게 구현을 해봤다. N = int(input()) Narray = list(map(int, input().split())) M = int(input()) for _ in range(M): S, E = map(int, input().split()) if Narray[S:E+1] == Narray[S:E+1][::-1]: print(1) else: print(0) 하지만 역시 골드 문제답게 호락호락하지 않아 시간초과로 False가 나왔다. 결국 여러 방법을 찾아보고 NxN 2차원 배열에 1,0으로 T/F로 저장을 해서 푸는 법을 알았다. 처음에 이런 방식을 생각하기는 했지만 이런 방식으로 풀면 N도 크고 M도 커서 시간 초과가 걸릴까 포기한 ..
백준 Algorithm 2021. 8. 24. 16:09
[백준 1915 가장 큰 정사각형 문제] PYTHON

전형적인 Dynamic Programming 문제로 머리를 굴려서 방안을 모색해야 한다. 새로운 DP 배열을 사용하기보다 주어진 배열을 사용하기로 했다. 문제를 푸는 법은 기존의 배열에서 for 문으로 모든 index를 탐색하며 만약 자신, 왼쪽, 위, 왼쪽 위의 index 값이 1일 경우 정사각형을 이루므로 자신을 제외한 3개의 index의 min 값을 자신의 index에 더하는 것으로 구현했다. 만약 길이 3짜리 정사각형일 경우 왼쪽, 위, 왼쪽 위의 min 값은 2가 되므로 길이 3이상에서도 문제없다. DP문제는 구현은 비교적 쉬운 것 같지만 상상을 많이 해야해서 힘든 것 같다. case = [] N, M = map(int, input().split()) for _ in range(N): case...
백준 Algorithm 2021. 8. 23. 00:01
[백준 1916 최소비용 구하기 문제] PYTHON

이번 문제는 최소비용 구하기 문제로 방향이 있는 edge들의 최소 비용을 구하면 된다. 우선은 평소와 같이 DFS를 사용하여 구현을 해보려했다. 아래와 같이 풀었지만 메모리 에러가 발생하여 구글링을 통해 다익스트라 알고리즘을 사용하기로 헀다. def DFS(start, end, cost): global answer if start == end: if cost < answer: answer = cost for i in range(1, M+1): if Mgraph[start][i] != 0: cost += Mgraph[start][i] if answer
백준 Algorithm 2021. 8. 20. 00:38
[백준 2252 줄 세우기 문제] PYTHON

이 문제는 위상 정렬을 사용해서 푸는 문제다. 위상 정렬이란 사이클이 없고 방향만 존재하는 vertex를 나열하는 것이다. 이 문제에선 키를 비교한 리스트에서 자신을 참조한 (자신보다 앞에선) vertex가 0인 것을 큐에 넣는다. - 여기서 무조건 맨 뒤에 있는 vertex는 0이므로 무조건 값이 있음 - 그 후 queue를 while문을 통해 돌리며 자신을 참조한 value들의 참조값을 -1 하며 queue 내의 index를 remove하고 다시 참조값이 0인 vertex를 append하며 반복을 하면 된다. 코드로 구현하면 아래와 같다. N, M = map(int, input().split()) indegree = [0 for i in range(N+1)] Tlist = [[] for i in ra..
백준 Algorithm 2021. 8. 18. 00:02
[백준 2056 작업 문제] PYTHON

이번 문제의 핵심은 K번 작업을 시작하기 전 완료되야하는 작업들이 1~K-1라는 부분이다. 따라서 for문을 돌며 K번째 작업은 1~K-1 작업 시간의 max 값 + K번째 작업의 시간이 된다. 이를 코드로 구현하면 아래와 같다. T = int(input()) Clist = {} cost = {0: 0} for i in range(1, T+1): tmp = list(map(int, input().split())) cost[i] = tmp[0] if(len(tmp) == 2): Clist[i] = [0] else: Clist[i] = tmp[2:] for j in range(1, T+1): temp = 0 for k in Clist[j]: temp = max(temp, cost[k]) cost[j] += ..
백준 Algorithm 2021. 8. 17. 16:57
[백준 2293 동전 1, 9084 동전 문제] PYTHON

9084 문제와 2293 문제는 거의 동일하다. 다른 점은 input을 받는 방식과, 9084는 여러 case들이 주어진 다는 점이다. 따라서 9084 문제를 풀 수 있으면 둘 다 풀 수 있다. 아래는 9084 문제의 풀이이다. 동전 문제를 푸는 법은 0원부터 목표 가격까지 1원 단위로 배열로 만들어 해당 가격을 만들 수 있는 방법의 수를 저장한다. 그 후 dp[k]+=dp[k-c] 로 배열을 늘려가면 문제를 풀 수 있다. T = int(input()) for i in range(T): N = int(input()) Clist = list(map(int, input().split())) target = int(input()) dp = [0 for _ in range(target+1)] dp[0] = 1 ..
백준 Algorithm 2021. 8. 17. 13:32
Prev 1 2 3 4 5 6 7 ··· 41 Next