알고리즘

문제 주어진 두 원 사이에 있는 정수의 점의 개수를 구하는 문제이다. 원의 방정식을 이용하여 쉽게 풀 수 있다. 제한 사항을 보면 주어지는 원의 반지름(r)이 꽤 크다. 따라서, 완전 탐색은 불가능하다고 판단했다. 문제 설명 x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해 주세요. ※ 각 원 위의 점도 포함하여 셉니다. https://school.programmers.co.kr/learn/courses/30/lessons/181187# 프로그래머스 코드 중심의 개발자 채용. ..

그래프 탐색의 기본인 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 구현하는 문제를 풀어보았다. 예전에 공부해서 잘 할 수 있으려나 하고 생각했는데 생각보다 잘 풀렸다. 역시 기본 개념을 이해하고 있다면 구현하기 쉬운 거 같다. DFS에서는 재귀를 이용한다는 점을 알고 구현하니 훨씬 순조로웠다. 또한 BFS에서 Queue를 사용한다는 키포인트를 알고있었기 때문에 쉽게 문제를 풀 수 있었다. DFS에서는 방문하지 않은 노드일 경우 출력을 하고, 해당 노드에서 갈 수 있는 노드를 하나씩 dfs()를 이용하여 재귀시키면 간단하게 풀린다. 그렇게 재귀 호출되어 탐색을 시작한 노드에서도 똑같은 작업을 수행하기 때문에 최대한 탐색할 수 있는 노드까지 최대한 순회한 뒤 반환되어 나머지 노드를 순회한다. BFS..

지난 포스트에 풀었던 다익스트라 알고리즘을 다른 문제로 다시 풀어 보았다. 저번의 실수를 만회하기위해 어제 틀린 부분을 집중해서 풀어보았다. 1트만에 맞았다 ㅎㅎㅎㅎ 0.5초라 시간 초과가 뜨지 않을까 했는데 다행히 뜨지 않았다. 지난 포스트에서는 모든 노드까지의 최단거리를 구하는 것인데 이번 문제는 그냥 도착 노드까지의 최소 비용만 구하면 된다. 즉, 도착 노드의 최소 비용만 출력하면 된다. 다음은 Java로 작성한 코드이다. import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner; public class MinimumCost { public static void main(String[] args) { //..

다익스트라 알고리즘을 복습하기 위해 문제 카테고리에서 제일 첫 번째에 위치한 문제를 풀러 들어갔다. 처음에는 다익스트라만 적용하면 간단하게 풀릴 문제라고 생각했다. 하지만...... 오만했던 나를 발견했다..... 거의 하루를 쏟아 부었다..... 몇 틀을 한 건지 모르겠다..... 15트만에 드디어 풀었다. 중간에 맞은 문제는 구글에 돌아다니는 코드를 붙여 넣어 봤다. 내 코드만 안 되는 줄 알고.... 점심 나가버릴 거 같았다.... 문제풀이는 간단했다. 노드의 수와 간선의 수, 시작 노드를 입력받고 간선들의 시작점, 도착점, 가중치를 입력받아 시작 노드에서 다른 노드들까지의 최단거리를 구하면 되는 문제이다. 나는 다익스트라 알고리즘을 이용하여 최단 경로를 구하려 했다. 다익스트라 알고리즘은 아직 방..

DP 제일 위에 있는 문제를 풀어보았다. 3kg과 5kg의 설탕으로 목표 무게를 만드는 것이다. 만들지 못하면 -1을 만들 수 있으면, 최소한의 수의 설탕으로 목표 무게를 만드는 것이다. 메모제이션을 이용하여 0부터 목표 무게까지 최소한의 수를 쌓아가면 된다. 0 = -1 1 = -1 2 = -1 3 = 1 4 = -1 5 = 1 은 기저 조건으로 설정한다. 만약 기저 조건보다 낮은 목표 무게가 있다면 예외 처리를 한다. 그리고, 이제 무게를 6부터 쌓아갈 때 3을 뺀 수와 5를 뺀 무게 중, 적은 수의 설탕 봉지를 쓴 경우를 택해 1을 더하면 된다. 또한, 15같은 무게는 3kg으로도 5kg으로도 만들 수 있다. 이런 경우를 생각해 3kg을 쓴 경우와 5kg을 쓴 경우 모두를 생각해 비교해야 한다. 다..

최대공약수와 최소공배수를 구하는 문제이다. 선형적인 탐색법으로 작은 수전까지 하나씩 나누어 보고 둘 다 나누어 떨어지는 수 중 가장 큰 수를 구하면 되겠지만, 다른 수학적인 방법을 이용하여 최대공약수를 구한 뒤 그를 이용하여 최소 공배수까지 구하는 방법이 있다. 임의의 수 a, b가 있다 가정하자. (단, a > b) a를 b로 나누면 몫과 나머지가 있을 것이다. 그러면 그 나머지로 나누는 수 (b)를 또 나눈다. 이를 반복하다 나누는 수 (b)가 0이 되면 나누어지는 수 a를 return 한다. 그림을 보면 x가 최대공약수라 할 때, a = 8x b = 3x a% b = 2x이다. 우리는 x를 구해야 하기 때문에, 나머지가 0이 될 때, 즉 모든 수가 나누어 떨어질 때까지 계속해서 b를 나머지로 나눈다..

DP문제에 전형적인 풀이 방법인 메모제이션을 이용하여 문제를 풀었다. 처음에는 어떤 식으로 문제를 풀어 나가야 할지 감이 잡히지 않았다. 계속 생각한 결과 한가지만 주의하면 된다는 생각을 하게 되었다. 이웃한 집만 같은 색깔이 아니면 되기 때문에 하나의 집을 임의의 색으로 칠하면 다음 집에서는 선택할 수 있는 경우가 2가지로 좁혀지고, 그다음은 여전히 2가지의 선택의 경우가 생긴다. 즉, 소모 값들을 배열에 저장한다 생각하면, 같은 column에 있는 값만 선택하지 않으면 된다. 그렇다면 이제 index문제만 해결하면 문제는 풀린다. R은 [0]에, G는 [1]에, B는 [2]에 저장한다 하자. 2번 index의 요소를 처리한다 했을때, 0과 1에 접근할 수 있는 방법을 찾으면 된다. 링 버퍼의 개념을 ..

정답 비율이 40%라 도전해봤는데 문제가 짧아서 당황했다. 문제를 읽어보니 문제 제목과 똑같이 입력받은 수로 어떠한 수를 나누었을 때 몫과 나머지가 같은 수들의 합을 구하면 되는 간단한 문제였다. 이런 문제 정답 비율이 왜 이렇게 낮을까 생각하고 문제 풀이를 시작했다. 입력받은 수를 n이라 했을 때 어떠한 수를 나누는 상황에서 나머지가 생기는 경우는 n-1가지의 경우이다. ( 나머지는 나누는 수 보다 무조건 작고, 1~n-1까지의 수이다. ) 이러한 원리로 1부터 n-1까지 어떠한 수의 몫과 나머지가 같은 수를 만들어 더해주면 될 거라 생각했다. 아래는 처음에 작성한 Java 코드이다. import java.util.Scanner; public class SameMod { public static voi..

초등학교 수학 문제에서 많이 봤던 문제이다. 낮에 이동하고 밤에 미끄러지기 때문에 낮에 이동했을 때 목표 거리와 비교한 뒤 만족하지 않았다면 미끄러진 높이를 계산하는 계산을 반복하면 되는 문제라고 생각했다. 하지만 결과는 시간 초과... 그래서 다음엔 배열을 이용해 봤다. 배열일 연산이 제일 빠르기 때문에 시간 초과 문제를 해결할 거라 생각했다. 낮에 이동한 거리의 배열과 미끄러진 후의 거리 배열을 생성하여 낮에 이동한 거리가 목표 높이에 도달하기까지 반복하여 index를 출력하면 될 줄 알았다. 하지만 이번에는 메모리 초과.... 한참 고민하다 해답이 떠올랐다. 결국 마지막에는 앞으로 이동을 해야 하기 때문에, 앞으로 가는 거리를 목표 높이에서 뺀 뒤 실제로 이동하는 거리(앞 - 뒤)로 나누어 주면 정..

연속되는 수 중 가장 큰 합을 찾아내는 문제이다. DP로 간단하게 해결 가능하다 배열에 수들을 저장해 해당하는 index의 수가 선택되었을 경우, 이전까지의 합과 index의 요소 중 큰 수를 골라 저장하며 풀어 나간 뒤 가장 큰 수를 찾아 출력하면 된다. 다음은 Java로 작성한 코드이다. import java.util.Scanner; public class continuitySum { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int num = scan.nextInt(); //수 배열 int[] arr = new int[num]; //큰 수 저장 배열 int[] solution = new int[num..