개발자되기 프로젝트

문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오. 입력 첫째 줄에 문자열 ..

1. 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 2. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 3. 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 4. 문제 접근 각 동전의 가치가 주어졋을 때, 전체 금액이 K가되도록하는 가장 작은 동전의 수! 무조건 큰 동전부터 고르면 됨. --> Greedy..

1. 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게..

1. 그리디(Greedy)알고리즘?? "당장 눈 앞에 보이는 최적의 상황마을 쫓는 알고리즘"을 뜻한다. 항상 최적의 답을 도출하지는 않지만 최적의 해에 근사한 값을 빠르게 구하는데 용이하다. 기본적으로 "무조건 큰 경우대로", "무조건 작은 경우대로", "무조건 긴 경우대로", "무조건 짧은 경우대로" 등 극단적으로 문제에 접근한다. 즉 극단적인 경우로 문제에 접근하기 때문에 Sort(정렬) 기법이 함께 사용되는 경우가 많을 수 밖에 없다.

이번에는 피보나치 수열을 구현해보자. 피보나치는 아래와 같이 n번 째 값은 n-1번째 n-2번 째 값의 합이다. 1. 먼저 함수에 표현된 대로 코드를 구성해 보자. 함수대로 표현하기 위해서는 재귀함수 방식을 활용해야 한다. 즉 int n에 해당하는 값을 구하기 위해 "n-2"번 째 값과 "n-1"번 째 값을 추가로 계산을 해줘야 한다. package fibonacci; public class FibonacciPractice { public int fibonacciRecur(int n){ if(n == 0) return 0; if(n == 1) return 1; return fibonacciRecur(n-2) + fibonacciRecur(n-1); } public static void main(Strin..

2021.06.07 - [Java/알고리즘] - 최단경로 구하기 : Dijkstra algorithm 최단경로 구하기 : Dijkstra algorithm 시작 노드에서 전체 노드로 가는 최단 거리를 구하는 알고리즘. 이 알고리즘을 시행하면 시작노드부터 각 노드까지 최단 경로를 알 수 있다. 특징으로는 각 단계를 반복하면서 시작노드부터의 bsh-developer.tistory.com 앞서 한 노드로부터 각 노드 까지 최단 거리를 구하는 Diijkstra 알고리즘에 대해 알아봤다. 이번엔 알고리즘을 코드로 구현해보자. 크게 세 가지를 중점으로 작성했다. * 시작 노드를 기준으로 weight 행렬 작성하는 method - weight 배열은 djikstra 생성자에서 모두 inf(=9999)로 초기화. - ..

시작 노드에서 전체 노드로 가는 최단 거리를 구하는 알고리즘. 이 알고리즘을 시행하면 시작노드부터 각 노드까지 최단 거리를 알 수 있다. 특징으로는 각 단계를 반복하면서 시작노드부터의 각 노드까지 최단 거리를 계속 업데이트 한다. 현재 노드를 기준으로, 기존에 입력된 weight(현재 노드를 거치지 않음)가 더 작은지 현재 노드를 거치는게 weight가 작은지 비교해야한다. 즉 노드 v에 인접한 노드 w에 대하여 아래 조건이 성립하면 w에 대한 최단거리를 업데이트 한다. (원래 w로 가는 거리보다 v를 거쳐서 가는 거리가 가까우면 w가는 거리를 v거쳐서 가는 거리로 수정.) Yv + Cvw Yw = Yv + Cvw ex) Y1 + C1,2 < Y2 그 결과로 알고리즘이 종료되었을 때, 시..

루트부터 시작하여 인접한 노드를 먼저 탐색하고 그 다음으로 깊이 방향으로 진행. 즉, 깊에 탐색하기 보다는 넓게 탐색 하는 방법 * 깊게 탐색하는 방법 : DFS(Depth First Search) 인접한 노드를 모두 탐색하고 깊게 나아가기 때문에 queue를 활용하여 구현이 가능한다. - 루트부터 시작하여, 방문할 때 마다 해당 노드를 enqueue하고 인접한 노드를 모두 enqueue한다. - 더이상 방문할 인접 노드가 없으면, queue에서 head를 dequeue한다. - 해당 노드와 인접한 노드를 방문 및 enqueue한다. - 모두 방문할 때 까지 계속 반복. - 즉 enqueue, dequeue를 계속 반복한다. 아래 순서를 따가 구체적인 사례를 보자. 1. 탐색 순서 1) 루트부터 시작. ..