본문 바로가기

전체 글1068

[자바] 백준 23817 - 포항항 (boj java) 문제 : boj23817 상당히 좋은 아이디어 문제라 생각한다. 얼핏 브루트포스 문제로 생각하기 힘들고, 당연히 bfs로 어떻게든 잘 해야 할 것 같이 생겼다. 하지만 잘 생각해보면 단순 탐색으로는 최소시간을 찾기 힘들고 모든 경우의 수를 보는 brute force(완전탐색)로 봐야할 것임을 알 수 있다. 로직을 나눠서 생각해보자. 1. 최대 20개의 식당에 대해 5개의 식당을 방문하는데 필요한 최소한의 시간을 구할 수 있어야 한다. 이걸 확인하려면 기본적으로 방문 순서도 중요하다. 즉 20C5가 아니라 20P5로 봐야 한다. -> 모든 정점 사이의 거리를 안다면 1000x1000 짜리 배열이 아니라 최대 21개(S가 1개, K개 20개)의 정점과 그 사이에 거리에 관한 간선이 있는 그래프로 변경할 수 .. 2022. 6. 25.
[자바] 백준 24723 - 녹색거탑 (boj java) 문제 : boj24723 뭐 복잡하게 생각할 것 없이, 1층에서 내려올 수 있는 방향은 2군데이다. 2층이라면 1층에서 2군데로 내려온 후, 1층에서 내려온 각각도 마찬가지로 2군데로 내려올 수 있다. 3층이라면 2층에서 내려온 녀석들이 각각 2군데로 내려갈 수 있다. 즉, 2^N 을 출력해주면 되는 문제이다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = I.. 2022. 6. 25.
[자바, 파이썬] 백준 14928 - 큰 수 (BIG) (boj java python) 문제 : boj14928 문제 자체는 아주 심플하다. 문제 그대로 N을 20000303으로 나눈 나머지를 출력해주면 된다. 문제는 큰 수를 지원해주는 언어에 따라 난이도가 매우 다르다는 점이다. 파이썬의 경우 큰 수를 지원하므로 그냥 n을 입력받아 나머지를 출력만 해주면 끝난다(물론 오래걸린다). 자바의 경우엔 BigInteger로 큰 수를 지원해주긴한데, 시간초과로 통과가 안된다ㅋㅋㅋ 사실상 파이썬으론 엄청 쉽고, 나머지 언어론 큰 수를 지원해줘도 시간초과가 날 것 같다. 아무튼 그럼 파이썬은 풀이라고 할게 없으니 자바코드를 풀이로 작성해보겠다. 이걸 파이썬처럼 단순히 푸는게 아니라 직접 풀려면 결국 나머지 연산(%)에 대한 수학적 지식이 좀 필요하다. 나머지 연산에도 분배법칙이 있는데 덧셈에 대해 다.. 2022. 6. 25.
[자바] 백준 6755 - Who is taller? (boj java) 문제 : boj6755 입력으로 들어온 M개의 x가 y보다 크다는 정보를 가지고, p가 q보다 큰지(yes) 혹은 q가 p보다 큰지(no) 혹은 검증이 불가한지(unknown) 알아낼 수 있어야 한다. 그래프로 생각해보자. 우선 각 N명의 사람을 정점으로 하고, 간선을 x에서 y로 (즉 큰 사람에서 작은사람쪽으로) 하는 방향 그래프를 생각해보자. 그럼 간단히 p에서 q로 간선을 타고 이동이 가능하다면 p가 q보다 큰게 된다. 반대로 q에서 p로 간선을 타고 이동이 가능하다면 q가 p보다 큰게 된다. 둘 다 불가했다면 검증이 불가하다. 지문의 'you always compare correctly'에 따라 사이클이 생긴다거나, p에서 q로도 갈 수 있고 q에서 p로도 갈 수 있는 상황은 그냥 문제가 틀린셈이.. 2022. 6. 25.
[자바] 백준 14625 - 냉동식품 (boj java) 문제 : boj14625 시작시간부터 종료시간까지 각 분마다 어떠한 숫자들이 표시될지만 잘 판단할 수 있다면 풀 수 있다. 함수를 나눠보자. 필요한건 결국 1. 시작시간부터 시작해서 종료시간까지 1분씩 잘 더해줄 수 있는 함수 2. '1'의 각 시간에서 N이 포함되어 있는지 판단해주는 함수 위의 두 개만 있으면 된다. 문자로 해도 상관없지만, 내 경우엔 숫자로 처리했다. '1'에 해당하는 부분이 plusMin, '2'에 해당하는게 canSee 이다. 찾는 방법은 코드를 참고해보자. 주의점은 HHMM 형태이므로, int로 나타냈을 때 1000이하의 수라면, 예를들어서 5시 34분이라면 534라고 표현될 것이다. 실제론 맨 앞에 0이 있다고 봐야 하므로 N이 0일 경우 1000 이하의 수라면 0이 항상 존재.. 2022. 6. 25.
[자바] 백준 12034 - 김인천씨의 식료품가게 (Large) (boj java) 문제 : boj12034 정상가와, 정상가의 75%인 할인가가 n 쌍 존재한다. 그리고 문제 조건으로 '정답은 단 하나만 존재하는것이 보장되어 있음'라고 했으므로 정답을 찾으려면 단순히 생각해서 모든 경우를 살펴봐서 그 중 모든 정상가-할인가 쌍이 맞아떨어지는 경우를 찾으면 될 것이다. 하지만 잘 생각해보면 결국 할인가는 정상가보다 언제나 클 것이다. 따라서 주어진 값들 중 가장 큰 값은 할인가가 될 수 없으며 무조건 정상가이다. 따라서, 큰 값부터 정상가로 생각해 할인가를 찾아나갈 경우, 매번 남은 값들 중 가장 큰 값은 정상가일 수 밖에 없다. 정리하자면 오름차순으로 입력이 들어오므로, 마지막 값부터 시작해서 점차적으로 내려오면서 아직 존재하는 값이라면 무조건 정상가이고, 해당 값과 그 할인가를 제외.. 2022. 6. 23.
[자바] 백준 23037 - 5의 수난 (boj java) 문제 : boj23037 입력으로 들어온 문자를 한 자리씩 숫자로 바꿔주는 부분과 n^5을 리턴해주는 함수를 정의해주면 깔끔하게 풀 수 있다. 입력은 int로 받은 후, 해당 값이 a라면 a%10으로 한자리씩 뽑고 -> a/=10으로 다음 자리로 이동하는 식으로 한 자리씩 수를 얻을 수 있다. 혹은 이하 코드처럼 String으로 받은 후, 각 자리수의 character를 숫자로 변경해줘도 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private int pow5(int n) { return n*n*n*n*n; } private void solution() throws E.. 2022. 6. 22.
[자바] 백준 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.
[자바, C#] 백준 1225 - 이상한 곱셈 (boj java csharp) 문제 : boj1225 우선 최악의 경우는 99999....9(10000자리) 라는 수가 두개 있는 경우이다. 이 때 총 합은 9x9x10000x10000으로 81억이 되므로, 계산의 결과는 int로 표현할 수 없음을 알 수 있다. 따라서 결과 표현은 long으로 해줘야 한다. 또한 입력으로 들어온 A와 B는 10000자리까지 가능하므로 long으로도 당연히 표현이 불가하다. 어차피 각 자리의 수만 알면 되므로 String으로 입력받으면 문제 없다. 즉, A와 B를 String으로 입력받은 뒤 각 자리의 가능한 모든 조합에 대해 character를 숫자로 변환해 곱해서 결과에 더해주는 과정을 코드로 옮겨주면 된다. 예를들어 A=abc, B=de라면(e.g. A가 211 이라면 a=2, b=1, c=1) .. 2022. 6. 21.
[자바] 백준 20053 - 최소, 최대 2 (boj java) 문제 : boj20053 t개의 테이스 케이스를 독립적인 것으로 잘 판단할 수 있게 짜보자. t가 변할 때 다른 변수들이 영향을 받지 않도록 짜면 된다. 그리고 n개를 입력받으면서 매번 최소값과 최대값을 갱신해주는 식으로 짜주면 된다. 이런식으로 들어오는 입력이 알고리즘 문제를 풀 때 많으므로, 로직적인 부분 보다는 입출력 예시라고 생각하고 풀면 될 것 같다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = n.. 2022. 6. 20.

티스토리툴바