BOJ
-
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. 11. 20:55
체스판 위의 공 16957번: 체스판 위의 공 크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다. 체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙�� www.acmicpc.net 풀이 체스판의 크기가 500x500이지만, 공들이 옮겨가면서 0인 부분이 많이 생길거라고 생각하고 DFS로 진행했다. 하지만, 6%에서 시간초과가 떴고 DFS로는 풀 수 없는 문제라고 생각이 들었다. 그래서 인접한 칸들 중 가장 작은 숫자로 이동한다는 조건을 보고, find-union을 응용하면 풀 수 있을거라고 생각했다. 일단, union부분은 필요가 없다고 생각을 했다. 생각하기도 복잡해지고, 타고 타고 이동해야하는 특성상 paren..
-
BOJ) 회의실배정알고리즘/백준 2020. 7. 11. 20:43
회의실배정 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 포스팅하기에는 조금 민망한 코드지만, 정답률이 높지 않아서 포스팅하게 됐다. 회의가 시작시간과 끝나는 시간이 담겨있는 여러 회의에 대해 요청받는다. 이 때, 고르게 분포해서 최대한 많은 팀이 회의를 할 수 있게 만들어야한다. 그래서 처음에는 회의 시간이 가장 짧은 순으로 정렬을 했었다. 하지만, 반례가 존재했고 다시 고민했다. 회의가 끝나는 시간을 기준으로 시작시간이 가장 빠른 순서로 정렬하기로 했다. 회의가 끝나는 시간이 빠른 회의들 중 가장 회의 시간이 짧은 회의들을 채택하는 방법이다. 이후, 정렬된 배열을 돌면서 앞선 회의의 끝나는 시간과 같거나 이후인 회의..
-
BOJ) 로프알고리즘/백준 2020. 7. 11. 20:36
로프 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 www.acmicpc.net 풀이 냉정하게 판단하자면 아주 간단한 문제다. 병렬로 로프를 연결하면, 각 로프에 가해지는 무게를 똑같은 무게로 나누어 가질 수 있다는 조건이 있다. 그리고, 각 로프가 최대 견딜 수 있는 하중이 주어진다. 1 2 3 4 5 라는 각각 하중을 버틸 수 있는 로프가 주어진다면, 5 하나만 쓰는 것이 가장 무거운 무게를 들 수 있는지, 5 4를 합쳐서 드는 것이 합리적인지 따져가면 되는것이다. 그래서 우선 입력받은 로프를 정렬해주었다. 자바의 Arrays..
-
BOJ) 30 (자바, JAVA)알고리즘/백준 2020. 7. 11. 20:30
30 10610번: 30 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶� www.acmicpc.net 풀이 N을 입력받는다. N는 최대 10^5개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 문제에서 주어진 이 조건을 N의 최대값이 10^5로 읽어서 처음에는 DFS로 시도했다. 하지만, 최대 10^5개의 숫자니까 100000 개의 숫자로 이루어져 있다는 거니까 DFS는 어마어마한 요청이 들어가고 stack over flow가 뜬다.. 런타임 에러가 뜨자마자 왜지?하고 봤더니 10^5가 숫자의 갯수였다. 그래서 로직을 찾아봤다. 30으로 나눠지는 숫자..