알고리즘
-
[프로그래머스] 가장먼노드 - 자바(JAVA)알고리즘/프로그래머스 2022. 6. 16. 00:01
https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 문제 해석 1번부터 n번까지의 노드가 있는 그래프가 존재합니다. 양방향 그래프를 가지며 간선의 weight는 모두 1으로 볼 수 있습니다. 그리고 1부터 n번까지의 거리를 모두 측정한 뒤 가장 멀리 떨어진 노드가 몇 개인지 찾아야 합니다. 문제 풀이 전 설계 1번을 출발지로 가지며 n번까지의 거리를 모두 최단거리로 구해야 합니다. 바로 다익스트라 알고리즘이 떠올랐기 때문에 다익스트라로 해결해보고자 합니다. 다익스트라에 대해 모르신다..
-
[백준] 10815번 : 숫자 카드 - 자바(JAVA)알고리즘/백준 2022. 6. 15. 00:01
문제 해석 int형 범위내의 N개의 숫자가 주어집니다. 이때 M개의 숫자가 다시 주어지고 M개의 숫자가 N개의 숫자에 존재하는지 탐색하는 문제입니다. 문제 풀이 전 설계 N제한이 50만이기 때문에 O(N^2)은 불가능합니다. 또한 문제에서는 정렬/이분 탐색으로 문제를 해결하라고 제시했지만 더 효율적인 방법인 HashSet을 이용하면 O(1)의 시간복잡도로 해결이 가능할 것 같습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main_10815_숫자카드 { public static void main(String[] ar..
-
[백준] 1644번 : 소수의 연속합 - 자바(JAVA)알고리즘/백준 2022. 6. 14. 00:01
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 해석 어떤 수 N을 소수의 합으로 나타낼 수 있다면 그 경우의 수를 구하는 문제입니다. 예를 들어보겠습니다. 3은 3 자기 자신으로 한 가지가 가능합니다. 41 = 2 + 3 + 5 + 7 + 11 + 13 , 11 + 13 + 17, 41으로 3가지가 가능합니다. 53 = 5+7+11+13+17 = 53으로 세 가지가 가능합니다. 소수를 모두 구한 다음에 해당 소수를 기반으로 투 포인터를 통해 경우의 수를 탐색하면 될 것 같습니다. 즉, 소수들의 연속된 부분합이 특정수를 만족하는 경우를 찾으면 됩니다. 문제 ..
-
[프로그래머스] 2020 카카오 인턴십 - 경주로 건설 - 자바(JAVA)알고리즘/프로그래머스 2022. 6. 13. 00:01
https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 문제 해석 경주로는 N x N 크기의 정사각형 격자형 태이며 각 격자의 크기는 1 x ..
-
[백준] 2957번 : 이진 탐색 트리 - 자바(JAVA)알고리즘/백준 2022. 6. 12. 00:01
https://www.acmicpc.net/problem/2957 2957번: 이진 탐색 트리 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 www.acmicpc.net 문제 해석 1보다 크거나 같고, N보다 작거나 같은 수 N개가 한 번씩 등장하는 수열이 주어집니다. 이때 이진트리를 구성하면 왼쪽 서브트리에는서브 트리에는 X보다 작은 수, 오른쪽 서브 트리에는 X보다 큰 수만 저장되어 있어야 합니다. 첫 번째 수를 루트로 놓고 다 머지 수들을 순서대로 삽입하고자 합니다. 이때 함수안에 C라는 카운터를 1씩 증가시키는 구문이 존재하는데 트리에 삽입된 후에 카..
-
[백준] 23807번 : 두 단계 최단 경로3 - 자바(JAVA)알고리즘/백준 2022. 6. 11. 00:01
https://www.acmicpc.net/problem/23807 23807번: 두 단계 최단 경로 3 첫째 줄에 정점의 수 N(10 ≤ N ≤ 100,000), 간선의 수 M(10 ≤ M ≤ 300,000)이 주어진다. 다음 M개 줄에 간선 정보 u v w가 주어지며 도시 u와 도시 v 사이의 가중치가 정수 w인 양방향 도로를 나타낸 www.acmicpc.net 문제 해석 시작점과 목적지의 최단거리를 구하는 문제이기 때문에 다익스트라가 바로 떠올랐습니다. 하지만 중간에 꼭 거쳐가야 하는 노드들이 주어집니다. 임의의 P개의 정점중에 적어도 3개의 정점은 무조건 거쳐가야 함. 문제 풀이 전 설계 DP를 사용해야 하나..? 전혀 방법이 떠오르지 않았습니다. 따라서 완전 탐색으로 접근해 보려고 합니다. 1번..
-
[프로그래머스] 2020 카카오 인턴십 - 동굴 탐험 - 자바(JAVA)알고리즘/프로그래머스 2022. 6. 10. 00:01
https://programmers.co.kr/learn/courses/30/lessons/67260?language=java 코딩테스트 연습 - 동굴 탐험 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[8,5],[6,7],[4,1]] true 9 [[8,1],[0,1],[1,2],[0,7],[4,7],[0,3],[7,5],[3,6]] [[4,1],[5,2]] true 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[4,1],[8,7],[6,5]] false programmers.co.kr 문제 해석 n개의 방으로 이루어진 지하 동굴을 탐험하고자 한다. 모든 방에는 0부터 n-1번까지 번호가 붙어있습니다. ..
-
[프로그래머스]2022 KAKAO BLIND RECRUITMENT - 양과 늑대 - 자바(JAVA)알고리즘/프로그래머스 2022. 6. 9. 00:01
https://programmers.co.kr/learn/courses/30/lessons/92343 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr 문제 해석 이진트리 모양 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 따라옵니다. 이때, 늑대는 양을 잡아먹..