[백준] 1520번 내리막길 (파이썬)
난이도 : GOLD III > 문제링크 : https://www.acmicpc.net/problem/1520 문제해결 아이디어 단순 dfs만으로는 시간초과가 난다.=> dp를 활용해서 시간복잡도를 줄여야 함. 목표지점 n-1, m-1에 도달하면 시작점에서 도착점까지 성공적으로 방문한 한 가지 경우가 되므로 1을 리턴해주고, 해당 값을 지금까지 걸어온 경로에 모두 더해준다. 만약에 현재 방문중인 경로를 이미 다른 경로가 방문하여 -1이 아닌 다른 값으로 업데이트 되어있다면 (0 or n으로) 더 이상의 탐색은 진행하지 않고 해당 값을 업데이트 해준다.
[백준] 1937번 욕심쟁이 판다 (파이썬)
난이도 : GOLD III > 문제링크 : https://www.acmicpc.net/problem/1937 문제해결 아이디어 상, 하, 좌, 우로 이동해서 최대 일수를 구한다는 것에서 dfs를 바로 떠올릴 수 있었다. 경로를 반복해서 이동하는 문제를 줄이기 위해 dp를 사용하였다. dfs와 dp를 사용하는 것이 핵심인듯 하다. 소스코드 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline n = int(input()) graph = [] for _ in range(n): graph.append(list(map(int, input().split()))) dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] dp = [[0] * n for _ in range(n)] def dfs(x, y): if dp
[백준] 14226번 이모티콘 (파이썬)
난이도 : GOLD IV > 문제링크 : https://www.acmicpc.net/problem/14226 문제해결 아이디어 걸리는 시간의 최솟값을 구한다. 즉, 최단시간을 구해야하니 BFS로 풀면 된다. 3가지 연산만 사용해서 이모티콘을 S개 만든다 즉, 화면에 이모티콘의 개수 s와 클립보드에 있는 이모티콘의 개수c를 고려해서 풀면 된다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 복사 : (s,c) -> (s,s) 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 붙여넣기 : (s,s) -> (s+c, c) 화면에 있는 이모티콘 중 하나를 삭제한다. (s,s) -> (s-1, c) => 모든 연산은 1초가 걸리니 모든 경로의 가중치는 1이다. 따라서, dists + 1 과 같이 1을 더해줘야 한다. 소스코드
[백준] 10942번 펠린드롬 (파이썬)
난이도 : GOLD III > 문제링크 : https://www.acmicpc.net/problem/10942 문제해결 아이디어 양 끝의 문자가 다르면 -> 팰린드롬 아님 양 끝의 문자가 같을 때, 가운데 문자열이 팰린드롬이라면 -> 팰린드롬 팰린드롬이 아니라면 -> 팰린드롬 아님 가운데 문자열이 팰린드롬인지 아닌지 모른다면 알 때까지 문자열의 길이를 앞뒤로 하나씩 줄이면서 위의 과정을 반복한다. 소스코드
[프로그래머스] 숫자 변환하기 (파이썬)
난이도 : LV2 > 문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154538 문제설명 > 자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다. x에 n을 더합니다 x에 2를 곱합니다. x에 3을 곱합니다. 자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요. 문제해결 아이디어 x가 y가 될때 까지의 최소 연산을 요구하는 문제이다. dp를 사용하면 시간초과 없이 해결할 수 있다고 생각했다. 소스코드
[프로그래머스] 연속 펄스 부분 수열의 합 (파이썬)
문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/161988 난이도 : LV3 문제해결 이중 DP배열을 사용해서 전 단계에서 -1 을 곱했을 경우와, 1 을 곱했을 경우로 나눈다. 소스코드 def solution(seq): n = len(seq) dp = [[0] * n for _ in range(2)] dp0 = seq[0] * -1 dp1 = seq[0] for i in range(1, n): dp0 = max(-seqi], dp[1 - seq[i]) dp1 = max(seqi], dp[0 + seq[i]) _max = 0 for i in range(2): _max = max(max(d