본문 바로가기

BOJ749

[자바] 백준 1253 - 좋다 (java) 문제 : boj1253 필요 알고리즘 개념 투 포인터, 이분 탐색, 해싱 등 이하 풀이는 투 포인터 풀이이다. 정렬 투 포인터 또는 이분 탐색 사용시엔 정렬도 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 말로만 적어보면 간단하다. 1. 입력받은 N개의 값을 정렬한다. 2. idx : 0 to N-1 에 대해 arr[idx]를 제외한 나머지 값들 중 두 개를 합쳐서 arr[idx]가 되는 경우가 존재한다면 cnt+.. 2022. 12. 2.
[자바] 백준 20976 - The Second Largest Integer (java) 문제 : boj20976 필요 알고리즘 개념 구현 문제에서 제시된 대로 구현하면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 일본어 문제지만, 제곧내 이므로 제목과 입출력 예시만 보면 풀 수 있다. 아무튼 3개를 입력받아서 그 중 2번째로 큰 값을 출력하면 된다. 3개의 값을 비교해서 출력해줘도 되고, 그냥 이하 코드처럼 정렬한 후 2번째 값(인덱스1)을 출력해주면 된다. 코드 : github import java... 2022. 12. 2.
[자바] 프로그래머스 - 순서쌍의 개수 (Lv0, Java) 문제 : Programmers-순서쌍의 개수 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 브루트포스 n의 크기가 100만밖에 안되므로 그냥 1부터 n까지의 모든 수를 비교해보면 된다. O(n) 수학 (정수론) 좀 더 효율적으로 O(sqrt(n))으로도 풀 수 있다. 이 경우 수학적 지식이 좀 필요하다. 풀이 우선 n의 크기가 100만으로 매우 작으므로 그냥 1부터 n까지의 모든 수를 보면 된다. a를 1부터 n까지 증가시키면서, n%a == 0 이라면 b = n/a 가 되므로 answer을 1 증가시켜주면 된다. 이 경우 O(n)이 걸린다. int answer = 0; for (int i = 1; i 2022. 12. 2.
[자바] 백준 8949 - 대충 더해 (java) 문제 : boj8949 필요 알고리즘 개념 문자열. 구현 문자열을 파싱할 줄 알아야 풀 수 있다. 이외 로직은 문제에서 제시된 대로 구현해주면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. 예를들어 A = "123, B = "2495" 라고 해보자. 이 때 문자열 자체로 A = "0123", B = "2495" 처럼 자리수를 동일하게 맞추기 위해 앞에 '0'을 넣어준다고 하자. 2. 그렇다면 A와 B의 길이는 동.. 2022. 11. 30.
[자바] 백준 17071 - 숨바꼭질 5 (java) 문제 : boj17071 필요 알고리즘 개념 그래프, BFS (너비 우선 탐색) 결론적으로 보면 그냥 BFS 문제이다. 다만 아이디어가 좀 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 생각 과정 및 풀이 이 문제의 경우 상당히 많이 잘못 생각했고, 결론적으로 proof by AC (정답 맞췄으니 증명됬다!) 느낌으로 풀었다 ㅋㅋ. 그러니 풀이를 생각한 과정을 적어보겠다. 정답 코드만 볼꺼면 맨 아래의 코드만 보면 될 .. 2022. 11. 29.
백준 2563 - 색종이 (자바, C, C++, node.js, Kotlin, Python, C#) 문제 : boj2563 필요 알고리즘 개념 구현 문제에 제시된대로 구현을 하면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 가장 쉽게 생각해볼 수 있는건, 100x100 짜리 배열을 만든 후 전부 0 또는 false로 초기화한다. 이후 입력을 받아 10X10 정사각형 모양의 색종이를 직접 배열에 +1 혹은 true로 변경한다. 이후 100x100 배열을 한번 더 순회하면서 0 또는 false가 아닌 배열 값의 수를 .. 2022. 11. 29.
[자바] 백준 23972 - 악마의 제안 (java) 문제 : boj23972 필요 알고리즘 개념 수학 수학적 사고가 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제에 제시된 방식에서 민주가 가지고 있는 금액이 x라 할 때, 손해를 보지 않는다는걸 수식으로 표현하면 '1'과 같다. 이걸 '5'가지 쭉 식을 정리해보자. 결국 '5'의 식이 나오고, 저걸 구해주면 된다. 이하 코드처럼 나눈 몫을 정수형으로 변경한 div, 나머지인 mod가 있을 때, div+(.. 2022. 11. 28.
[자바] 백준 6763 - Speed fines are not fine! (java) 문제 : boj6763 필요 알고리즘 개념 구현 문제에 제시된 대로 구현해주면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. gap = 차 속도 - 속도 제한 2. gap 2022. 11. 27.
[자바] 백준 6750 - Rotating letters (java) 문제 : boj6750 필요 알고리즘 개념 문자열, 구현 문자열 파싱이 필요한 구현 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. 입력으로 받은 문자열의 각 문자열이 I, O, S, H, Z, X, N 중 하나인지 판단해야 하므로, I, O, S, H, Z, X, N를 쉽게 사용할 수 있는 방식으로 코드에 넣어둔다. 내 경우엔 그냥 String으로 두었고, 배열로 둬도 된다. 2. 입력받은 문자열의 각 문자를.. 2022. 11. 26.
[자바] 백준 2162 - 선분 그룹 (java) 문제 : boj2162 필요 알고리즘 개념 분리 집합 그룹의 개수 및 그룹의 크기를 구하기 위해 분리 집합 알고리즘을 알고 있으면 좋다(안써서 푼 사람들도 있긴하다). 선분 교차 판정 (기하학, CCW) 선분 교차 판정 알고리즘으로 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우 union-find를 쓸 때, 코드상의 parents 배열 기준으로 그룹의 메인 번호는 음수, 나머지는 양수로 메인 번호를 나.. 2022. 11. 26.

티스토리툴바