Algorithm

BOJ 11652 - 카드

https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 1. 아이디어 Int 범위로는 부족하니까 long 자료구조를 사용해야 한다. 최빈값을 구해야 하는 문제이다. 정렬의 특성을 생각해보면 같은 정보들은 인접해있다는 것을 알 수 있으므로 이 특성을 이용해 최빈값을 구한다. 예를 들어 6 7 2 3 2 6 7 6 의 카드가 주어졌을 때 정렬을 하면 2 2 3 6 6 6 7 7 이 된다. 먼저 정렬을 한 후 같은 정보들은 인접해있다는 특성을 이용해 ..

BOJ 1015 - 수열 정렬

https://www.acmicpc.net/problem/1015 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net 1. 아이디어 1. 주어진 배열을 인덱스와 함께 정렬 2. 정렬된 배열의 인덱스 값을 P 배열에 저장 2. 시간 복잡도 정렬만 해주면 바로 P 배열을 채워줄 수 있으므로 정렬의 시간복잡도인 O(N log N) 만큼 걸린다. N의 최댓값은 50이므로 1초안에 풀이가 가능하다. 3. 구현 import java.io.*; import java.uti..

[Algorithm] 정렬

류호석님의 패스트캠퍼스 강의 자료를 참고하여 정리한 글입니다. 출처 : https://github.com/rhs0266/FastCampus 정렬 어떤 자료들이 주어졌을 때 그 자료들에 대해서 오름차순 혹은 내림차순 등의 기준이 주어졌을 때 그 기준에 맞게 정렬하는 것 정렬의 조건 1. 정렬 조건이 필요 static class Elem implements Comparable { public int num, idx; @Override public int CompareTo(Elem other) { // 오름차순 -> return 음수 return num - other.num; // 내림차순 -> return 양수 // return other.num - num; // 같은 경우 -> return 0 } } re..

BOJ 2661 - 좋은 수열

https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 아이디어 먼저 조건 없이 생각해보면 숫자 1, 2, 3 중에서 중복을 허용하여 N개를 순서있게 나열하는 백트래킹 문제이다. 이 문제의 조건은 나쁜 수열을 제외하고 좋은 수열 중 가장 작은 수를 출력하는 것이다. 길이가 N인 수열에서 임의의 길이의 인접하는 두 개의 동일한 수열이 있는 경우를 나쁜 수열이라고 한다. 백트래킹을 통해 방문하면서 check 함수를 통해 좋은 수열만 다음 탐색으로 넘어갈 수 있도록 해..

BOJ 2529 - 부등호

2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 아이디어 탐색 일단 조건을 생각하지 말고 0~9까지의 숫자를 중복없이 순서있게 나열한다. private static void rec_func(int k) throws IOException { if (k == M + 1) { // 조건 } else { for (int i = 0; i 0) && (inequality[i] == '>')) { possible = true; } else { possible = false; } if (possible == false) { break;..

BOJ 2580 - 스도쿠

2580번: 스도쿠 (acmicpc.net) 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 아이디어 재귀로 완전탐색하는 부분과 위의 2조건을 판단하는 부분을 따로 만들어 생각한다. 탐색 부분 행과 열을 전체적으로 돌면서 탐색하니까 재귀함수 rec_func의 파라미터는 행과 열로 지정해주었다. private static void rec_func(int row, int col) 먼저 row 행을 기준으로 col 열을 1열부터 9열까지 돌면서 숫자가 채워지지 않은 부분 (0인 부분)을 찾아서 for문으로 1~9까..

BOJ 10819 - 차이를 최대로

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 아이디어 N개의 정수를 중복을 허용하지 않고 순서있게 나열하는 순열문제이다. 먼저 가능한 순열을 완전탐색을 통해 다 뽑고 난 후 주어신 식에 대입해서 최댓값을 갱신한다. 시간복잡도 N의 최댓값은 8 이므로 순열의 시간복잡도인 O(N!)에 대입하면 8! < 1초라서 가능한 접근법이다. 구현 import java.io.*; import java.util.StringTokenizer; public class Main..

BOJ 1759 - 암호 만들기

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 아이디어 일단 먼저 최소 한개의 모음과 최소 두 개의 자음이라는 조건을 제외하고 생각해보자 서로 다른 C개의 알파벳 소문자들 중 L개를 중복없이 사전순으로 순서있게 나열하는 순열 문제이다. C개의 알파벳을 먼저 정렬한 후 중복없이 사전순으로 조합을 짜기 위해 prev 인자를 통해 k자리의 다음 자리인 k+1 자리는 prev +1 부터 탐색하도록 설정해서 완전 탐색으로 모든 경우의 수를 구한다. 이제 여..

BOJ 14888 - 연산자 끼워넣기

14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 아이디어 주어진 순서를 바꾸면 안되니까 연산자만 순서를 잘 조합해서 숫자 사이사이에 끼워넣으면 된다. 연산자는 딱 N-1개만큼 주어지고 모두 사용해야 하니까 N-1개의 연산자를 순서있게 나열하는 순열문제이다. 연산자를 +, -, *. / 순으로 개수를 받으니까 +를 1, -를 2, *를 3, /를 4로 인덱스를 설정하고 이 인덱스들을 N-1개 만큼 순서있게 나열한 후 인덱스로 연산자를 불러와서 계산하면 된다...

BOJ 1182 - 부분수열의 합

1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 1. 아이디어 먼저 정답의 최대치 계산해보기 먼저 N의 최대치가 20이이니까 부분수열의 개수는 최대 2^20 -> int N 결정 부분수열의 합은 최대 20*1,000,000 -> int S 결정 N개의 정수를 중복을 허용하지 않고 합이 S가 되는 진부분수열을 구하는 문제 1~N 크기의 부분수열 전부 체크해서 합이 S가 되는 경우 찾으면 되겠다!!! 부분 수열은 중복을 허용하지 않고 순서도 고려하지 않기 때문에 조합으로 구하면..