개발자 지망생의 끄적끄적 개발기록

백준 4792 : 레드 블루 스패닝 트리 등급 : Platinum III 4792번: 레드 블루 스패닝 트리 (acmicpc.net) 4792번: 레드 블루 스패닝 트리 무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내 www.acmicpc.net 사용 알고리즘 : Kruskal Algorithm 사용 자료구조 : Vector, Union-Find 크루스칼 알고리즘을 두 번 이용하여 스패닝 트리의 수정 가능성을 확인하는 문제였습니다. 위의 그래프를 예로 들어보자. 먼저 파란색 간선을 최소로 사용해주기 위해 빨간색으로 이뤄진 간선을 모두 이어준다. 이후 각 정점을 확인..

백준 2104 : 부분배열 고르기 등급 : Platinum V 2104번: 부분배열 고르기 (acmicpc.net) 2104번: 부분배열 고르기 크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[j]) × min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에 i부터 j까지의 최솟값을 곱 www.acmicpc.net 사용 알고리즘 : Divide and Conquer 사용 자료구조 : Vector 세그먼트 트리로도 구현할 수 있는 문제이지만, 분할 정복으로 더 간단하게 구현할 수 있다. 크기가 9(인덱스 0~8)인 위의 배열을 예로 들어보자. 마지막 인덱스가 8이므로, ..

백준 11003 : 최솟값 찾기 등급 : Platinum V 11003번: 최솟값 찾기 (acmicpc.net) 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 사용 알고리즘 : Sliding Window 사용 자료구조 : Priority_Queue, Deque 이 문제는 두 가지 방법으로 풀 수 있다. 1. 우선순위 큐를 이용한 방법 (C++ 통과, JAVA 시간초과) 우선순위 큐에 값과 인덱스를 같이 넣고, 최솟값이 유효한 인덱스에 있는지를 확인하여 출력. 다음과 같이 값이 ..

백준 1562 : 계단 수 등급 : Gold I 1562번: 계단 수 (acmicpc.net) 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 사용 알고리즘 : Bitmasking, Dynamic Programming 사용 자료구조 : - 다이나믹 프로그래밍에 비트필드 배열을 추가한 형식의 문제이다. 길이가 5인 수의 경우를 예로 들어보자. 행 부분은 길이, 열 부분은 그 위치에 올 수 있는 숫자이다. 계단 수는 0으로 시작할 수 없으므로 위와 같은 상태가 된다. 두 자리 수의 경우, 0은 1에서만 올 수 있으므로 1. → 두 자리 수이며, 두 번째 자리가 0인 계단 수는 10 하나 뿐이다. → 마찬가지로 9의 경우도 8에서만 올 ..

백준 12865 : 평범한 배낭 등급 : Gold V 12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 사용 알고리즘 : Dynamic Programming 사용 자료구조 : Vector 고전적인 다이나믹 프로그래밍 문제, 0-1 배낭(Knapsack) 문제이다. 배낭 하나에 가치가 최대가 되도록 물건을 넣는 문제. 배열에 물건의 무게와 가치를 저장하고, 그에 따른 DP테이블을 생성한다. 0번 인..