이숭간 공부기록

www.acmicpc.net/source/26224365 로그인 www.acmicpc.net 문제유형 : DFS/BFS _ connected component찾기 문제핵심 : 한칸의 땅을 노드로 하고 상하좌우로 연결을 갖는 그래프라고 생각하고 각 노드마다 DFS를 수행하여 처음 DFS를 시작한부분에서만 카운트 DFS수행방법 : 하나의 노드는 상하좌우로 연결되어있다고 생각하고 해당 노드가 1이면서 방문되지 않았을때 ( 배추가 심어져있으면서 방문전이면 ) 방문처리+ 상하좌우로 움직여서 다시 해당노드에서 재귀적으로 DFS수행 그래프는 2차원배열로 구현한 좌표평면의 형태이며, 움직일때마다 움직인곳이 좌표평면을 넘어가면 안되므로 그부분만 예외처리를 해주면된다. 처음 DFS를 시작한부분에서만 카운트하는 방법 : D..

순차탐색 : 리스트 안에 있는 특정한 데이터를 찾기위해 앞에서부터 하나씩 확인 이진탐색 : 정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 데이터 탐색 ( 시작점, 끝점, 중간점을 이용하여 탐색범위를 설정한다.) 단계마다 절반씩 줄어드는 알고리즘의 시간복잡도는 보통 로그N 내코드 _ 잘못됨 ( 완전탐색이므로 시간초과남 ) n,m = map(int, input().split()) input_list = list(map(int, input().split())) for i in range(max(input_list), 0, -1): count = 0 for j in input_list: count += max(0, j-i) if count >= m: print(i) break 내코드2 _ 이진탐색으로 다시..

www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제유형 : DP / 수학(다르게푼방식) 문제핵심 : 피보나치수열과 같은 점화식임을 깨닫는것(?) dp[i] = dp[i-1]+dp[i-2] 피보나치수열과 같은 형태의 점화식이 나오는 이유 : i번째 사각형의 채우는 방법은 i-1번째에 2*1짜리 사각형을 붙이는것 (오른쪽 기준) + i-2번째에 1*2짜리 사각형을 붙이는것 생각보다 이런유형의 문제는 어느정도까지 직접 구해보고 그 안에서 규칙성을 찾는것도 문제를 빠르게 푸는 방법일수..

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 ..