자바
-
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..
-
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으로 나눠지는 숫자..
-
BOJ) 리모컨알고리즘/백준 2020. 7. 11. 20:22
리모컨 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼�� www.acmicpc.net 풀이 리모콘이 고장나면 고치거나 바꿔야하는데, 그대로 써서 골치아프게한 문제다. 우선, 1~9 버튼과 채널 위아래 이동 + - 버튼 11개가 있는 리모컨이다. 그리고, 입력에서 버튼이 고장난 갯수와 버튼의 위치를 알려주는데, 여기서 런타임에러가 한번 떴다. 처음에는 if(n !=ZERO)를 해주지 않아서, n이 0인 경우 ( 고장난 버튼이 없는 경우 ) 에 입력을 받고 저장하려고 시도해서 에러가 났다. 그래서 if문을 통해 걸러줬다. ..