본문 바로가기

PS25

[BOJ] Python 백준 침투(13565) 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): .. 2024. 12. 18.
[BOJ] Python 백준 해킹(10282) 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 .. 2024. 12. 10.
[BOJ] Python 백준 가장 긴 바이토닉 부분 수열(11054) 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문으로 하는 것은 좋았으나, 거꾸로 만든 배열을 증가하는 부분수열 + 감소하는 부분 수열 하는 과정.. 2024. 11. 28.
[BOJ] Python 백준 줄세우기(2631) 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으로 빼줌.. 2024. 11. 28.

티스토리툴바