목록백준 Algorithm (60)

웹찢남

[백준 5502 펠린드롬 문제] PYTHON

아래의 LCS 알고리즘의 점화식만 안다면 쉽게 풀 수 있는 문제다. 만약 두 알파벳이 같을때, dp[i][j] = dp[i -1][j - 1] +1 두 알파벳이 다를때는 dp[i][j] = max(dp[i -1][j], dp[i][j -1]) https://gusdnr69.tistory.com/192 LCS 알고리즘이란? (최장 공통 부분 수열) LCS는 longest common subsequence의 약자입니다. 우리나라 말로는 최장 공통 부분 수열을 의미합니다. 이해하기 쉽도록 longest common substring 과 비교해보겠습니다. substring은 연속된 부분 문자열이고 su.. gusdnr69.tistory.com import sys input = sys.stdin.readline ..
백준 Algorithm 2021. 10. 8. 22:46
[백준 1937 욕심쟁이 판다 문제] PYTHON

이 문제는 출발점이 정해져있지 않기때문에 시간 복잡도에 더 유의해야한다. 또한, 방문했던 노드에서 가질 수 있는 최댓값(이동거리)은 동일하기 때문에 이를 저장하여 사용하도록 한다. (DP+DFS) from sys import stdin from sys import setrecursionlimit setrecursionlimit(10**9) dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] input = stdin.readline answer = 0 def DFS(i, j): if visit[i][j] < 0: visit[i][j] = 0 for k in range(4): xindex = i+dx[k] yindex = j+dy[k] if 0
백준 Algorithm 2021. 9. 10. 17:17
[백준 1744 수 묶기 문제] PYTHON

그리디 알고리즘 문제다. 단순한 문제인데 골드로 평가된 이유는 hidden case 가 좀 있다. 신경써야 할 사항은 1. 음수와 음수의 곱 2. 음수와 0의 곱 3. 1의 존재이다. 이걸 생각하며 코드를 짜면 아래처럼 나온다. from sys import stdin input = stdin.readline t = int(input()) minus = 0 oneval = 0 gd = [] for _ in range(t): tmp = int(input()) if tmp
백준 Algorithm 2021. 9. 10. 15:36
[백준 1202 보석 도둑 문제] PYTHON

우선 보석 리스트와 가방 리스트를 받아 정렬한다. 그 후 힙을 사용하여 문제를 해결해야한다. 가방을 기준으로 for문을 돌리는데 이때 가방은 sort되어 무게가 작은 순으료 값이 나온다. 여기서 생각해야 할 점은 보석도 무게를 기준으로 sort 했기 때문에 보석을 heap에 넣어 놓고 다음 for 문 루프를 돌아도 heap에 있는 보석은 다음 가방 속에도 들어갈 수 있다. 그렇다면 heap에 보석을 넣을 때 maxheap으로 값을 넣고 for문이 돌때마다 가방에 들어갈 수 있는 보석을 업데이트 하며 heap 속에 들어있는 가장 가치있는 보석을 pop 하여 result에 값을 더하면 답이 나오게 된다. 처음에는 단순히 이중 포문으로 문제를 해결하려 했으나, 역시나 안된다. import sys import ..
백준 Algorithm 2021. 9. 9. 22:33
[백준 4358 생태학 문제] PYTHON

처음에는 두가지 방식을 생각을 했다. 1. dict 객체를 만들어 input을 하나씩 넣고 마지막에 sort를 하는 방식 2. input을 다 받고 sort를 하여 list를 순회하며 퍼센트를 출력하는 방식 결국은 첫번째 방식으로 코드를 구현했다. import sys from typing import DefaultDict input = sys.stdin.readline n = 0 trees = DefaultDict(int) while True: a = input().rstrip() if not a: break trees[a] += 1 n += 1 trees2 = list(trees.keys()) trees2.sort() for a in trees2: print('%s %.4f' % (a, trees[a]..
백준 Algorithm 2021. 9. 9. 15:47
[백준 1309 동물원 문제] PYTHON

DP 문제는 규칙을 찾을 수 있으면 쉽다. 우선 N=1일때 2일때 ~ 이런식으로 N=4일때까지의 값을 계산해봤다. 결국 i[N]= i[N-2]+i[N-1]*2 라는 규칙을 찾을 수 있었다. N = int(input()) dp = [1, 3] for i in range(2, N+1): dp.append((dp[i-1]*2+dp[i-2]) % 9901) print(dp[-1])
백준 Algorithm 2021. 9. 7. 17:14
Prev 1 2 3 4 ··· 10 Next