본문 바로가기

PS/BOJ764

[자바] 백준 24461 - 그래프의 줄기 (java) 목차문제 : boj24461  필요 알고리즘그래프 이론, 브루트 포스별다른 알고리즘 지식은 필요하지 않긴한데, 구현이 어려울 수 있다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  아래와 같은 그래프를 생각해보자.    각 정점에 대해 현재 연결된 간선의 수를 적어보면 아래와 같다. 이번에 제거될 가장자리 정점은 연결된 간선의 수가 '1'인 정점들임을 알 수 있다.    한 번 삭제된 후엔 아래와 같이 된다. 그리고 그래.. 2024. 5. 15.
[자바] 백준 11909 - 배열 탈출 (java) 목차문제 : boj11909  필요 알고리즘DP (동적 계획법)DP를 알고 있다면 쉽게 해결 가능한 문제이다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  need(X, Y)를 X 좌표에서 Y 좌표로 갈 때 필요한 비용이라고 하자. 예를들어 X가 (1,1), Y가 (1,2) 이고, 배열의 값이 각각 3과 5였다면 need(X, Y)는 3이다.   이 때 dp[a][b]는 (a, b) 좌표로 가는데 필요한 최소 비용이라고 .. 2024. 5. 14.
[자바] 백준 1484 - 다이어트 (java) 목차문제 : boj1484  필요 알고리즘수학수학 문제긴한데 딱히 수학적 지식이나 알고리즘 지식이 필요한 문제는 아니다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  내 풀이 로직은 다음과 같다. 보면 알겠지만 딱히 수학이나 알고리즘 지식이 필요한 부분은 없다. 다만 이전과의 차이가 G를 넘어서는 제곱수부터는 무시해도 된다는 직관은 필요하다. 저걸로 인해 시간복잡도가 엄청 줄어든다. 1. 제곱수들의 리스트를 만드는데, 바.. 2024. 5. 2.
[자바] 백준 31778 - PPC 만들기 (java) 목차문제 : boj31778  필요 알고리즘그리디, 투 포인터 (두 포인터), 수학 그리디 아이디어로 풀 수 있고, 내 경우 투 포인터를 사용해 구현했다. 경우의 수를 찾기 위해 약간의 수학적 지식도 필요하다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  우선 어떻게 K번 연산을 적용해야 PPC 부분문자열의 최대치가 될지부터 생각해보자. 직관적으로 찾기 어렵지 않은데, 아무튼 최대한 많은 P가 앞쪽으로 가야하고, 최대한 .. 2024. 4. 30.
[자바] 백준 28109 - 약속 장소 2 (java) 목차문제 : boj28109  필요 알고리즘문자열, 그리디규칙을 찾아 그리디로 해결 가능하다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  규칙만 찾으면 로직은 생각보다 간단하다."CDD" 를 가지고 한 글자만 변경해서 사전순으로 어떻게 나타낼 수 있을지 생각해보자.순서대로 살펴보면 아래와 같다.// 첫번째 글자만 변경됨ADDBDD// 두번째 글자만 변경됨CADCBDCCD// 세번째 글자만 변경됨CCACCBCDC// 자기.. 2024. 4. 25.
[자바] 백준 2836 - 수상 택시 (java) 목차문제 : boj2836  필요 알고리즘정렬, 스위핑사실 그냥 정렬 + 반복문 + 조건문만 알면 풀 수 있다. 아이디어가 더 중요한 문제다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  아이디어만 잘 떠올리면 풀 수 있는 문제이다. 내 경우 이하와 같이 진행했다.   어차피 0부터 M까진 무조건 가야 한다. 따라서 입력값에서 타는 위치가 목적지보다 이전이라면, 사실 신경을 안써도 .. 2024. 4. 24.
[자바] 백준 14728 - 벼락치기 (java) 목차 문제 : boj14728 필요 알고리즘 DP, 냅색 (배낭 문제) DP로 해결 가능한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 dp[x]를 x시간을 사용해 얻을 수 있는 최대 점수라고 해보자. 그렇다면 현재 단원에 대한 K와 S가 주어졌을 때, x시간을 사용해 얻을 수 있는 최대 점수는, '현재까지 파악한 x시간을 사용해 얻을 수 있는 최대 점수', 'x-K 시간까지 얻을 수 있는 최대 점수에 이번 단원.. 2024. 4. 8.
[자바] 백준 23128 - Math (java) 목차 문제 : boj23128 필요 알고리즘 수학, 브루트 포스 (brute force) 약간의 수학적 직관으로 범위를 좁히면, 그냥 브루트 포스로 다 대입해보면 답을 구할 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제에서 제시된 찾고자 하는 내용을 수식으로 나타내보면 다음과 같이 나타낼 수 있다. A와 B는 각각 a_i와 a_j를 뜻한다. C는 임의의 정수이다. 여기서 A, B의 범위는 [1, 1000000.. 2024. 4. 6.
[자바] 백준 14786 - Ax+Bsin(x)=C ② (java) 목차 문제 : boj14786 필요 알고리즘 수학, 이분 탐색 이분 탐색으로 답의 범위를 좁혀가며 상대 오차 10^-9 이하로 찾아주면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 처음에 문제보고 일단 수식이 나오니 무서웠는데, 어차피 y=x랑 y=sin(x) 합친 형태라 대충 그래프 형태가 상상이 되기도 하고, 입력값 범위도 좁아서 도전해보니 생각보다 어렵진 않았다. 풀고보니 '뉴턴-랩슨법' 이라는걸로 풀면 바로 .. 2024. 4. 5.
[자바] 백준 2653 - 안정된 집단 (java) 목차 문제 : boj2653 필요 알고리즘 직관(?), 그래프 이론 어찌보면 그냥 구현 문제이긴 한데, 좀 헷갈릴 수도 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 서로 싫어하는 사람들은 빼고, 그냥 서로 좋아하는 사람들끼리 집단을 만든다고 생각해보자. 이 때 문제에서 제시된 바에 따라 논리적으로 맞는지만 확인해주면 된다. 내 로직은 다음과 같다. 이하 로직대로 구현해주면 된다. 1. 1부터 N까지 확인하다가 아직 .. 2024. 4. 4.