이지선의 블로그

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 문제 문제 해결 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in));..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 문제 해결 문제를 풀기 전 DP 알고리즘에 대해 학습 후 진행하였다. DP, 즉 다이나믹 프로그래밍(동적 계획법)은 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하여 사용하는 것으로 하나의 문제해결 패러다임으로 볼 수 있다. 일반적인 재귀를 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산이 될 수 있다. 예를 들어 피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하면 다음과 같다. f..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 문제 풀이 문제를 풀기 전 그리디 알고리즘에 대해 학습 후 진행하였다. 해당 문제는 한 사람이 하나의 활동에 대해서만 작업할 수 있을 때 최대한 많은 활동을 할 수 있는 수를 선택하는 문제이다. CPU 스케줄링을 공부 할 때 그리디하게 우선순위를 정하라는 뜻을 이제야 이해하게 되었다! 각설하고 서로 겹치지 않는 활동에 대해 종료시간이 빠르면 더 많은 활동을 선택할 수 있는 시간이 많아진다는 것을 알면 쉽게 풀 수 있는 문제였다. 1. 2차원 배열에 회의실을 시작시간과 종료시간으로 나누어 입력해 준다. 2. ..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 문제 풀이 입력된