본문 바로가기

Algorithm

백준 10610 30 Java 2019. 5. 10. 그리디 알고리즘 문제인 30이다. 문제를 이해하지 못해서 풀지 못했는데 주어진 수들을 아무렇게나 조합해서 가장 큰 30의 배수를 찾는 문제인줄 알았다. 310이 주어졌으면 가장 큰수인 310은 30의 배수가아니므로 아니고 310을 가지고 30을 만들 수 있으므로 답을 30으로 출력되도록 문제를 풀어나갔다. 그런데 문제는 그런게 아니라 주어진 수를 전부 사용해야만 했다. 그래서 주어진 수를 한자리씩 빼서 일단 정렬한 다음에 역순으로 출력해 가장 큰 수를 만든후 그 수가 30의 배수인지 체크하여 문제를 풀고 제출했다. 하지만 이런식으로 풀면 어김없이 시간초과가 발생했다. 더 빠르게 해본다고 여러가지의 방법을 시도했지만 3연속 시간초과의 시련을 만나게된다. 정답인 풀이법은 이러했다. 30을 소인수분해 해보면 ..
백준 1019 책 페이지 Java 2019. 5. 3. N쪽인 책의 페이지에 나온 0~9까지 숫자의 횟수를 출력하면 되는 문제이다. 내가 풀어내진 못했고, 알고리즘을 잘 하시는 마이구미님의 블로그를 통해 소스코드를 보고 이해하려고 노력한 문제이다. 시간이 좀 걸려서 이해했지만 까먹을 수 있으니 정리해야겠다. 11페이지를 입력받았을 경우엔 0 1 2 3 4 5 6 7 8 9 1 4 1 1 1 1 1 1 1 1 이렇게 출력이 되야한다. 1이 4번 나왔는데 1에서 한 번 10에서 한 번 11에서 두 번 총 네 번인 것이다. 암튼 이 문제의 경우엔 크기 10 배열을 선언하고 그 배열의 0번째 .. n번째 인덱스에 횟수를 넣어주어야 되는 것은 틀림없다. 누구나 그렇듯 처음엔 1부터 n까지 반복문을 돌며 charAt()으로든 %연산과 /연산으로든 출연 횟수를 구하려 했..
백준 14697 방 배정하기 Java 2019. 4. 29. 문제집에 있는 문제를 무작위로 풀어보던 도중 만난 문제이다. 문제를 보자마자 백준 2839번 설탕 배달 문제가 생각났다. 그래서인지 설탕 배달을 풀었을 때 처럼 풀어보려고 노력을 해봤지만 설탕 배달 문제와는 다른 부분이 많아서 설탕 배달 처럼 풀지는 못하였다. 우선 세 개의 수가 주어지는데 세 가지의 수를 전부 안써도 된다. 하나의 수로만 주어진 인원을 꽉채워도 되고 두 개의 수도 되고.. 세 개의 수도 되고 어떻게 풀어야할지 도저히 감이 안잡혔다. 주어진 수의 배수를 모두 저장하고 배수들 끼리 더해보는 방법도 생각해봤지만 아무리 생각해도 그렇게 푸는건 아닌 것 같았다. 근데 그런식으로 푸는게 맞았다.. 나올 수 있는 경우의 수를 다 더해보는... 이것을 완전탐색 또는 브루트포스(brute force)알..
백준 1167 트리의지름 Java 2019. 4. 29. 정답률 36퍼센트의 트리 문제이다. 트리의 지름을 구하는 문제인데 트리에 존재하는 모든 경로 중 가장 긴 것의 길이를 트리의 지름이라고 한다. BFS/DFS는 그래프에서만 해당되는 탐색 방법인 줄 알았는데 트리에서도 많이 사용되는 것을 알게 되었다. 트리의 부모를 찾을 때도 BFS탐색을 통해 구할 수 있고 트리의 지름도 BFS탐색을 통해 구할 수 있다. 트리의 지름을 구하는 방법은 따로 있는 것 같다. 1. 가장 긴 길이를 갖고있는 정점을 구한다. 2. 가장 긴 길이의 정점을 기준으로 다시 거리를 측정한다. 3. 거리를 저장한 배열 중 최대값이 트리의 지름이다. 입력 받을 때 기준 정점을 하나 입력 받고 -1이 입력되기 전까지 정점, 길이를 입력 받는다. 트리를 저장할 배열에 정점과 길이 -> 값이 2개..
백준 2146 다리만들기 Java 2019. 4. 24. 정답률 30퍼센트의 DFS/BFS문제이다. 머리가 안좋아서인지 내 기준에선 많이 어려운것 같다 ㅠ 이 문제를 푸는방법에는 여러가지가 있다고 하지만 난 간척방법을 택해서 이해하기로 했다. 처음에도 간척하는 식으로 인접한 수를 +1 씩하며 거리를 체크하며 문제에 접근했는데 섬과 섬사이의 가장 짧은 거리를 어떻게 뽑아내야할지를 도저히 생각해내지 못했다. 결국 해설을 봐야만 했다. 난 입력받은 배열로만 처리하려고 했는데 그게 실수였다. 이 문제에서 간척방법으로 해결하려면 총 3개의 배열이 필요하다. int [][] a ->입력받은 배열 int [][] d ->섬과 섬사이의 거리 int [][] g -> 섬의 영역을 표시 처음엔 g배열에 입력받은 배열에서 섬끼리 숫자를 매겨가며 구분을 한다. 만약 5 1 0 0 ..
백준 9466 텀 프로젝트 Java 2019. 4. 23. 정답률 24퍼센트의 어려운 그래프 문제이다. '팀'프로젝트 인줄 알았는데 '텀'프로젝트였다. 이유는 모르겠다. 학생끼리 조를 짤 때 하고싶은 사람이 꼭 겹쳐야 조를 짤 수 있다. 한마디로 싸이클인 그래프에 속한 학생들만 조를 짤 수 있다는 것이다. 혼자하고 싶은 학생들은 자기 자신을 가리켜도 된다. 또는 마지막 학생이 가리킨 학생이 반드시 시작한 학생이여야 한다. 방문했는지를 확인하는 boolean형 배열 대신 int형 배열로 현재 정점이 몇 번째 방문한 정점인지 저장하고 또다른 int형 배열로 현재 정점이 어디서 부터 시작된 정점인 건지를 체크하고 확인하는 방식으로 문제를 풀면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ..
백준 1377 버블 소트 Java 2019. 4. 19. 정렬문제인 버블 소트이다. 제목 그대로 버블 소트에 관한 문제인데 버블 소트 코드가 주어지고 버블 소트가 더 이상 정렬할게 없을 때 i가 몇인지 즉 몇단계 인지를 출력해서 맞히는 문제이다. 주어진 코드를 그래도 사용해도 답은 다 맞는다. 다만 시간초과로 정답처리가 안된다. 버블 소트는 O(n^2)이기에 N이 500,000이면 250000000000번 연산하게 돼서 당연히 시간초과이다. 그래서 정답률이 30퍼센트 대 이다.. 예제로 주어진 배열 10 1 5 2 3을 보면 i가 증가 될때 마다 10 1 5 2 3 1 5 2 3/ 10 1 2 3 /5 10 - > break; 이렇게 배열이 변하게 된다. 버블 소트는 뒤로 큰수를 뒤로 보내면서 정렬하는 방식이기에 뒤로 보내는걸 보지 않고 앞으로 이동되는 수가 ..
백준 6588 골드바흐의 추측 Java 2019. 4. 17. 정답률 27퍼센트의 소수관련 문제이다. 어떤 짝수 n은 홀수 소수를 더해서 만들 수 있다는 추측을 증명하는 문제이다. 입력으로 주어지는 짝수n를 홀수 소수 a와 b로 n = a + b 형태를 출력하면 된다. 정답률이 27퍼센트인 만큼 쉽지 않다. 에라토스테네스의 체로 소수를 구한다음에 for문 두개로 하나씩 비교하며 i+j == n 형태로 답을 구하면 시간초과로 틀리게 된다. 시간초과를 해결하기 위해 생각해봤지만 답은 나오지 않았다. 답은 for문을 한개 써서 해결하는 것이였다. 홀수인 소수들을 따로 빼서 새로운 배열을 하나만들고 소수인지 아닌지를 담아놓은 boolean형 배열 b에서 b[n-홀수인 소수]이면 출력을 하는 형태로 해결해야 했다. 입력으로 짝수 8이 들어왔다고 예를 들면 첫 번째 홀수인 소..

티스토리툴바