본문 바로가기

코딩일기/알고리즘75

[백준 1931번 : 실버 2] 회의실 배정 (그리디 / Java) 이번 문제는 내가 알고리즘도 내 스스로 짰고 그랬지만 시간 초과 때문에 답을 보게 되었다. 거의 다 풀었는데 좀 아쉬운 문제였다 문제를 살펴보자. 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까.. 2021. 7. 24.
[백준 9095번 : 실버3] 1,2,3 더하기 (DP / Java) 이번 문제는 DP라고 해서 1부터 값을 저장하는건가? 까지 생각을 했지만 그 생각이 답까지 이어지진 못했다. 그래서 결국 답을 확인해봤다. 문제부터 살펴보자. 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 문제 접근 방법.. 2021. 7. 24.
[백준 2178번 : 실버 1] 미로탐색 ( BFS/ Java) 이번 문제는 BFS로 내가 잘 풀려고 했고 내가 생각한 알고리즘은 맞았지만 인접 노드 구하는 부분에서 애를 먹어서 풀지 못하고 결국엔 답을 찾아 봤다. 일단 문제부터 보자. 문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도.. 2021. 7. 23.
[백준 : 실버2] 동전 0 : 그리디 알고리즘(Java) 이번 문제는 생각외로 정말 쉬웠다. 문제부터 살펴보자. 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 문제 접근 나는 이번문제를 어떻게 접근 했냐면 일단 가장 적은 동전의 수를 사용하려면 일단 수가 가장큰거부터 .. 2021. 7. 22.

티스토리툴바