본문 바로가기

전체 글

백준 1541 잃어버린 괄호 Java 2019. 5. 10. 그리디 알고리즘 문제인 잃어버린 괄호 문제이다. 입력으로 어떠한 식이 한 줄 주어졌을 때 괄호를 적절히 쳐서 값을 최소로 만들면 되는 문제이다. 예제만 보고도 알 수 있듯이 값을 최소로 만들기 위해서는 괄호를 마이너스 뒤에 치면 된다. String으로 식을 입력 받고 -,+를 저장하는 배열을 따로, 수를 저장하는 배열을 따로 만든다. 어떠한 수가 한 자리이든 두 자리이든 수의 다음엔 무조건 +또는- 가 오므로 +와-를 만날 때 까지 숫자를 String으로 계속 합치고 +와-를 만나면 숫자를 저장하는 배열에 넣어준다. 마찬가지로 +나- 또한 같이 다른 배열에 넣어준다. 그리고 연산자배열과 수를 저장한 배열을 동시에 하나 씩 꺼내서 확인한다. 이 때 처음으로 - 연산자를 만나면 그때부터는 수를 전부 빼주면 ..
백준 10610 30 Java 2019. 5. 10. 그리디 알고리즘 문제인 30이다. 문제를 이해하지 못해서 풀지 못했는데 주어진 수들을 아무렇게나 조합해서 가장 큰 30의 배수를 찾는 문제인줄 알았다. 310이 주어졌으면 가장 큰수인 310은 30의 배수가아니므로 아니고 310을 가지고 30을 만들 수 있으므로 답을 30으로 출력되도록 문제를 풀어나갔다. 그런데 문제는 그런게 아니라 주어진 수를 전부 사용해야만 했다. 그래서 주어진 수를 한자리씩 빼서 일단 정렬한 다음에 역순으로 출력해 가장 큰 수를 만든후 그 수가 30의 배수인지 체크하여 문제를 풀고 제출했다. 하지만 이런식으로 풀면 어김없이 시간초과가 발생했다. 더 빠르게 해본다고 여러가지의 방법을 시도했지만 3연속 시간초과의 시련을 만나게된다. 정답인 풀이법은 이러했다. 30을 소인수분해 해보면 ..
정수와 실수 자료형의 최소값과 최대값 2019. 5. 4. 내가 기억해둬야 할 것은 int형은 약 21억 까지 long형은 약920경 까지 920경을 넘어간다면 BigInteger를 쓰도록 하자. double도 long과 같은 8바이트인 것도 기억하자.
백준 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 ..

티스토리툴바