본문 바로가기

분류 전체보기

백준 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이 들어왔다고 예를 들면 첫 번째 홀수인 소..
백준 1929 소수 구하기 Java 2019. 4. 17. 이 문제는 정답률 28퍼센트의 소수 구하기 문제이다. 정답률이 28퍼센트인 이유는 아마 에라토스테네스의 체를 쓰지 않고 제출한 분들 때문일 것이다. 이 문제는 에라토스테네스의 체를 쓰지 않고는 시간초과가 나는 문제이다. 이 글에선 에라토스테네스의 체를 정리하려고 한다. 소수를 구하는 방법 중 O(루트n)인 방법도 있지만 이 방법도 정수 n 한개가 소수인지 아닌지 구하는데 O(루트n)의 시간이 소요되는 것이다. 따라서 정수 n의 개수가 1000000000 처럼 큰 수 이면 그 수는 실행 횟수는 한 없이 늘어나게 된다. 그래서 여러 수의 소수를 구하는 가장 빠른 방법인 에라토스테네의 체를 사용해야 한다. 에라토스테네스의 체에 대해 자세히 설명해주는 다른 블로그나 티스토리가 많다. 간단하게 설명하자면 O(루트..
백준 1978 소수 찾기 Java 2019. 4. 16. 소수 문제의 기초 문제이다. 풀이가 어렵지도 않은 문제를 다시 한번 정리하는 이유는 소수를 찾는 세 가지 방법에 대해 정리하기 위해서이다. 소수를 찾는 방법 중 가장 빠르다고 알려진 방법은 에라토스테네스의 체를 이용하는 방법이다. 하지만 다른 방법들 보단 복잡하기 때문에 에라토스테네스의 체는 다른 문제를 통해 정리하기로 하고 이 문제에서는 에라토스테네스를 제외한 빠른 방법들을 정리하고자 한다. 가장 기본 적인 방법으로는 n이 있을때 n이 소수인지 판명하기 위해 n을 2부터 n-1까지 나눠보는 방법이 있다. 소수는 약수가 1과 자기자신 뿐이여야 하기 때문에 자신 보다 작은 어떤 수와 나누어 떨어진다면 그 수는 약수가 아니다. for(int i=2; i
백준 2089 -2진수 Java 2019. 4. 16. 그냥 2진법으로 바꾸는 문제가 아닌 -2진법으로 바꾸는 문제이다. -2진법 문제는 그냥 2진법으로 바꿀 때 처럼 똑같이 풀면 된다. 다른점이 있다면 나머지 연산과 나누기 연산을 할때 -2를 해줘야 한다는 점과 나머지 연산을 할때 몫을 버림이 아닌 올림을 해줘야 한다는 점이다. 예를 들어 7/3 = 2 지만 7/-3 = 3이 라는 말이다. 왜 그런지 열심히 검색해봤지만 뚜렷한 이유를 알 수 없었다. 그냥 그렇다고 암기해야 겠다. 암튼 이렇게 해서 나머지를 구한 다음에 2진법을 구할 때 처럼 역순으로 출력해주면 된다. Math.ceil()메소드를 통해 올림을 처리하였다. n이 0일땐 따로 처리를 해줘야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public static vo..
백준 1373 2진수 8진수 & 백준 1212 8진수 2진수 Java 2019. 4. 15. 주어진 2진수를 8진수로 바꾸면 되는 문제이다. 간단해보이는 문제이지만 정답률이 37퍼센트이다. 내 생각에 37퍼센트인 이유는 문제를 보고 반 이상의 사람들은 2진수를 10진수로 바꾼다음에 8진수로 변환했을 것이다. Integer메소드를 활용해서 말이다. 나 또한 처음에 그렇게 풀었는데 결과는 시간초과였다.. 항상 배워도배워도 까먹는 2진수를 8진수로 변환하는 법을 다시 한번 정리한다. 110101 이라는 이진수가 있을 때 세 자리씩 끊어서 10진수로 변환하면 8진수가 된다. 110/101 110 -> 6 101 -> 5 =>65 이런 방법으로 2진수를 바로 8진수로 바꿔주면 맞췄습니다가 뜬다. 하지만 이것을 코드로 옮기는 것도 쉽지만은 않다. 10101인 경우 10/101로 끊어지게 되고 세 자리가 아..
백준 2745 진법 변환 Java 2019. 4. 15. 아래 글에 있는 진법 변환2 의 반대 버전 문제이다. 진법 변환2 는 10진수 n을 b진수로 바꾸는 문제 였다면 진법 변환은 b진수 n을 10진수로 바꾸는 문제이다. 진법 변환2에서 b진수로 변환 시킬때 if(a%b < 10) (char)(n%b + '0') 나머지가 10보다 작을 땐 아스키코드 의 '0'을 더해줘서 char값을 표현 했고 else (char)(n%b-10+'A') 나머지가 10이상 일땐 10을 빼주고 아스키코드 'A'을 더해줘서 A~Z의 값을 표현 했다. 그리고 반대로 출력해서 값을 만들었다. 만약 값이 2진수 1011 이라면 이 값은 반대로 출력한 값이기 때문에 다시 10진수로 바꾸기 위해서는 뒤집지 않고 첫번째 자리부터 첫 번째 자리 값*2^0 + 두 번째 자리 값*2^1 + 세 번..
백준 11005 진법 변환 2 Java 2019. 4. 15. 진법 변환 문제이다. 이 문제는 2진법, 8진법, 16진법 뿐 만 아니라 1~36진법까지 변환해야 한다. Integer.toBinaryString 같은 메소드는 못쓰는 문제인 것이다. 그러므로 나머지 연산을 통한 진법 변환을 해야한다. Java카테고리의 진법변환 관련 글에 적어놓은 방법으로 나머지 연산을 통해 n진수를 구하면 된다. 근데 10이상 부터는 A~Z로 표현 되기 때문에 char형 ArratList를 만들어 아스키코드 값을 통해 값을 넣어주었다. 만약 9 이하라면 list.add(a%b+'0') 아스키코드값 0을 더해줌으로써 a%b의 값을 아스키코드로 char형 list에 저장한다. 10이상 이라면 list.add(a%b-10+'A') 10부터 A이므로 나머지 값에서 10을 빼고 아스키코드 값 ..

티스토리툴바