정렬55 [자바] 백준 2750 - 수 정렬하기 (java) 문제 : boj2750 필요 알고리즘 개념 정렬 정렬이란 무엇인지와 어떻게 구현할 수 있는지 알아야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 기본중의 기본! 오름차순으로 정렬만 하면 되는 문제이다. 물론 자바에서 제공하는 sort 함수로 정렬을 해도 되긴하다. 하지만 그러면 너무 난이도가 쉬우니 여러 정렬 방식을 사용해서 한번 풀어보자. 내 경우엔 이하의 3가지로 풀어봤다. 1. 자바에서 제공하는 sort.. 2022. 8. 12. [자바, 코틀린] 백준 17390 - 이건 꼭 풀어야 해! (java, kotlin) 문제 : boj17390 필요 알고리즘 개념 누적 합 (prefix sum) 연속된 범위의 합을 O(1)로 구하기 위해 누적 합을 사용한다. 누적 합에 대한 개념이 있어야 풀 수 있다. 정렬 정렬이 무엇인지, 자바나 코틀린으로 정렬은 어떻게 하는지 알아야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. 비내림차순으로 정렬해야 한다. 비내림차순이 생소할 수 있다. 그냥 이 문제에서는 오름차순이라고 생각하면 된.. 2022. 8. 8. [자바] 백준 23882 - 알고리즘 수업 - 선택 정렬 2 (java) 문제 : boj23882 필요 알고리즘 개념 시뮬레이션 문제 자체가 풀이에 해당하고 문제 그대로 구현해주면 되므로 시뮬레이션이라 볼 수 있다. 딱히 이걸 알아야 풀 수 있는건 아니다. 정렬 정렬이 뭘 하는건지 알고 있어야 한다.역시 딱히 이걸 알아야 풀 수 있는건 아니다. 문제 자체가 풀이에 해당하므로! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제 자체가 풀이에 해당하기 떄문에 별도로 말할건 없을 것 같다. 그래도 설.. 2022. 8. 6. [자바] 백준 23881 - 알고리즘 수업 - 선택 정렬 1 (java) 문제 : boj23881 필요 알고리즘 개념 시뮬레이션 문제 자체가 풀이에 해당하고 문제 그대로 구현해주면 되므로 시뮬레이션이라 볼 수 있다. 딱히 이걸 알아야 풀 수 있는건 아니다. 정렬 정렬이 뭘 하는건지 알고 있어야 한다.역시 딱히 이걸 알아야 풀 수 있는건 아니다. 문제 자체가 풀이에 해당하므로! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제 자체가 풀이에 해당하기 떄문에 별도로 말할건 없을 것 같다. 그래도 설.. 2022. 8. 4. [자바] 백준 2470 - 두 용액 (boj java) 문제 : boj2470 예시 입력 1을 봐보자. 5 -2 4 -99 -1 98 위 상태로만 보자면, 결국 O(N^2)으로 모든 쌍을 확인하는 것 외에 별다른 방법이 떠오르지 않을 것이다. 정렬을 하면 어떨까? -99 -2 -1 4 98 이 경우 가장 좌측에서 시작하는 포인터를 s, 가장 우측을 e라고 해보자. 's의 값 + e의 값'을 기준으로 포인터를 중앙으로 점차 가져와보자. - 두 포인터가 가르키는 값의 합이 0 초과이라면 -> 더 작은 값을 확인해야하니 e를 좌측으로 이동한다. - 두 포인터가 가르키는 값의 합이 0 미만이라면 -> 더 큰 값을 확인해야하니 s를 우측으로 이동한다. 위 두가지 경우에 따라 s와 e를 중앙으로 이동시키면서 0과 가장 가까운 값을 찾으면 된다! 위의 경우 1. s=-9.. 2022. 7. 4. [자바] 백준 15688 - 수 정렬하기 5 (boj java) 문제 : boj15688 사실 그냥 배열에 입력받은 후 sort 함수를 사용하고, 순서대로 출력해주기만 하면 되는 간단한 문제이다. 그냥 그렇게 하면 재미없으니 내 경우엔 카운팅 정렬로도 구현해봤다. 당연히 후자가 더 빠르다. 이하 일반적인 sort 함수를 통한 풀이 코드와, 카운팅 정렬 구현을 통한 풀이 코드 모두 첨부해두었다. 코드(일반적인 자바 sort 사용) : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class Main { StringBuilder sb = new StringBuilder(); private void solution() throws Ex.. 2022. 6. 21. [자바] 백준 13548 - 수열과 쿼리 6 (boj java) 문제 : boj13548 우선 가장 간단한 방법으로, 각 쿼리마다 직접 해당 범위를 순회하면서 가장 많은 등장 수를 찾는 것은 당연히 간단하다. 하지만 그러면 O(MN)이 될 것이므로 시간초과가 나게 된다. 그러니 이번엔 이전 쿼리의 결과를 이용할 방법을 생각해보자. 첫 번째 쿼리가 i=3, j=10이고 두 번째 쿼리가 i=5, j=11 이라고 해보자. 그림으로 나타내면 아래와 같다. 이 경우 만약 위에서 말한 방법대로 매번 직접 순회하며 볼 경우 첫 번째 쿼리는 8번, 두 번재 쿼리는 7번을 봐야하므로 총 15번을 봐야한다. 하지만 첫 번째 쿼리에서 i가 +2가 됬으므로 주황색으로 빗금친 부분을 빼면 2번을 빼면 되고, 마찬가지 방식으로 파란 빗금부븐을 1번 더해줄 수 있다. 그럼 총 15번 필요했던게.. 2022. 6. 9. [자바] 백준 24155 - 得点 (Score) (boj java) 문제 : boj24155 다음의 표를 보자. (A)는 애초에 입력이 내림차순이고 겹치는 점수가 없는 경우이다. 이 경우 등수는 순서대로가 될 것이다. (B)는 내림차순이지만, 겹치는 점수가 있는 경우이다. 이 경우 이전과 점수가 같다면 등수도 이전과 동일하고, 이전과 점수가 다를 경우 현재 자신의 위치를 출력하면 순서대로 등수를 출력할 수 있다. 이 문제의 경우 처음에 정렬이 되어 들어오지 않는다. 따라서 (C)와 같이 정렬한 후 등수를 매겨보자. (A), (B)와 달리 '학생'부분의 숫자가 뒤죽박죽인 것을 알 수 있다. 정렬 후 등수를 매기는 것은 (A), (B)와 동일하다. 이후 (D)와 같이 학생 번호 순서대로 다시 정렬하면 처음 입력된 순서대로 등수를 출력할 수 있다. 코드 : github imp.. 2022. 5. 15. 백준 11004 자바 - K번째 수 (boj 11004 java) 문제 : boj11004 정렬만 할 줄 안다면 바로 풀 수 있는 날먹문제. 정렬 후 K-1 인덱스에 있는 값을 출력해주면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(.. 2022. 4. 11. 백준 2170 자바 - 선 긋기 (boj 2170 java) 문제 : boj2170 당연히 전체 위치를 보게되면 -10억부터 +10억까지 봐야하므로 시간초과가 뜬다. 최대 100만개인 N을 기준으로 동작할 방법을 찾아야 한다. 문제에서 제시된 '예제 입력 1'은 이미 그렇게 정렬된 데이터긴 하지만, N개를 전부 x를 기준으로 오름차순으로 정렬했다고 생각하고 어떻게 풀지 한번 생각해보자. 4 1 3 2 5 3 5 6 7 그렇다면 위와 같이 x값 기준 오름차순으로 차례대로 확인할 경우(x값이 동일할 경우 y값 순서는 상관 없음. 그나마 내림차순으로 하면 아주 약간의 대입연산 정도는 줄여볼 수 있는데 의미 없음), 이전 y 값보다 현재의 x값이 작거나 같다면 이어진 항목으로 생각해볼 수 있다. 1-3을 본 후, 2-5를 보자. 현재 보고 있는 x인 2는 이전의 y값인 .. 2022. 3. 30. 이전 1 2 3 4 5 6 다음
