알고리즘6 [백트래킹] N-Queen문제 백트래킹이란? 해를 찾기 위해 DFS방식으로 탐색하다가 해당 루트가 유망한지(Promising) 검사하여 조건이 맞지 않다면 가지치기(Pruning)하고 다른 루트로 돌아가 최적의 해를 찾는 방법이다. 상태 공간 트리(State Space Tree) 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리이다. N-Queen문제 대표적인 백트레킹 문제이다. 백준 9663번 문제: https://www.acmicpc.net/problem/9663 n = int(input()) row = [250] * n answer = 0 #현재 레벨에서 놓을 수 있는지 없는지 체크하는 함수 (행[자동 생략], 열, 대각선) def can(level): for i in range(level): if row[level] =.. 2021. 12. 28. [알고리즘] 최소 비용 신장 트리(MST) - 크루스칼 알고리즘(Kruskal Algorithm) 신장 트리 (Spanning Tree) 신장 트리란 그래프안에서 모든 정점(노드)을 포함하는 트리이다. 신장 트리는 모든 정점들이 연결되어 있어야 하고, 사이클을 포함하면 안된다. (사이클: 그래프가 순환되어 돌아오는 경로) 신장 트리는 그래프에 있는 n개의 정점을 n-1개의 간선으로 연결하게 된다. 최소 비용 신장 트리 MST (Minimun Spanning Tree) 신장 트리들 중에서 사용된 간선의 가중치 합이 최소인 트리를 말한다. 크루스칼(Kruskal) 알고리즘과 프림 알고리즘이 있다. 크루스칼 알고리즘(Kruskal Algorithm) 그리디 알고리즘을 이용하여 그래프의 모든 정점을 최소 비용으로 연결하여 최적의 답을 구하는 알고리즘이다. 크루스칼 알고리즘 동작 그래프의 간선들을 가중치의 오.. 2021. 11. 10. 완주하지 못한 선수 (python, hash, dict, collections) 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 participantcompletionreturn ["leo", "kiki".. 2021. 8. 6. Java HashSet Set은 List와 다르게 순서가 보장되지 않는 자료구조입니다. 1) HashSet은 다음과 같은 특징이 있습니다. 중복된 값을 허용하지 않습니다. 순서를 보장하지 않습니다. null 값을 저장할 수 있습니다. 내부적으로 HashMap을 사용하여 데이터를 저장합니다. Hashset은 중복된 값을 허용하지 않기 때문에 public int solution(int[] nums){ HashSet set = new HashSet(); int length = nums.length; int pk = length/2; for (int i=0; i 2020. 9. 20. [알고리즘] 조합 nCr 예제 ex)오름차순으로 정렬된, 중복이 없는 정수열로부터, 크기가 3인 모든 부분집합을 출력하는 프로그램을 작성하시오. 부분집합들은 사전 오름차순으로 출력되어야 합니다. 세 숫자 중 첫 숫자가 가장 작은 부분집합이 먼저 출력되어야 하고, 첫 숫자가 같은 두 부분집합 중에는 두 번째 숫자가 더 작은 부분집합이 먼저 출력되어야 합니다. 오름차순으로 정렬된, 중복이 없는, 정수열 한 줄 크기가 3인 모든 부분집합들을 한 줄에 하나씩 출력한다. import java.util.Arrays; import java.util.Scanner; class Main { public static void main(String[] args) { int n = 3; Scanner sc = new Scanner(System.in); S.. 2020. 9. 15. [알고리즘] 분할 정복 예제 ex)오름차순으로 정렬된, 중복이 없는 정수열로부터, 크기가 3인 모든 부분집합을 출력하는 프로그램을 작성하시오. 부분집합들은 사전 오름차순으로 출력되어야 합니다. 세 숫자 중 첫 숫자가 가장 작은 부분집합이 먼저 출력되어야 하고, 첫 숫자가 같은 두 부분집합 중에는 두 번째 숫자가 더 작은 부분집합이 먼저 출력되어야 합니다. 오름차순으로 정렬된, 중복이 없는, 정수열 한 줄 크기가 3인 모든 부분집합들을 한 줄에 하나씩 출력한다. package hi; import java.util.Scanner; class Main2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.nextLine.. 2020. 9. 15. 이전 1 다음
