본문 바로가기

PS/BOJ764

[자바] 백준 23740 - 버스 노선 개편하기 (java) 목차 문제 : boj23740 필요 알고리즘 정렬, 스위핑 스위핑을 통해 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. 겹친다는 부분을 어떻게 알 수 있을까? 노선A의 e가 노선 B의 s 이상이고, 노선 B의 e가 노선 A의 s 이상이라면 겹친다고 볼 수 있을 것이다. 이 때, 무조건 s가 증가하는 순서대로 정렬해두고 확인해본다고 해보자. s가 더 작은 쪽이 노선 A라고 한다면 이후 겹친다는 판단.. 2023. 4. 8.
[자바] 백준 5426 - 비밀 편지 (java) 목차 문제 : boj5426 필요 알고리즘 구현, 문자열 문제에 제시된 대로 구현해주면 된다! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제에서 제시된 것 처럼 문자열을 배열 형태로 바꿀 수 있다면, 역으로 반시계방향으로 90도 회전해준 후, 그걸 다시 문자로 바꾸면 답이 나올 것이다. 그럼 그대로 해보자. 우선은 정사각형이라고 했으므로, 배열의 크기는 문자열 길이의 제곱근이 된다. int len = (int) Math.. 2023. 4. 7.
[자바] 백준 1205 - 등수 구하기 (java) 목차 문제 : boj1205 필요 알고리즘 구현 결국 문제에서 제시된 방식대로 등수를 구해주면 되는 구현문제이다. 다만 실수하가기가 쉽게 문제가 구성되어 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 예외를 잘 처리해줘야 하는 구현 문제이다. 차분하게 조건들 다 따져가면서 구현해주면 된다. 1. n = 0일 경우 답은 항상 1이다. (P의 최소값은 10 이므로 불가능한 경우가 없다.) if (n == 0) { Syst.. 2023. 4. 5.
[파이선] 백준 1793 - 타일링 (python) 목차 문제 : boj1793 필요 알고리즘 동적 계획법(DP), 큰 수 기본적인 형태의 DP 문제이다. 다만 큰 수를 처리하는게 포함되어 파이썬 이외로 풀긴 좀 까다롭다. 풀이 별 생각없이 자바로 풀고보니 출력이 어마무시한 수였다.. ㅋㅋㅋㅋ DP를 BigInteger로 푸는 맛없는 짓은 하기 싫었으니 파이썬으로 갈아탔다. 이하 자바로 풀었다가 출력보고 버린 코드 이다. 파이썬으로 푼 맨 아래에 있는 코드에서 결국 핵심은 다음 한 줄 뿐이다. dp[i] = 2*dp[i-2] + dp[i-1] dp[x]를 x번째 열까지 타일을 놓는 경우의 수라 하자. dp[5]의 경우 아래 그림처럼 dp[4]에 2x1 타일을 놓는 경우와, dp[3]에 1x2 타일 2개를 놓는 경우, dp[3]에 2x2 타일을 놓는 경우가.. 2023. 4. 4.
[자바] 백준 23813 - 회전 (java) 목차 문제 : boj23813 필요 알고리즘 구현, 문자열, 수학 문자열로 문제에서 제시된대로 구현해주는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제 제한이 짧아서 그냥 문자열 자체로 자르고 붙이고 Integer.parseInt로 정수로 변경해주면서 구현해도 상관없다. 내 경우엔 숫자로 바꿔서 계산했다. 우선 mult는 입력으로 들어온 숫자의 자리수-1 만큼 0이 붙은 숫자이다. 예를들어 "12345"라면 .. 2023. 4. 3.
[자바] 백준 2033 - 반올림 (java) 목차 문제 : boj2033 필요 알고리즘 구현 반올림을 직접 해주면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 입력으로 들어온 숫자를 각 자리수별로 배열로 잘라두고 직접 반올림을 진행해주면 된다! 예를들어 "446"일 경우 아래처럼 진행된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main {.. 2023. 4. 2.
[자바] 백준 25904 - 안녕 클레오파트라 세상에서 제일가는 포테이토칩 (java) 목차 문제 : boj25904 필요 알고리즘 구현, 시뮬레이션 문제에서 제시된 방식대로 구현해주면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 어차피 목소리 높이의 상한선은 200이므로, N이 몇이 되든 최악의 경우에도 200번만 확인해보면 된다! 따라서 어렵게 생각할 것 없이, N개짜리를 순서대로 계속 확인하면서 매번 X를 1씩 증가해준다. 그리고 X의 값이 해당 위치보다 더 커지면 해당 위치를 출력해주면 된다. .. 2023. 3. 27.
[자바] 백준 10471 - 공간을 만들어 봅시다 (java) 목차 문제 : boj10471 필요 알고리즘 브루트포스 모든 경우를 확인해서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제는 0, W, 그리고 입력받은 P개의 파티션(0 < P < W) 총 P+2개에 대해 모든 쌍을 확인해 차이를 확인하면 되는 문제이다. 모든 경우를 보면 되므로 브루트포스(완전탐색) 이다. 그렇게 해도 O(P^2) 이므로 시간이 충분하다! 코드 : github import j.. 2023. 3. 17.
[자바] 백준 7570 - 줄 세우기 (java) 목차 문제 : boj7570 필요 알고리즘 그리디 알고리즘 모든 경우에 적용되는 규칙을 적용해 푸는 그리디 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이게 특정 위치의 수를 원하는 위치로 보낼 수 있었으면 좀 쉬웠겠는데, 맨 앞이나 맨 뒤로만 보낼 수 있는 부분 때문에 좀 생각하기 어려워지는 것 같다. 내가 정한 규칙은, 가장 긴 +1씩 증가하는 부분 수열을 고정시키고 나머지 애들을 어떻게든 움직여보는 것이다... 2023. 3. 16.
[자바] 백준 18224 - 미로에 갇힌 건우 (java) 목차 문제 : boj18224 필요 알고리즘 너비 우선 탐색 (BFS) 좀 어려운 BFS 문제이다. 근본은 동일하다. 방문체크와 탐색만 잘 하면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 BFS에 대해 모른다면 '이 글'을 참고해보자. 특히 '방문체크에 대해 좀 더 써봄' 부분을 이해해야 풀 수 있다. 결국 이 문제도 방문체크를 모든 경우를 표현할 수 있으면서도 최소한으로 할 수 있고, 문제에서 주어진 대로 탐색을.. 2023. 3. 15.

티스토리툴바