Algorithm

BOJ 14889 - 스타트와 링크

14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다. 스타트 팀: S12 + S21 = 1 + 4 = 5 링크 팀: S34 + S43 = 2 + 5 = 7 1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다. 스타트 팀: S13 + S31 = 2 + 7 = 9 링크 팀: S24 + S42 = 6 + 4 = 10 1. 아이디어 모든 N은 짝수이고 N/2명씩 팀을 짜니까 N개의 자연수에서 중복을 허용하..

BOJ 15666 - N과 M (12)

15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 아이디어 N개의 자연수 중 중복을 허용하여 M개를 골라 순서있게 나열하는 중복순열 문제이다. 비내림차순이어야 하니까 재귀호출 시 prev를 넘겨주어 탐색하는 다음 자리는 이전 자리보다 큰 수, 즉 prev+1부터 탐색하도록 설정한다. N개의 자연수 중 같은 수가 여러번 나올 수 있다는 것을 생각해야 한다. N이 1 7 9 9 이고 M이 2인 경우를 생각해보면 1 1 1 7 1 9 1 9 7 7 7 9 7 9 9 9 9 9 9 9 문제의 조건이 중복되는 수..

BOJ 15665 - N과 M (11)

15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 아이디어 N개의 자연수 중에서 중복을 허용하여 M개를 골라서 순서있게 나열하는 중복순열 문제이다. N개의 수 중 중복되는 수가 있을 수 있다는 사실을 알아야 한다. N이 1 7 9 9 이고 M이 2인 경우를 생각해보자 중복을 허용하여 순서있게 나열하면 다음과 같다 1 1 1 7 1 9 1 9 7 1 7 7 7 9 7 9 9 1 9 7 9 9 9 9 9 1 9 7 9 9 9 9 문제의 조건이 중복되는 수열은 출력하지 않는 것이므로 LinkedHashSet에..

BOJ 15664 - N과 M (10)

15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 아이디어 N개의 자연수 중 M개를 중복없이 골라서 순서있게 나열하는 순열문제이다. 여기에 비내림차순이어야 하므로 N개의 수를 정렬한 후 prev 인자를 통해 k번째 다음 자리인 k+1번 자리는 prev +1부터 탐색할 수 있도록 설정해준다. 여기서 N개의 숫자가 같은 것이 있을 경우를 생각해야 한다. N개의 숫자가 9 7 9 1 이고 M이 2인 경우를 생각해보자 정렬을 하고 순열을 구해보면 다음과 같다. 1 7 1 9 1 9 7 9 7 9 9 9 여기서 ..

BOJ 15663 - N과 M (9)

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 아이디어 기존 중복을 허용하지 않고 순서있게 고르는 순열문제와 동일하지만 이번에는 N개의 수가 전부 다른 수가 아닐 수도 있기 때문에 좀 더 생각을 해봐야 한다. 만약 N개의 수가 1 4 4일 때, 중복을 허용하지 않고 2개를 순서있게 고르면 다음과 같다. 1 4 1 4 4 4 이렇게 되면 1 4가 중복되게 출력되는데 문제에서 중복 출력은 없도록 하라고 했으니 이걸 중복을 제거해주고 입력 ..

BOJ 15657 - N과 M (8)

https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 아이디어 N개의 자연수 중에서 중복을 허용하여 M개를 골라야 하고 비내림차순이어야 한다. 각 자리에서 백트래킹으로 모든 경우의 수를 탐색하는 완전탐색 문제이다. 그 중 중복을 허용하여 순서있게 고르는 것이므로 중복순열 문제이다. 재귀함수의 매개변수로 prev를 넘겨줘서 각 경우의 prev에 해당하는 숫자부터 탐색을 시작하도록 설정하면 (k자리의 숫자)

BOJ 15656 - N과 M (7)

https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 아이디어 N개의 자연수 중에서 중복을 허용하여 M개를 순서있게 나열하는 중복순열 문제이다. 각 자리에서 다음 자리에 올 수 있는 모든 경우의 수를 탐색한다. 2. 시간복잡도 중복순열 문제이므로 N개 중 M개의 자리를 뽑는 것과 같으므로 시간복잡도는 O(N^M)이다. N과 M의 최댓값은 7이므로 7^7 < 1초라서 가능한 풀이법이다. 3. 구현 import java.io.*; impo..

BOJ 15654 - N과 M (6)

https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 아이디어 N개의 자연수 중에서 중복 없이 M개를 순서있게 나열하는 완전탐색의 순열문제이다. 각 자리에서 재귀호출로 다음 자리에 올 수 있는 모든 경우의 수를 탐색한다. 단, 중복을 허용해야 하고, 오름차순이어야 하므로 재귀함수에 prev인자를 넘겨줘서 다음 자리는 prev+1부터 탐색하게 하여 오름차순이 되도록 설계한다. N개의 자연수는 모두 다른 수이므로 prev인자를 통해 중복도..

BOJ 14888 - 연산자 끼워넣기

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 1. 아이디어 주어진 수열의 순서는 바뀌지 않으므로 그 사이사이 연산자만 끼워넣으면 된다. N-1개의 연산자를 중복 없이 순서있게 나열하여 모든 경우의 수를 탐색하는 완전탐색 문제이다. 모든 경우를 탐색하면서 최댓값/최솟값이 되는 경우의 연산자 조합을 찾는다. 2. 시간복잡도 완전탐색으로 구현하면 중복없이 순서있게 나열하는 순열문제이므로 O(..

[자료구조] Set Collection

Set Collection 저장 순서를 유지하는 List와 다르게 Set은 저장 순서가 유지되지 않고, 객체의 중복 저장이 불가능하며, 하나의 null만 저장할 수 있다. 순서가 유지되지 않기 때문에 당연히 index로 데이터 접근이 불가능하다. Set 인터페이스를 구현한 클래스 HashSet TreeSet LinkedHashSet HashSet 순서대로 입력되지 않고, 일정하게 유지되는 것이 특징이고, 객체의 중복을 허용하지 않는다. 사용 예제) import java.util.HashSet; import java.util.Iterator; class HashSet { public static void main(String[] args) { // Integer 담는 HashSet HashSet set =..