본문 바로가기

전체 글1068

[종만북] MATCHORDER - 출전 순서 정하기 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-MATCHORDER 풀이 생각해야 할 조건은 두 가지이다. 1. 러시아와 한국 팀이 1:1로 매칭이 되긴 해야 한다. 2. 러시아팀의 레이팅 이상이기만 하다면 그 차이는 무시할 수 있다. 위 두가지를 생각하면서 최대한으로 이기려고 한다면, 각 러시아팀 레이팅에 대해 최대한 차이가 적은 그 이상의 한국팀 레이팅을 매칭시켜주면 된다. 또한 1:1로 매칭되긴 해야하므로, 현재 러시아팀 레이팅 이상의 값이 남는게 없다면 남은 한국팀 레이팅 중 가장 낮은 값을 매칭해준다. 현재 러시아의 레이팅 이상이면서 가장 작은 값은 이분 탐색으로 찾도록 구현했다. 코드 : github import java.io.BufferedReader; import j.. 2023. 4. 17.
[자바] 백준 25206 - 너의 평점은 (java) 목차 문제 : boj25206 필요 알고리즘 구현, 문자열 문자열을 잘 파싱해서 문제에서 제시된대로 구현해주는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 구현 로직은 다음과 같다. 1. 20줄 각각을 받으면서 첫 번째 문자는 필요없으니 버리고, 세 번째 입력값이 'P' 라면 다음 줄로 넘어간다. 2. 2번째 값을 double로 받은걸 grade, 3번째는 double로 과목평점을 변환해서 받은걸 rating 이.. 2023. 4. 15.
[종만북] STRJOIN - 문자열 합치기 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-STRJOIN 풀이 N개의 문자열이 주어질 때, 여기서 2개를 선택해 새로운 문자열을 만들고, 그 길이의 합이 비용이 된다. 이걸 하나의 문자열만 남을 때 까지 반복하는 문제이다. 합치는 순서가 중요할텐데, 4개의 문자열이 있고 각 길이가 A, B, C, D라고 해보자. (A)와 (B)를 합치면 (A+B)의 문자열이 된다. 그럼 문자열은 현재 (A+B), (C), (D)가 있다. (A+B)와 (C)를 합치면 (A+B+C)가 된다. 그리고 다시 (D)와 합치면 (A+B+C+D)가 된다. 여기서 비용에 들어간 횟수를 살펴보면 'A'와 'B'는 비용에 총 3번, 'C'는 2번, 'D'는 1번 더해졌다. 따라서 직관적으로 여러번 합쳐질 녀석.. 2023. 4. 14.
[종만북] LUNCHBOX - Microwaving Lunch Boxes (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-LUNCHBOX 풀이 N개의 Lunch Box가 있고, 각각 전자렌지에 돌리는 시간 M과 먹는시간 E를 가지는 상황이다. 여기서 고정인 부분은 전자렌지 돌리는 시간 M는 무조건 N개의 M을 전부 더한 시간만큼이 필요하다. 반면에 먹는시간 E는 각 M이 끝날때마다 시작된다. 예를들어 아래와 같은 입력을 보자. 1 3 1 3 2 10 4 1 순서대로 진행해본다면 아래와 같이 진행된다. 사실 저 순서대로 처리하는게 풀이인데, 결국 M의 총합은 항상 고정이고, E가 시작하는건 각 M이 끝난 이후이므로 E가 긴 녀석을 최대한 빨리 먹기 시작해서 처리하는게 무조건 이득이다. 따라서 E값 내림차순으로 정렬한 후 (E가 동일할 시 M을 내림차순으로.. 2023. 4. 14.
[자바] 백준 15025 - Judging Moose (java) 목차 문제 : boj15025 필요 알고리즘 구현 문제에서 제시된 대로 구현해주면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 해석만 잘하면 제시된 대로 풀면 된다. 로직을 정리하면 다음과 같다. 1. L과 R을 입력받는다. 2. L과 R이 둘 다 0이면 "Not a moose" 3. L과 R 중 큰 값을 B라고 해보자. 4. L == R 이라면 "Even [B*2]"를 출력한다. 5. 그렇지 않다면 "Odd [B*.. 2023. 4. 14.
[자바] 백준 3359 - 사각 사각 (java) 목차 문제 : boj3359 필요 알고리즘 동적 계획법(DP) 사각형을 순서대로 보면서, 점화식을 만들어 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 완전 탐색으로 한번 생각해보자. 각 사각형은 a변이 위로 올라오게 놓거나, b변이 위로 올라오게 놓을 수 있으므로 O(2^n) 으로 구할 수 있다. 이 때 n이 최대 1000 이므로 완전 탐색으론 풀 수 없음을 알 수 있다. 그렇다면 우선 생각해볼.. 2023. 4. 13.
[자바] 백준 18352 - 특정 거리의 도시 찾기 (java) 목차 문제 : boj18352 필요 알고리즘 너비 우선 탐색(BFS) 일반적인 BFS 탐색에서, 최단 거리에 목적지를 도착하는게 아니고 특정 거리인 지점을 찾는다는점만 다르다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 BFS를 잘 모른다면 'BFS 알고리즘 (너비 우선 탐색)' 글을 참고해보자. 일반적인 BFS 알고리즘으로 구현해주면 되는데, 목적지까지의 최단 거리를 구하는게 아니라 특정 거리인 위치를 찾는다는 점이 다.. 2023. 4. 12.
[자바] 백준 16200 - 해커톤 (java) 목차 문제 : boj16200 필요 알고리즘 그리디, 정렬 그리디 규칙을 잘 생각해보면 의외로 쉽게 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 결국 팀을 어떻게 정하는게 항상 최선의 선택일지 규칙을 정해야 한다. 얼핏 X값이 큰 학생들부터 골라서 선택해야 각 팀의 인원이 많아지므로 팀의 수가 줄어든다고 생각할 수 있는데, 어차피 X값은 고정된 것이고 바뀔 수 없으며, 모든 학생은 하나의 팀에 소속이 되어야만.. 2023. 4. 11.
[종만북] POLY - 폴리오미노 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-POLY 풀이 문제에서 제시된 규칙은 결국, 세로야 어떻든 가로로 선을 그었을 때 빈 곳이 있으면 안되고 또 전부 붙어있어야한다는 의미가 된다. 따라서 n개를 행 1개~행 n개 에 걸쳐 각 행에 몇 개씩 배치할 것인지로 바꿔서 생각하면 된다. 그리고 2개의 행을 봤을 때, 두 행에 대해 만들 수 있는 경우의 수는 '행1의 블록 수 + 행2의 블록 수 - 1' 이 된다. 예를들어 각 행에 3개씩 배치했을 경우 나올 수 있는 경우의 수는 3+3-1 = 5 이다. 아래 경우들과 같다. 따라서 각 행별로 현재 남은 블록의 수를 '1개부터 남은 블록의 수'로 배치하면서 위에서 얘기한 경우의 수를 바로 직전 행의 블록수와 함께 계산해보면 된다... 2023. 4. 10.
[종만북] NUMB3RS - 두니발 박사의 탈옥 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-NUMB3RS 풀이 예제 입력의 첫 번째 테스트케이스를 그래프로 그려보면 아래와 같다. 탈출 전 확률이 1(100%)이라 한다면 이후 간선을 따라, 간선이 존재하는 만큼 확률이 나뉘어져서 들어가게 된다. 탈출 전일 때 0에서 시작하므로 0은 1로 시작하고, 탈출 1일차에 0에서 갈 수 있는 간선이 1,2,3 이므로 1/3씩 나뉘어 들어간다. 그리고 2일차에 1과 3에 있던 1/3은 0으로 다시 돌아오고, 2에 있던 1/3은 0과 4로 1/6씩 나뉘어 들어가게 된다. 따라서 2일차에 0에 위치는 5/6, 1,2,3 위치는 0, 4는 1/6이 된다. 이런식으로 일차별로 계속 진행한 후 q에 따라 출력해주면 된다. 코드 : github i.. 2023. 4. 10.

티스토리툴바