본문 바로가기

PS831

[자바] 백준 25375 - 아주 간단한 문제 (java) 문제 : boj25375 필요 알고리즘 개념 정수론, 수학 수학적인 추론이 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 a, b가 최대 10^18 이므로 당연히 x, y를 직접 찾아낼 순 없다. 그렇다면 수학적인 추론이 필요할 것임을 예측할 수 있다. 수학적으로 매우 약하기 때문에 내 경우엔 우선 간단히 생각해낼 수 있는 부분을 생각해봤다. gcd(x,y) = a 라면 당연히 x와 y는 각각 a로 나누어 .. 2022. 10. 19.
[자바] 백준 24075 - 計算 (Calculation) (java) 문제 : boj24075 필요 알고리즘 개념 구현 번역기 돌린 후 문제에서 제시된대로 풀면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 일본어인게 문제지만, 번역기 돌리면 대강 알아볼 수 있게 나온다. 결론적으로 a+b와 a-b 중 큰쪽을 출력해주면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.u.. 2022. 10. 19.
[자바] 프로그래머스 - 쿠키 구입 (Lv4, Java) 문제 : Programmers-쿠키 구입 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 두 포인터 (투 포인터) 투 포인터 알고리즘을 알고 있다면 어렵지 않게 풀어볼 수 있다. 일반적으로 문제를 좀 더 단순화해서 생각해보면 풀이를 생각하기 쉬운 경우가 많다. 한번 m이 고정이라고 생각해보고 어떻게 풀지 생각해보자. 그렇다면 l과 r을 적절히 조정해서 l~m의 합과 m+1~r 까지의 합을 동일하게 만드는 문제가 된다. 그리고 입력값으로 0 또는 음수가 주어지지 않으므로 단순히 l~m의 합이 m+1~r의 합보다 작다면 l을 줄이고, 그 반대라면 r을 늘려주기만 하면 된다. 즉 l과 r 두개의 포인터가 있는 투 포인.. 2022. 10. 14.
[자바] 프로그래머스 - n^2 배열 자르기 (Lv2, Java) 문제 : Programmers-n^2 배열 자르기 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 구현, 수학 태그가 상당히 애매하긴한데, 그냥 단순 구현문제인 것 같다. 1. 문제에서는 2차원 배열을 만들고나서 1차원배열로 만들고, left부터 right까지를 출력하라고 했으나, 애초에 n의 최대값이 10^7이므로 2차원 배열을 만드는 순간 물리적으로 O(10^14)가 필요해서 무조건 시간초과이다. (대강 O(10^9)을 1초로 잡으면 되므로 10만초임) 2. 마찬가지로, 1차원 배열로 바꾸는것도 O(10^14)이므로 하면 안됨. 3. 그럼 남은건 left부터 right까지에 대해 right - left < 1.. 2022. 10. 14.
[자바] 백준 20205 - 교수님 그림이 깨지는데요? (java) 문제 : boj20205 필요 알고리즘 개념 구현 2중 반복문을 활용해 구현해주면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 NxN 짜리 배열에 0과 1이 있고, 그걸 (N*K)x(N*K) 배열로 늘려주면 된다. 이 때, 자바의 경우 배열 생성 시 기본적으로 0으로 초기화 되므로 0인 경우는 신경쓰지 않아도 된다. NxN 배열에서 1이 입력으로 들어온 경우만 채워주면 되며, (r, c) 위치에 있던 '1'은 (r*.. 2022. 10. 14.
[자바] 프로그래머스 - 호텔 방 배정 (Lv4, Java) 문제 : Programmers-호텔 방 배정 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 해시를 사용한 집합과 맵 자바의 HashMap을 적절하게 사용할 줄 알아야 한다. 근데 이렇게 알고리즘 분류만 봐서는 아마 풀이를 생각하긴 힘들 것 같다. 구현 난이도보다는 아이디어가 필요한 문제이다. 그룹 관련된 개념(유니온 파인드 등)이 있다면 좀 더 쉽게 생각해낼 수 있어보인다. 생각 과정 (오답) * 제가 풀이를 생각하는 과정이고 오답노트처럼 적어놓은 것이므로, 이하 생각 과정에 나온 알고리즘을 모두 몰라도 문제 푸는데 지장 없습니다. 그냥 바로 풀이만 보시려면 아래쪽에 '풀이'로 넘어가시면 됩니다. 아직 선택되지.. 2022. 10. 13.
[자바] 백준 6220 - Making Change (java) 문제 : boj6220 필요 알고리즘 개념 동적 계획법 (DP; Dynamic Programming) DP로 효율적으로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 얼핏 큰 동전부터 최대한 사용하면 가능할 것이라 생각할 수 있다. 예를들어 예시 1의 경우 25, 50, 10, 1, 5원 이므로 큰 동전부터로 정렬하면 50, 25, 10, 5, 1 이다. 차례대로 사용해서 93 - 50원, 43 - 2.. 2022. 10. 13.
[자바] 백준 2921 - 도미노 (java) 문제 : boj2921 필요 알고리즘 개념 구현 규칙을 찾아 2중 반복문으로 구현해주면 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 N=2, 3, 4 일 경우를 그려보면 아래와 같다. 즉, 윗줄을 i로 두고, 아랫줄을 j로 뒀을 때, 아래 코드처럼 2중 반복문을 통해 i와 j를 합계에 더해주면 된다. for (int i = 0; i 2022. 10. 12.
[자바] 백준 25704 - 출석 이벤트 (java) 문제 : boj25704 필요 알고리즘 개념 사칙연산, 수학 뺄셈, 나눗셈을 할 줄 알면 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 코드 설계를 이쁘게 해서 구현만 잘 해주면 된다. 이 때, P는 항상 100의 배수이므로 10%, 25% 할인 쿠폰 적용 후에 int로 변경해줘도 소수점 문제 없이 정수로 떨어지게 된다. 내 경우에 코드를 어떻게 구성했는지는 이하의 주석을 봐보자. int n = Integer... 2022. 10. 11.
[자바] 백준 20353 - Atrium (java) 문제 : boj20353 필요 알고리즘 개념 기하학, 수학 정사각형의 넓이를 어떻게 구하는지 알고 있다면 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 정사각형의 넓이는 한 변의 길이의 제곱으로 구할 수 있다. 한 변의 길이를 x라 한다면 넓이는 x^2이다. 이 문제에서는 넓이가 주어지고, 원하는건 4x 이다. 따라서 '4*sqrt(입력으로 주어진 넓이)'을 출력해주면 된다. 자바에서 제곱근은 Math.sqrt.. 2022. 10. 10.

티스토리툴바