전체 글50 [백준] 모든 순열 www.acmicpc.net/problem/10974 문제 해석 n이 입력되었을때 1부터 순회하면서 사전순으로 가능한 모든 순열을 출력하라 문제 풀이 12345를 출력하고 다음 12354를 출력한다고 생각했을때 1234를 선택한 시점에서 4는 선택해봤으니 4를 선택하기 이전으로 돌아가 5를 먼저 선택하는 개념 조건없이 모든 경우를 탐색하는 백트레킹 방법 import java.util.*; public class Main { static int[] checked; static int N; static ArrayList list; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); chec.. 2021. 4. 16. [프로그래머스] 2 x n 타일 programmers.co.kr/learn/courses/30/lessons/12900?language=java# 문제 해석 높이가 2이고 길이가 N 인 공간이 있을때 가로가 1이고 세로가 2인 타일을 이용해서 공간을 채우는 경우의수를 구해라 문제 풀이 처음에는 조합으로 푸는 문제인줄 알았는데 조금만 생각해보면 간단하게 풀 수 있었다 n이 순차적으로 증가할때 1, 2, 3, 5, 8, 13, 21 .... n을 채우는 경우의 수는 피보나치 순으로 증가한다는 것!! 경우의 수가 너무 커지는 경우 오버플로우를 피하기 위해 나머지연산을 먼저 하는것만 주의 class Solution { public int solution(int n) { int answer = 0; if(n == 0) return 0; int .. 2021. 4. 15. [프로그래머스] 섬 연결하기 https://programmers.co.kr/learn/courses/30/lessons/42861?language=java 문제 해석 노드들간의 연결과 가중치가 주어진다 모든 섬을 연결하면서 가장 작은 비용이 드는 경우의 비용을 구하는 문제 문제 풀이 노드 수 100개로 탐욕적 방법으로 서치가 가능한 문제이다 Kruskal 이라고 가장 작은 비용이 드는 간선을 하나씩 선택하면서 사이클이 생성되는지만 체크하는 알고리즘을 사용했다. 이 알고리즘은 사이클인지 판단하는 Union-Find가 핵심 Find - 현재 연결된 최고 조상을 찾는다 Union - 두 노드를 결합해 최고 조상을 같게 만든다 결국 Union으로 나온 결과가 false라는건 두 노드의 최고 조상이 같다는 뜻이기 때문에 두 노드를 연결하면 .. 2021. 4. 12. Kruskal 알고리즘 네트워크의 모든 정점을 최소 비용으로 연결하는 해답을 구하는 것 탐욕적인 방법으로 매 순간 가장 최적의 비용인 노드를 선택하는데 동작 방법은 다음과 같다 1. 간선들의 비용을 오름차순으로 정렬한다 2. 최소 비용부터 하나씩 선택하는데 사이클을 형성하는 간선을 제외 3. 해당 간선을 현재 MST에 추가한다 사이클 생성 여부 union-find 알고리즘 사용 시간복잡도 간선들을 정렬하는데 시간복잡도가 결정된다 퀵정렬을 사용하면 O(elog2e) 희소 그래프인 경우 Kruskal알고리즘이 적합 밀집그래프인 경우 Prim이 적합 Union-Find public int Find(int n){ if(n == Parent[n]) return n; else return Parent[n] = Find(Parent[n]).. 2021. 4. 12. [프로그래머스] 카펫 https://programmers.co.kr/learn/courses/30/lessons/42842?language=java 문제 해석 테두리를 1줄 둘러싸는 갈색 격자의 수와 내부를 채우는 노란색 격자의 수가 주어질때 카펫의 가로 세로 크기를 구하는 문제 문제 풀이 갈색 격자는 테두리를 한줄만 채운다 따라서 4모서리를 제외하고 절반만큼의 갯수로 만들 수 있는 카펫의 조합에서 노란 격자의 수와 일치하는 조합을 찾으면 된다 class Solution { public int[] solution(int brown, int yellow) { int[] answer = {0, 0}; int rowCol; rowCol = (brown - 4) / 2; for(int i = 1; i < rowCol / 2 + 1;.. 2021. 4. 11. [프로그래머스] 구명보트 programmers.co.kr/learn/courses/30/lessons/42885?language=java 문제 해석 최대 2명밖에 탈 수 없다 무게 제한 만큼의 사람만 탈 수 있다 구명보트를 최대한 적게 사용해서 모든 사람을 구출해야 한다 제한사항 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다. 각 사람의 몸무게는 40kg 이상 240kg 이하입니다. 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다. 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다. 문제 풀이 핵심은 2명만 탈 수 있다는것 따라서 최대 몸무게를 가진 사람부터 한명씩 데려갈 수 있는 사람을 데려가면 된다 꼭 제한을 최대한 채울 필요는 없다 10.. 2021. 4. 8. 이전 1 2 3 4 5 6 7 ··· 9 다음