CS & Algorithm
-
[CS & Algorithm-10] 로프 문제 (Greedy)CS & Algorithm 2021. 8. 19. 23:01
BaekJoon Online Judge 2217 Question :https://www.acmicpc.net/problem/2217 Source :https://github.com/lee-maru/practice_algorithm/blob/master/src/Solution7.java /** * 문제 * N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. * * 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 ..
-
[CS & Algorithm-9] 거스름돈 (Greedy)CS & Algorithm 2021. 8. 19. 22:56
BaekJoon Online Judge 5585 Question :https://www.acmicpc.net/problem/5585 Source :https://github.com/lee-maru/practice_algorithm/blob/master/src/Solution6.java /** /** @link : https://www.acmicpc.net/problem/5585 * * @implNote 타로는 자주 JOI잡화점에서 물건을 산다. * JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. * 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 ..
-
[CS & Algorithm-8] 잃어버린 괄호 (Greedy)CS & Algorithm 2021. 8. 19. 22:54
BaekJoon Online Judge 1541 Question :https://www.acmicpc.net/problem/1541 Source :https://github.com/lee-maru/practice_algorithm/blob/master/src/Solution5.java /** * 문제 & 설명 : https://www.acmicpc.net/problem/1541 * 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. * * 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. * * 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. * * 입력 * 첫째 줄에 식이 주어진다. 식은 ‘0’~..
-
[CS & Algorithm-7] 회의실 배정 (Greedy)CS & Algorithm 2021. 8. 19. 22:50
BaekJoon Online Judge 1931 Question :https://www.acmicpc.net/problem/1931 Source :https://github.com/lee-maru/practice_algorithm/blob/master/src/Solution4.java /** * 문제 * 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다...
-
[CS & Algorithm-6] 동전 0 (Greedy)CS & Algorithm 2021. 8. 18. 18:06
BaekJoon Online Judge 11399 Question :https://www.acmicpc.net/problem/11047 Source :https://github.com/lee-maru/practice_algorithm/blob/master/src/Solution3.java //https://www.acmicpc.net/problem/11047 /** * 문제 * 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. * * 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. * * 입력 * 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) * * ..
-
[CS & Algorithm-5] BaekJoon 설탕 배달 문제 (Greedy)CS & Algorithm 2021. 8. 18. 15:46
BaekJoon Online Judge 11399 Question :https://www.acmicpc.net/problem/11399 Source :https://github.com/lee-maru/practice_algorithm/blob/master/src/Solution2.java 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더..
-
[CS & Algorithm-4] BaekJoon ATM 문제 (Greedy)CS & Algorithm 2021. 8. 18. 09:38
BaekJoon Online Judge 11399 Qusetion : https://www.acmicpc.net/problem/11399 Source : https://github.com/lee-maru/practice_algorithm/blob/master/src/Solution1.java 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3,..
-
[CS & Algorithm-3] DFS, BFS 알고리즘 에 대하여CS & Algorithm 2021. 1. 1. 17:32
D F S (Depth - First Search) & B F S (Breadth - First Search) D F S 란 깊이 우선 탐색이라고 불림, 깊은 부분을 우선적으로 탐색하는 알고리즘 스택 자료구조 (또는 재귀)를 이용함. 처음 시작하는 노드를 스택에 push 스택의 최상단 노드에 방문하지 않은 인접한 노드가 있다면 또다시 조회 이를 지속적으로 반복 (끝날 때 까지) B F S 란 BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘, 큐 자료구조를 이용 탐색 시작 노드를 큐에 삽입하고 방문 처리를 함. 큐에서 노드를 꺼낸 뒤에 해동 노드의 인접 노드 중에서 방문하지 않는 노드를 큐에 삽입 이를 지속적으로 반복 (끝날 때 까지)