이숭간 공부기록

www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제유형 : DP 문제핵심 : 뒤에서부터 확인해서 DP값을 갱신하는것 아래 두 값중에 더 큰값으로 갱신이 이루어진다 i번째 일을 할때의 이익 ( = i번째일의 이익 + i번째일을 하는데 걸리는시간후의 이익) : cost[i]+dp[i+day[i]]) i번째 일을 건너뛰고 i+1번째 일을 할때의 이익 : dp[i+1] 핵심 점화식 : dp[i] = max(dp[i+1], cost[i]+dp[i+day[i]]) 둘중에 더 큰값으로 dp[i]값을 갱신하고 최종적으로 dp[0]의 값이 최대가된다 n = int(input()) day = [] cost = ..

www.acmicpc.net/problem/11399 이문제는 문제 읽자마자 풀이방법이 생각이 나서 큰 고민없이 맞았다. 그냥 쉬운 문제였다. 핵심아이디어 : 오름차순으로 정렬후에 더하는 개수를 1,2, 3, ~~~ n까지 더해야 가장 최소가 나온다(?) 앞에서부터 중복해서 더해지기때문에 중복되는 횟수가 많은 수일수록 적어야 최종합은 가장 적으니까 내코드 n = int(input()) input_list = list(map(int, input().split())) input_list.sort() print(input_list) count = 0 for i in range(len(input_list)): count += sum(input_list[:i+1]) #인덱싱은 범위초과해도 오류안남 print(co..

www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제유형 : DP 문제해설 : 1 = (1) 2 = (1 + 1), (2) 3 = (1 + 1 + 1), (1 + 2), (2 + 1), (3) 4 = (1 + 1 + 1 + 1), (1 + 1 + 2), (1 + 2 + 1), (1 + 3), (2 + 1 + 1), (2 + 2), (3 + 1) 핵심 : 점화식찾기 F(n) = F(n-1) + F(n-2) + F(n-3) (n>3) 을 찾으면 쉽게 풀리는 문제였다. test_case=int(input()) input_list=[int(input()) for ..

입력을 받아 2차원배열로 연결된 노드를 표현하는 그래프를 만들고, dfs혹은 bfs를 통해 노드를 방문 최종적으로 1번(감염된노드)로부터 연결되어있어서 방문된 노드의 개수를 출력 내코드 : dfs로 해도 되는데 bfs로 풀어봄 ( 큐 이용 ) from collections import deque p = int(input()) q = int(input()) graph = [[] for _ in range(p+1)] for _ in range(q): n, k = map(int, input().split()) graph[n].append(k) graph[k].append(n) visited = [False] * (p+1) def bfs(graph, start, visited): queue = deque([st..

정렬이란? 데이터를 특정한 기준에 따라 순서대로 나열하는것 일반적으로 문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용됨 선택정렬 : 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는것을 반복 시간복잡도 : O(n^2) 삽입정렬(Insertion Sort) : 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입 ( 위치를 매번 계산해서 데이터를 넣어줌 / 정렬범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 꼽아주는 알고리즘 시간복잡도 : O(n^2) 선택정렬에 비해 난이도가 높지만 더 효율적으로 작동함, 특히 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하여 최선의 경우 O(N)의 시간복잡도를..

대표적 그래프탐색 알고리즘 : DFS / BFS 탐색이란, 많은 양의 데이터중 원하는 데이터를 찾는 과정 _ 파이썬에서는 간단히 리스트로 스택 구현 가능 DFS : 깊이우선 탐색으로 가장 깊은곳까지 먼저 탐색하는 방식 DFS는 스택자료구조(혹은 재귀함수)를 이용한다. 1. 시작노드를 스택에 삽입 / 방문처리 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 더이상 2번의 과정을 수행할 수 없을때까지 반복한다. 너비우선탐색으로 그래프에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. BFS는 큐를 이용한다. 1. 탐색 시작노..