본문 바로가기
  • 초부득3 - 어제보다 나은 내일을 위해
  • 꿈이 현실이 되는 날까지

전체 글195

[그리디] 백준 회의실 배정 1931번 with Python3 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 내 풀이 -실패- import sys input = sys.stdin.readline n = int(input()) tmt = [list(map(int, input().rstrip().split())) for _ in range(n)] tmt.sort() ans = [] check = 0 chk2 = 0 for i in range(n): if check = end_time: cnt += 1 end_time = time[i][1] print(cnt) 출처:https://suri78.tistory.com/26 .. 2021. 8. 30.
그리디 알고리즘 동빈나 강의:https://www.youtube.com/watch?v=2zjoKjt97vQ 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 그리디 해법은 그 정당성 분석이 중요. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토. 정당성 분석 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코딩 테스트에서 대부분의 그리디 문제는 탐욕법으로 얻는 해가 최적의 해가 되는 상황에서, 이를 추론 할 수 있어야 풀리도록 출제 됨. 2021. 8. 30.
[DP] 백준 LIS 11053번 with Python3 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 내 풀이 n = int(input()) sqnc = list(map(int, input().split())) # dp = sqnc[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이 dp = [1 for _ in range(n)] for i in range(n): for j in range(i): i.. 2021. 8. 29.
[DP] 백준 점프 2253번 with Python3 ★★ https://www.acmicpc.net/problem/2253 2253번: 점프 N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은 현재 1번 돌 위에 있는데, 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려 www.acmicpc.net 문제 풀이 import sys input = sys.stdin.readline n, m = map(int, input().rstrip().split()) max_speed = int((2*n)**0.5) + 1 dp_table = [[float('inf')] * (max_speed+1) for i in range(n+1)] # dp_table[i][j] / [i] = 돌 번호 [.. 2021. 8. 28.
[DP] 백준 평범한 배낭 12865번 with Python3 ★ https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 정답 풀이 import sys N, K = map(int, input().split()) stuff = [[0,0]] for _ in range(N): stuff.append(list(map(int, input().split()))) #냅색 문제 풀이 knapsack = [[0 for _ in range(K + 1)] for .. 2021. 8. 27.
[DP] 백준 LCS, 2 9251번 with Python3 ★ https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 정답 풀이 import sys X = sys.stdin.readline().strip().upper() Y = sys.stdin.readline().strip().upper() len1 = len(X) len2 = len(Y) dp = [[0] * (len2 + 1) for _ in range(len1+1)] for i in range(1, len.. 2021. 8. 27.
다이나믹 프로그래밍 동빈나 강의 :https://www.youtube.com/watch?v=5Lu34WIx2Us https://blog.naver.com/ndb796/221233570962 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않음 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운, 바텀업)으로 구성 일반적인 프로그래밍 분야에서의 동적(Dynamic)의 의미 프로그램이 실행되는 도중 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법' 다이나믹 프로그래밍에서 다이나믹은 특별한 의미는 없음. 다이나믹 프로그맹의.. 2021. 8. 26.
[BFS] 백준 이분 그래프 1707번 with Python3 ★ https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 문제 정답 풀이 ### bfs import collections import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline for _ in range(int(input())): V, E = map(int, input().split()) graph = [[] for i in range(V+1)] # 빈 그래프 생성 visi.. 2021. 8. 25.
[DFS, DP] 백준 내리막길 1520번 with Python3 ★★ https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 문제 정답 풀이 import sys input = sys.stdin.readline sys.setrecursionlimit(10000) dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] def dfs(x, y): if x == 0 and y == 0: return 1 if dp[x][y] == -1: dp[x][y] = 0 for i in range(4): nx = x + dx.. 2021. 8. 25.

티스토리툴바