java
-
BOJ) 대회 or 인턴알고리즘/백준 2020. 7. 18. 22:01
대회 or 인턴 2875번: 대회 or 인턴 문제 백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.) 백준대학교는 뛰어난 인재들이 많아 www.acmicpc.net 풀이 1. 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙 2. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 위의 두 조건에 따라, 여학생과 남학생, 인턴에 참여하는 학생의 수가 순서대로 주어질 때, 인턴쉽에 참가할 수 있는 최대 팀의 수를 구하는 문제다. 여학생 2명과 남학생 한명을 짝지어야 하기 때문에, 반복문을 통해 인턴십에 참여..
-
BOJ) 동전 1알고리즘/백준 2020. 7. 18. 21:56
동전 1 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 n 가지 종류의 동전을 각각 여러개 이용해서 k원이 되게 하는 수를 구하는 문제다. 처음에는 dfs로 접근했다가, 동전은 몇개라도 사용할 수 있다는 조건을 보고 DP로 선회했다. 각각 동전에 대해서 K원 이하일 때, 쓰일 수 있는 모든 돈에 경우의 수를 추가시켜주었다. for문을 돌면서 각 동전 coin에 대해coin의 가치부터 K원 까지 들어갈 수 있는 경우만 추가시켜주면 해결되는 문제였다. 코드 import java.io.BufferedReade..
-
BOJ) 암호 만들기알고리즘/백준 2020. 7. 18. 21:47
암호 만들기 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 C 개의 문자 중 L개를 선택해서 만들 수 있는 암호를 출력하는 문제다. 이 때, 암호는 모음(a,e,i,o,u)이 최소 하나 이상 자음이 두개 이상인 조합만 가능하다. 또한, 모든 암호의 경우를 사전순서대로 출력해야한다. 위의 두 조건을 충족하기 위해 C개 중 L개를 선택하는 것은 DFS를, 사전 순서대로 하기 위해 정렬을 선택했다. DFS이후에 정렬을 하기에는 너무 많은 시간과 메모리를 낭비할 것 같아서 입력 받자마자 정렬을 해주었다. DFS에서..
-
BOJ) 신입 사원알고리즘/백준 2020. 7. 18. 21:38
신입 사원 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성�� www.acmicpc.net 풀이 처음에는 완전탐색으로 풀려고 시도했다. 하지만, 모든 배열을 n번씩 돌다보니까 시간초과가 떴다. 그래서 정렬을 이용해야 겠다고 생각했다. 정렬의 기준을 잡는데 고민을 많이 했는데, 서류와 면접 둘 다 포함시켜 정렬하기엔 너무 복잡해서 하나를 기준으로 정렬을 해야겠다고 생각했다. 그래서, 서류 심사를 기준으로 오름차순 정렬을 해줬다. 서류 심사에서 1등을 받은 사람의 면접 등수를 첫 기준으로 삼고, 서류 2등부터 쭉 돌면서..
-
BOJ) 적록색약알고리즘/백준 2020. 7. 16. 16:59
적록색약 10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G( www.acmicpc.net 풀이 적록색약이 있는 사람이 봤을 때 영역의 갯수와 일반 사람이 봤을 때 영역의 갯수를 각각 출력하는 문제다. 가장 기본적인 grouping을 활용하는 문제였다. 코드 수를 줄이려면, 서칭하는 메소드를 하나로 합치고 식별 번호를 부여해서 if문을 통해 처리할 수 있다. 하지만, 코드의 길이가 200 300줄이 되는 정도는 아니어서 그냥 나눠서 진행했다. ( solution에서 더 깔끔하게 볼 수 있기 때문에) 평범한 사람이 봤을 때는, 해당 맵과 ..
-
BOJ) 토마토알고리즘/백준 2020. 7. 16. 16:52
토마토 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 세 번을 시도한 끝에 풀었다. 처음에는 익지 않은 토마토의 총 갯수를 입력받을 때 저장하고, 매 회차 익지않은 토마토 주변을 탐색하면서 익게 만들었다. 하지만, 당연하게도 시간초과가 떴다. 두번째로는 익지 않은 토마토에서 시작하는 방법을 그대로 적용하고, 각 토마토 위치마다 익게되는 날짜를 저장할 int형 배열을 만들었다. BFS 탐색을 통해서 저장한 다음, 최대 날짜를 최신화했고, 안익은 토마토가 0일로 남아있다면 불가능하다..
-
BOJ) 다리 놓기알고리즘/백준 2020. 7. 16. 16:42
다리 놓기 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 강의 왼쪽과 오른쪽에 다리를 건설하는데, 교차해서 지으면 안되는 조건의 문제다. 왼쪽보다 오른쪽에 다리를 지을 수 있는 포인트가 더 많다. 여기서 Combination 문제라고 생각했다. 하지만, 30이나 되는 수에서 직접 Combiantion을 구할 수 없었기 때문에 수학 공식을 찾아봤다. nCr = n-1Cr-1 + n-1Cr 이라는 공식이 있다는 것을 알았다. 앞으로는 콤비네이션을 이용해 푸는 문제를 만났을 때, 더욱 효율적으로 풀기 위해 ..
-
BOJ) 체스판 위의 공알고리즘/백준 2020. 7. 11. 20:55
체스판 위의 공 16957번: 체스판 위의 공 크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다. 체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙�� www.acmicpc.net 풀이 체스판의 크기가 500x500이지만, 공들이 옮겨가면서 0인 부분이 많이 생길거라고 생각하고 DFS로 진행했다. 하지만, 6%에서 시간초과가 떴고 DFS로는 풀 수 없는 문제라고 생각이 들었다. 그래서 인접한 칸들 중 가장 작은 숫자로 이동한다는 조건을 보고, find-union을 응용하면 풀 수 있을거라고 생각했다. 일단, union부분은 필요가 없다고 생각을 했다. 생각하기도 복잡해지고, 타고 타고 이동해야하는 특성상 paren..