극꼼이 이야기 (GG_Tales)

문제 : https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net * 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. * 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는..

문제 : https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net * 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸..

문제 : https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net * 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. * 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) * 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안..

문제 : https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net * 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. * 입력 첫째 줄에 자연수 N과 M이 주어진다. ..

문제 : https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net * 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 * 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) * 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서..

문제 : https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net * 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. * 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7) * 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 ..

1. 백트래킹이란? 2. 백트래킹 예시(N-Queen) 1. 백트래킹이란? : 제약된 조건을 가진 문제에서 답을 찾기 위한 방법. - DFS 방식으로 확인(https://geukggom.tistory.com/66). - 모든 경우의 수를 상태 공간 트리를 통해 표현해 탐색. Promising : 해당 루트가 제약된 조건에 맞는지 확인 Pruning : 가지치기. Promising단계에서 조건에 맞지 않으면 바로 다른 루트로 가서 탐색 시간 절약. * 상태 공간 트리(State Space Tree) : 문제 해결 과정의 중간 상태를 Node로 나타낸 트리 2. 백트래킹 예시 백트래킹의 대표적인 문제 예시로는 N-Queen 문제가 있습니다. * N-Queen : 크기가 N * N인 체스판 위에 퀸 N개를 서..

저번 크루스칼 알고리즘 포스팅에 이어서, 최소 신장 트리를 찾는 대표 알고리즘인 프림 알고리즘에 대해 알아보겠습니다. * 크루스칼 알고리즘 https://geukggom.tistory.com/177 1. 프림 알고리즘이란? 2. 프림 알고리즘 구현 1. 프림 알고리즘이란? : 크루스칼 알고리즘과 마찬가지로 탐욕 알고리즘을 기반으로 하고 있습니다. 크루스칼 알고리즘과 차이점이 있다면, 크루스칼 알고리즘은 가중치가 가장 작은 간선부터 선택한다면, 프림 알고리즘은 특정 정점에서 시작해서 해당 정점에 연결된 가장 작은 가중치를 선택합니다. 2. 프림 알고리즘 구현 1) Edge 만들기 public class Edge : IComparable { public int weight; //가중치 public strin..

유니티에서 버튼에 함수를 연결할 때 아래와 같이 인스펙터 창에서 On Click () 창에 스크립트를 직접 연결하는 방법을 주로 사용하는데요, 이 방법은 함수 이름이 바뀌거나 하면 연결이 풀려 계속 다시 연결해줘야 하는 단점이 있습니다. 오늘은 직접 드래그 앤 드랍으로 연결하는 방식 말고, 연결이 끊어질 걱정없게 스크립트 내에서 함수를 연결해주는 방법을 알아보도록 합시다. 제 쿠키런 오븐브레이크 모작 포트폴리오에서 이를 활용해줄겁니다. 사용 방법은 간단합니다. Button jumpButton; void Start() { //버튼 찾아서 연결해주기 jumpButton = transform.GetChild(0).GetComponent(); //AddListener로 jump 함수 연결 jumpButton.o..

1. 최소 신장 트리 알고리즘 2. Disjoint Set (Union-Find, Union-by-Rank) 3. 크루스칼 알고리즘(Kruskal Algorithm) 1. 최소 신장 트리 알고리즘 : Minimum Spanning Tree(MST). * Spanning Tree : 그래프 내의 모든 정점을 포함하는 트리를 말합니다. 최소 신장 트리란 Spanning Tree 중 사용된 간선들의 가중치의 합이 최소인 트리입니다. 신장 트리에서 최소 신장 트리를 찾는 알고리즘에는 크루스칼 알고리즘, 프림 알고리즘이 있습니다. * 최소 신장 트리의 특징 1) 간선의 가중치의 합이 최소여야 함 2) n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 함 3) 사이클이 포함되어서는 안 됨 ..